An example of a proof by mathematical induction
Example: Use mathematical induction to show that n3-n is divisible
by 3, for all positive integers n.
13-1 = 1-1=0 is divisible by 3.
Inductive step. Assume that n3 -n is divisible by 3 (inductive
Show that (n+1)3 - (n+1) is also divisible by 3.
(n3 + 3n2 + 3n + 1) - (n +1) =
n3 + 3n2 + 3n + 1 - n - 1 =
By the inductive hypothesis, n3- n is divisible by 3. Thus, every term of
the sum n3- n + 3n2+3n is divisible by 3, and so is the sum itself.