Number of odd binomial coefficients is a power of $2$ 
Prove that for any positive integer $n$, the number of odd integers among the binomial coefficients $\binom{n}{k}$ $(0 \leq k \leq n)$ is a power of $2$.

I am thinking of trying to prove that the number of odd binomial coefficients is equal to 2 to the power of the number of $1$s in the binary form of $n$. How should I go about proving this?
 A: This is an immediate consequence of Kummer's theorem.
The maximum power of $2$ that divides $\binom{n}{k}$ is equal to the number of "carries" when adding $k$ and $n-k$ in binary. So you need to have $0$ carries when adding $k$ and $n-k$.
It is easy to see that this happens if and only if for every position for which $k$ has a one in binary, $n$ also has a one. There are $2^{f(n)}$ such numbers, where $f(n)$ is the number of ones digits in the binary representation of $n$.
A: You may look at Pascal's triangle modulo 2 (your question amounts to counting the number of ones on a given line).
From Pascal's triangle relation,  we can see that the ones make a recursive pattern of a Sierpinski triangle : basically take the shape formed by the $2^n$ first lines, and copy it twice below "in a triangle fashion".

From this remark, you can show that the number of ones on line $n$ is twice the number of ones on line $n-2^k$ (where $2^{k-1}< n\le 2^k$), and you recursively get that this is a power of $2$ (as stated above, it's $2^{f(n)}$ where $f(n)$ is the number of ones on the binary representation of $n$). 
