Why does $(1 + x)(1 + x^2)(1 + x^4)(1+x^8) \cdots = 1 + x + x^2 + x^3 + \cdots$?

Question

Is there an intuitive explanation as to why $$(1 + x)(1 + x^2)(1 + x^4)(1+x^8) \cdots = 1 + x + x^2 + x^3 + \cdots$$ for $ |{x}| < 1?$

Of course, we can show that each side of the equation is equal to $\frac{1}{1-x}$ fairly easily (RHS is the basic geometric series with common ratio of $x$ and LHS multiplied by $(1-x)$ will collapse the product to $1$)

^ This proof is perfect for a quick grasp on the equality, although it still remains unclear as to why an infinite product with factors of the form $1+x^{(2^n)}$ should expand into a simple G.S.

I would love to see a more direct proof that would at least make it more obvious as to why we can equate the product into the sum or vice-versa.

Any help would be greatly appreciated.

Answer 1

Let us rewrite the LHS as $\prod_{n=1}^{\infty}(1+x^{2^{n-1}})$. Let $P(k)=\prod_{n=1}^{k}(1+x^{2^{n-1}})$. $$P(1)=x+1$$ $$P(2)=(1+x)(1+x^2)=x^2(x+1)+(x+1)=x^3+x^2+x+1$$ $$P(3)=(x^3+x^2+x+1)(1+x^4)=x^4(x^3+x^2+x+1)+(x^3+x^2+x+1)=x^7+x^6+\cdots+x+1$$ By observation, we notice that $$P(a)=\sum_{n=0}^{2^a-1}x^n.$$ We shall prove this fact by induction.

$$P(1)=x+1$$ Note that $$P(a)=(1+x^{2^{a-1}})P(a-1)=x^{2^{a-1}}P(a-1)+P(a-1). $$ Assume that $$P(t)=\sum_{n=0}^{2^t-1}x^n.$$ Then $$P(t+1)=x^{2^t}P(t)+P(t)=x^{2^t}\sum_{n=0}^{2^t-1}x^n+\sum_{n=0}^{2^t-1}x^n=x^{2^t}(1+x+x^2+\cdots+x^{2^t-1})+(1+x+x^2+\cdots+x^{2^t-1})=(x^{2^t}+x^{2^t+1}+x^{2^t+2}+\cdots+x^{2^{t+1}-1})+(1+x+x^2+\cdots+x^{2^t-1})=1+x+x^2+\cdots+x^{2^{t+1}-1}=\sum_{n=0}^{2^{t+1}-1}x^n. $$

Thus, by induction, we can conclude that $P(t)=\sum_{n=0}^{2^t-1}x^n.$ holds for all integers $t\ge1$.

As $t$ approaches infinity, we obtain that $$(1+x)(1+x^2)(1+x^4)\cdots=1+x+x^2+x^3+\cdots. $$

Answer 2

Any of the powers on the RHS can be written in the form $x^b$ where $b$ is a non-negative integer. Specifically, consider $b$ in binary. There is exactly one way to make a power of $x$ with degree $b$: for each digit in $b$ which is a $1$, we must choose to multiply by the power of $x$ term in the corresponding bracket, while for each digit in $b$ which is a $0$ we must multiply by the $1$ term. All in all there is only and exactly one way to form each non-negative integer $b$, and so expanding out the LHS produces the RHS term by term.