Simple induction help

• Sep 28th 2008, 12:01 PM
Jones
Simple induction help
Hi,

I have a very simple induction problem that i'd like help solving.

Prove that for all positive Integers n, that :
$\sum_{k=1}^{n} \frac{1}{k(k+1)} = \frac{n}{(n+1)}$

I know that the first step is to replace n with n+1 but then what?

/Jones
• Sep 28th 2008, 12:07 PM
Moo
Hello,
Quote:

Originally Posted by Jones
Hi,

I have a very simple induction problem that i'd like help solving.

Prove that for all positive Integers n, that :
$\sum_{k=1}^{n} \frac{1}{k(k+1)} = \frac{n}{(n+1)}$

I know that the first step is to replace n with n+1 but then what?

/Jones

The first step is to prove it is true for n=1.
The second step is to state the inductive hypothesis, that is to say assuming that $\sum_{k=1}^n \frac{1}{k(k+1)}=\frac{n}{n+1}$

The third step is to prove that it is true if you "replace" n by n+1, that is to say $\sum_{k=1}^{n+1} \frac{1}{k(k+1)}=\frac{n+1}{n+2}$ :
$\sum_{k=1}^{n+1} \frac{1}{k(k+1)}=\left(\sum_{k=1}^n \frac{1}{k(k+1)}\right)+\frac{1}{(n+1)(n+2)}$

Now, use the inductive hypothesis to substitute $\sum_{k=1}^n \frac{1}{k(k+1)}$

----------------------------------------------
Another way would have been to note that $\frac{1}{k(k+1)}=\frac 1k-\frac 1{k+1}$ and use telescoping series (Telescoping series - Wikipedia, the free encyclopedia)
• Sep 29th 2008, 02:09 AM
Jones
Hmm, how do you mean?

isn't it just a simple matter of:

$\sum_{k=1}^{n+1} \frac {1}{(k+1)(k+2)} = \frac{n+1}{n+2}$
• Sep 29th 2008, 06:29 AM
Showcase_22
I'd do it like this:

Proving it true for n=1:

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

$\frac {1}{1+1}=\frac{1}{2}$

True for n=1.

That's the easy bit. I'll leave it up to you to do the rest.