<aside> ✅ Strong induction, Induction, and Well Ordering are different methods that achieve the same result.

</aside>

The Induction Principle

Let $P$ be a predicate on nonnegative integers. If

• $P(0)$ is true
• $P(n) \implies P(n+1)$ for all nonnegative integers,

then,

• $P(m)$ is true for all nonnegative integers $m$.

The Induction Rule

$$ \begin{array}{c}P(0), \forall n \in \N. P(n) \implies P(n+1)\\ \hline \forall m \in \N. P(m) \end{array} $$

Proof Template

1. State that the proof uses induction
2. Define an appropriate predicate
3. Prove that $P(0)$ is true
4. Prove that $P(n) \implies P(n+1)$
5. Invoke Induction

The Strong induction Principle

Let $P$ be a predicate on nonnegative integers. If

• P(0) is true, and