Proof by induction

Printable View

July 5th 2009, 03:23 AM
LHS

Proof by induction

http://img30.imageshack.us/img30/2584/imageskr.jpg

I know roughly what has to be done here, but for some reason its not working out like the other questions, any help would be greatly appreciated!
July 5th 2009, 03:32 AM
HallsofIvy

$T_n= \frac{1}{2}+ \frac{2}{3}+ \cdot\cdot\cdot+ \frac{n}{n+1}$
and you want to show that $T_n< n$ .

Okay, if n= 1, $T_n= \frac{1}{2}< 1$ .

Now suppose that, for some k, $T_k< k$ . Now $T_{k+1}= T_k+ \frac{k+1}{k+2}< k+ \frac{k+1}{k+2}$ . And you want to show that that is less than k+1.

Looks to me that you just need to show that $\frac{k+1}{k+2}< 1$ !
July 5th 2009, 03:43 AM
LHS

Ah I see, yes, it was at that stage I got confused.
I thought to prove it you would have to rearrange the RHS to show that the summation + the next term < k+1
Why do you need to show that (k+1)/(k+2) is less than one?
July 6th 2009, 07:55 PM
AlephZero

Here is the "rearrangement" version you wanted:

$T_{k+1}=T_k+\frac{k+1}{k+2}<k+\frac{k+1}{k+2}$

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

and you are done.

HallsofIvy's point was somewhat more elegant.
July 6th 2009, 08:17 PM
malaygoel

Quote:

Originally Posted by AlephZero

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

you made a mistake

$k^2+3k+1=(k+2)(k+1)$

which is not true.
July 6th 2009, 08:46 PM
AlephZero

Whoops, forgot to type a step. Here's the "rearrangment" proof:

$T_{k+1}=T_k+\frac{k+1}{k+2}<k+\frac{k+1}{k+2}$

$=\frac{k^2+3k+1}{k+2}<\frac{k^2+3k+2}{k+2}=\frac{( k+2)(k+1)}{k+2}=k+1.$

Thanks for pointing that out, malaygoel.
July 6th 2009, 09:16 PM
simplependulum

$T_n = \frac{1}{2} + \frac{2}{3} + ... + \frac{n}{n+1}$

$= 1 - \frac{1}{2} + 1 - \frac{1}{3} + 1 - ... + 1 \frac{1}{n+1}$

$= 1+1+1+1 +... - \frac{1}{2} - \frac{1}{3} - ... - \frac{1}{n+1}$

$= n - \sum_{k=2}^{n+1} \frac{1}{k} < n$

for $n \geq 1$
July 6th 2009, 10:13 PM
LHS

I think I see why that fraction has to be less than one. That right hand side should be k+1, or whenever you add the next term to the LHS you only add one to the RHS? So that fraction we gained from the LHS has to be less than 1 for the RHS to still be greater?
Thanks guys for your help!
July 7th 2009, 01:42 AM
Prove It

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

$= 1 - \frac{1}{k + 2} < 1$ .