Strong Induction and the Well-Ordering Principle

Reading

Section 2.2

Practice Problems

2.2

1, 2, 3, 7

Notes

We will very briefly cover the Well-Ordering Principle and what is known as "strong induction". For now, we just want you to be aware of their existence.

• In normal induction, we:
  • Prove our statement when \(n = 1\)
  • Prove that if the statement is true when \(n = k\), it must also be true when \(n=k+1\)
• In strong induction:
  • Prove our statement when \(n = 1\)
  • Prove that if the statement is true for all \(n = 1,2,3,...,k\), then it must be true for \(k+1\) also.
• In other words, we assume all previous statements are true, not just the one right before the one we are working on.

• The Well-Ordering Principle says the following:

  Every non-empty subset of the natural numbers must have a smallest element

  We will see examples of this principle as we move along. But every time we say "let's take the smallest ..." we are applying this principle.