# Proof $\prod_{i=0}^{\infty}(1+x^{2^i})=\frac{1}{1-x}$ both algebraically and combinatorially

I was doing some school work review and came across this equation $\prod_{i=0}^{\infty}(1+x^{2^i})=\frac{1}{1-x}$.

I'm suppose to prove this combinatorially but I was having trouble to believe that this equation holds in the first place. So can someone enlighten me with its proof both combinatorially and algebraically?

I know that the RHS expands into $\sum_{i=0}^{\infty}x^i$ but how does the LHS equal to the RHS? If I attempt to expand the LHS I get something like $x^2+x^4+x^6+...$ with varing coefficients.

Thanks!

Edit: As multiple people suggested, the original equation should be $\prod_{i=0}^{\infty}(1+x^{{2}^{i}})=\frac{1}{1-x}$ instead, otherwise the equation does not hold.

• Observe that coefficient of $x^i$ is the same on LHS and RHS for each $i$ – Dhanvi Sreenivasan Dec 9 '16 at 5:06
• There is a typo in the equation, should be $\displaystyle\;\prod_{i=0}^{\infty}(1+x^{2^\color{red}{i}})=\frac{1}{1-x}\;$ instead. – achille hui Dec 9 '16 at 5:18

The equation should be:

$$\prod_{i=0}^{\infty}(1+x^{2^i})=\frac{1}{1-x}$$

which makes sense combinatorially because every integer has a unique binary representation, and the algebraic expansion of the LHS follows the same pattern.

• That's what I got as well – Dhanvi Sreenivasan Dec 9 '16 at 5:12
• @DhanviSreenivasan So he(my professor) made a typo. Sigh. – Allen Ai Dec 9 '16 at 5:13
• @MarcvanLeeuwen Yes you are right. I've corrected it. – Allen Ai Dec 9 '16 at 5:24

Hint :- $$1 + x + x^2 + x^3+x^4+x^5...= (1+x)(1+x^2+x^4...) = (1+x)(1+x^2)(1+x^4+x^8...)$$

You can continue this indefinitely to regenerate the LHS

• Algebraic (and other) proofs need to have finite length. An infinite rewriting procedure might give a first idea, but it not a proof. – Marc van Leeuwen Dec 9 '16 at 5:38
• True. But showing that $\sum_{i=0}^{2^{n}-1} x^i = \prod_{j=0}^{n-1} (1+x^{2^j})$ for all $n$ is well on the way to a proof. – amcerbu Dec 9 '16 at 7:09
• This is just a hint.. we can do it for $n$, and then make $n$ arbitrarily large – Dhanvi Sreenivasan Dec 9 '16 at 15:55