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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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$