**Up:** Types of Proof
** Previous:** Uniqueness Proofs

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 *n*th 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 .

**Up:** Types of Proof
** Previous:** Uniqueness Proofs
*Peter Williams *

Sun Sep 15 22:27:27 PDT 1996