1. Limited time only! Sign up for a free 30min personal 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 of a problem

  1. Feb 25, 2007 #1
    I'm working out a problem that requires me to proof a result by induction. I have worked out what I think is a correct proof, but I would like for somebody to look over it and give me feedback.
    Part 1: Give a reasonable definition of the symbol [tex]\sum_{k = m}^{m + n}{a}_{k}[/tex]
    I first define:
    \sum_{k = m}^{m}{a}_{k} = {a }_{ m}
    Then assuming I have defined [tex]\sum_{k = m}^{n}{a}_{k}[/tex] for a fixed n >= m, I further defined:
    [tex] \sum_{ k=m}^{n+1 } {a }_{k } =( \sum_{k=m }^{ n} { a}_{ k} )+ { a}_{n+1 } [/tex]

    Part 2 requires me to prove by induction that for all n >= 1, we have the assertion (call it A(n)):
    [tex]\sum_{k=n+1 }^{ 2n} \frac{1 }{k } = \sum_{ m=1}^{ 2n} \frac{ {(-1) }^{m+1 } }{m } [/tex]

    I approach this problem as I would have any proof by induction. The base case A(1) is true so I won't write it out here. Now, assuming the assertion is true for some k:
    [tex] \frac{ 1}{ k+1} + \frac{1 }{k+2 } +...+ \frac{ 1}{ 2k} = 1 - \frac{ 1}{2 } + \frac{1 }{3 } - \frac{ 1}{ 4} +...+ \frac{ {(-1) }^{2k+1 } }{ 2k} [/tex]

    where the last term on the RHS simplifies to [tex]- \frac{ 1}{2k } [/tex].
    I have to show that A(k+1) is true:
    (*)[tex]\frac{ 1}{ k+2} + \frac{1 }{k+3 } +...+ \frac{ 1}{ 2(k+1)} = 1 - \frac{ 1}{2 } + \frac{1 }{3 } - \frac{ 1}{ 4} +...+ \frac{ {(-1) }^{2(k+1)+1 } }{ 2(k+1)} [/tex]

    where the last term on the RHS simplifies to [tex]- \frac{1 }{ 2(k+1)} [/tex]
    Starting with A(k), I add [tex] \frac{1 }{ 2k+1} + \frac{ 1}{ 2k+2} - \frac{ 1}{ k+1} [/tex] to each side and obtain:

    [tex]\frac{ 1}{k+1 } + \frac{ 1}{k+2 } +...+ \frac{ 1}{2k } - \frac{1 }{k+1 } + \frac{1 }{ 2k+1} + \frac{1 }{2k+2 } =1- \frac{ 1}{ 2} + \frac{ 1}{ 3} - \frac{ 1}{ 4} +...- \frac{1 }{2k+2 } - \frac{1 }{ k+1} + \frac{ 1}{ 2k+1} + \frac{1 }{2k+2 }
    After subtracting out the two like terms on each side, the left hand side becomes the sum
    [tex] \sum_{ k=(n+1)+1}^{ 2(n+1)} \frac{1 }{k } [/tex]

    and the terms [tex] \frac{ 1}{ 2k+2}- \frac{ 1}{ k+1} [/tex] on the right simplify to [tex] \frac{ -1}{2(k+1) } [/tex], so the right side resembles the right side in (*). Therefore, the RHS becomes the sum [tex] \sum_{ m=1}^{2(n+1) } \frac{ {(-1) }^{m+1} }{2m } [/tex]

    I'm wasn't sure if I was supposed to use the definition of part 1 in part 2 and I didn't, but I'm wondering if that would have made things easier. Thanks.
    Last edited: Feb 25, 2007
  2. jcsd
  3. Feb 26, 2007 #2


    User Avatar
    Science Advisor

    Your teacher might not appreciate that! Saying something is true is not proving that it is true.

    In going form n to n+1, two things happen. First, since the sum starts at n+1 in the first case and (n+1)-1 in the second, you are missing the first term. Second, since the sum ends at 2n in the first case and 2(n+1)= 2n+ 2 in the second, you will have two new terms, 2n+1 and 2n+ 2. That is,
    [tex]\sum_{k= (n+1)+1}^{2(n+1)} \frac{1}{k}= \sum_{k= n+1}^{2n} \frac{1}{k}+ \frac{1}{2n+1}+ \frac{1}{2n+2}- \frac{1}{n+1}[/tex]
    Now, replace that sum by
    [tex]\sum_{m=1}^{2n} \frac{(-1)^m+1}{m}[/tex]
    and do the algebra.

    You might want to use the fact that
    [tex]\frac{1}{2n+2}- \frac{1}{n+1}= \frac{1- 2}{2n+2}= -\frac{1}{2n+2}[/tex]
  4. Feb 26, 2007 #3
    Thanks, your answer was helpful and much appreciated.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook