# Prove by Induction

• 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"?

• May 30th 2008, 08:38 AM
flyingsquirrel
Hello

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

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

\displaystyle \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 $\displaystyle \frac{2}{2}$ and the second one by $\displaystyle \frac{3}{3}$ so that they can be added.

$\displaystyle 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 $\displaystyle n$,

I assumed the equality $\displaystyle \sum_{j=0}^n\left(\frac{-1}{2}\right)^j=\frac{2^{n+1}+(-1)^n}{3\cdot 2^n}$ was true for $\displaystyle 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 $\displaystyle n=0$. (easy :D)

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

\displaystyle \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 $\displaystyle \frac{2}{2}$ and the second one by $\displaystyle \frac{3}{3}$ so that they can be added.

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

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

Otherwise, one can do this as follows :

\displaystyle \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}