Mathematical Investigations IV

Name

Mathematical Induction - Let the Dominoes Fall

Proofs, Old and New

In geometry you proved various theorems and exercises. In developing your proofs, you usually used what is called a Direct Proof. That is, you started with the given and through a series of logical steps, you arrived at what you were to prove.

For example, a direct proof would be an appropriate means for you to prove:

Given the figure at the right with
AB CD and E the midpoint of AD.
Prove: DAEB DDEC

A second form of proof, usually developed in geometry class, is called an Indirect Proof. In this situation, you started with the given, assumed that the conclusion was false and then derived a contradiction. For example, an indirect proof would be an appropriate means for proving:

There are infinitely many prime numbers.
[The assumption would be that there are only finitely many. We would then look for a contradiction.]

In this unit, we want to look at an additional way to verify relationships. We are going to use the First Principle of Mathematical Induction.

Mathematical Induction is an important technique for proving certain types of statements. In particular, it is often used to prove assertions dependent on a positive integer n, or occasionally, simply for non-negative integers. For example, consider the following propositions Pn.

(1) Pn: 1 + 3 + 5 + … + (2n – 1) = n2 for n ³ 1

(2) Pn: 1 + 2 + 22 + … + 2n = 2n+1 – 1 for n ³ 0

(3) Pn: 4n ³ 4n for n ³ 1

(4) Pn: is a multiple of 5 for n ³ 1

(5) Pn: The sum of the interior angles of a convex n-gon is 180(n – 2).

These are different types of examples that all make some statement for an arbitrary value of n. Proof by Mathematical Induction involves two basic steps. Very often, the method is described by thinking of a line of dominos. First, we have to be able to make the first domino fall. Secondly, if any one of the dominos in the line falls, the next one in the line will also fall. If both of these hold true, then when the first one falls, it will knock over the second one, the second will knock over the third, etc., so all of the dominos will eventually fall. Now, we need to translate this concept back into mathematics. If the proposition Pn is true for the starting value of n (usually n = 0 or 1) and if Pn is true when n is equal to some specific value of k always implies that it will be true for the next value of k, then this will imply that the statement will be true for all values of n.

To formalize this:

The First Principle of Mathematical Induction
Let P1, P2, P3, ... be a sequence of statements.
If it can be shown that
(1) P1 is true, and that
(2) Pn+1 is true whenever Pn is true,
then all of the statements P1, P2, P3, ... are true.

Note that there are two parts of each proof:

First you must show that a specific statement (usually P1) is true.

Second you must show that the (k+1)th statement is true based on the assumption that the kth statement is true.

Example 1:

Use Mathematical Induction to show that: [State that you are using M.Ind.]

Pn: 1 + 3 + 5 + 7 + ... + (2n - 1) = n2

is true for all positive integers.

[Note that P1 is the statement 1 = 12, P2 is the statement 1 + 3 = 22, etc.]

Step 1: Show that P1 is true. [Usually, this is rather trivial.]

Obviously (2 1 - 1) = 12.

Step 2: Show that if Pk is true, then Pk+1 is true.

Pn is 1 + 3 + 5 + ... + (2k-1) = k2. (Equation 1)

Assuming that is true, we need to show that ,
1 + 3 + 5 + ... + (2(k) - 1) + (2(k+1) - 1) = (k+1)2,
is true. [Restate what you wish to prove in terms of Pk+1.]

In order to complete this proof, we are going to start with the left side of the equation for Pn+1 and using substitution and various algebraic properties, derive the right hand side. This is similar to the technique we used to prove trigonometric identities.

1 + 3 + 5 + ... + (2k-1) + (2(k+1) - 1) = k2 + (2(k+1) - 1) [Substitution using Equation 1]

= k2 + 2k + 2 - 1

= k2 + 2k + 1

= (k + 1)2

Thus, Pk+1 is true, assuming that Pk is true, which is what we wished to prove.

Therefore, the sum of the first n odd integers is equal to n2.

[Summarize what you have just proven.]

Example 2:

Prove that the sum of the interior angles of a convex n-gon (a polygon with n-sides) is 180 (n-2).

Proof by Mathematical Induction [It is proper to state the method of proof.]

In this case, we will start with n = 3 instead of n = 1. [I think you know why.]

Step 1: Let n = 3 and we know that the sum of the measures of the angles of a triangle is 180 = 180 (n-2).

Step 2: Assume that for some k, the sum of the measure of the interior angles of the convex k-gon is 180 (k-2). Show that the sum of the measures of the interior angles of the convex (k+1)-gon is 180 ((k+1) - 2).

Proof: Let A1A2A3...AkAk+1 be a convex (k+1)-gon. From our assumption that Sk is true, we know that the sum of the angles of the polygon A1A2A3...Ak is 180 (k-2). We need to consider how many more degrees are added when the (k+1) vertex is added. From the figure at the right, it is clear that the sum of the angles of A1A2A3...AkAk+1 = (the sum of A1A2A3...Ak) + (the sum of DAkAk+1A1)

= 180 (k-2) + 180

= 180 (k-2 + 1)

= 180 ((k+1) - 2)

which is what we wished to show.

Therefore the sum of the interior angles of any convex n-gon is 180 (n-2).

Now it is your turn to try some. Use Mathematical Induction to prove the following. Remember to first show that the statement is true for a specific case (usually S1) and then show the general case.

Problem 1:

Prove proposition (2) Pn: 1 + 2 + 22 + … + 2n = 2n+1 – 1 for n ³ 0.

Step 1: Show that this is true for n = 0.

Step 2: Assume that Pk is true:

Pk:

[Show the finished statement for Pk+1 to know where you're headed.]

We wish to prove:

Pk+1:

Proof:

Which is what we wished to derive.

Therefore,


Follow the two step outline above to prove each of the following.

2. For all positive integers, 3 + 7 + 11 + . . . + (4n-1) = n(2n + 1)

Step 1:

Step 2: Assume that Pk is true:

Pk:

We wish to prove:

Pk+1:

Proof:

Which is what we wished to derive.

Therefore,

3. Using the First Principle of Mathematical Induction, prove .

4. For all positive integers, 1 1! + 2 2! + 3 3! + . . . + n n! = (n+1)! - 1

5. For all positive integers, 1 2 + 2 3 + 3 4 + . . . + n(n+1) =

6. Prove that the number of diagonals in a convex n-gon is .

7. Prove that 52n - 1 is divisible by 24 for every positive integer n.

8. Prove that + + . . . + = for k 1

9. Prove that if A = , then An =

Additional Problems

10. Given any square and any integer n > 5, prove that the square can be divided up into n squares (not necessarily the same size).

[Hint: Show that the statement is true for n = 6, 7, and 8.

Then show that if Sn is true, then Sn+3 is true.]

11. Prove

12. Show that, for all n 0,

13. Prove that every nonprime natural number greater than 1 can be written as a product of primes.

14. Prove that is even.

Induction .XXX Rev. F07