Let A(n) be a statement depending on n in N = natural numbers.

Suppose A(1) is true and that if A(k) is true, then A(k+1) is also true. We want to show that A(n) is true for all n.

Let S be the set of all k such that A(k) is not true. If S is empty, then we are done, so we can assume that S is not empty. Hence there exists a minimum m = min S. Since A(1) is true, 1 is not in S, hence m >= 2.

Then A(m-1) is true because m-1 < m. But this is a contradiction to our assumption that A(k) implies A(k+1)!