# Prove equation with induction

Prove by induction that for every natural number $n\in\mathbb{N}$ and every real number $x\in\mathbb{R}$:

$$(1+x)(1+x^2)(1+x^4)\cdot\,\dots\,\cdot(1+x^{2^{n-1}}) = 1 +x +x^2+\dots+(x^{2^n-1})$$

I proved for $n=1$ but i don't know how to continue with $(n+1)$

THANKS

I think you made some mistake in the formula. We prove $$(1+x)(1+x^2)\cdots (1+x^{2^{n-1}}) = 1+x+x^2+x^3+\cdots + x^{2^n-1}.$$ For $n=1$ we get $x+1=x+1$ which holds.

Assume the statement holds for $n$. We prove it holds for $n+1$. So we have $$(1+x)(1+x^2)\cdots(1+x^{2^{n-1}})(1+x^{2^{n}}) = (1+x+\cdots +x^{2^n-1})(1+x^{2^{n}}),$$ by our induction assumption. But $$(1+x+\cdots +x^{2^n-1})(1+x^{2^{n}})=1+x+\cdots +x^{2^n-1} + x^{2^n}+x^{2^n+1} \cdots + x^{2^n+2^{n-1}}=1+x+\cdots+x^{2^{n+1}-1},$$ proving the statement.

I can't resist to show non purely inductive proof. Denote $$P=(1+x)(1+x^2)\cdot\ldots\cdot(1+x^{2^{n-1}})$$ Note that \begin{align} (1-x)P&=(1-x)(1+x)(1+x^2)(1+x^4)\cdot\ldots\cdot(1+x^{2^{n-1}})\\ &=(1-x^2)(1+x^2)(1+x^4)\cdot\ldots\cdot(1+x^{2^{n-1}})\\ &=(1-x^4)(1+x^4)\cdot\ldots\cdot(1+x^{2^{n-1}})\\ &=\ldots\\ &=(1-x^{2^{n-1}})(1+x^{2^{n-1}})\\ &=1-x^{2^n} \end{align} Hence $$P=\frac{1-x^{2^n}}{1-x}=1+x+x^2+\ldots+x^{2^n-1}$$

• The middle part of your proof looks pretty inductive to me. – robjohn Dec 5 '12 at 16:59
• @robjohn When I say non purely inductive I mean that I don't follow all the necessary "ceremnony rules" like base of induction, induction step and etc. – Norbert Dec 5 '12 at 17:44

Here is a proof that doesn't seem to employ induction but uses the uniqueness of the binary representation of the non-negative integers (which may use induction).

Let $0\le m\lt2^n$ then there is only one way to get $x^m$ from the product $$(1+x)(1+x^2)(1+x^4)\dots(1+x^{2^{n-1}})$$ that is by choosing $x^{2^k}$ in the factors where bit $k$ is $1$ in the binary representation of $m$ and choosing $1$ in the factors where bit $k$ is $0$. All coefficients in the factors are $1$ so the coefficient of $x^m$ in the product is $1$.

Therefore, $$(1+x)(1+x^2)(1+x^4)\dots(1+x^{2^{n-1}})=1+x+x^2+x^3+\dots+x^{2^n-1}$$