Register to reply

Prove by Induction.

by PFStudent
Tags: induction, prove
Share this thread:
PFStudent
#1
Jan29-08, 01:25 PM
P: 171
1. The problem statement, all variables and given/known data
1.1.2

Write,

[tex]
{\frac{1}{1\cdot2}} + {\frac{1}{2\cdot3}} + {\frac{1}{3\cdot4}} + . . . + {\frac{1}{99\cdot100}}
[/tex]

as a fraction in lowest terms.

3. The attempt at a solution

Rewriting the problem as a summation,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\frac{1}{1\cdot2}} + {\frac{1}{2\cdot3}} + {\frac{1}{3\cdot4}} + . . . + {\frac{1}{n\cdot(n+1)}}
[/tex]

Then considering the first few terms,

[tex]
{\frac{1}{1\cdot2}} = \frac{1}{2}
[/tex]

[tex]
{\frac{1}{1\cdot2}} + {\frac{1}{2\cdot3}} = \frac{2}{3}
[/tex]

[tex]
{\frac{1}{1\cdot2}} + {\frac{1}{2\cdot3}} + {\frac{1}{3\cdot4}} = \frac{3}{4}
[/tex]

This leads to the conjecture that,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\frac{n}{n+1}}
[/tex]

How would I prove the above by induction?

-PFStudent
Phys.Org News Partner Science news on Phys.org
Bees able to spot which flowers offer best rewards before landing
Classic Lewis Carroll character inspires new ecological model
When cooperation counts: Researchers find sperm benefit from grouping together in mice
rock.freak667
#2
Jan29-08, 01:38 PM
HW Helper
P: 6,205
Assume the statement is true for n=N, then prove true for n=N+1

EDIT:

Your formula should be

[tex]\sum_{i=1} ^{n} \frac{1}{i(i+1)}=\frac{n}{n+1}[/tex]
jdavel
#3
Jan29-08, 01:53 PM
P: 618
the last term in your sum (where i = n) is going to be 1/n(n+1). if you take the sum one further (to i = n+1) what will the last term be now?

PFStudent
#4
Jan29-08, 02:12 PM
P: 171
Prove by Induction.

Hey,

Thanks for the reply rock.freak667 and jdavel.

Assume,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\frac{n}{n+1}}
[/tex]

is true for k. That is,

[tex]
{{\sum_{i = 1}^{k}}{\frac{1}{i(i+1)}}} = {\frac{k}{k+1}}
[/tex]


Then to prove it is true for k+1, consider the following,

[tex]
{{\sum_{i = 1}^{k+1}}{\frac{1}{i(i+1)}}} = {{\sum_{i = 1}^{k}}{\frac{1}{i(i+1)}}} + {\frac{1}{k+1((k+1)+1)}}
[/tex]

Which reduces to,

[tex]
{{\sum_{i = 1}^{k+1}}{\frac{1}{i(i+1)}}} = {\frac{k}{k+1}} + {\frac{1}{{k^2}+3k+1)}}
[/tex]

However, how do I know the above is true?

In other words how do I know if the proof by induction actually proved it?

Thanks,

-PFStudent
rock.freak667
#5
Jan29-08, 02:22 PM
HW Helper
P: 6,205
Quote Quote by PFStudent View Post
In other words how do I know if the proof by induction actually proved it?

Well you basically want to get

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\frac{(k+1)}{(k+1)+1}}

[/tex]


basically the sum is the same but instead of "n" put k+1
jdavel
#6
Jan29-08, 03:25 PM
P: 618
you're missing a pair of parenetheses in your 3rd equation that's leading to an error in the last term of your 4th equation. what should that last term be?
PFStudent
#7
Jan29-08, 04:51 PM
P: 171
Hey,

Consider the following,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\frac{n}{n+1}}
[/tex]

Assume it is true for k,

[tex]
{{\sum_{i = 1}^{k}}{\frac{1}{i(i+1)}}} = {\frac{k}{k+1}}
[/tex]

Now, if it is true for k+1 the result expected is,

[tex]
{{\sum_{i = 1}^{k+1}}{\frac{1}{i(i+1)}}} = {\frac{k+1}{(k+1)+1}}
[/tex]

[tex]
{{\sum_{i = 1}^{k+1}}{\frac{1}{i(i+1)}}} = {\frac{k+1}{k+2}}
[/tex]

Then to prove that, consider the following,

[tex]
{{\sum_{i = 1}^{k+1}}{\frac{1}{i(i+1)}}} = {{\sum_{i = 1}^{k}}{\frac{1}{i(i+1)}}} + {\frac{1}{(k+1)((k+1)+1)}}
[/tex]

[tex]
{{\sum_{i = 1}^{k+1}}{\frac{1}{i(i+1)}}} = {\left({\frac{k}{k+1}}\right)} + {\frac{1}{(k+1)(k+2)}}
[/tex]

[tex]
{{\sum_{i = 1}^{k+1}}{\frac{1}{i(i+1)}}} = {{\frac{k(k+2)}{(k+1)(k+2)}}} + {\frac{1}{(k+1)(k+2)}}
[/tex]

Which reduces to,

[tex]
{{\sum_{i = 1}^{k+1}}{\frac{1}{i(i+1)}}} = {\frac{(k+1)(k+1)}{(k+1)(k+2)}}
[/tex]

[tex]
{{\sum_{i = 1}^{k+1}}{\frac{1}{i(i+1)}}} = {\frac{k+1}{k+2}}
[/tex]

Proof.

Thanks,

-PFStudent
HallsofIvy
#8
Jan30-08, 07:30 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,348
Were you required to use induction?

Since
[tex]\frac{1}{n(n+1)}= \frac{1}{n}- \frac{1}{n+1}[/tex]
that is a "telescoping" series and the sum is immediate.
PFStudent
#9
Jan30-08, 12:07 PM
P: 171
Hey,

Quote Quote by HallsofIvy View Post
Were you required to use induction?

Since
[tex]\frac{1}{n(n+1)}= \frac{1}{n}- \frac{1}{n+1}[/tex]
that is a "telescoping" series and the sum is immediate.
Could I have proved,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\frac{n}{n+1}}
[/tex]

by showing that it is a telescoping series? If so, how?

Thanks,

-PFStudent
HallsofIvy
#10
Jan30-08, 02:12 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,348
[tex]\sum_{i=1}^{100} \frac{1}{i(i+1}= \frac{1}{1\cdot2}} + {\frac{1}{2\cdot3}} + {\frac{1}{3\cdot4}} + . . . + {\frac{1}{99\cdot100}[/tex]
[tex]= (\frac{1}{1}- \frac{1}{2})+ (\frac{1}{2}-\frac{1}{3})+ (\frac{1}{3}-\frac{1}{4})+ \cdot\cdot\cdot+ (\frac{1}{99}- \frac{1}{100})[/tex]
The last fraction in each pair cancels the first fraction in the next pair (except of course in the last pair). Every fraction except the first and last cancel so the sum is
[tex]\frac{1}{1}- \frac{1}{100}= \frac{100-1}{100}= \frac{99}{100}[/tex]

More generally,
[tex]\sum_{i= 1}^n \frac{1}{i(i+1)}= \frac{1}{1}- \frac{1}{n+1}= \frac{n+1-1}{n+1}= \frac{n}{n+1}[/tex]
PFStudent
#11
Feb4-08, 12:22 PM
P: 171
Hey,

Quote Quote by HallsofIvy View Post
[tex]
\sum_{i=1}^{100} \frac{1}{i(i+1}= \frac{1}{1\cdot2}} + {\frac{1}{2\cdot3}} + {\frac{1}{3\cdot4}} + . . . + {\frac{1}{99\cdot100} = (\frac{1}{1}- \frac{1}{2})+ (\frac{1}{2}-\frac{1}{3})+ (\frac{1}{3}-\frac{1}{4})+ \cdot\cdot\cdot+ (\frac{1}{99}- \frac{1}{100})
[/tex]

The last fraction in each pair cancels the first fraction in the next pair (except of course in the last pair). Every fraction except the first and last cancel so the sum is
[tex]\frac{1}{1}- \frac{1}{100}= \frac{100-1}{100}= \frac{99}{100}[/tex]

More generally,
[tex]\sum_{i= 1}^n \frac{1}{i(i+1)}= \frac{1}{1}- \frac{1}{n+1}= \frac{n+1-1}{n+1}= \frac{n}{n+1}[/tex]
Thanks HallsofIvy for showing how it could have been proved by showing it was a telescoping sum.

However, how would you know that the individual sums can be rewritten as the sum or difference of two fractions. In other words, how did you figure out the following,

[tex]
\sum_{i=1}^{100} \frac{1}{i(i+1}= \frac{1}{1\cdot2}} + {\frac{1}{2\cdot3}} + {\frac{1}{3\cdot4}} + . . . + {\frac{1}{99\cdot100} = \left(\frac{1}{1}-\frac{1}{2}\right) + \left(\frac{1}{2}-\frac{1}{3}\right)+ \left(\frac{1}{3}-\frac{1}{4}\right) + \cdot\cdot\cdot + \left(\frac{1}{99}- \frac{1}{100}\right)
[/tex]

That is, how did you figure out that,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\left({{\frac{A_{1}}{1}}-{\frac{B_{1}}{2}}}\right)} + {\left({{\frac{A_{2}}{2}}-{\frac{B_{2}}{3}}}\right)} +. . . + {\left({{\frac{A_{n}}{n}}-{\frac{B_{n}}{n+1}}}\right)}
[/tex]

Additionally, is finding the above the same as using the technique of partial fractions?

Also, what is the general way of finding [tex]A[/tex] and [tex]C[/tex] for the following (where: [tex]B, D, E, and{\textcolor[rgb]{1.00,1.00,1.00}{.}}F[/tex]; are all given),

[tex]
{\frac{E}{F}} = {{{\frac{A}{B}}\pm{\frac{C}{D}}}}
[/tex]

Where it can be shown that,

[tex]
{E} = {AD \pm BC}
[/tex]

[tex]
{F} = {BD}
[/tex]

Which is the same as,

[tex]
{\frac{E}{F}} = {\frac{AD \pm BC}{BD}}
[/tex]

Thanks,

-PFStudent
PFStudent
#12
Feb6-08, 12:48 PM
P: 171
Hey,

I was looking over this and realized that the following,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\left({{\frac{A_{1}}{1}}-{\frac{B_{1}}{2}}}\right)} + {\left({{\frac{A_{2}}{2}}-{\frac{B_{2}}{3}}}\right)} +. . . + {\left({{\frac{A_{n}}{n}}-{\frac{B_{n}}{n+1}}}\right)}
[/tex]

Was better written as,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\left({{\frac{C_{1}}{1}}-{\frac{C_{2}}{2}}}\right)} + {\left({{\frac{C_{2}}{2}}-{\frac{C_{3}}{3}}}\right)} + {\cdot} {\cdot} {\cdot} + {\left({{\frac{C_{n-1}}{n-1}}-{\frac{C_{n}}{n}}}\right)} + {\left({{\frac{C_{n}}{n}}-{\frac{C_{n+1}}{n+1}}}\right)}
[/tex]

But, I'm still having some trouble figuring how would one decipher what the constants "C" must be.

Thanks,

-PFStudent
rock.freak667
#13
Feb6-08, 05:05 PM
HW Helper
P: 6,205
[tex]\sum_{n=1} ^{N} \frac{1}{n(n+1)} \equiv \sum_{n=1} ^{N} (\frac{1}{n}-\frac{1}{n+1})[/tex]

Use partial fractions on 1/n(n+1)


[tex]\sum_{n=1} ^{N} \frac{1}{n}-\frac{1}{n+1}[/tex]

then input n=1,2,3,...,N-2,N-1,N. then add them all up.
PFStudent
#14
Feb6-08, 06:50 PM
P: 171
Hey,

Quote Quote by rock.freak667 View Post
[tex]\sum_{n=1} ^{N} \frac{1}{n(n+1)} \equiv \sum_{n=1} ^{N} (\frac{1}{n}-\frac{1}{n+1})[/tex]

Use partial fractions on 1/n(n+1)


[tex]\sum_{n=1} ^{N} \frac{1}{n}-\frac{1}{n+1}[/tex]

then input n=1,2,3,...,N-2,N-1,N. then add them all up.
I see that however, how would you have figured out what the constants for the partial fractions of,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}}
[/tex]

would be?

In other words, how would you have solved the following,

[tex]{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\left({{\frac{C_{1}}{1}}-{\frac{C_{2}}{2}}}\right)} + {\left({{\frac{C_{2}}{2}}-{\frac{C_{3}}{3}}}\right)} + {\cdot} {\cdot} {\cdot} + {\left({{\frac{C_{n-1}}{n-1}}-{\frac{C_{n}}{n}}}\right)} + {\left({{\frac{C_{n}}{n}}-{\frac{C_{n+1}}{n+1}}}\right)}[/tex]


for: [tex]C_{1}, C_{2}, C_{3},..., C_{n-1}, C_{n}[/tex]?

That is where I am stuck.

Thanks,

-PFStudent
rock.freak667
#15
Feb6-08, 07:17 PM
HW Helper
P: 6,205
I don't think you need to do all of that.
PFStudent
#16
Feb11-08, 03:15 PM
P: 171
Hey,

Quote Quote by rock.freak667 View Post
I don't think you need to do all of that.
Thanks for the reply, rock.freak667. Your right I did not need to prove that it is a telescoping sum.

However, I still would like to know how would one have realized that,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}}
[/tex]

is a telescoping sum?

Further after the above realization one would have had to solve for the constants: [tex]C_{1}, C_{2}, C_{3},..., C_{n-1}, C_{n}[/tex]; for the following,

[tex]
{{\sum_{i = 1}^{n}}{\frac{1}{i(i+1)}}} = {\left({{\frac{C_{1}}{1}}-{\frac{C_{2}}{2}}}\right)} + {\left({{\frac{C_{2}}{2}}-{\frac{C_{3}}{3}}}\right)} + {\cdot} {\cdot} {\cdot} + {\left({{\frac{C_{n-1}}{n-1}}-{\frac{C_{n}}{n}}}\right)} + {\left({{\frac{C_{n}}{n}}-{\frac{C_{n+1}}{n+1}}}\right)}
[/tex]

And that is, what I wanted to know. How do you do that?

Thanks,

-PFStudent


Register to reply

Related Discussions
Prove the expressions by induction method Precalculus Mathematics Homework 3
Prove 1/(z-1) by induction Calculus & Beyond Homework 2
Induction to prove an inequality Calculus & Beyond Homework 4
Prove by induction? Set Theory, Logic, Probability, Statistics 1
Prove by Mathematical induction , please help Math & Science Software 15