How do I prove this equation? $\prod _{n=0}^j(1+x^{^{2^n}})=\sum _{m=0}^{2^j+1}x^m$

Question

So I just stumbled upon this while trying to find the limit of a series. I tried induction but didn't have much success. I did find the left side here under "simple pole" https://en.wikipedia.org/wiki/Infinite_product but no proof is stated. Thanks for any help!

Answer 1

The left-hand side is a telescoping product$$\prod_{n=0}^j\frac{1-x^{2^{n+1}}}{1-x^{2^n}}=\frac{1-x^{2^{j+1}}}{1-x}=\sum_{m=0}^{2^{j+1}-1}x^m,$$so the right-hand side's upper limit is incorrect.

Answer 2

We can write it in the slightly more suggestive way,

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

Now when we expand the product, each term contributes either $0*2^n$ or $1*2^n$ to the exponent, and so we are constructing the base 2 expansion of every integer from $0$ to $1+2+2^2+\cdots+2^j = 2^{j+1}-1$.

$$\sum_{m=0}^{2^{j+1}-1} x^m$$