mathematical induction

Proving a statement true for every whole number by knocking over an infinite line of dominoes.

The technique of mathematical induction shows a statement $P(n)$ holds for every whole number $n$ starting at some base case by two steps — a base case, showing $P(n_0)$ is true, and an inductive step, showing that whenever $P(k)$ is true, $P(k+1)$ must be true too. Together they guarantee $P(n)$ for every $n \geq n_0$ , the way one falling domino guarantees every domino after it falls.

Examples

Proving $1+2+\cdots+n=\frac{n(n+1)}{2}$ for every $n \geq 1$ is a standard induction proof.

Read the full section →

snap pen only

Graph settings

indep dep deg

grid intersections

xmin xmax ymin ymax

x-tick y-tick

Calculator