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 any integer , p(k+1) is true whenever p(k) is true then p(n) is true for all .

It is important to show that the base step and the inductive step in the principle are satisfied. Let's prove the above result. The first step is to establish the base step p(1). This is easy since the expression on the right of the equals sign in p(1) has value which is 1 and this is the value of the left hand side of p(1). Hence p(1) is a true statement. Next we need to establish the inductive part of the proof. We assume that for some that p(k) is true. That is the statement

is true for some positive integer k. We must use this to show p(k+1) is a true statement. In such proofs we think of the equals sign as separating two expressions. The quantity to the left of the equals sign is called the left hand side (or lhs for short) and the quantity to the right the right hand side (rhs). To show p(k+1) is true means to show the lhs of p(k+1) is equal to the rhs of p(k+1). This is achieved by starting with one side and manipulating it until it becomes the other side. We usually start with the lhs but this is not always the case. Let's proceed.

We have now established that p(k+1) is true, assuming p(k) is true. In other words, . The principle of mathematical induction now tells us that p(n) is true for all positive integers n.

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

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

Let's use this to prove the statement . Our base step this time is to establish p(5). Now lhs p(5) has value 32 and the rhs p(5) has value 25 showing p(5) is a true statement. Now we assume that p(k) is true for some .

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.