Register to reply

Proof by induction of a problem

by marcin w
Tags: induction, proof
Share this thread:
marcin w
#1
Feb25-07, 04:05 PM
P: 12
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.
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
HallsofIvy
#2
Feb26-07, 07:28 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,310
Quote Quote by marcin w View Post
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.
Your teacher might not appreciate that! Saying something is true is not proving that it is true.

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.
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
#3
Feb26-07, 08:52 PM
P: 12
Thanks, your answer was helpful and much appreciated.


Register to reply

Related Discussions
Another induction proof Precalculus Mathematics Homework 5
Help with Proof and Mathematical Induction problem Math & Science Software 14
Complex roots problem (a proof by induction) General Math 12
Another proof by induction Calculus 1
Proof by Induction General Math 6