Solving Induction Proof w/ Homework: Step by Step Guide

In summary: So it is valid for all n+1>2.In summary, the conversation involves discussing a problem that requires using strong induction to prove a statement about the sum of absolute values of a sequence. The main inductive step and its validity for all n+1 greater than 2 is shown.
  • #1
ar6
5
0

Homework Statement


http://img87.imageshack.us/img87/469/17317851uu7.jpg [Broken]


Homework Equations





The Attempt at a Solution



First I have to show that P(1) is true
|a1| ≤ |a1| This is true

Assume above is true for all n.

Show that

|∑i=1n+1 ai| ≤ n+1∑i=1 |ai|


|a1 + a2 + a3…+ an + an+1| ≤ |a1| + |a2| + |a3| +…+ |an| + |an+1|

|∑i=1n ai + an+1| ≤ n+1∑i=1 |ai| + |an+1|

assuming I'm on the right track. How can i proceed. This problem is so abstract its driving me crazy. Sorry for formatting.
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
ar6 said:

Homework Statement


http://img87.imageshack.us/img87/469/17317851uu7.jpg [Broken]


Homework Equations





The Attempt at a Solution



First I have to show that P(1) is true
|a1| ≤ |a1| This is true

Assume above is true for all n.

Show that

|∑i=1n+1 ai| ≤ n+1∑i=1 |ai|


|a1 + a2 + a3…+ an + an+1| ≤ |a1| + |a2| + |a3| +…+ |an| + |an+1|

.
you have to arrive at the last equation using the preceding equation.
Lets start with the left hand side of last equation.
|a1 + a2 + a3…+ an + an+1|≤|a1 + a2 + a3…+ an |+ |an+1|
.......{ since it is valid for n=2}
|a1 + a2 + a3…+ an + an+1|≤|a1| + |a2 |+ |a3|+…+ |an |+ |an+1|
........{since valid for n=n(seond last equation i your post)}

Keep Smiling
Malay
 
Last edited by a moderator:
  • #3
You use a strong induction. Assume true for all k<n. Then

[tex]\left|\sum_i a_i\right|=\left|\sum_{i=1}^{n-1}a_i +a_n\right|[/tex]

You should see where to go from here.Problems like these are often trivial inductions. Like, for example, showing that taking the intersection of two open sets is open immediately implies that the finite intersection of open sets is always open. Why? Well, for n=3 we have (A n B)nC but we showed AnB is open! So we just repeatedly use this fact.

It's the same thing here, really.

Edit: If you know nothing about open sets, completely disregard.
 
Last edited:
  • #4
You should demonstrate that it is true for n = 2...

MalayInd showed the main inductive step which is valid for n+1>2 but not for n+1 = 2.
 
  • #5
for n+1=2, it reduces to triangle inequality.
 

1. What is an induction proof?

An induction proof is a mathematical method used to prove that a statement is true for all natural numbers. It involves breaking down the statement into smaller cases and proving that it holds for the first case, then assuming it holds for the next case and using that to prove it holds for the following case, and so on.

2. Why is it important to solve induction proofs?

Induction proofs are important because they provide a rigorous way to prove that a statement is true for all natural numbers, rather than just testing a few cases and assuming it holds for all cases. This is especially useful in mathematics and computer science, where proving theorems and algorithms requires this level of certainty.

3. How do you approach solving an induction proof?

The first step in solving an induction proof is to identify the statement you want to prove. Then, you need to determine the base case, which is the smallest value of the natural numbers for which the statement is true. Next, you need to assume the statement holds for a general case, and then use that assumption to prove that it holds for the following case. Finally, you need to conclude that the statement holds for all natural numbers.

4. What are some common mistakes to avoid when solving induction proofs?

One common mistake is to incorrectly identify the base case or the general case. It is important to make sure that the base case is the smallest value and that the general case is applicable to all natural numbers. Another mistake is to assume that the statement holds for the next case without properly using the assumption in the proof. Additionally, it is important to clearly explain each step of the proof and to avoid making logical or mathematical errors.

5. Can you provide a step-by-step guide for solving an induction proof?

Sure! Here are the steps to follow when solving an induction proof:

  1. Identify the statement you want to prove.
  2. Write out the base case, which is the smallest value of the natural numbers for which the statement is true.
  3. Assume the statement holds for a general case and use that assumption to prove it holds for the following case.
  4. Explain each step of the proof and make sure to properly use the assumption.
  5. Conclude that the statement holds for all natural numbers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
983
  • Calculus and Beyond Homework Help
Replies
6
Views
870
  • Calculus and Beyond Homework Help
Replies
4
Views
987
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
Back
Top