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

3 Answers 3

3

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.

3

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

  • 0
    @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.2012-12-05
1

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