Proof of Product Formula by Induction: Ruslan's Question on Yahoo Answers

[MarkFL]

Here is the question:

Please help to prove by induction?

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

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

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

for any $$n\in\mathbb{N}$$ and any $$x\in\mathbb{Q}$$ with $$x\ne1$$.

I have posted a link there to this thread so the OP can view my work.

 

[MarkFL]

Hello Ruslan,

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

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

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

$$\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:

$$\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 $$\left(1+x^{2^{n+1}} \right)$$ to obtain:

$$\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:

$$\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 $$\left(a^b \right)^c=a^{bc}$$ to obtain:

$$\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 $$a\cdot a^b=a^{b+1}$$ to obtain:

$$\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.