Prove that $\prod_{k=0}^{n-1}(1+x^{2^k})=\sum_{j=0}^{2^n-1}x^j$

Question

How I can demonstrate the following equation?

$$\prod_{k=0}^{n-1}(1+x^{2^k})=\sum_{j=0}^{2^n-1}x^j$$

It is easy to apply the geometric sum: $$\sum_{j=0}^{2^n-1}x^j=\frac{1-x^{2^n}}{1-x}$$

How can I find the formula for this equation?: $$\prod_{k=0}^{n-1}(1+x^{2^k}) =\text{???}$$

Answer 1

We have $$\prod_{k=0}^{n-1}\left(1+x^{2^{k}}\right)=\prod_{k=0}^{n-1}\frac{1-x^{2^{k+1}}}{1-x^{2^{k}}}=\frac{1}{1-x}\prod_{k=0}^{n-1}\left(1-x^{2^{k+1}}\right)\prod_{k=0}^{n-2}\left(1-x^{2^{k+1}}\right)^{-1}=\color{red}{\frac{1-x^{2^{n}}}{1-x}}.$$

Answer 2

Hint : Use \begin{align} \frac{1-x^{2^{j+1}}}{1-x^{2^{j}}}=1+x^{2^{j}}. \end{align}

Answer 3

Recursion as already suggested gives the easiest proof. But you may also carry out the (huge) product and note that you get $2^n$ terms of the form $$ x^{b_0+2b_1 +4b_2 + \cdots + 2^{n-1} b_{n-1}}$$ where the $b_k$'a are either zero or one (depending on choosing the factor $1$ or $x^{2^k}$. Ans the exponent is precisely the binary expansion of all integers from $0$ to $2^{n}-1$.