# 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
@ThomasAndrews - I agree that this assertion requires a proof and I elaborate on that in my last line. If it wasn't clear, I am sorry and I don't mind if you'll edit my post. – Ofir Feb 28 '13 at 22:05
@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

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$

-

I would like to add a second answer as well. This one is much simpler, and is likely the one that was intended as the answer in the Book of Proof (which is where I'm guessing you got the question from).

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

$Proof.$ (Contrapositive) Suppose it is not the case that every entry in Row $n$ of Pascal's Triangle is odd. Then $\exists i \in \mathbb{N}:0<i<n$, for which $2| \binom{n}{i}$. Because $\binom{n}{n} = 1$, there exists some number $m \in \mathbb{N}$ such that $2| \binom{n}{m}$ and $2\not| \binom{n}{m+1}$. Then $\binom{n}{m} + \binom{n}{m+1} = \binom{n+1}{m+1}$, thus $\binom{n+1}{m+1}$ is odd. Now $\binom{n+1}{m+1} = \frac{(n+1)!}{(m+1)!(n+1-(m+1))!} = \frac{(n+1)(n)!}{(m+1)(m)!(n+1-m-1)!} =$$\frac{(n+1)(n)!}{(m+1)(m)!(n-m)!} = \frac{n+1}{m+1}\cdot\binom{n}{m}$. We know $\binom{n}{m}$ is even, so $m+1$ must not only be even, but it must also cancel all the $2$'s in the prime factorization of both $n+1$ and $\binom{n}{m}$ in order to make $\binom{n+1}{m+1}$ odd. But then it must not be the case that $n+1=2^k$ as that would mean $m+1$ would be greater than $n+1$ since it has to also cancel at least one $2$ from $\binom{n}{m}$. If $n+1\neq2^k$, then $n\neq2^k-1$. Thus, if it is not the case that every entry in Row $n$ of Pascal's Triangle is odd, then it is not the case that $n=2^k-1$ for $k \in \mathbb{N}$. Therefore, if $n=2^k-1$, for $k\in\mathbb{N}$, then every entry in Row $n$ of Pascal's Triangle is odd. $\blacksquare$

-