1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by Induction

  1. Oct 18, 2011 #1
    1. The problem statement, all variables and given/known data
    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.


    2. Relevant 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]


    3. 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!
     
  2. jcsd
  3. Oct 18, 2011 #2

    ehild

    User Avatar
    Homework Helper
    Gold Member

    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: Oct 18, 2011
  4. Oct 18, 2011 #3
    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!
     
  5. Oct 18, 2011 #4

    ehild

    User Avatar
    Homework Helper
    Gold Member

    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
     
  6. Oct 18, 2011 #5
    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]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by Induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...