Proof by Induction

The natural ordering on the set of natural numbers(that is,) has the well ordering property that every nonempty subset ofhas a least (smallest) element. The principle of induction is the following theorem, which is equivalent to the well ordering property of the natural numbers.

Theorem (Principle of induction). Letbe a statement about

Suppose that

1. (basis statement)is true,

2. (induction step) ifis true, thenis true.

Thenis true for all

Proof. Suppose thatis the set of natural numbersfor whichis not true. Suppose that is nonempty. Thenhas a least element by the well ordering principle. Let us callthe least element ofWe know thatby assumption. Thereforeandis a natural number as well. Sincewas the least element of S, we know thatis true. But by the induction step we can see thatis true, contradicting the statement thatThereforeis empty andis true for all

Sometimes it is convenient to start at a different number than 1.

Example: Prove for

We letbe the statement thatis true. Puttingwe can see that P(1) is

true. Suppose thatis true. That is, suppose thatholds. Multiply both sides byto obtain

Aswhenwe haveThat is,

and henceis true. By the principle of induction, we see thatis true for alland

henceis true for all

The principle of strong induction is similar:

Letbe a statement about a natural numberSuppose that

1. (basis statement)is true,

2. (induction step) ifis true for allthenis true.

Thenis true for all