Proof by induction of a problem

In summary: I will work through the algebra to complete the proof. In summary, the conversation discusses a problem that requires a proof by induction and the individual has worked out a proof but is seeking feedback. They also define the symbol \sum_{k = m}^{m + n}{a}_{k} and approach the proof in a typical manner. The individual was unsure if they were supposed to use the definition in the proof, but it is suggested that it would have made things easier. The conversation then goes into the steps of the proof and the individual thanks the expert for their help.
  • #1
marcin w
12
0
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.
 
Last edited:
Mathematics news on Phys.org
  • #2
marcin w said:
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]
 
  • #3
Thanks, your answer was helpful and much appreciated.
 

1. What is proof by induction?

Proof by induction is a mathematical technique used to prove statements that involve natural numbers or integers. It is based on the principle of mathematical induction, which states that if a statement is true for a certain number (usually 1), and if it can be shown that the statement being true for any particular number implies that it is also true for the next consecutive number, then the statement is true for all natural numbers or integers.

2. How does proof by induction work?

Proof by induction works by breaking down a statement into smaller parts and then proving that each part is true. This is done in two steps: the base case, where the statement is shown to be true for the first number (usually 1), and the inductive step, where it is shown that if the statement is true for a particular number, it is also true for the next consecutive number. By repeating this process, the statement is proven to be true for all natural numbers or integers.

3. When is proof by induction used?

Proof by induction is commonly used in mathematics to prove statements about natural numbers or integers, such as formulas, equations, and inequalities. It is also used in computer science and physics to prove properties of algorithms, data structures, and physical systems.

4. What are the limitations of proof by induction?

Proof by induction can only be used to prove statements that involve natural numbers or integers. It cannot be used for real numbers or irrational numbers. Additionally, it can only be used for statements that can be broken down into smaller parts and have a clear base case and inductive step.

5. Can proof by induction be used to prove all statements?

No, proof by induction can only be used to prove statements that follow the principle of mathematical induction. There are some statements that cannot be proven using this technique, such as statements that involve infinite sets or involve complex logic. In these cases, other proof techniques may be necessary.

Similar threads

Replies
13
Views
1K
Replies
14
Views
1K
  • General Math
Replies
1
Views
162
Replies
4
Views
287
  • General Math
Replies
4
Views
1K
Replies
4
Views
1K
Replies
3
Views
622
Replies
1
Views
275
  • Linear and Abstract Algebra
Replies
2
Views
883
  • General Math
Replies
3
Views
1K
Back
Top