Show that the cardinal of $ A := \left\{ k \in \mathbf{Z} | 0 \leq k \leq n \text{ and } \binom{n}{k} \text{ is odd} \right\} $ is a power of 2

Question

Let $ A := \left\{ k \in \mathbf{Z} | 0 \leq k \leq n \text{ and } \binom{n}{k} \text{ is odd} \right\} $.

I must show that the cardinal of $A$ is a power of 2.

I have tried to show that there exist a bijection between $A$ and the set of subparts of another set, but unsuccessfully.

I also thought about trying to show that the cardinal of $A$ must divide the cardinal of $ P(\left\{ k \in \mathbf{Z} | 0 \leq k \leq n \right\}) $ (it is $ 2^{n+1} $), which would ensure the result, but I do not think this a good path.

Are there simple arguments to show that ?

Answer 1

Consider the following partial involution on the set of size $k$ subsets of $\{1,2,\dots,n\}$. Given such a subset $S$, find the smallest number $i$ such that $S$ contains exactly one of the numbers in $\{2i-1,2i\}$. Then $f(S)$ is attained by removing that number and adding the other one. We can divide the set of subsets for which $f(S)$ is defined into pairs, $\{S,f(S)\}$.

The involution is undefined if $S$ contains neither or both of $\{2i-1,2i\}$ for all $1\le i \le \lfloor n/2\rfloor$. If $n$ is even and $k$ is odd, then $f(S)$ is defined for all subsets (why?). Otherwise, there are precisely $\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}$ subsets for which the involution is undefined. Since removing the pairs defined by $f$ does not affect the parity of $\binom{n}k$, this shows $$ \binom{n}{k}\equiv_{\pmod 2} \begin{cases} 0 & n\equiv 0, k\equiv 1\pmod 2\\ \binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor} & \text{otherwise} \end{cases}\tag{1} $$ Now, let $a_n$ be the number of odd entries in the $n^{th}$ row of Pascal's triangle.

• If $n=2m$ is even, then $\binom{2m}k$ is even whenever $k$ is odd. There are $m+1$ entries in the $(2m)^{th}$ row of Pascal's triangle for which $k$ is even. The parities of these entries are equal to the $m+1$ entries of the $m^{th}$ row of Pascal's triangle, because $\binom{2m}{2i}\equiv \binom{m}i$, by $(1)$. Therefore,$$a_{2m}=a_m.$$

• If $n=2m+1$ is odd, then $(1)$ implies $\binom{2m+1}{2i}\equiv\binom{2m+1}{2i+1}\equiv \binom{m}i$. This means each odd entry in the $(m)^{th}$ row of Pascal's triangle corresponds to two odd entries on the $(2m+1)^{st}$ row, so $$a_{2m+1}=2a_m.$$

These last two equations imply that $a_n$ is always a power of $2$.

Answer 2

Let $n=a_r\cdot2^r+\cdots+a_1\cdot2+a_0$ where all $a_i\in\{0,1\}$. For $0\le k\le n$ let $k=b_r\cdot2^r+\cdots+b_1\cdot2+b_0$ where all $b_i\in\{0,1\}$.

For convenience, denote $Z=\{i:a_i=0\}$ and $N=\{i:a_i=1\}$. Then Lucas Correspondence tells us that $\binom{n}{k}$ is odd if and only if $\prod_{i\in Z}\binom{0}{b_i}\cdot\prod_{j\in N}\binom{1}{b_j}=1$. Since $b_i,b_j\in\{0,1\}$, we can conclude that $\binom{n}{k}$ is odd if and only if $b_i=0$ for all $i\in Z$. This implies that the number of integers $k$ such that $\binom{n}{k}$ is odd is exactly $2^{|N|}$.