1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Observe that coefficient of $x^i$ is the same on LHS and RHS for each $i$ $\endgroup$ – Dhanvi Sreenivasan Dec 9 '16 at 5:06
  • 2
    $\begingroup$ 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. $\endgroup$ – achille hui Dec 9 '16 at 5:18
3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Algebraic (and other) proofs need to have finite length. An infinite rewriting procedure might give a first idea, but it not a proof. $\endgroup$ – Marc van Leeuwen Dec 9 '16 at 5:38
  • $\begingroup$ 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. $\endgroup$ – amcerbu Dec 9 '16 at 7:09
  • $\begingroup$ This is just a hint.. we can do it for $n$, and then make $n$ arbitrarily large $\endgroup$ – Dhanvi Sreenivasan Dec 9 '16 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.