Mathematical Induction

Mathematical induction proves a statement for every integer in a sequence by checking a starting case and then linking one case to the next.

Induction proves inequalities by checking a base case and then comparing the k+1 expression to something already known from the hypothesis.

Recurrence claims often need strong induction because the next term depends on several earlier terms, not just one.

Strong induction assumes the claim holds for all earlier cases up to n and then proves it for n + 1.