# Prove that all entries of the nth row of Pascal's Triangle are odd given that $n=2^k-1$

Like the title says, I'm to prove that if $n=2^k-1$ then all entries of the nth row of Pascal's Triangle are odd. I know a couple of things that I can use for this, for one I know that I can describe the $j$th entry as $\binom{n}{j}$, and I know that $\binom{n+1}{j} = \binom{n}{j-1} + \binom{n}{j}$. I think the way to go is to show that $\binom{n}{j-1}$ and $\binom{n}{j}$ have opposite parities, thereby showing that their sum must be odd. The clincher is that I'm only allowed to use direct or contrapositive proof, i.e. no induction allowed.

• "No induction allowed" ought to be banned from classrooms. It's an elegant form of proof, and if we get into the nitty gritty details, just the fact that we are using the natural numbers means that we are automatically using induction, at least somewhere deep down. Jan 31 '18 at 15:26
• Can you prove that $\binom{2^k}j$ is even for $0<j<2^k$? It then follows that $\binom n{j-1}$ and $\binom nj$ have the same parity for all $j$ (since they add up to an even number). But $\binom n0$ is odd. Jan 31 '18 at 15:36

$$\binom nj = \dfrac{n!}{j!(n-j)!} = \dfrac{n(n-1)\cdots(n-(j-1))}{j!} = \dfrac{(2^k-1)(2^k-2)\cdots(2^k-j)}{1\cdot 2\cdots j}$$
$2$ divides $2^k-i$ the same number of times it divides $i$ for $1 \leq i \leq j$, so all factors of $2$ on the top and bottom will cancel.
• @Peatherfed If we split each $2^k-i$ into prime factors, and each $i$ into prime factors, all the factors of $2$ will cancel. This leaves only odd factors in the numerator, so the number must be odd. Please let me know if this helps. Feb 5 '18 at 11:31