So here is the Question :-
Given $n \in \mathbb{N}$, find the number of odd numbers among ${n}\choose{0}$,${n}\choose{1}$,${n}\choose{2}$, $…,$${n}\choose{n}$ .
What I Tried :- I don't know but I guess maybe Lucas's Theorem can help doing it . It states that :-
${m}\choose{n}$ = $\prod_{i = 0}^{k}$${m_i}\choose{n_i}$ (mod p) for all:-
$m = m_kp^k + m_{k – 1}p^{k – 1} + … + m_1p + m_0 , n = n_kp^k + n_{k – 1}p_{k – 1} + … + n_1p + n_0$
I can use Lucas's Theorem by substituting $p = 2$ , but I am not sure how to do it, neither I am not sure whether this theorem will help or not. Can anyone help ?
Best Answer
Write $n=(n_kn_{k-1}\cdots n_0)_2$ in base two notation, and similarly for $n$. The Lucas theorem implies that $\binom n m$ is odd iff every $\binom{n_i}{m_i}$ is odd, and the only way that fails is if $n_i=0$ and $m_i=1$ for some $i$.
For oddness of $\binom nm$ then $m_i$ must be zero when $n_i=0$ but $m_i$ may be zero or one when $n_i=1$. So we have two valid choices for each $i$ with $n_i=1$, so $2^k$ valid choices overall where $k$ is the number of ones in the base two expansion of $n$.