How to derive this infinite product formula? Show:
$$\prod_{n=0}^{\infty}\left(1 + x^{2^n}\right) = \frac{1}{1-x}$$
I tried numerous things, multiplying by $x$, dividing, but none of that worked. Also, I realized that: 
$$\prod_{n=0}^{\infty} \left(1 + x^{2^n}\right) = \sum_{n=0}^{\infty} x^n$$
But I cannot prove the relation. I get:
$$(1 + x)(1+x^2)(1+x^4)(1+x^8)...$$
But for  a general $n$ it is more difficult. 
 A: The partial products are
$$1+x,$$
$$(1+x)+x^2(1+x)=1+x+x^2+x^3,$$
$$(1+x+x^2+x^3)+x^4(1+x+x^2+x^3)=1+x+x^2+x^3+x^4+x^4+x^5+x^6+x^7$$
$$\cdots$$
Every time the number of terms doubles.
Doesn't that ring a bell ?
A: Since:
$$\begin{eqnarray*} (1-x)(1+x)&=&(1-x^2),\\ 
 (1-x^2)(1+x^2) &=& (1-x^4), \\
 (1-x^4)(1+x^4) &=& (1-x^8),\\ \ldots\end{eqnarray*} $$
we have:
$$ (1-x)\prod_{k=0}^{N}\left(1+x^{2^k}\right) = 1-x^{2^{N+1}} \tag{1}$$
so, assuming $|x|<1$ and letting $N\to +\infty$ we have:
$$ (1-x)\prod_{k=0}^{+\infty}\left(1+x^{2^k}\right) = 1\tag{2} $$
as wanted.
Notice that a possible combinatorial interpretation of $(2)$ is: there is only one way of writing a natural number as a sum of distinct powers of two.
A: We have 
$$\prod_{n = 0}^\infty (1 + x^{2^n}) = \lim_{m \to \infty} \prod_{n = 0}^m \frac{1 - x^{2^{n+1}}}{1 - x^{2^n}} = \lim_{m\to \infty} \frac{1 - x^{2^{m+1}}}{1 - x} = \frac{1}{1 - x}$$
for $|x| < 1$.
A: You were almost done. Recall that, for $|x| < 1$,
$$\frac1{1+x} = \sum_{n = 0}^\infty(-1)^n x^n \qquad\mbox{(MacLaurin expansion).}$$
Therefore
$$\frac1{1-x} = \sum_{n = 0}^\infty x^n\qquad\mbox{for }|x| < 1$$
and you can conclude the proof.
A: And formally, i.e., "in form," it's true for all $x$ (just not convergent for $|x| \geq 1$).  The sum you found is the "hardest" part: from there, use Gauss' (apocryphal) Method: let the sum $= S$.  Then, formally, $xS = -1 + S \implies S(1 - x) = 1 \implies S = 1/(1-x)$.  One can then prove  convergence for $|x| < 1$, $x$ complex (including real), separately. 
