TAOCP 1.2.6 Exercise 12

Let P(n):\qquad \binom{n}{k}\equiv 1 \pmod 2 \quad\text{for every }k\text{ with }0\le k\le n\text{ and }\binom{n}{k}\ne0.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 12. [M22] Are there any positive integers $n$ for which all the nonzero entries in the $n$th row of Pascal's triangle are odd? If so, find all such $n$.

Verified: yes
Solve time: 44s

Solution

Let

$$ P(n):\qquad \binom{n}{k}\equiv 1 \pmod 2 \quad\text{for every }k\text{ with }0\le k\le n\text{ and }\binom{n}{k}\ne0. $$

Since $n$ is a positive integer, the nonzero entries in the $n$th row of Pascal's triangle are precisely

$$ \binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}. $$

We seek all positive integers $n$ for which every one of these coefficients is odd.

Exercise 10(6), Lucas's theorem modulo $2$, states that if

$$ n=a_r2^r+\cdots+a_12+a_0,\qquad k=b_r2^r+\cdots+b_12+b_0, $$

with $a_i,b_i\in{0,1}$, then

$$ \binom{n}{k} \equiv \binom{a_r}{b_r}\cdots\binom{a_1}{b_1}\binom{a_0}{b_0} \pmod 2. $$

Since

$$ \binom{1}{0}=\binom{1}{1}=\binom{0}{0}=1, \qquad \binom{0}{1}=0, $$

the coefficient $\binom{n}{k}$ is odd if and only if every binary digit $b_i$ satisfies $b_i\le a_i$.

Assume first that every nonzero entry in row $n$ is odd. Write

$$ n=a_r2^r+\cdots+a_12+a_0. $$

If some digit $a_j=0$, choose

$$ k=2^j. $$

Then the binary digits of $k$ satisfy $b_j=1$ and $b_i=0$ for $i\ne j$. Lucas's theorem gives

$$ \binom{n}{k} \equiv \binom{a_j}{1} \prod_{i\ne j}\binom{a_i}{0} = 0 \pmod 2. $$

Since $0<k\le n$, the coefficient $\binom{n}{k}$ is a positive integer, hence nonzero. Therefore row $n$ contains an even nonzero entry, contrary to the hypothesis. Consequently no binary digit of $n$ can be $0$.

Thus

$$ a_r=a_{r-1}=\cdots=a_0=1, $$

and therefore

$$ n=2^r+2^{r-1}+\cdots+2+1 =2^{r+1}-1. $$

This proves that any solution must be of the form $2^m-1$ with $m\ge1$.

Conversely, let

$$ n=2^m-1. $$

Its binary representation is

$$ n=\underbrace{11\cdots1}_{m\text{ digits}}{}_2. $$

For any integer $k$ with $0\le k\le n$, every binary digit of $k$ is either $0$ or $1$, hence each digit satisfies $b_i\le a_i=1$. Lucas's theorem therefore yields

$$ \binom{n}{k} \equiv \prod_i \binom{1}{b_i} = 1 \pmod 2. $$

Hence every coefficient in row $n$ is odd.

The positive integers $n$ for which all nonzero entries in the $n$th row of Pascal's triangle are odd are exactly

$$ n=2^m-1, \qquad m\ge1. $$

Therefore

$$ \boxed{\text{all such }n\text{ are }2^m-1\ (m\ge1).} $$

This completes the proof.

∎