# Prove: If $n=2^k-1$, then $\binom{n}{i}$ is odd for $0\leq i\leq n$

Kinda stuck on this one. Help is appreciated. I'm going for either a direct or contrapositive proof.

Prove: If $n=2^k-1$, for $k\in\mathbb{N}$, then every entry in Row $n$ of Pascal's Triangle is odd.

I've been considering entry $i$ in row $n$ of Pascal's Triangle, so for $0\leq i\leq n$, we have: $$\binom{n}{i}=\frac{n!}{i!(n-1)!} = \frac{(2^k-1)!}{i!(2^k-1-i)!}$$ I've tried manipulating this in a bunch of ways, including using the fact that $\binom{n}{i}=\binom{n-1}{i-1}+\binom{n-1}{i}$, but nothing's panned out.

-

First of all, note that $\binom{2^k}{i} = \binom{2^k - 1}{i} + \binom{2^k-1}{i-1}$, so if we show that $\binom{2^k}{i}$ is even whenever $0<i<2^k$, it will follow that $\binom{2^k - 1}{i}$ is constant modulo $2$, and since $\binom{2^k - 1}{0}=1$ is odd, your claim will follow.
So we need to calculate $\binom{2^k}{i}$ modulo $2$. Those binomial coefficients are the coefficients of the polynomial $(1+X)^{2^k}$. Modulo 2 it can be seen that $(1+X)^{2^k} = 1+X^{2^k}$, which establishes this claim. This equality follows by direct induction on $k$ or simply using the Frobenius homomorphism $x \to x^2$.
I'm having a hard time following some of this. We've shown that $(1+X)^{2^k}\equiv 1+X^{2^k}\pmod{2}$, but how does that relate to the parity of the individual coefficients, and how do we know whether $(1+X)^{2^k}\pmod{2}$ is 0 as opposed to 1? –  ivan Feb 28 '13 at 21:14
@ivan - The identity $(1+X)^{2^k} = 1+X^{2^k} \mod 2$ is a polynomial identity! This means that the coefficients of both polynomials agree. The coefficient of $X^i$ in the LHS (left hand side) is $\binom{2^k}{i}$, and in the RHS it is $1$ for $i=0,2^k$ and $0$ otherwise. You can prove this identity by direct induction. –  Ofir Feb 28 '13 at 22:06