$n=2^k-1$ iff ${n \choose 1}, {n \choose 2}, ..., {n \choose n-1}$ are odd

Question

Let $n$ be a natural number, $n=2^k-1$ if and only if ${n \choose 1}, {n \choose 2}, ..., {n \choose n-1}$ are odd.

To prove $(\Rightarrow)$, is induction the best way? And I'm completely stuck with proving $(\Leftarrow)$.

Answer 1

The condition that all $\binom{n}k$ are odd is the same as $$(X+1)^n\equiv \sum_{k=0}^n X^k\pmod 2$$ over the ring $\Bbb Z[X]$, which is equivalent to $$(X+1)^{n+1}\equiv X^{n+1}+1\pmod 2.$$ We need $(X+1)^m\equiv X^m+1$ iff $m=2^k$ for some $k$. If $m$ is not a power of $2$, it is $2^kr$ with $r>1$ odd and $$(X+1)^m=(X+1)^{2^kr}\equiv (X^{2^k}+1)^r\equiv X^{2^kr}+X^{2^k(r-1)}+ \cdots\pmod 2.$$