Why does Pascal's Triangle (mod 2) encode the Fermat primes?

Solution 1:

It is indeed true that each $x_{n}$ is a product of integers of the form $2^{2^{m}}+1$ (although not of the ones you have stated).

To prove this, we fix an $n\in\mathbb{N}$. Your definition of $x_{n}$ rewrites as $x_{n}=\sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}}2^{i}$.

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

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

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}}}2^{i}$. Thus, this sum rewrites as follows:

$\sum\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\ \dbinom{n}{i}\text{ is odd}}}2^{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{2^{b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}}}_{=\left( 2^{2^{k}}\right) ^{b_{k}}\left( 2^{2^{k-1}}\right) ^{b_{k-1}}\cdots\left( 2^{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( 2^{2^{k}}\right) ^{b_{k}}\left( 2^{2^{k-1}}\right) ^{b_{k-1} }\cdots\left( 2^{2^{0}}\right) ^{b_{0}}$

$=\left( \sum\limits_{b_{k}=0}^{a_{k}}\left( 2^{2^{k}}\right) ^{b_{k}}\right) \left( \sum\limits_{b_{k-1}=0}^{a_{k-1}}\left( 2^{2^{k-1}}\right) ^{b_{k-1} }\right) \cdots\left( \sum\limits_{b_{0}=0}^{a_{0}}\left( 2^{2^{0}}\right) ^{b_{0}}\right) $

$=\left( \sum\limits_{b=0}^{a_{k}}\left( 2^{2^{k}}\right) ^{b}\right) \left( \sum\limits_{b=0}^{a_{k-1}}\left( 2^{2^{k-1}}\right) ^{b}\right) \cdots\left( \sum\limits_{b=0}^{a_{0}}\left( 2^{2^{0}}\right) ^{b}\right) $

$=\prod\limits_{g=0}^{k}\underbrace{\left( \sum\limits_{b=0}^{a_{g}}\left( 2^{2^{g} }\right) ^{b}\right) }_{\substack{= \begin{cases} 2^{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} 2^{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( 2^{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( 2^{2^{g}}+1\right) $.

Thus, $x_{n}=\sum\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}}2^{i}=\prod\limits_{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g}=1}}\left( 2^{2^{g}}+1\right) $. This is clearly a product of Fermat numbers.

EDIT: This result also appears as equation (10) in Andrew Granville, Binomial coefficients modulo prime powers, 1997, where it is ascribed to Larry Roberts.

Solution 2:

The claim is an example of the "law of small numbers".

The numbers you are looking at are products of the Fermat numbers $2^{2^n} + 1$, and not the Fermat primes. Since the first few such numbers are Fermat primes, but no larger Fermat primes are known, it is not surprising at all that the pattern holds for the first few $n$ and then fails at 32. It will continue to fail over and over again at larger row numbers.

More specifically, if $n = \sum_{0 \leq i \leq t} a_i 2^i$, the identity is $\sum_{0 \leq i \leq n} ({n \choose i} \bmod 2) 2^i = \prod_{0 \leq j \leq t} (2^{2^j}+1)^{a_j}$. This is indeed a nice identity, but it has virtually nothing to do with primes or Fermat primes.

Solution 3:

There is a 1977 article, "A Relationship Between Pascal's Triangle And Fermat's Numbers" (link to PDF), which provides a proof by induction that the number you call $x_n$ is equal to $$F_k^{d_k}\cdots F_0^{d_0}$$ where $n=(d_k\ldots d_0)_2$ is the binary expansion of $n$.