Math Induction Explained: Step-by-Step Guide

[Richter915]

Hi I was wondering if any of you could explain the concept of Mathematical Induction to me...I really am confused on this, we didn't learn it in class (yet we're going to be quizzed on it)...if you could walk through a simple example, it would be really appreciated...thank you!

 

[hypermorphism]

See this page.

 

[Richter915]

Wow, thank you so much. I have a question though. My teacher, as an example asked to use induction to prove that a certain sequence is increasing...so by using induction would I:
1. Prove P(1) exists
2. Prove P(K) is increasing
3. Prove P(K+1) > P(K) thus concluding that the sequence increases>

 

[hypermorphism]

Wow, thank you so much. I have a question though. My teacher, as an example asked to use induction to prove that a certain sequence is increasing...so by using induction would I:
1. Prove P(1) exists
2. Prove P(K) is increasing
3. Prove P(K+1) > P(K) thus concluding that the sequence increases>

The first step is not to prove that P(1) exists, it is to prove that the first theorem in a chain of theorems holds true. The "arbitrary kth theorem being true implies truth of (k+1)th theorem" proof then allows one to form a logical chain to the (k+1)-th theorem from the 1st theorem if challenged to prove that the (k+1)-th theorem is true.
In your case, you want to prove that the second item in the sequence is greater than the first item. Your second step is to prove that given an arbitrary kth term in the sequence and assuming the kth term is greater than the (k-1)th term, prove that the (k+1)th term is greater than or equal to (if your aim is not to prove strictly increasing) the kth term. The actual item to prove changes with each set of theorems, only the logical machinery is the same.

 

[Richter915]

oh ok I see my mistake...so I'd have to say that P(1) holds true for the condition...so for this example it'd be P(1)>0 and then I'd proceed from there?

 

[hypermorphism]

oh ok I see my mistake...so I'd have to say that P(1) holds true for the condition...so for this example it'd be P(1)>0 and then I'd proceed from there?

Unless the P(0)'th term is 0, it doesn't prove much of anything to show that P(1) is greater than zero (Consider an increasing sequence that starts with negative numbers). This inductive proof starts with showing P(2)>P(1).