1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The middle part of your proof looks pretty inductive to me. $\endgroup$ – robjohn Dec 5 '12 at 16:59
  • $\begingroup$ @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. $\endgroup$ – Norbert Dec 5 '12 at 17:44
1
$\begingroup$

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

$\endgroup$

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.