Mathematical Induction

The principle of mathematical induction is stated as follows:

If a given statement S_n concerning a positive integer n is true for n = 1, and if the truth of S_n for n = k, where k is a positive integer, implies that S_n is true for n = k + 1, then S_n is true for every positive integer n.

The premise behind this principle is self-intuitive. If a particular statement S_n (normally a mathematical equation or inequality involving the variable n) is true for n = 1, and it can also be proven that S_n being true implies that S_{n + 1} is also true, then the statement S_n is true for n = 1 + 1 = 2. Similarly, S_n is true for n = 2 + 1 = 3, n = 3 + 1 = 4, and so on for all positive integers.

It should be noted that the principle of mathematical induction can be extended to include whole numbers by simply proving S_n to be true for
n = 0. Then, if S_n being true implies that S_{n + 1} is true, S_n will be true for n = 0 + 1 = 1, n = 1 + 1 = 2 and so on for all positive integers. Thus, S_n will be true for all whole numbers (the set of positive numbers plus zero).

The principle of mathematical induction is very helpful in proving many statements about positive integers. According to this principle, a mathematical statement involving the variable n can be shown to be true for any positive integer n by proving the following two statements:

(1) The statement is true for n = 1.
(2) If the statement is true for any positive integer k, then it is also
true for k + 1.

The following examples should clarify the use of this principle:

Example 1: Use mathematical induction to prove that

1 + 3 + 5 + .... + (2n - 1) = n² is true for every positive integer n.

Solution: Utilize the two steps of mathematical induction outlined above.

Step 1. Replacing n by 1 in the above equation gives

2 (1) - 1 = 1 = 1² so n = 1 satisfies the equation.

Step 2 Assume that the equation is true for n = k. Then

1 + 3 + 5 + .... + (2k - 1) = k²
1 + 3 + 5 + .... + (2k - 1) + (2(k+1) - 1)= k² + ( 2(k+1) - 1 )
= k² + ( 2k + 2 - 1 )
= k² + 2k + 1
= (k + 1)²

The final equality proves that the equation is true for n = k + 1, given it is true for n = k.

The proof of the above equality by mathematical induction is complete.

Example 2: Use mathematical induction to prove that

0 + 1 + 2 + .... + n = n (n+1) / 2 is true for every whole number n.

Solution: Apply the two steps of mathematical induction, but prove the equality true for n = 0, since the statement is to be shown valid for all whole numbers (including zero).

Step 1 By plugging n = 0, we have

0 = 0 (0+1) / 2 = 0 so n = 0 satisfies the equation.

Step 2 Assume that the equation is true for n = k. Then

0 + 1 + 2 + .... + k = k (k+1) / 2
0 + 1 + 2 + .... + k + (k + 1) = k (k + 1) / 2 + (k + 1)
= (k + 1) ((k/2) + 1)
= (k + 1) (k + 2) / 2

The last equality proves that n = k satisfying the above equation implies that n = k + 1 also satisfies it.

Thus, the above equality is satisfied for n = 0, as well as n= 0 + 1 = 1,

n = 1 + 1 = 2, and so on for all positive integers; it is true for all whole numbers.

The following example illustrates a helpful method in formulating the required proofs in Step 2. In this example, the mathematical statement in question is explicitly written out for n = k and n = k + 1. Then, the attempt is made to derive the latter statement from the former, using axioms and previously-proven theorems. This procedure may facilitate the thinking process required in establishing the appropriate proofs, as is the case here.

Example 3: Use mathematical induction to show that

n² < 2ⁿ for all positive integers n > 4

Solution: While mathematical induction can still be applied to prove the above statement, a few changes must be made to the solution process. Since the equation is to be shown true for all integers greater than 4, the starting point should be n = 5 instead of n = 1. Furthermore, the fact that n > 4 should be used in Step 2.

Step 1. Using n = 5, we have

5² = 25 < 2⁵ = 32 so n=5 satisfies the inequality

Step 2 Assume that the inequality is true for n = k, where k > 4.

Then

k² < 2^k
2k² < 2·(2^k) = 2^k+1

To show that n = k + 1 satisfies the inequality, we must show that (k+1)² < 2 ^{k + 1}, where k > 4. If it can be proven that (k+1)² < 2k², then (k+1)² < 2^k+1 by transitivity.

Since k > 4, k - 1 > 3 > 2. As k + 1 > k,
(k - 1) (k + 1) > 2k
k₂ - 1 > 2k
k₂ > 2k + 1
2k² > k² + 2k + 1 = (k + 1 )²

Since and (k + 1)² < 2k² and 2k² < 2^k+1 < 2^k+2, so n = k + 1 satisfies the above inequality whenever n = k does.

This completes the proof.