Combinatorial interpretation of $\prod^\infty_{k=0}\left( 1+x^{2^k}\right) = \frac{1}{1-x}$

Question

I came across a problem that asked me to prove this for $|x|<1$. My first instinct upon seeing the identity was the fact that $\frac{1}{1-x}$ happens to be the generating function of the sequence $1, 1, 1, \dots$, corresponding to the formal series $1+x+x^2+\dots$. Although I proved the identity without resorting to any combinatorics (using a telescoping product, as discussed here), it would be interesting to know if

$$ \prod^\infty_{k=0}\left( 1+x^{2^k}\right) = \frac{1}{1-x} = \sum^\infty_{k=0}x^k$$ has a combinatorial interpretation related to generating functions.

Answer 1

If you want to find the coefficient of $x^n$ in the expression $$(1+x)(1+x^2)(1+x^4) (1+x^8)\dots,$$ you could reframe the question as "How many ways are there to write $n$ as the sum of powers of $2$, using each power only once?"

This is just asking about how many ways there are to express $n$ as a binary number, which is $1$.

Answer 2

It is clear that $\prod^\infty_{k=0}\left( 1+x^{2^k}\right)$ is an infinite polynomial in $x$. Now the question is what is the coefficient of $x^n$. Observe that if we develop the product, we essentially have to choose either $1$ or $2^{2^k}$ for each of the $k$ and multiply those together. We have to do this for all possible choice and then sum. In otherwords \begin{align*} \prod^\infty_{k=0}\left( 1+x^{2^k}\right) &= \sum_{A\subseteq \mathbb N} \left(\prod_{k\in \mathbb N\setminus A} 1 \right)\cdot\left(\prod_{k\in A} x^{2^k} \right)\\ &= \sum_{A\subseteq \mathbb N} x^{\sum_{k\in A}2^k} \end{align*}

But as mentioned by @Diger the term $\sum_{k\in A}2^k$ is related to the binary expansion of integers. Every integer will be expressed exactly once, by exactly one set $A$. therefore $\prod^\infty_{k=0}\left( 1+x^{2^k}\right)=\sum_{n=0}^\infty x^n$.

Answer 3

The combinatorial argument is that every natural number can be uniquely expressed in binary (base $2$), i.e. it is a unique sum of powers of two (without repeating, with some powers of two potentially omitted).

For an example, the representation of $37$ is $100101_2$, i.e. $37=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+0\cdot 2^3+0\cdot 2^4+1\cdot 2^5$ or, if you like it better, $37=2^0+2^2+2^5$.

This is because $1+x^{2^k}$ is a generating function of the sequence $1,\underbrace{0,0,\ldots,0}_{2^k-1\text{ times}},1,\underbrace{0,0,\ldots}_\text{forever}$ (where the second "$1$" is at position $2^k$), which is the number of ways to express a natural number as a sum of just $2^k$: the numbers $0$, and $2^k$ itself, can be uniquely expressed that way, no other numbers can.

Now, the product of those generating functions gives you the generating function for the number of ways to express a number as a finite sum of those $2^k$'s; on the other hand, as we know the binary representation is unique, this number of ways must always be $1$. Thus the product is $1+1\cdot x+1\cdot x^2+\ldots=\frac{1}{1-x}$.