The Art and Craft of Problem Solving

2.3 METHODS OF ARGUMENT 47

natural thing to "induct on" is the number of lines we draw. In other words, we shall

prove the statement P(n): "If we divide the plane with n lines, then we can color the

regions with two colors so that adjacent regions are different colors." Let us call such

a coloration "good." Obviously, P(I) is true. Now assume that P(n) is true. Draw in

the (n + I )st line, and "invert" the coloration to the right of this line.

The regions to the left of the line still have a good coloration, and the regions to the
right of the line also have a good coloration (just the inverse of their original colors).
And the regions that share borders along the line will, by construction, be differently

colored. Thus the new coloration is good, establishing P(n + 1). •

Strong Induction

Strong induction gets its name because we use a "stronger" inductive hypothesis. After

establishing the base case, we assume that for some n, all of the following are true:

P(no),P(no + 1 ),P(no + 2), ... ,P(n),

and we use this assumption to prove that P(n + 1 ) is true. Sometimes strong induction

will work when standard induction doesn't. With standard induction, we use only the

truth of P(n) to deduce the truth of P(n+ 1). But sometimes, in order to prove P(n + 1),

we need to know something about "earlier" cases. If you liked the domino analogy,

consider a situation where the dominos have springs that keep them from falling, with

the springs getting stiffer as n increases. Domino n requires the force not only of the

nearest neighbor, but of all of the falling neighbors to the left, in order to fall.

OUT first example of strong induction continues the problem we began in Exam­

ple 2.2.1 on page 27.

Example 2.3.8 Recall that the sequence aO,at ,a 2 , ... satisfied at = I and

I

am+n+am-n = 2 (a2m+a 2 n) ( 8)

for all nonnegative integers m and n with m 2:: n. We deduced that ao = 0,a 2 = 4 and

that a 2 m = 4am for all m, and we conjectured the proposition P(n), which states that

an = n^2.

Solution: Certainly the base case P(O) is true. Now assume that P(k) is true for

k = 0, 1, ... ,U. We have [let m = u,n = 1 in (8) above]

I I

au+t +au-t = 2 (a 2 u +a 2 ) = 2 (4au +a 2 ) = 2au +2.