Mathematical induction - Topics in precalculus

Topics in

P R E C A L C U L U S

MATHEMATICAL INDUCTION

THE NATURAL NUMBERS are the counting numbers: 1, 2, 3, 4, etc. Mathematical induction is a technique for proving a statement -- a theorem, or a formula -- that is asserted about every natural number.

By "every" natural number, or "all" natural numbers, we mean any one that we might possibly name. See the Appendix, What is a number?.

For example,

1 + 2 + 3 + . . . + n = ½n(n + 1).

This asserts that the sum of consecutive numbers from 1 to n is given by the formula on the right. We want to prove that this will be true for n = 1, n = 2, n = 3, and so on. Now we can test the formula for any given number, say n = 3:

1 + 2 + 3 = ½· 3· 4 = 6

-- which is true. It is also true for n = 4:

1 + 2 + 3 + 4 = ½· 4· 5 = 10

But how are we to prove this rule for every value of n?

The method of proof is the following. It is called the principle of mathematical induction.

If

	1)	when a statement is true for the natural number n = k, then it is also true for its successor, n = k + 1;

and

	2)	the statement is true for n = 1;

then the statement is true for every natural number n.

For, when the statement is true for 1, then according to 1), it will also be true for 2. But that implies it will be true for 3; which implies it will be true for 4. And so on. It will be true for every natural number.

To prove a statement by induction, then, we must prove parts 1) and 2) above.

The hypothesis of Step 1) -- "The statement is true for n = k" -- is called the induction assumption, or the induction hypothesis. It is what we assume when we prove a theorem by induction.

Example 1. Prove that the sum of the first n natural numbers is given by this formula:

S(n) = 1 + 2 + 3 + . . . + n

n(n + 1)
2

We will call this statement S(n), because it depends on n.

Proof. We will do Steps 1) and 2) above. First, we will assume that the statement is true for n = k; that is, we will assume that S(k) is true:

S(k) = 1 + 2 + 3 + . . . + k

k(k + 1)
2

. . . . . (1)

This is the induction assumption. Assuming this, we must prove that S(k + 1) is also true. That is, we must show:

S(k + 1) = 1 + 2 + 3 + . . . + (k + 1)

(k + 1)(k + 2)
2

. . . (2)

To do that, we will simply add the next term (k + 1) to both sides of the induction assumption, line (1):

This is line (2), which is the first thing we wanted to show.

Next, we must show that the statement is true for n = 1. We have

S(1) = 1 = ½· 1· 2

The formula therefore is true for n = 1. We have now fulfilled both conditions of the principle of mathematical induction. S(n) is therefore true for every natural number.

Example 2. Prove this rule of exponents:

(ab)ⁿ = aⁿbⁿ,

for every natural number n.

Proof. Again, let us call this statement S(n). And we begin by assuming that it is true when n = k; that is, we assume that S(k) is true:

S(k) = (ab)^k = a^kb^k . . . . . . . . . . . (3)

With this assumption, we must prove that S(k + 1) is also true:

S(k + 1) = (ab)^{k + 1} = a^{k + 1}b^{k + 1}. . . . . . . . . (4)

(When using mathematical induction, the student should always write exactly what is to be proved.)

Now, given the assumption, line (3), how can we produce from it line (4)?

Simply by multiplying both sides of line (3) by ab:

(ab)^kab	=	a^kb^kab

	=	a^kab^kb

since the order of factors does not matter,

	=	a^{k + 1}b^{k + 1}.

This is line (4), which is what we wanted to show.

So, we have shown that if the theorem is true for any specific natural number k, then it is also true for its successor, k + 1.

Next, we must show that the theorem is true for n = 1; that is, that

(ab)¹ = a¹b¹.

But (ab)¹ = ab; and a¹b¹ = ab.

This theorem is therefore true for every natural number n.

Example 3. Prove this formula for the sum of consecutive cubes:

n²(n + 1)²
4

Proof. Assume that the statement -- the formula -- is true for n = k. That is, assume that the sum up to k -- S(k) -- is true:

S(k)	=	k²(k + 1)² 4	(1)

Then we must show that it is also true for n = k + 1:

S(k + 1)	=	(k + 1)²(k + 2)² 4	(2)

To do that, add the next cube to S(k), line (1):

S(k + 1)	=	S(k) + (k + 1)³

	=	k²(k + 1)² 4	+ (k + 1)³

	=	k²(k + 1)² + 4(k + 1)³ 4

	=	(k + 1)²[k² + 4(k + 1)] 4

-- on having factored (k + 1)²,

	=	(k + 1)²(k² + 4k + 4) 4

	=	(k + 1)²(k + 2)² 4

This is line (2), which is what we wanted to show.

Next, show that the formula is true for n = 1.

S(1)	=	1³	=	1²· 2² 4

		1	=	1· 4 4

-- which is true. The formula, therefore, is true for every natural number.

Problem 1. According to the principle of mathematical induction, to prove a statement that is asserted about every natural number n, there are two things to prove.

a) What is the first?

To see the answer, pass your mouse over the colored area.
To cover the answer again, click "Refresh" ("Reload").

b) What is the second?

c) Part a) contains the induction assumption. What is it?

Problem 2. Let S(n) = 2n − 1. Evaluate

a) S(k) = 2k − 1

b) S(k + 1) = 2(k + 1) − 1 = 2k + 2 − 1 = 2k + 1

Problem 3. The sum of the first n odd numbers is equal to the nth square:

1 + 3 + 5 + 7 + . . . + (2n − 1) = n²

a) To prove that by mathematical induction, what will be the induction
a) assumption?

b) On the basis of this assumption, what must we show?

c) Show that.