Prove by Induction

Printable View

May 30th 2008, 08:24 AM
robocop_911

Prove by Induction

How to do this following "Induction sum"?

n
SUM (-1/2)^j = (2^n+1 + (-1)^n)/ 3. 2^n
j=0

How do we remove the "summation" sign here? Also, how to go about proving it by using "induction"?

Thanks for you reply!
May 30th 2008, 08:38 AM
flyingsquirrel

Hello

To prove this by induction, check that the equality is true for $n=0$ . (easy :D)

Then, assuming the equality is true for an integer $n$ ,

$\begin{aligned} S_{n+1}=\sum_{j=0}^{n+1}\left(\frac{-1}{2}\right)^j&=\sum_{j=0}^n\left(\frac{-1}{2}\right)^j+\left(\frac{-1}{2}\right)^{n+1}\\ &=\frac{2^{n+1}+(-1)^n}{3\cdot 2^n}+\left(\frac{-1}{2}\right)^{n+1}\\ \end{aligned}$

Multiply the first fraction by $\frac{2}{2}$ and the second one by $\frac{3}{3}$ so that they can be added.

$S_{n+1}=\frac{2}{2}\cdot\frac{2^{n+1}+(-1)^n}{3\cdot 2^n}+\frac{3}{3}\cdot\left(\frac{-1}{2}\right)^{n+1}=\frac{2^{n+2}+2\cdot(-1)^n}{3\cdot2^{n+1}}+\frac{3\cdot(-1)^{n+1}}{3\cdot 2^{n+1}}=\ldots$

Does it help ?
May 30th 2008, 08:54 AM
robocop_911

Hi, Thanks for you quick reply man!

Anyways, I didn't got how did you "expand"

n
sum (-1/2)^j into (2^n+1+(-1)^n)/3.2^n etc...
j =0

Also, how to get the symbols like you are using? Do we have to write the code for that?

Thanks
May 30th 2008, 09:18 AM
flyingsquirrel

Quote:

Originally Posted by robocop_911

Hi, Thanks for you quick reply man!

Anyways, I didn't got how did you "expand"

n
sum (-1/2)^j into (2^n+1+(-1)^n)/3.2^n etc...
j =0

Quote:

Originally Posted by flyingsquirrel

Then, assuming the equality is true for an integer $n$ ,

I assumed the equality $\sum_{j=0}^n\left(\frac{-1}{2}\right)^j=\frac{2^{n+1}+(-1)^n}{3\cdot 2^n}$ was true for $n$ . :D

Quote:

Also, how to get the symbols like you are using? Do we have to write the code for that?

Yes, you have to write the code for each formula. See this thread.
May 30th 2008, 09:43 AM
robocop_911

Quote:

Originally Posted by flyingsquirrel

Hello

To prove this by induction, check that the equality is true for $n=0$ . (easy :D)

Then, assuming the equality is true for an integer $n$ ,

$\begin{aligned} S_{n+1}=\sum_{j=0}^{n+1}\left(\frac{-1}{2}\right)^j&=\sum_{j=0}^n\left(\frac{-1}{2}\right)^j+\left(\frac{-1}{2}\right)^{n+1}\\ &=\frac{2^{n+1}+(-1)^n}{3\cdot 2^n}+\left(\frac{-1}{2}\right)^{n+1}\\ \end{aligned}$

Multiply the first fraction by $\frac{2}{2}$ and the second one by $\frac{3}{3}$ so that they can be added.

$S_{n+1}=\frac{2}{2}\cdot\frac{2^{n+1}+(-1)^n}{3\cdot 2^n}+\frac{3}{3}\cdot\left(\frac{-1}{2}\right)^{n+1}=\frac{2^{n+2}+2\cdot(-1)^n}{3\cdot2^{n+1}}+\frac{3\cdot(-1)^{n+1}}{3\cdot 2^{n+1}}=\ldots$

Does it help ?

Can you expand this further more... I don't get it why are you multiplying and dividing by 2/2 and 3/3.
May 30th 2008, 11:16 AM
flyingsquirrel

Quote:

Originally Posted by robocop_911

Can you expand this further more... I don't get it why are you multiplying and dividing by 2/2 and 3/3.

I did this so that the two fractions share the same denominator.

$\frac{2^{n+1}+(-1)^n}{3\cdot 2^n}+\left(\frac{-1}{2}\right)^{n+1}= \frac{2^{n+1}+(-1)^n}{{\color{blue}3\cdot 2^n}}+\frac{(-1)^{n+1}}{{\color{red}2^{n+1}}}$

As $3\cdot 2^{n+1}=2\cdot {\color{blue}3\cdot2^n}=3\cdot{\color{red}2^{n+1}}$ , we choose $3\cdot 2^{n+1}$ as the common denominator. To make appear $3\cdot 2^{n+1}$ at the denominator of the first fraction, we multiply it by $\frac{2}{2}$ . For a similar reason, we multiply the second fraction by $\frac{3}{3}$ .

Otherwise, one can do this as follows :

$\begin{aligned} \frac{2^{n+1}+(-1)^n}{3\cdot 2^n}+\left(\frac{-1}{2}\right)^{n+1}&= \frac{2^{n+1}+(-1)^n}{{3\cdot 2^n}}+\frac{(-1)^{n+1}}{{2^{n+1}}}\\ &=\frac{1}{2^n}\left(\frac{2^{n+1}+(-1)^n}{3}+\frac{(-1)^{n+1}}{2}\right)\\ &= \frac{1}{2^n}\cdot\frac{2\left(2^{n+1}+(-1)^n\right)+3(-1)^{n+1}}{3\cdot 2}\\ &=\ldots \end{aligned} $