Mathematical Induction

A type of proof that deserves special attention is mathematical induction. Some of the statements of theorems which can be proved using mathematical induction involve an integer variable. An example of such a theorem is

Let p(n) denote the statement involving the integer variable n. The Principle of Mathematical Induction states

If p(1) is true and, for each integer , p(k+1) is true whenever p(k) is true then p(n) is true for all .

This principle is often compared to an infinite line of dominos. The inductive part of the principle (for each integer , p(n+1) is true whenever p(n) is true) would say that the domino in the (n+1)st position falls whenever the nth domino falls. However, at that stage we still don't know if the line of dominos has fallen or is still upright. The base step in the principle (If p(1) is true) is analogous to saying the first domino has fallen. We would now realize that the complete line of dominos will fall. It is important to show that the base step and the inductive step in the principle are satisfied.

There are several variations in this principle. The first covers statements that are true for all integers beyond a certain value (such as which is true for all ).

If is true and, for each integer , p(k+1) is true whenever p(k) is true then p(n) is true for all .

There is also a stronger form of mathematical induction which states the following:

If p(1) is true and, for each integer the statements imply the statement p(k+1) then p(n) is true for all .

This principle of strong mathematical induction is used for example to prove the result that every positive integer is a prime number, a power of a prime or a product of primes. As with the principle of mathematical induction, there is a variation on this to cover those statements that are true for all integers beyond a certain value .