How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?

Question

This is exercise number $59$ from Chapter $2$ of Hugh Gordon's Discrete Probability.

Show that there are infinitely many rows of Pascal's Triangle that consist entirely of odd numbers.

Intuitively, if you draw boxes around the numbers in Pascal's triangle and color the boxes black if the number is odd and white if the number is even, then the triangle will look like the Sierpinsky triangle as you zoom out.

In particular, if we number the rows starting with the top as $1$, the rows will all odd numbers will be exactly the rows with number $2^n$ for some $n \in \mathbb{N}$ (or $n=0$ for the first). You can see this if you think about the Sierpinsky triangle coloring.

Anyway, is there any direct way to show the following for all $k$ with $0 \leq k \leq 2^n-1$?

$$\binom{2^n-1}{k} \equiv 1 \pmod{2}$$

This can probably be done by induction but a direct proof would be preferable.

Answer 1

Modulo $2$,

$$(1+x)^{2^n-1} = \frac{(1+x)^{2^n}}{1+x} = \frac{1+x^{2^n}}{1+x}=1+x+x^2+ \dots + x^{2^n-1}. \qquad\blacksquare$$

---

Also, modulo an odd prime $p$,

$$(1+x)^{p^n-1} = \frac{(1+x)^{p^n}}{1+x} = \frac{1+x^{p^n}}{1+x}= \frac{1-(-x)^{p^n}}{1-(-x)} = 1 - x+x^2- \dots + x^{p^n-1},$$

which shows that $${p^n-1 \choose k} \equiv (-1)^k \pmod p.$$

Answer 2

hint

this property follows from the fact that if $m+n=2^k-1$ there are no "carries" in the addition.

the power of $2$ which divides $a!$ is simply $a-\sigma_2(a)$ where $\sigma_2(a)$ returns the sum of the binary digits of $a$

Answer 3

$\binom{2^n-1}{k}=\frac{(2^n-k)\cdot\dots (2^n-2)\cdot(2^n-1)}{1\cdot 2 \cdot 3 \dots k}$ notice that $\bmod 2^n$ the last number on top is congruent to the first multiplied by minus $1\bmod 2^n$, the second to last in the top is congruent to the second in the bottom multiplied by minus one $\bmod 2^n$. Since there is no factor divisible by $2^n$ in the division the congruence $\bmod 2^n$ gives us all the divisibility we need $\bmod 2^n$. Since $m$ and $-m$ are equally divisible by $2^n$ they cancel out as I said.

Answer 4

illustration purposes; certainly seems rows $2^k - 1$ are a good bet. I would revise the problem and point out that all even, except the initial and final $1,$ seems to be rows $2^k$ only.

I drew this initially for finding the total number of gifts in "The Twelve Days of Christmas" song. I remember telling my father about that twenty or thirty years ago, and him complaining "Why is it binomial (14,3)? It's 12 days, how does 14 make sense?" Much later, I got some graph paper (quadrille) and made the most legible version i could and made a jpeg. I like, especially, how row 14 has consecutive coefficients 1001,2002,3003. Good reason for this, relying on $7 \cdot 11 \cdot 13 = 1001.$

Answer 5

Will Jagy inspired me to do this solution. Notice the terms in $\binom{2^n}{k}$ are always even unless $k=0$ or $2^n$.

Using the pascal recurrence (and the triangle) , the fact $\binom{2^n-1}{1}$ is odd and all terms under that row are even we conclude the number to the right of that one is odd, and repeating the term to the right of that one is odd....

Answer 6

For the record, it can indeed be done by induction, and quite easily at that. Recall the generalization of Pascal’s identity, itself easily proved by induction on $m$:

$$\binom{n+m}k=\sum_{\ell}\binom{m}\ell\binom{n}{k-\ell}\;.$$

Assume now that $\binom{2^n-1}k$ is odd for $0\le k\le 2^n-1$. Then

$$\begin{align*} \binom{2^{n+1}-1}k&=\sum_{\ell=0}^{2^n}\binom{2^n}\ell\binom{2^{n+1}-1-2^n}{k-\ell}\\\\ &=\sum_{\ell=0}^{2^n}\binom{2^n}\ell\binom{2^n-1}{k-\ell}\\\\ &=\sum_{\ell=0}^{2^n}\left(\binom{2^n-1}{\ell-1}+\binom{2^n-1}\ell\right)\binom{2^n-1}{k-\ell}\\\\ &=\sum_{\ell=1}^{2^n}\binom{2^n-1}{\ell-1}\binom{2^n-1}{k-\ell}+\sum_{\ell=0}^{2^n}\binom{2^n-1}\ell\binom{2^n-1}{k-\ell}\;,\tag{1} \end{align*}$$

where $(1)$ is the sum of $2^n+2^n+1=2^{n+1}+1$ odd terms and is therefore odd.

Answer 7

How about a nice combinatorial proof after all that algebra? (It is still by induction, though -- sorry.)

$\binom{2^n-1}{k}$ is the number of strings of $2^n-1$ letters of which $k$ are a and the rest are b.

Most of these strings can be paired with a different string of the same kind by reading it backwards. The ones that can't are the palindromes.

How many palindromes are there? We can choose a palindrome by taking one of the $\binom{2^{n-1}-1}{\lfloor k/2\rfloor}$ possible first almost-halves, followed by either a or b according to whether $k$ is odd or even, followed by the reverse of the first half.

By the induction hypotheis $\binom{2^{n-1}-1}{\lfloor k/2\rfloor}$ is odd. So there's an odd number of palindromes among our strings. And the non-palindromes match up two by two, so adding those in we still have an odd number of qualifying strings.