15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can use the identity $\binom{2^n-1}{k} + \binom{2^n-1}{k-1} = \binom{2^n}{k}$ to prove the congruence relation $\pmod{2}$ ! $\endgroup$ – r9m Dec 28 '14 at 18:44
  • $\begingroup$ $\binom{2^n}{k}$ clearly (?) has to be even for $0 < k < 2^n$. This means the two coefficients on your LHS have the same parity. I'm not sure how to show that they're not both even ... $\endgroup$ – Zubin Mukerjee Dec 28 '14 at 18:46
  • 1
    $\begingroup$ $\binom{2^n}{k} = \frac{2^n}{k}\binom{2^n-1}{k-1}$, where $k < 2^n$ ensures it's even ! start with $k=1$ and see its odd and then work up with induction ! $\endgroup$ – r9m Dec 28 '14 at 18:49
  • 2
    $\begingroup$ @r9m: Excessive exclamation marks are painful to read in any setting, but when the topic is factorials... $\endgroup$ – TonyK Dec 28 '14 at 19:50
  • 2
    $\begingroup$ @TonyK I will not argue but I made sure I didn't leave a ! next to a number where it could lead to ambiguity. $\endgroup$ – r9m Dec 28 '14 at 19:58
27
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Wow. This is brilliantly simple. +1 and accept $\endgroup$ – Zubin Mukerjee Dec 28 '14 at 19:06
  • $\begingroup$ I don't understand $\endgroup$ – Jorge Fernández-Hidalgo Dec 28 '14 at 19:07
  • $\begingroup$ @Jorge Compare with the binomial theorem. This shows that ${2^n-1 \choose k} \equiv 1 \pmod 2$. $\endgroup$ – Bruno Joyal Dec 28 '14 at 19:08
  • 1
    $\begingroup$ @JorgeFernández Binomial coefficients $\binom{n}{k}$ are the $k^\text{th}$ coefficients of the expansion of $(1+x)^n$. This answer shows that all of these coefficients are odd (equivalently, $1$ modulo $2$). $\endgroup$ – Zubin Mukerjee Dec 28 '14 at 19:08
  • 1
    $\begingroup$ @Zubin This is Freshman's dream in prime characteristic $\endgroup$ – Bruno Joyal Mar 9 '15 at 17:25
6
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ Sierpinsky! $\,$ $\endgroup$ – Zubin Mukerjee Dec 28 '14 at 19:01
  • 2
    $\begingroup$ wow, if I tried to to do this it would look like a picasso by the fifth row. $\endgroup$ – Jorge Fernández-Hidalgo Dec 28 '14 at 19:02
  • 1
    $\begingroup$ It's true , if $k$ is odd the binomial coefficient $\binom{2^nk}{2^n}$ is odd since the factors in the numerator and denominator are all congruent $\bmod 2^n$ and $2^nk$ cancels with $2^n$ since $k$ is odd. $\endgroup$ – Jorge Fernández-Hidalgo Dec 28 '14 at 19:04
  • $\begingroup$ @JorgeFernández, that gives a slightly different approach to the problem. If all entries in one row are odd, then all entries in the next row, other than the initial and final $1,$ are sums of two odd numbers and therefore even. $\endgroup$ – Will Jagy Dec 28 '14 at 19:08
  • $\begingroup$ Did you draw that yourself? +1! $\endgroup$ – Joao Dec 29 '14 at 1:59
5
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice! Kummer's theorem. $\endgroup$ – Jorge Fernández-Hidalgo Dec 28 '14 at 18:49
  • $\begingroup$ Yeah, I just learned it yesterday when looking at the solution for the fourth problem of the 2015 china national olympiad $\endgroup$ – Jorge Fernández-Hidalgo Dec 28 '14 at 18:54
  • $\begingroup$ Well, there can't be any carries when adding two numbers that give $11111111$ in binary. How would those numbers look? $\endgroup$ – Jorge Fernández-Hidalgo Dec 28 '14 at 18:55
  • 1
    $\begingroup$ Well, Kummer's theorem says that the largest power dividing $\binom{n}{m}$ is the number of carries when you add $m$ and $n-m$ in base $2$. since $n$ is $2^{n-1}$ and $m$ can be any number you have to prove if two non-negative integers which add up to $2^n-1$ are added in base $2$ then there are no carries. $\endgroup$ – Jorge Fernández-Hidalgo Dec 28 '14 at 19:01
  • 1
    $\begingroup$ @JorgeFernández Random observation: via Kummer's theorem, the commutativity of addition corresponds to the fact that $$\binom{n}{m}=\binom{n}{n-m}$$ $\endgroup$ – Zubin Mukerjee Dec 28 '14 at 19:04
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What does "equally divisible by $2^n$" mean? Should I finish your idea with $$a \equiv (-1)^k \pmod{2^n} \,\,\,\Rightarrow\,\,\, a \equiv 1 \pmod{2}$$ (is this correct?) $\endgroup$ – Zubin Mukerjee Dec 28 '14 at 18:55
  • $\begingroup$ I mean that if $n \equiv -m \neq0 \bmod 2^n$ then the largest power of $2$ dividing both of them is equal. $\endgroup$ – Jorge Fernández-Hidalgo Dec 28 '14 at 18:57
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ already indicated that in my comments under OP :-) $\endgroup$ – r9m Dec 28 '14 at 19:19
  • $\begingroup$ $$\binom{2^n}{k}$$ isn't even for $k=0$ or $k=2^n$ $\endgroup$ – Zubin Mukerjee Dec 28 '14 at 19:19
  • $\begingroup$ @ZubinMukerjee, of course not, but the first and last entries have nothing to do with the previous row. He could just edit in $k \neq 0, 2^n$ $\endgroup$ – Will Jagy Dec 28 '14 at 19:21
  • $\begingroup$ @r9m oh sorry, should I take it down? $\endgroup$ – Jorge Fernández-Hidalgo Dec 28 '14 at 19:22
  • $\begingroup$ @WillJagy Yeah it doesn't change the answer, it's just a minor nitpick (aren't mathematicians all about annoying precision?) $\endgroup$ – Zubin Mukerjee Dec 28 '14 at 19:24
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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