Mathematical Induction and Well Ordering Principle

Today we learned how to do mathematical induction. Although this was very hard and sometimes intimidating breaking the process down into two simple steps helps ease the pain just a tad. 

Step #1: Prove the statement is true at the starting point (usually n=1).

Step #2: Assume the statement is true for n.  Prove the statement is true for n+1.

     As Miss V eloquently explained in class mathematical induction only works because of the well ordering principle. This principle states that "Every nonempty set of non-negative integers has a smallest element."  Furthermore, the well-ordering principle is often used and structured in this format:

"To prove that “P (n) is true for all n ∈ N” using the Well Ordering Principle: 

•  Define the set, C, of counterexamples to P being true. Namely, define

C ::= {n ∈ N | P (n) is false} . 

•  Assume for proof by contradiction that C is nonempty. 

•  By the Well Ordering Principle, there will be a smallest element, n, in C. 

• Reach a contradiction (somehow) —often by showing how to use n to find 

another member of C that is smaller than n. (This is the open-ended part of 

the proof task.) 

•  Conclude that C must be empty, that is, no counterexamples exist."

Here is an example of the mathmatical side of induction to gain a better grasp of how the process works.