Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$


share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer

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} $$

share|cite|improve this answer
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} $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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