# Total number of odd numbers in a row of Pascal's triangle is a natural power of two

This seems like a combinatorial problem so there might be something simple that hasn't struck me. Although I do have an idea but I am unable to proceed from it. The statement of the question is:

Prove that in any row of Pascal's triangle, the number of odd elements is $$2^k$$, for some $$k \in \mathbb{N}$$.

I was working on a Pascal's triangle but in a binary format, where two adjacent 1's add up to 0. Something of the sort:

                 1
1   1
1   0   1
1   1   1   1
1   0   0   0   1
1   1   0   0   1   1


It is a definitive sequence and the thing I liked about it was that you can add up the adjacent 1's in a row to get the number of odd elements, but I haven't been able to generalize this information. I was thinking along the lines of a recursive relation in polynomials whose coefficients would represent the rows of this triangle, then I can just feed 1 into the equation and inductively prove that it is a perfect power of 2.

Can someone help me out on a proof along these lines, if I'm going in the right direction here?

P.S. I know there is the modulo 2 proof but can someone help me generalize that binary pascal's triangle?

• This will be helpful: math.hmc.edu/funfacts/ffiles/30001.4-5.shtml Jan 11 '17 at 13:07
• Okay, cool. But I want to try a proof along the lines of what I was trying. That is a good solution, but I wanna see where this goes. Jan 11 '17 at 13:15
• To get an inductive proof, you may want to use the results from the answers based on Kummer's Theorem. That is, try to show that the number of $1$s in a row of Pascal's Triangle is $2$ to the power of the number of $1$ bits in the binary representation of $n$.
– robjohn
Jan 11 '17 at 17:58
• You may be interested by the fact that Pascal's triangle modulo 2 generates Sierpinski's sieve (mathworld.wolfram.com/SierpinskiSieve.html) Jan 11 '17 at 22:18

## 3 Answers

Similar idea to Andreas Caranti's answer:

Kummer's Theorem says that the number of factors of $$p$$ in $$\binom{n}{k}$$ is the number of carries when adding $$k$$ and $$n-k$$ in base-$$p$$. There are no carries when adding $$k$$ and $$n-k$$ in binary if and only if $$k\veebar n-k=0$$; when that is true, $$n=k\lor n-k$$. This means that $$\binom{n}{k}$$ is odd when the $$1$$ bits of $$k$$ are a subset of the $$1$$ bits of $$n$$. That is, there are $$2^{\sigma_2(n)}$$ odd entries in row $$n$$ of Pascal's Triangle, where $$\sigma_2(n)$$ is the sum of the bits in the binary representation of $$n$$.

Will delete because this is not what OP intends, but a proof via Kummer's Theorem looks rather neat to me.

Write $n, m$ in base $2$ $$n = 2^{k} n_{k} + \dots + 2 n_{1} + n_{0}, \qquad m = 2^{k} m_{k} + \dots + 2 m_{1} + m_{0},$$ with $n_{i}, m_{i} \in \{ 0, 1 \}$.

Then

$\dbinom{n}{m}$ is odd iff there are no carries in the sum in base $2$ $$m + (n - m) = n,$$ that is, iff $m_{i} \le n_{i}$ for each $i$.

Given $n$, there are thus $$\prod_{i=0}^{k} (n_{i} + 1)$$ possibilities for $m$, and each $n_{i} + 1 \in \{ 1, 2 \}$.

This also tells you what is the exponent $k$ in the question - it is the number of $1$'s in the diadic expansion of $n$, or equivalently, the number of distinct powers of $2$ that sum up to $n$.

The simplest (at least simplest to explain) solution (using Lucas's theorem) has not been posted; let me fill that "much needed gap". Lazy as I am, I will mostly copypaste my answer from https://math.stackexchange.com/a/2184460/ , since the argument is essentially the same.

I use the notation $$\mathbb{N}$$ for the set $$\left\{0,1,2,\ldots\right\}$$.

The question asks the following:

Theorem 1. Let $$n \in \mathbb{N}$$. Then, the number of $$i \in \left\{0,1,\ldots,n\right\}$$ such that $$\dbinom{n}{i}$$ is odd is a power of $$2$$.

I shall prove something slightly more general:

Theorem 2. Let $$n \in \mathbb{N}$$. Let $$q$$ be a real number. Then, there exists a finite subset $$G$$ of $$\mathbb{N}$$ such that \begin{align} \sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}} q^i = \prod_{g \in G} \left(q^{2^g} + 1\right) . \end{align}

Proof of Theorem 2. Write $$n$$ in the form $$n=a_{k}2^{k}+a_{k-1}2^{k-1}+\cdots+a_{0}2^{0}$$ for some $$k\in\mathbb{N}$$ and $$a_{0},a_{1},\ldots,a_{k}\in\left\{ 0,1\right\}$$. (This is just the base-$$2$$ representation of $$n$$, possibly with leading zeroes.)

Lucas's theorem tells you that if $$i=b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}$$ for some $$b_{0} ,b_{1},\ldots,b_{k}\in\left\{ 0,1\right\}$$, then \begin{align} \dbinom{n}{i} &\equiv \dbinom{a_{k}}{b_{k}}\dbinom{a_{k-1}}{b_{k-1}} \cdots\dbinom{a_{0}}{b_{0}}=\prod\limits_{j=0}^{k}\underbrace{\dbinom{a_{j}}{b_{j}} }_{\substack{= \begin{cases} 1, & \text{if }b_{j}\leq a_{j}\\ 0, & \text{if }b_{j}>a_{j} \end{cases} \\\text{(since }a_{j}\text{ and }b_{j}\text{ lie in }\left\{ 0,1\right\} \text{)}}} \\ &=\prod\limits_{j=0}^{k} \begin{cases} 1, & \text{if }b_{j}\leq a_{j}\\ 0, & \text{if }b_{j}>a_{j} \end{cases} = \begin{cases} 1, & \text{if }b_{j}\leq a_{j}\text{ for all }j\text{;}\\ 0, & \text{otherwise} \end{cases} \mod 2 . \end{align} Hence, the $$i\in\mathbb{N}$$ for which $$\dbinom{n}{i}$$ is odd are precisely the numbers of the form $$b_{k}2^{k}+b_{k-1}2^{k-1} +\cdots+b_{0}2^{0}$$ for $$b_{0},b_{1},\ldots,b_{k}\in\left\{ 0,1\right\}$$ satisfying $$\left( b_{j}\leq a_{j}\text{ for all }j\right)$$. Since all these $$i$$ satisfy $$i \in \left\{ 0,1,\ldots,n\right\}$$ (because otherwise, $$\dbinom{n}{i}$$ would be $$0$$ and therefore could not be odd), we can rewrite this as follows: The $$i \in \left\{ 0,1,\ldots,n\right\}$$ for which $$\dbinom{n}{i}$$ is odd are precisely the numbers of the form $$b_{k}2^{k}+b_{k-1}2^{k-1} +\cdots+b_{0}2^{0}$$ for $$b_{0},b_{1},\ldots,b_{k}\in\left\{ 0,1\right\}$$ satisfying $$\left( b_{j}\leq a_{j}\text{ for all }j\right)$$. Since these numbers are distinct (because the base-$$2$$ representation of any $$i\in\mathbb{N}$$ is unique, as long as we fix the number of digits), we thus can substitute $$b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}$$ for $$i$$ in the sum $$\sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\ \dbinom{n}{i}\text{ is odd}}}q^{i}$$. Thus, this sum rewrites as follows: \begin{align} \sum\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\ \dbinom{n}{i}\text{ is odd}}}q^{i} &=\underbrace{\sum\limits_{\substack{b_{0},b_{1} ,\ldots,b_{k}\in\left\{ 0,1\right\} ;\\b_{j}\leq a_{j}\text{ for all }j} }}_{=\sum\limits_{b_{0}=0}^{a_{0}}\sum\limits_{b_{1}=0}^{a_{1}}\cdots\sum\limits_{b_{k}=0}^{a_k} }\underbrace{q^{b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}}}_{=\left( q^{2^{k}}\right) ^{b_{k}}\left( q^{2^{k-1}}\right) ^{b_{k-1}}\cdots\left( q^{2^{0}}\right) ^{b_{0}}} \\ &=\sum\limits_{b_{0}=0}^{a_{0}}\sum\limits_{b_{1}=0}^{a_{1}}\cdots\sum\limits_{b_{k}=0}^{a_{k} }\left( q^{2^{k}}\right) ^{b_{k}}\left( q^{2^{k-1}}\right) ^{b_{k-1} }\cdots\left( q^{2^{0}}\right) ^{b_{0}} \\ &=\left( \sum\limits_{b_{k}=0}^{a_{k}}\left( q^{2^{k}}\right) ^{b_{k}}\right) \left( \sum\limits_{b_{k-1}=0}^{a_{k-1}}\left( q^{2^{k-1}}\right) ^{b_{k-1} }\right) \cdots\left( \sum\limits_{b_{0}=0}^{a_{0}}\left( q^{2^{0}}\right) ^{b_{0}}\right) \\ &=\left( \sum\limits_{b=0}^{a_{k}}\left( q^{2^{k}}\right) ^{b}\right) \left( \sum\limits_{b=0}^{a_{k-1}}\left( q^{2^{k-1}}\right) ^{b}\right) \cdots\left( \sum\limits_{b=0}^{a_{0}}\left( q^{2^{0}}\right) ^{b}\right) \\ &=\prod\limits_{g=0}^{k}\underbrace{\left( \sum\limits_{b=0}^{a_{g}}\left( q^{2^{g}}\right) ^{b}\right) }_{\substack{= \begin{cases} q^{2^{g}}+1, & \text{if }a_{g}=1;\\ 1 & \text{if }a_{g}=0 \end{cases} \\\text{(since }a_{g}\in\left\{ 0,1\right\} \text{)}}} \\ &=\prod\limits_{g=0}^{k} \begin{cases} q^{2^{g}}+1, & \text{if }a_{g}=1;\\ 1 & \text{if }a_{g}=0 \end{cases} \\ &=\left( \prod\limits_{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g} =1}}\left( q^{2^{g}}+1\right) \right) \underbrace{\left( \prod\limits _{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g}=0}}1\right) }_{=1} \\ &=\prod\limits_{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g}=1}}\left( q^{2^{g}}+1\right) . \end{align} Thus, there exists a finite subset $$G$$ of $$\mathbb{N}$$ such that \begin{align} \sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}} q^i = \prod_{g \in G} \left(q^{2^g} + 1\right) \end{align} (namely, $$G$$ is the set of all $$g\in\left\{ 0,1,\ldots,k\right\}$$ satisfying $$a_g = 1$$). This proves Theorem 2. $$\blacksquare$$

Proof of Theorem 1. Theorem 2 (applied to $$q = 1$$) shows that there exists a finite subset $$G$$ of $$\mathbb{N}$$ such that \begin{align} \sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}} 1^i = \prod_{g \in G} \left(1^{2^g} + 1\right) . \end{align} Consider this $$G$$. Comparing \begin{align} \sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}} 1^i = \prod_{g \in G} \underbrace{\left(1^{2^g} + 1\right)}_{= 1+1 = 2} = \prod_{g \in G} 2 = 2^{\left|G\right|} \end{align} with \begin{align} \sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}} \underbrace{1^i}_{=1} & = \sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}} 1 \\ & = \left(\text{the number of all i\in\left\{ 0,1,\ldots,n\right\} such that \dbinom{n}{i} is odd}\right) \cdot 1 \\ & = \left(\text{the number of all i\in\left\{ 0,1,\ldots,n\right\} such that \dbinom{n}{i} is odd}\right) , \end{align} we obtain \begin{align} \left(\text{the number of all i\in\left\{ 0,1,\ldots,n\right\} such that \dbinom{n}{i} is odd}\right) = 2^{\left|G\right|} . \end{align} Hence, the number of $$i \in \left\{0,1,\ldots,n\right\}$$ such that $$\dbinom{n}{i}$$ is odd is a power of $$2$$. This proves Theorem 1. $$\blacksquare$$