# Induction Problem

• Feb 8th 2009, 07:19 AM
vexiked
Induction Problem
Hi I am having alot of trouble with this induction question. Any help would be much appreciated!

Find a formula for 1/1*2 + 1/2*3 + 1/n*(n+1) and prove by induction.
• Feb 8th 2009, 07:24 AM
running-gag
Hi

To find the formula you can compute the first terms of the series.
Another way is to use
$\displaystyle \frac{1}{n(n+1)}=\frac{1}{n} - \frac{1}{n+1}$
• Feb 8th 2009, 07:33 AM
vexiked
So could the formula be
$\displaystyle \frac{1}{n} - \frac{1}{n+1}$ or is this just another way used to solve ?
I can calculate the first few terms but I am not able to find a formula.
• Feb 8th 2009, 07:35 AM
running-gag
Quote:

Originally Posted by vexiked
So could the formula be
$\displaystyle \frac{1}{n} - \frac{1}{n+1}$ or is this just another way used to solve ?

This is just a way to solve

Quote:

Originally Posted by vexiked
I can calculate the first few terms but I am not able to find a formula.

You should : what are your results ?
• Feb 8th 2009, 07:38 AM
Jester
Quote:

Originally Posted by vexiked
Hi I am having alot of trouble with this induction question. Any help would be much appreciated!

Find a formula for 1/1*2 + 1/2*3 + 1/n*(n+1) and prove by induction.

Here's some details. You'll notice that each term can be split up

$\displaystyle \frac{1}{1 \cdot 2} = \frac{1}{1} - \frac{1}{2},\;\;\;\;\;\frac{1}{2 \cdot 3} = \frac{1}{2} - \frac{1}{3},\;\;\;\;\;\frac{1}{3 \cdot 4} = \frac{1}{3} - \frac{1}{4}$
$\displaystyle \frac{1}{n \cdot (n+1)} = \frac{1}{n} - \frac{1}{n+1}$
Then when you add them up all the terms cancel except the first and last, so

$\displaystyle S_n = 1 - \frac{1}{n+1} = \frac{n}{n+1}$

For the induction part, it true for the first few, assume true for $\displaystyle n = k$

so

$\displaystyle S_k = \frac{k}{k+1}$

Prove true for $\displaystyle n = k+1$, i.e. $\displaystyle S_{k+1} = \frac{k+1}{k+2}$
so

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

$\displaystyle S_{k+1} = \frac{k+1}{k+2}$
so it must be true for all n.
• Feb 8th 2009, 07:51 AM
vexiked
Could you verify that I am on the right track for another?

Prove that 3^n < n! if n is an integer greater than 6..

- Base case 3^7 = 2187 and 7! = 5040
- Inductive
- Assume for p(k) show for p(k+1)
- 3^K+1 < K+1!
- 3^k + 3^k < K + 1!

I am stuck on this part now.
• Feb 8th 2009, 08:25 AM
You should have an initial condition that n>2

$\displaystyle 3^{n} < n!$
Let the following is true
$\displaystyle P(k) = 3^{k}<k!$
To prove
$\displaystyle P(k+1) = 3^{k+1}<(k+1)!$
Therefore

$\displaystyle 3^{k}\times 3 < k!(k+1)$
Putting k! instead of 3^k we get something greater hence if we can prove that this greater thing less than our RHS
then we have done it
$\displaystyle 3*k! < k! (k+1)$
For $\displaystyle k > 2$

Thus $\displaystyle 3<(k+1)!$
and $\displaystyle 3k!<(k+1)!$
• Apr 19th 2009, 08:13 PM
vexiked
Quote:

Originally Posted by running-gag
Hi

To find the formula you can compute the first terms of the series.
Another way is to use
$\displaystyle \frac{1}{n(n+1)}=\frac{1}{n} - \frac{1}{n+1}$

Could someone show me how to compute the first terms of the series to get the formula? Im in dire need, have an exam tomorrow and I have had no luck figuring out the steps.
• Apr 20th 2009, 08:06 AM
running-gag