Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

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

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.