How do you prove #1/(1*2)+1/(2*3)+...+1/(n(n+1)) = 1-1/(n+1)# by induction?

3 Answers
George C.
Dec 17, 2017

See explanation...

Explanation:

Let #P(n)# be the proposition:

#1/(1*2)+1/(2*3)+...+1/(n(n+1)) = 1-1/(n+1)#

Base case

Note that:

#1/(1*2) = 1/2 = 1-1/2 = 1-1/(1+1)#

So #P(1)# is true.

Induction step

Suppose #P(n)# is true.

Then:

#1/(1*2)+1/(2*3)+...+1/(n(n+1))+1/((n+1)(n+2)#

#=1-1/(n+1)+1/((n+1)(n+2))#

#=1-((n+2)/((n+1)(n+2))-1/((n+1)(n+2)))#

#=1-((n+2)-1)/((n+1)(n+2))#

#=1-(n+1)/((n+1)(n+2))#

#=1-1/(n+2)#

That is #P(n) => P(n+1)#

Conclusion

We have shown #P(1)# and #P(n)=>P(n+1)#.

So by induction #P(n)# holds for all #n >= 1#

Bisma J.
Dec 17, 2017

Show that it is true for #n = 1#, and show that if it is true for #n = k#, then it must also be true for #n = k + 1#, where you may use proof by contradiction.

Explanation:

In mathematical induction, there are two steps:
1. Show that it is true for the first term
2. Show that if it is true for a term #k#, then it must also be true for a term #k + 1# (by first assuming it is true for a term #k#).

Here is our current sequence:

#S_n = 1/(1 * 2) + 1/(2 * 3) + ... + 1/((n - 1)n) + 1/(n(n + 1))#
#= 1 - (1/(n + 1))#

Huh, this feels a bit wrong, there's a similar answered question, but it's not quite the same. Anyway, we should be able to rewrite this sum in terms of sigma:

#S_n = sum_(k = 1)^(n) (1/(n(n+1))) = 1 - (1 / (n + 1))#

The first step is to show that it is true for the first term. Here we go, #n = 1#:

#S_1 = (1/(1(1+1))) = 1 - (1 / (1 + 1))#

#S_1 = 1/2 = 1/2#

Nice! Turns out this was a different sum than what I thought. For the second step, assume that the sum is true for a constant, say, #m#:

#S_m = sum_(k = 1)^(m) (1/(m(m+1))) = 1 - (1 / (m + 1))#

And now, we need to prove that it is true for #S_(m + 1)#:

#S_(m + 1) = sum_(k = 1)^(m + 1) (1/((m + 1)(m+2))) = 1 - (1 / (m + 2))#

Let's start a little proof by contradiction: assume it isn't, then show that it must be.

#S_(m + 1) = sum_(k = 1)^(m + 1) (1/((m + 1)(m+2))) ne 1 - (1 / (m + 2))#

The thing is, though, is that #S_m# and #S_(m + 1)# share #S_m#. In other words:

#S_(m + 1) = 1/((m + 1)(m+2)) + sum_(k = 1)^(m) (1/(m(m+1)))#
#ne 1 - (1 / (m + 2))#

#S_m#, as we have assumed, is equal to #1 - (1 / (m + 1))#:

#S_(m + 1) = 1/((m + 1)(m+2)) + 1 - (1 / (m + 1))#
#ne 1 - (1 / (m + 2))#

At this point we can start ignoring #S_(m + 1)#.

#1/((m + 1)(m+2)) + 1 - (1 / (m + 1))#
#ne 1 - (1 / (m + 2))#

We can subtract both sides by #1#:

#1/((m + 1)(m+2)) - 1 / (m + 1) ne -1 / (m + 2)#

Interesting. Let's somehow make all of these fractions share the same denominator:

#1/((m + 1)(m+2)) - (m + 2) / ((m + 1)(m + 2))#
#ne -(m + 1) / ((m + 1)(m + 2))#

Combining those two fractions on the left hand side:

#(1 - (m + 2))/((m + 1)(m+2)) ne -(m + 1) / ((m + 1)(m + 2))#

Subtracting the fraction on the right hand side, by itself:

#(1 - (m + 2))/((m + 1)(m+2)) + (m + 1) / ((m + 1)(m + 2)) ne 0#

Let's simplify:

#(1 - (m + 2) + (m + 1))/((m + 1)(m+2)) ne 0#

#(1 - m - 2 + m + 1)/((m + 1)(m+2)) ne 0#

#0/((m + 1)(m+2)) ne 0#

#0 ne 0#

We have a contradiction! Therefore, it is also true that if the sequence is true for a term #m#, then it must also be true for a term #m + 1#, and our proof by mathematical induction (and contradiction) is complete.

Rhys
Dec 17, 2017

Proof via method of differences

Explanation:

I wanted to provide another approach to showing this is true:

We know #1/(1*2) + 1/(2*3) + ... + 1/(n(n+1)) #

# = sum_(r = 1) ^n 1/(r(r+1) ) #

Using partial fractions:

#=> 1/( r(r+1) ) = A/r + B/(r+1) #

# 1 = A(r+1) + Br #

Letting #r = 0 => A = 1 #

Letting #r = -1 => B = -1 #

#=> = sum_(r=1) ^n 1/r - 1/(r+1) #

#r =1 : 1/1 cancel(- 1/2) #

#r = 2: cancel( 1/2) cancel(- 1/3) #
.
.
.
#r = n-1: cancel(1/(n-1)) cancel(- 1/n)#
# r = n: cancel(1/n) - 1/(n+1) #

Hence using what is left:

#1/1 - 1/(n+1) #

#=> 1 - 1/(n+1) #

Related questions
Impact of this question
2598 views around the world
You can reuse this answer
Creative Commons License