Mathematical Induction

Proving Infinitely Many Cases

Some statements hold for every natural number, like $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ for all $n \ge 1$. Mathematical induction proves infinitely many cases with a finite argument. Think of a line of dominoes: if the first falls and each knocks the next, all fall.

An induction proof relies on two essential parts:

Both parts are required. Both alone leave the chain unstarted or broken.

Strong Induction & Pitfalls

Strong induction is a variant where the inductive step assumes the statement for all values from the base up to $k$, not just $k$. This helps when cases depend on multiple earlier ones, such as proving every integer $>1$ has a prime factorization.

To prove $1 + 2 + \dots + n = \frac{n(n+1)}{2}$: the base case $n=1$ gives $1 = \frac{1 \cdot 2}{2}$. Assuming it for $k$, adding $k+1$ yields the formula for $k+1$.