Proof by induction of a problem

marcin w

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:
[tex]
\sum_{k = m}^{m}{a}_{k} = {a }_{ m}
[/tex]
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 }
[/tex]
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.

HallsofIvy

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]

marcin w

Thanks, your answer was helpful and much appreciated.