The Principle of Induction | Artin's Honors Calculu

The principle of induction which we mentioned before is a statement about the positive integers. It reads as follows:

Principle of Induction. Let $P (n)$ be an assertion about the positive integer $n$ . Suppose that:

(a) The assertion $P (1)$ is true;

(b) If the assertion $P (k)$ is true for a given integer $k$ , then the assertion $P (k + 1)$ is also true.

Then the assertion $P (n)$ is true for all $n$ .

If we think about this a little, we should see that it is entirely in keeping with our intuition. There are various models to help us visualize the principle. In one such model, we consider a system of dominoes on edge, aligned so that if any one tips toward the next one it will knock it over toward the following one. This is the analogue of the hypothesis (b). The analogue of (a) is simply that we can knock over the first one. But then it will tip over the second, which will hit the third, ... . By writing enough such steps, we could reach any specified domino, or the assertion $P (n)$ for any prescribed $n$ . However, we have now seen that the hypotheses (a) and (b) are the essentials of this process, and that we can save all this writing simply by showing that they are valid.

As an example, let us give a proof by induction of a formula for the sum of a familiar arithmetic progression:

1 + 2 + \dots + n = \frac{n (n + 1)}{2} .

Then $P (n)$ is the statement that the sum of the first $n$ integers is equal to $\frac{n (n + 1)}{2}$ . $P (1)$ thus says that the sum of the first integer, or 1, is equal to $\frac{1 (1 + 1)}{2} = 1$ . Therefore hypothesis (a) is satisfied. Now hypothesis (b) begins with, "If $P (k)$ is true,". This means that we must suppose $P (k)$ to be true, and see if the truth of $P (k + 1)$ is a consequence of this assumption. Thus we begin by supposing

P (k) : 1 + 2 + \dots + k = \frac{k (k + 1)}{2} .

Then we must consider the sum

1 + 2 + \dots + k + (k + 1) = (1 + 2 + \dots + k) + (k + 1) .

But, by what we are assuming,

1 + 2 + \dots + k = \frac{k (k + 1)}{2} = (k + 1) \cdot \frac{k}{2} .

Therefore

1 + 2 + \dots + k + (k + 1) = (k + 1) (\frac{k}{2} + 1) = (k + 1) (\frac{k + 2}{2}),

1 + 2 + \dots + (k + 1) = \frac{(k + 1) ((k + 1) + 1)}{2},

which is $P (k + 1)$ . Thus (a) and (b) are satisfied, and $P (n)$ holds for all $n$ by induction.

Exercises

Exercise 1.

Prove that $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6} .$

Exercise 2.

Prove that (f_1 + f_2 + \dots + f_n)' = f_1' + f_2' + \dots + f_n' .

Exercise 3.

Prove that (f_1 f_2 \dots f_n)' = f_1' f_2 \dots f_n + f_1 f_2' f_3 \dots f_n + \dots + f_1 \dots f_{n-1} f_n' .

Exercise 4.

Show that hypothesis (b) is satisfied for $P (n) : n = n + 2,$ which is obviously false.

Exercise 5.

Give an example of a $P (n)$ which is false for $n > 1$ but for which hypothesis (a) holds.

Exercise 6.

Prove that $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}, n = 1, 2, 3, \dots .$

Exercise 7.

Prove that $(1 - \frac{1}{4}) (1 - \frac{1}{9}) (1 - \frac{1}{16}) \dots (1 - n^{- 2}) = \frac{n + 1}{2 n} n = 2, 3, 4, \dots .$

Mathematical Induction

Exercises

Quick Links

Social Media