Proof by Induction

Oct 2009
16
0
I am to prove the following equation by induction:

(1/2)+(1/6)+(1/12)+...+1/n(n+1)=n/(n+1)

so far I have the base case= 1

Assume this is true for n=k

(1/2)+(1/6)+(1/12)+...+1/k(k+1)=k/(k+1)

now I want to assume this is true for n=k+1

(1/2)+(1/6)+(1/12)+...+1/(k+1)(k+2)=(k+1)/(k+2)

This is where I am stuck...am I placing (k+1) in the correct places?
 
Nov 2009
485
184
You have a little problem here:

now I want to assume this is true for n=k+1

(1/2)+(1/6)+(1/12)+...+1/(k+1)(k+2)=(k+1)/(k+2)
You shouldn't assume this. You need to show that this is true, based on the \(\displaystyle n=k\) case.

Let's just look at the left hand side and try to work our way to the right.

\(\displaystyle
\frac{1}{2}+\frac{1}{6}+\ldots +\frac{1}{k(k+1)}+\frac{1}{(k+1)(k+2)}
\)

Look at all of the terms except the last one. By the induction hypothesis, we can substitute them with \(\displaystyle \frac{k}{k+1}\) and receive

\(\displaystyle
\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}
\)

Just clean this up and you will get what you want.
 
Oct 2009
16
0
How do we get the k/(k+1) on the left hand side of the equation via the induction hypothesis? Do I have to change the right hand side at all or is it just (k+1)/(k+2)?
 
Nov 2009
485
184
By the induction hypothesis, you have

\(\displaystyle
\frac{1}{2}+\frac{1}{6}+\ldots +\frac{1}{k(k+1)}=\frac{k}{k+1}
\)

As I said earlier, you don't have a right hand side. You just start with
\(\displaystyle
\frac{1}{2}+\frac{1}{6}+\ldots +\frac{1}{k(k+1)}+\frac{1}{(k+1)(k+2)}
\) and hope that you can work your way over to \(\displaystyle \frac{k+1}{k+2}\).
 
Dec 2009
3,120
1,342
How do we get the k/(k+1) on the left hand side of the equation via the induction hypothesis? Do I have to change the right hand side at all or is it just (k+1)/(k+2)?
Hi baker11108,

P(k)

\(\displaystyle \frac{1}{2}+\frac{1}{6}+......+\frac{1}{k(k+1)}=\frac{k}{k+1}\)

P(k+1)

\(\displaystyle \frac{1}{2}+\frac{1}{6}+....+\frac{1}{(k+1)(k+2)}=\frac{k+1}{k+2}\)

You want to try to prove that the formula being true for n=k causes the formula to be true for n=k+1

Hence we write P(k+1) in terms of P(k) to see if there is a cause.

Therefore if the sum of the first k terms really is \(\displaystyle \frac{k}{k+1}\)

then the sum of k+1 terms is

\(\displaystyle \frac{1}{2}+\frac{1}{6}+......+\frac{1}{k(k+1)}+\frac{1}{(k+1)(k+2)}\)

will be \(\displaystyle \frac{k}{k+1}+\frac{1}{(k+1)(k+2)}\)

which is

\(\displaystyle \left(\frac{k+2}{k+2}\right)\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}\)

\(\displaystyle =\frac{k^2+2k+1}{(k+1)(k+2)}=\frac{(k+1)^2}{(k+1)(k+2)}=\frac{k+1}{k+2}\)

Since this is what you get when you replace k with k+1 in the RHS
it means that your hypothesis being true for some n=k
causes the hypothesis to be true for the next n=k+1.

Hence "true for n=1 causes it to be true for n=2 causes it to be true for n=3 causes......."