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 [duplicate]

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 ?

marked as duplicate by Chris Culter, Cesareo, Theo Bendit, Lord Shark the Unknown, mrtaurhoJan 29 at 6:11

• But the solution given is not very simple. Simplier arguments ? – MrMaths Jan 28 at 21:22

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|}$$.

• Is there any proof which does not use Lucas Correspondance ? – MrMaths Jan 29 at 7:45

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$$.