The Art and Craft of Problem Solving

Mathematical Induction

2.3 METHODS OF ARGUMENT 45

This is a very powerful method for proving assertions that are "indexed" by integers;
for example:

• The sum of the interior angles of any n-gon is 180(n - 2) degrees.

• The inequality n! > 2 n is true for all positive integers n ;:::: 4.

Each assertion can be put in the form

P(n) is true/or all integers n ;:::: no,

where P( n) is a statement involving the integer n and no is the "starting point." There

are two forms of induction, standard and strong.

Standard Induction

Here's how standard induction works:

1. Establish the truth of P(no). This is called the "base case," and it is usually an

easy exercise.

2. Assume that P(n) is true for some arbitrary integer n. This is called the induc­

tive hypothesis. Then show that the inductive hypothesis implies that P( n + 1)

is also true.

This is sufficient to prove P(n) for all integers n ;:::: no, since P(no) is true by (1) and

(2) implies that P( no + 1) is true, and now (2) implies that P( no + 1 + 1) is true, etc.

Here's an analogy. Suppose you arranged infinitely many dominos in a line, cor­

responding to statements P(1 ),P(2), .... If you make the first domino fall to the right,

then you can be sure that all of the dominos will fall, provided that whenever one
domino falls, it knocks down its neighbor to the right.

2 3 4 n n+l

Knocking the first one down is the same as establishing the base case. Showing that

falling domino knocks down its neighbor is equivalent to showing that P(n) implies

P( n + 1) for all n ;:::: 1.

Let's use induction to prove the two examples above.

Example 2.3.5 Prove that the sum of the interior angles of any n-gon is 180(n - 2)

degrees.

Partial Solution: The base case (no = 3) is the well-known fact that the sum of

the interior angles of any triangle is 180 degrees (see 8.2.7 for suggestions for a proof).

Now assume that the theorem is true for n-gons for some n ;:::: 3. We will show that this

implies truth for (n + 1 )-gons; i.e., the sum of the interior angles of any (n + 1 )-gon is

180(n + 1 -2) = 180(n - 1) degrees.