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

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


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

$Proof.$ (Direct) Suppose $n=2^k-1$, for $k \in N$. Then $n+1 = 2^k$. Each entry in Row $n+1$ of Pascal's Triangle is given by $\binom{n+1}{i}$, where $0\le i \le n+1$. Clearly, $\binom{n+1}{0}=\binom{n+1}{n+1}=1$, so let's consider two cases for $0<i<n+1$: one where $i$ is odd, and the other where $i$ is even.

$Case 1.$ Let $i$ be odd. If $n+1=2^k$, then $n+1$ is even. The meaning of $\binom{n+1}{i}$ is the total number of subsets of size $i$ from a set, $A$, with $n+1$ elements. Since $n+1$ is even, we can arbitrarily pair elements from $A$ so that any given element is related to exactly one other element in the set which we could call its “complement.” Then for any given subset of $A$ of size $i$, there will be exactly one other subset of size $i$ which contains the unpaired complements of the first subset. Since there will always exist such pairings for all odd size subsets of sets with even cardinalities, $\binom{n}{k}$ is divisible by 2 for all even $n>0$ and odd $k$ where $0<k<n$. Then $\binom{n+1}{i}$ is even for all odd $i$ in $0<i<n+1$.

$Case 2$. Let $i$ be even. Note $\binom{n+1}{i}=\binom{ 2^{k}}{i}=$ ${ 2^{k}! } \over {i! (2^k - i)!}$ $=$ ${ (2^k)(2^k - 1)(2^k - 2)...( 2^k - i + 1 ) } \over { (1)(2)(3)...(i) }$.

Both the numerator and denominator contain $i$ factors. Because $\binom{n+1}{i}$ is an integer, we know that the number of $2$'s in the prime factorization of the numerator must be greater than or equal to that of the denominator. If there are more $2$'s in the numerator, $\binom{n+1}{i}$ is even, and else the $2$'s cancel completely and $\binom{n+1}{i}$ is odd. Then let us only consider the even factors of $\binom{n+1}{i}$. From ${ (2^k)(2^k - 1)(2^k - 2)...( 2^k - i + 1 ) } \over { (1)(2)(3)...(i) }$ we consider only the even factors: ${ (2^k)(2^k - 2)...( 2^k - i + 2 ) } \over { (2)(4)...(i) }$ which has ${i}\over{2}$ factors in both the numerator and denominator. Since both the numerator and denominator contain the same number of factors, we can multiply every factor in both by ${1}\over{2}$ and maintain the equality:

${ (2^k)(2^k - 2)...( 2^k - i + 2 ) } \over { (2)(4)...(i) }$ $=$ $ \frac{1} {2}(2^k) \frac{1}{2}(2^k - 2)... \frac{1}{2}( 2^k - i + 2 ) \over \frac{1}{2}(2)\frac{1}{2}(4)... \frac{1}{2}(i) $ $=$ ${ (2^{k-1})(2^{k-1} - 1)...( 2^{k-1} - \frac{i}{2} + 1 ) } \over { (1)(2)...( \frac{i}{2}) }$.

But this last equality is nothing more than $\binom{2^{k-1}}{{i}/{2}}$. This means if $\binom{2^{k-1}}{{i}/{2}}$ is even then $\binom{n+1}{i}$ is even as well. As we already know from $Case 1$, since $2^{k-1}$ is even, if $\frac{i}{2}$ is odd, $\binom{2^{k-1}}{{i}/{2}}$ is even. On the other hand, if $\frac{i}{2}$ is even, the process can be repeated until reaching some binomial of the form $ \binom{2^{k-j}}{{i}/{2^j}} $ where $\frac{i}{2^j}$ is odd for $0<j<k$, as $i<2^k$. Thus $\binom{n+1}{i}$ is even for all even $i$ where $0<i<n+1$.

Finally, because $\binom{n+1}{i}$ is even for all $0<i<n+1$, and because $\binom{n+1}{i} = \binom{n}{i} + \binom{n}{i-1}$, the parity for all $\binom{n}{i}$ must be the same. Therefore, since $\binom{n}{0} = 1$, $\binom{n}{i}$ is odd for all $0 \le i \le n$, and every entry in Row $n$ of Pascal's Triangle is odd. $\blacksquare$