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

Question

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.

Answer 1

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$.