Summary of induction

Weak induction. Base case $P(n_0)$; step $P(n)\Rightarrow P(n+1)$. Concludes $P(n)$ for all $n\ge n_0$.

Strong induction. Base case $P(n_0)$; step $[\forall k\in[n_0,n],P(k)]\Rightarrow P(n+1)$. Allows using more hypotheses.

Structural induction. For recursively defined objects (trees, formulas, etc.): prove for base objects; step from subobjects to compound objects.

Well-ordering. Equivalent to induction: every nonempty subset of $\mathbb{N}$ has a least element.

Conclusion. Choose the form best suited to the problem's recursive structure.