Proof for odd number of coefficients .

Question

I am reading a book and the author has stated that the numbers of odd numbers in the sequence

$\binom{n}{0} , \binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n}$ is $2^k$ where $k$ is the number of one's in the binary representation of $n$

I am interested to know how that came ?

Answer 1

Note that $(1+x^k)^2\equiv 1+x^{2k}\pmod 2$. Then by induction you get:

$$(1+x)^{2^j}\equiv 1+x^{2^j}\pmod 2.$$

Then if $n=2^{a_1}+2^{a_2}+\cdots+2^{a_k}$ with $0\leq a_1<\cdots<a_k$ So $$(1+x)^n\equiv \left(1+x^{2^{a_1}}\right)\left(1+x^{2^{a_2}}\right)\cdots\left(1+x^{2^{a_k}}\right)\pmod 2$$

Use this to show that $\binom{n}{i}$ is odd if the locations of the binary digits $1$ in the number $i$ is a subset of the locations of the binary digits of $n$.