Product function exercise.

Question

For $x\ne 1$ show that

$$ \prod\limits_{k=1}^{n}\left(1+x^{2^{k-1}}\right) = \frac{1-x^{2^{n}}}{1-x} $$

Answer 1

Expanding the product, we get $$ \eqalign{ & \prod\limits_{k = 1}^n {\left( {1 + x^{\,2^{\,k - 1} } } \right)} = \prod\limits_{k = 0}^{n - 1} {\left( {1 + x^{\,2^{\,k} } } \right)} = \cr & = 1 + \sum\limits_{0\, \le \,k_{\,0} \, < \,\,n} {x^{\,2^{\,k_{\,0} } } } + \sum\limits_{0\, \le \,k_{\,0} < \,\,k_{\,1} \, < \,\,n} {x^{\,2^{\,k_{\,0} } + 2^{\,k_{\,1} } } } + \cdots + \sum\limits_{0\, \le \,k_{\,0} < \,\,k_{\,1} \, \cdots \, < \,\,k_{\,n} < \,\,n} {x^{\,2^{\,k_{\,0} } + 2^{\,k_{\,1} } + \cdots + 2^{\,k_{\,n} } } } \cr} $$ as can be easily seen when proceeding recursively.

The set of exponents $$ \eqalign{ & \left\{ {\,2^{\,k_{\,0} } + 2^{\,k_{\,1} } + \cdots + 2^{\,k_{\,q} } \quad \left| {\;0\, \le \,k_{\,0} < \,\,k_{\,1} \, \cdots \, < \,\,k_{\,q} < \,\,n} \right.} \right\} \quad \Rightarrow \cr & \Rightarrow \quad \left\{ {\underbrace {\left( { \cdots 0, \cdots ,0,1,0 \cdots ,1, \cdots } \right)_{\,2} }_{n\,{\rm bits},\;q\,{\rm ones}}} \right\} \cr} $$ when represented in base $2$, corresponds to the set of all the binary strings of length $n$ having $q$ one bits.

At varying of $q$ we get the whole set of binary strings of length $n$ (without holes and without duplications): $$ \left\{ {\left( {0,0, \cdots ,0, \cdots ,0} \right)_{\,2} , \cdots ,\left( {0, \cdots ,0,1,0, \cdots ,0} \right)_{\,2} , \cdots ,\left( {1,1, \cdots ,1, \cdots ,1} \right)_{\,2} } \right\} $$ that is, the representation of all the digits in $[0,2^{(n-1)+1}-1]=[0,2^n-1]$.

Therefore $$ \prod\limits_{k = 0}^{n - 1} {\left( {1 + x^{\,2^{\,k} } } \right)} = \sum\limits_{0\, \le \,j < \,\,2^{\,n} - 1} {x^{\,j} } = {{1 - x^{\,2^{\,n} } } \over {1 - x}} $$

Refer to this interesting "Lectures on Integer Partitions"- H. S. Wilf, at page 8.

Answer 2

We can do it by induction. $n=1$ is obvious, for $n+1$ we have:

$$\prod\limits_{k=1}^{n+1}\left(1+x^{2^{k-1}}\right)=(1+x^{2^n})\prod\limits_{k=1}^{n}\left(1+x^{2^{k-1}}\right)=(1+x^{2^n})\frac{1-x^{2^n}}{1-x}=\frac{1-x^{2^{n+1}}}{1-x}$$