Mathematical induction

Consider the sum of the first $n$ positive odd numbers: $1=1,\ 1+3=4,\ 1+3+5=9,\ 1+3+5+7=16,\ldots$ — the right-hand sides are exactly the perfect squares $1,4,9,16,\ldots$, suggesting the conjecture

A pattern noticed on a handful of cases is not yet a proof for every $n$ — that is exactly what the Principle of Mathematical Induction supplies. It applies to statements $P(n)$ phrased in terms of a positive integer $n$, and mirrors climbing an infinite staircase: if you can (a) climb the first step, and (b) climb from any given step to the next, then you can climb every step. Formally, to prove $P(n)$ true for all $n$:

• Step 1 (initial/base step). Verify $P(1)$ is true.
• Step 2 (inductive step). Assume $P(k)$ is true for some positive integer $k$ (the inductive hypothesis), and show that this forces $P(k+1)$ to be true as well.
• Step 3 (conclusion). If Steps 1 and 2 both hold, then $P(n)$ is true for every positive integer $n$.