5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ This will be helpful: math.hmc.edu/funfacts/ffiles/30001.4-5.shtml $\endgroup$ Jan 11 '17 at 13:07
  • $\begingroup$ 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. $\endgroup$ Jan 11 '17 at 13:15
  • $\begingroup$ 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$. $\endgroup$
    – robjohn
    Jan 11 '17 at 17:58
  • 1
    $\begingroup$ You may be interested by the fact that Pascal's triangle modulo 2 generates Sierpinski's sieve (mathworld.wolfram.com/SierpinskiSieve.html) $\endgroup$
    – Jean Marie
    Jan 11 '17 at 22:18
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

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