Proof by induction

**LHS** · July 5th 2009, 03:23 AM

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!

**HallsofIvy** · July 5th 2009, 03:32 AM

$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$ !

**LHS** · July 5th 2009, 03:43 AM

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?

**AlephZero** · July 6th 2009, 07:55 PM

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.

**malaygoel** · July 6th 2009, 08:17 PM

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.

**AlephZero** · July 6th 2009, 08:46 PM

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.

**simplependulum** · July 6th 2009, 09:16 PM

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

**LHS** · July 6th 2009, 10:13 PM

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!

**Prove It** · July 7th 2009, 01:42 AM

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

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

Thread: Proof by induction

LinkBack

Thread Tools

Display

Proof by induction

Similar Math Help Forum Discussions

Proof by Induction

Proof by Induction

Mathemtical Induction Proof (Stuck on induction)

Proof by Induction??

Proof with algebra, and proof by induction (problems)

Search Tags