Proof by Induction

  • Thread starter Oriako
  • Start date
  • #1
107
1

Homework Statement


For each positive integer n, let [tex]S_{n} = \frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} + ... + \frac{1}{(2n-1)2n}.[/tex]
(a) Calculate [tex]S_{1}, S_{2}, S_{3}[/tex]. Then use this data to guess a simple formula for [tex]S_{n}[/tex].
(b) Prove your guess in part (a) by mathematical induction
(c) Use Result 6.6 on page 136 to give another proof of your guess
(d) Prove that [tex]\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}[/tex] for all positive real numbers k. Use this to give yet another proof of your guess in part (a). This method of proof is called telescoping.


Homework Equations


Result 6.6: For every positive integer n:
[tex]\frac{1}{(2)(3)} + \frac{1}{(3)(4)} + ... + \frac{1}{(n+1)(n+2)} = \frac{n}{2n+4}.[/tex]


The Attempt at a Solution


Part a)
Since [tex]S_{1} = \frac{1}{2}, S_{2} = \frac{1}{4}, S_{3} = \frac{1}{6}[/tex], a good guess would be that [tex]S_{n} = \frac{1}{2n}[/tex].

Part b)
For n=1, [tex]\frac{1}{(2n-1)2n}=\frac{1}{(2(1)-1)2(1)}=\frac{1}{2}[/tex], so the entire sum is given by [tex]\frac{1}{n(n+1)} =\frac{1}{(1)((1)+1)} = \frac{1}{2}[/tex]. Thus, [tex]S_{n} = \frac{1}{2n}[/tex] is true for n=1. By induction, let k be an arbitrary integer and assume that [tex]\frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} + ... + \frac{1}{(2k-1)2k} = \frac{1}{2k}[/tex]. We want to prove that [tex]\frac{1}{(k+1)((k+1)+1)} + \frac{1}{((k+1)+1)((k+1)+2)} + ... + \frac{1}{(2(k+1)-1)(2(k+1))} = \frac{1}{2(k+1)}[/tex], which when simplified gives: [tex]\frac{1}{(k+1)(k+2)} + \frac{1}{(k+2)(k+3)} + ... + \frac{1}{(2k+1)(2k+2)} = \frac{1}{2(k+1)}[/tex].

I don't know where to go from here on (b) and I have no idea how Result 6.6 could help prove the result in a different way, and I'm completely lost on (d) as well. If anyone could help me out that would be massively appreciated, I've been spending hours trying to figure this out. I've run into tons of dead ends and what I've typed up here is the only thing that I know is for sure correct.

Thanks!
 

Answers and Replies

  • #2
ehild
Homework Helper
15,543
1,913
Assume that the sum is 1/(2k) for n=k, that is

[tex]S_k=\frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} + ... + \frac{1}{(2k-1)2k} = \frac{1}{2k}[/tex]

Compare it with the sum for n=k+1:

[tex]S_{k+1}=\frac{1}{(k+1)(k+2)} + \frac{1}{(k+2)(k+3)} + ... +\frac{1}{(2k)(2k+1)} +\frac{1}{(2k+1)(2k+2)} = \frac{1}{2(k+1)} [/tex]
If you subtract 1/(k(k+1)) and add 1/((2k)(2k+1))+1/((2k+1)(2k+2)) to both sides of the sum Sk you get Sk+1.

So [tex]S_k-\frac{1}{k(k+1)}+\frac{1}{(2k)(2k+1)} +\frac{1}{(2k+1)(2k+2)}=S_{k+1}[/tex]

Substitute Sk=1/(2k) and simplify.

ehild
 
Last edited:
  • #3
107
1
Thank you for the response!

I already tried what you suggested and got stuck so I thought it was an incorrect way to do it.
From what you suggest, I get

[tex]\frac{1}{2k} - \frac{1}{k(k+1)} + \frac{1}{(2k+1)(2k+2)} = \frac{(k-1)(2k+1)(2k+2) + (2k^2 + 2k)}{(2k^2 + 2k)(2k+1)(2k+2)}[/tex] And I am now stuck, I tried typing in the result into Wolframalpha and nothing simpler was given. I'm not sure how this is supposed to simplify to [tex]\frac{1}{2(k+1)}[/tex]

Also, I haven't made any progress on part (c) or (d) so even a hint if you have some ideas for those ones would be really helpful!
 
  • #4
ehild
Homework Helper
15,543
1,913
Sorry, I left out a term.... I edited my previous post. So the correct formula is

[tex]\frac{1}{2k}-\frac{1}{k(k+1)}+\frac{1}{(2k)(2k+1)} +\frac{1}{(2k+1)(2k+2)}=S_{k+1}[/tex]

The common denominator is 2k(k+1)(2k+1).

[tex]\frac{(k+1)(2k+1)-2(2k+1)+k+1+k}{2k(k+1)(2k+1)}=S_{k+1}[/tex]


ehild
 
  • #5
107
1
Okay, thank you very much. So I think I have a final proof for that part that is correct!

Now, would it be possible for you to help me with part (c)? This is what I've got so far.

Based off of the sum and Result 6.6, I can say that:

[tex]S_{n} = \sum\limits_{k=n}^{2n-2} \frac{1}{(k+1)(k+2)} = \frac{1}{2n}, T_{n} = \sum\limits_{k=1}^{n} \frac{1}{(k+1)(k+2)} = \frac{n}{2(n+2)}[/tex]
Where, T_{n} is equal to the sum of result 6.6.

A friend told me the following, but I don't understand why any of of it is true.

[tex]T_{n} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} +... \frac{1}{n}, S_{n} = \frac{1}{n+1} + ... + \frac{1}{n}, T_{2n} = \frac{1}{1} + \frac{1}{2} + ... + \frac{1}{n} + ... + \frac{1}{2n-1} + \frac{1}{2n}, S_{n} = T_{2n} - T_{n} = \frac{1}{2n(2n+1)} - \frac{1}{n(n+1)}[/tex]
 

Related Threads on Proof by Induction

  • Last Post
Replies
6
Views
869
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
753
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
2
Views
912
  • Last Post
Replies
4
Views
852
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
4
Views
2K
Top