Welcome to our community

Be a part of something great, join today!

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

  • Thread starter
  • Admin
  • #1

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
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 \(\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.
 
  • Thread starter
  • Admin
  • #2

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
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.