# Thread: Prove by Induction

1. ## 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!

2. Hello

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

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 ?

3. 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

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

5. Originally Posted by flyingsquirrel
Hello

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

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.

6. 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}