April 13, 2018
The proof that strong induction and induction (also called weak or simple induction) are equivalent is a bit tricky. Showing that strong induction implies induction is straightforward; however, showing that induction implies strong induction requires using induction on itself—very meta!
In addition to induction over the natural numbers, other types of induction are possible. For example, transfinite induction extends things to more generic well-ordered sets.