Physics Forums

## Proof by induction of a problem

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 $$\sum_{k = m}^{m + n}{a}_{k}$$
I first define:
[tex]
\sum_{k = m}^{m}{a}_{k} = {a }_{ m}
[/tex]
Then assuming I have defined $$\sum_{k = m}^{n}{a}_{k}$$ for a fixed n >= m, I further defined:
$$\sum_{ k=m}^{n+1 } {a }_{k } =( \sum_{k=m }^{ n} { a}_{ k} )+ { a}_{n+1 }$$

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

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:
$$\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}$$

where the last term on the RHS simplifies to $$- \frac{ 1}{2k }$$.
I have to show that A(k+1) is true:
(*)$$\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)}$$

where the last term on the RHS simplifies to $$- \frac{1 }{ 2(k+1)}$$
Starting with A(k), I add $$\frac{1 }{ 2k+1} + \frac{ 1}{ 2k+2} - \frac{ 1}{ k+1}$$ 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
$$\sum_{ k=(n+1)+1}^{ 2(n+1)} \frac{1 }{k }$$

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

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.

Recognitions:
Gold Member
Science Advisor
Staff Emeritus

Quote by 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 $$\sum_{k = m}^{m + n}{a}_{k}$$ I first define: $$\sum_{k = m}^{m}{a}_{k} = {a }_{ m}$$ Then assuming I have defined $$\sum_{k = m}^{n}{a}_{k}$$ for a fixed n >= m, I further defined: $$\sum_{ k=m}^{n+1 } {a }_{k } =( \sum_{k=m }^{ n} { a}_{ k} )+ { a}_{n+1 }$$  Part 2 requires me to prove by induction that for all n >= 1, we have the assertion (call it A(n)):  $$\sum_{k=n+1 }^{ 2n} \frac{1 }{k } = \sum_{ m=1}^{ 2n} \frac{ {(-1) }^{m+1 } }{m }$$  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: $$\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}$$  where the last term on the RHS simplifies to $$- \frac{ 1}{2k }$$. I have to show that A(k+1) is true: (*)$$\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)}$$  where the last term on the RHS simplifies to $$- \frac{1 }{ 2(k+1)}$$ Starting with A(k), I add $$\frac{1 }{ 2k+1} + \frac{ 1}{ 2k+2} - \frac{ 1}{ k+1}$$ to each side and obtain:  $$\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  $$\sum_{ k=(n+1)+1}^{ 2(n+1)} \frac{1 }{k }$$   and the terms $$\frac{ 1}{ 2k+2}- \frac{ 1}{ k+1}$$ on the right simplify to $$\frac{ -1}{2(k+1) }$$, so the right side resembles the right side in (*). Therefore, the RHS becomes the sum $$\sum_{ m=1}^{2(n+1) } \frac{ {(-1) }^{m+1} }{2m }$$  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,
$$\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}$$
Now, replace that sum by
$$\sum_{m=1}^{2n} \frac{(-1)^m+1}{m}$$
and do the algebra.

You might want to use the fact that
$$\frac{1}{2n+2}- \frac{1}{n+1}= \frac{1- 2}{2n+2}= -\frac{1}{2n+2}$$

Thread Tools

|                                                      |                                  |         |
|------------------------------------------------------|----------------------------------|---------|
| Similar Threads for: Proof by induction of a problem |                                  |         |
| Thread                                               | Forum                            | Replies |
|                                                      | Precalculus Mathematics Homework | 5       |
|                                                      | Math & Science Software          | 14      |
|                                                      | General Math                     | 12      |
|                                                      | Calculus                         | 1       |
|                                                      | General Math                     | 6       |
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 31, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9404316544532776, "perplexity_flag": "head"}