Proof Question: Using Mathematical Induction

[Lococard]

1. The problem statement, all variables and given/known data
Prove that, for all integers n =>1

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


2. Relevant equations

I am a little stuck on this question. :|

3. The attempt at a solution

[Gib Z]

Well, the LHS can be expressed as

\sum_{k=1}^n \frac{1}{k(k+1)}. Use partial fractions on that expression, you should get a telescoping series.

[Lococard]

Anyone got any ideas with this problem?

I cant find any notes regarding a similar question.

[HallsofIvy]

What was wrong with Gib Z's suggestion?

[Lococard]

We haven't been taught that.

Im a little unsure what he means as well.

Could you possibly give more help?

Sorry if im a pain.

[Schrodinger's Dog]

We haven't been taught that.

Im a little unsure what he means as well.

Could you possibly give more help?

Sorry if im a pain.

Putting it in partial fractions gives.

\frac{1}{k(k+1)}=\frac{1}{k}\cdot\frac{1}{(k+1)} or \equiv?

Do you mean you don't understand summation?

All that expression is is your first expression for any given value of n. It's essentially the same thing.

[tiny-tim]

Prove that, for all integers n =>1

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

Hi Lococard! :smile:

For induction proofs, it often helps to give a name to the sum (if the question hasn't already doe so).

In this case, use the name a_n+1:

a_{n+1}\,=\,\frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4}... + \frac{1}{n+1}

Then what you have to prove is that, assuming that:
a_n = 1 - 1/n,
then:
a_n+1 = 1 - 1/(n+1).

You see how that makes the problem easier? :smile:

[Lococard]

How would i put it into a partial fraction?

[Schrodinger's Dog]

How would i put it into a partial fraction?

Well I gave one partial fraction that is in fact equivalent to your original equation. Put that equation into your calculator, plug in some numbers and then use the original equation, if they are equivalent it follows that both equations are different versions of the same partial fraction. Of course you could do this algebraically too, but I'll leave that to you. Tiny-tim has given you a nice hint there.

[Lococard]

I've done them both on paper and i got the same result.

Do i then add a_n+1 to the equation and get the formula in the lowest form?

[tiny-tim]

I've done them both on paper and i got the same result.

Do i then add a_n+1 to the equation and get the formula in the lowest form?

Hi Lococard! :smile:

I'm not sure what you mean. :confused:

Just say a_n+1 - a_n = 1/n(n+1);

then, from the induction assumption, a_n = 1 - 1/n = (n - 1)/n.

So a_n+1 = a_n + 1/n(n+1) = (n - 1)/n + 1/n(n+1) = (n^2 - 1)/n(n+1) + 1/n(n+1) = … ? :smile:

Is that what you meant?

[Lococard]

Alright, i got some more info on the question.

It seems that:

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


But. The number after \frac{1}{n+1} would be \frac{(n+1)}{(n+1)(n+2)}

So.

1 - \frac{1}{(n+1)} + \frac{1}{(n+1)(n+2)}

= 1 - ??

Would would i simplify the rest of it?

[tiny-tim]

ah! … you have a misprint …

it should be \frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4}... + \frac{1}{n*(n+1)}\,=\,1-\frac{1}{n+1}\,.

Does that look better? :smile:

[Lococard]

Oh whoops. Yeah thats what i meant

[Lococard]

How would i do the next part?

[tiny-tim]

1 - \frac{1}{(n+1)} + \frac{1}{(n+1)(n+2)}

= \frac{n+1}{(n+1)} - \frac{1}{(n+1)} + \frac{1}{(n+1)(n+2)}

= … ? :smile:

(btw, wouldn't it have been easier to work out if you'd "gone down one", and writen:
1 - \frac{1}{n} + \frac{1}{n(n+1)} ?)

[Lococard]

did you just substitute the 1 for a \frac{n+1}{n+1}?


Im really stuck on simplifying the RHS.

[tiny-tim]

did you just substitute the 1 for a \frac{n+1}{n+1}?

Yes!

Tell me what bothers you about that …

Anyway, the next step is to use

\frac{n+1}{(n+1)} - \frac{1}{(n+1)}\,=\,\frac{n}{(n+1)}\,.

And then … ? :smile:

[Lococard]

How did you do that step?

Now im really lost.


The lecturer suggested i get the equation to = 1 - \frac{1}{n+2}

[tiny-tim]

ah!

You don't like polynomial fractions, do you?

They're just like ordinary fractions …

If you had 1 - 15/17, you'd say that's 17/17 - 15/17, = 2/17.

Similarly, if you had 1 - 15/(n+17), you'd say that's (n+17)/(n+17) - 15/(n+17), = (n+17-15)/(n+17) = (n+2)/(n+17).

You gotta practise this, and become happy with it!

So … 1 - 1/(n+1) = … ? :smile:

[Lococard]

Ah.

1 - \frac{1}{N+1} = \frac{n+1}{n+1} - \frac{1}{n+1} = \frac{n}{n+1}


How did you get:

\frac{n+1}{(n+1)} - \frac{1}{(n+1)} + \frac{1}{(n+1)(n+2)}

to get to:


\frac{n+1}{(n+1)} - \frac{1}{(n+1)}\,=\,\frac{n}{(n+1)}\,.

[tiny-tim]

1 - \frac{1}{N+1} = \frac{n+1}{n+1} - \frac{1}{n+1} = \frac{n}{n+1}

Yes! :smile:

How did you get:

\frac{n+1}{(n+1)} - \frac{1}{(n+1)} + \frac{1}{(n+1)(n+2)}

to get to:

\frac{n+1}{(n+1)} - \frac{1}{(n+1)}\,=\,\frac{n}{(n+1)}\,.

I didn't - I was just doing the first two terms.

Now, what is

\frac{n}{(n+1)} + \frac{1}{(n+1)(n+2)} ? :smile:

[Lococard]

That was the bit i was stuck on.

[tiny-tim]

ok, well you do the same thing:

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

And then … ? :smile:

[Lococard]

how do you transfer \frac{1}{(n+1)(n+2)} from the LHS to the RHS?

[tiny-tim]

I don't follow :confused:

From the LHS to the RHS of what?

[Lococard]

\frac{n}{(n+1)} + \frac{1}{(n+1)(n+2)} = 0

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


Did you swap \frac{1}{(n+1)(n+2)} to the other side of the equals sign?

How did you simplify did you get n(n+2)/(n+1)(n+2). Is it all on the LHS of the equals sign, or did you swap some of it to the right side?

[tiny-tim]

Sorry, you've completely lost me:
\frac{n}{(n+1)} + \frac{1}{(n+1)(n+2)} = 0

Where did the "= 0" come from? :confused:

There's no 0 in this.
Did you swap \frac{1}{(n+1)(n+2)} to the other side of the equals sign?

How did you simplify did you get n(n+2)/(n+1)(n+2). Is it all on the LHS of the equals sign, or did you swap some of it to the right side?

I just did: \frac{n}{(n+1)}\,=\,\frac{n}{(n+1)}\,\frac{(n+2)}{ (n+2)}\,=\,\frac{n(n+2)}{(n+1)(n+2)}\,.

That was so that I could then add it to the \frac{1}{(n+1)(n+2)} , giving … ? :smile:

[Lococard2]

\frac{n(n+2)}{(n+1)(n+2)}


is that right?

Would i then expand:

\frac{n^2+2n}{n^2+3n+2}

then after cancelling:

\frac{1}{(n+2)}

[tiny-tim]

\frac{n(n+2)}{(n+1)(n+2)}

is that right?

Yes! :smile:
Would i then expand:

\frac{n^2+2n}{n^2+3n+2}

Noooo … never expand the bottom !!!! :rolleyes:
then after cancelling:

\frac{1}{(n+2)}

Cancelling what? :confused:

(And how did you get that?)

The whole plan was to add 1/(n+1)(n+2) to it first … then you can try cancelling. :smile:

[Lococard2]

So, what i need to do is:

\frac{n(n+2)}{(n+1)(n+2)} + \frac{1}{(n+1(n+2)}

Doesnt that just equal:

\frac{n(n+2)}{(n+1)(n+2)}?

[tiny-tim]

So, what i need to do is:

\frac{n(n+2)}{(n+1)(n+2)} + \frac{1}{(n+1(n+2)}

Doesnt that just equal:

\frac{n(n+2)}{(n+1)(n+2)}?

Hey … what happened to the original Lococard? :confused:

I liked him!

:redface: erm … just read what you've written … :redface:

[Lococard]

haha, Sorry i lost my password and this connection doesnt allow gmail.com to load.

But im back now.

\frac{n(n+2)+1}{(n+1)(n+2)}

And from then i simplfy it?

[tiny-tim]

haha, Sorry i lost my password and this connection doesnt allow gmail.com to load.

But im back now.

I can tell the difference! :biggrin:
\frac{n(n+2)+1}{(n+1)(n+2)}

And from then i simplfy it?

Yes! :smile:

[Lococard]

So that is the same as:

\frac{(n+1)(n+1)}{(n+1)(n+2)}?

yes? no?

Now im not sure what to do :S

[tiny-tim]

So that is the same as:

\frac{(n+1)(n+1)}{(n+1)(n+2)}?

yes? no?

Yes! :smile:

(You knew that, didn't you?)
Now im not sure what to do :S

You really don't dig polynomial fractions, do you? :frown:

It's the same as \frac{(n+1)}{(n+1)}\,\frac{(n+1)}{(n+2)} , which is … ? :smile:

[Lococard]

Im really not sure.

You can cancel the (n+1) / (n+1)


Leaving (n+1) / (n+2)?



Im a little confused as the teacher suggested that i work my way to get 1 - [1 / (n+2)]

[tiny-tim]

You can cancel the (n+1) / (n+1)

Leaving (n+1) / (n+2)?

Yes! :smile:
Im a little confused as the teacher suggested that i work my way to get 1 - [1 / (n+2)]

Well, maybe teacher is right …

What is 1 - [1 / (n+2)] ?

Hint: 1 = … ? :smile:

[Lococard]

(n+2) / (n+2) - [1/(n+2)]?

= [(n+2) - 1] / (n+2)?

[tiny-tim]

Yes!

= … ? :smile:

[tiny-tim]

= \frac{(n+2) - 1} {(n+2)}? = 1-\frac{1}{n+1} \equiv \sum_{k=1}^n \frac{1}{k(k+1)}

erm …
:redface: … êtes-vous sûr …? :redface:

[Schrodinger's Dog]

erm …
:redface: … êtes-vous sûr …? :redface:

Which of those equals the last one, I left the question marks in there for a good reason, writing which of these is correct in latex gets messy, Ie ?=. The point is that one of those = a third, or the summation given at the beginning of the thread with a telescoping series.

Ie you have your answer. Et voila...

Since obviously some people found this confusing I've edited it to clear that up.

I kept putting \neq in then removing it then putting it in again before I decided it looks better with the question marks. :smile:

If you don't believe me ask a mentor if I edited it about 219283927^34839 times. :tongue:


EDIT: Actually sod it I might as well delete it, as it only makes sense, if you take on board the post about 1/k(k+1) being equivalent to the LHS. So nm.

I was trying to helpfully point out that what gib7 said was the same as what you eventually end up with, but it came out completely wrong.