Take the 2-minute tour ×
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.

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

share|improve this question

3 Answers 3

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|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|improve this answer
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. –  no identity 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|improve this answer

Your Answer

 
discard

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.