# Ruslan's question at Yahoo! Answers regarding the proof of a product formula by induction

#### MarkFL

Staff member
Here is the question:

Please explain me how to prove this by induction. Thanks a lot!

Use the fact that $$\displaystyle (x+y)(x-y)=x^2-y^2$$ to prove by induction that:

$$\displaystyle \prod_{k=0}^n\left(1+x^{2^k} \right)=\frac{1-x^{2^{n+1}}}{1-x}$$

for any $$\displaystyle n\in\mathbb{N}$$ and any $$\displaystyle x\in\mathbb{Q}$$ with $$\displaystyle x\ne1$$.
I have posted a link there to this thread so the OP can view my work.

#### MarkFL

Staff member
Hello Ruslan,

First, we want to show the base case $P_1$ is true:

$$\displaystyle \prod_{k=0}^1\left(1+x^{2^k} \right)=\frac{1-x^{2^{1+1}}}{1-x}$$

$$\displaystyle \left(1+x^{2^0} \right)\left(1+x^{2^1} \right)=\frac{1-x^{2^2}}{1-x}$$

$$\displaystyle \left(1+x \right)\left(1+x^2 \right)=\frac{1-x^4}{1-x}=\frac{\left(1+x^2 \right)\left(1-x^2 \right)}{1-x}=\frac{\left(1+x^2 \right)(1+x)(1-x)}{1-x}=\left(1+x^2 \right)(1+x)$$

Thus, the base case is true. Hence, we state the given hypothesis:

$$\displaystyle \prod_{k=0}^n\left(1+x^{2^k} \right)=\frac{1-x^{2^{n+1}}}{1-x}$$

As our induction step, we may multiply both sides by $$\displaystyle \left(1+x^{2^{n+1}} \right)$$ to obtain:

$$\displaystyle \prod_{k=0}^n\left(1+x^{2^k} \right)\cdot\left(1+x^{2^{n+1}} \right)=\frac{1-x^{2^{n+1}}}{1-x}\cdot\left(1+x^{2^{n+1}} \right)$$

On the left side, incorporate the new factor into the product, and on the right carry out the indication multiplication:

$$\displaystyle \prod_{k=0}^{n+1}\left(1+x^{2^k} \right)=\frac{1-\left(x^{2^{n+1}} \right)^2}{1-x}$$

On the right apply the property of exponents $$\displaystyle \left(a^b \right)^c=a^{bc}$$ to obtain:

$$\displaystyle \prod_{k=0}^{n+1}\left(1+x^{2^k} \right)=\frac{1-x^{2\cdot2^{n+1}}}{1-x}$$

Now, on the right apply the property of exponents $$\displaystyle a\cdot a^b=a^{b+1}$$ to obtain:

$$\displaystyle \prod_{k=0}^{n+1}\left(1+x^{2^k} \right)=\frac{1-x^{2^{(n+1)+1}}}{1-x}$$

We have derived $P_{n+1}$ from $P_{n}$ thereby completing the proof by induction.