46 CHAPTER 2 STRATEGIES FOR INVESTIGATING PROBLEMS
Let S be an arbitrary (n + 1 )-gon with vertices VI, V2,"., Vn+l. Decompose S
into the union of the triangle T with vertices VI, V2, V3 and the n-gon U with vertices
VI, V3, .•• , VII+I·The sum of the interior angles of S is equal to the sum of the interior angles of T
(which is 180 degrees), plus the sum of the interior angles of U [which is 180(n - 2 )
by the inductive hypothesis]. Hence the sum is 180+ 180(n - 2 ) = 180(n - 1), just
what we want.
We call this a "partial solution" because our argument has a subtle flaw. How do
we know that we can decompose the polygon as above to extract a triangle "on the
border?" There's no problem if the polygon is convex, but if it is concave, as in the
example, it is not quite obvious that this can always be done. See Problem 3.2.1 1 for a
suggestion.Example 2.3.6 Prove that if n is an integer greater than 3, then n! > (^211).
Solution: The base case, no = 4, is obviously true: 4! > 24. Now assume that
n! > 2 n for some n. We wish to use this to prove the "next" case; i.e. we wish to
prove that (n + I)! > 2 n+l. Let's think strategically: the left-hand side of the inductive
hypothesis is n!, and the left-hand side of the "goal" is (n + I)!. How to get from
one to the other? Multiply both sides of the inductive hypothesis by n + 1, of course.
Multiplying both sides of an inequality by a positive number doesn't change its truth,
so we get(n + I )! > 2 n (n + 1).
This is almost what we want, for the right-hand side of the "goal" is 211 +1 = 2 n ·2, andn + 1 is certainly greater than 2; i.e.,
(n + I)! > 211 (n + (^1) ) > 2 n. 2 = 2 n+ I. •
Induction arguments can be rather subtle. Sometimes it is not obvious what plays
the role of the "index" n. Sometimes the crux move is a clever choice of this variable,
and/or a neat method of traveling between P( n) and P( n + 1). Here is an example.
Example 2.3.7 The plane is divided into regions by straight lines. Show that it is
always possible to color the regions with two colors so that adjacent regions are never
the same color (like a checkerboard).
Solution: The statement of the problem does not involve integers directly. How
ever, when we experiment, we naturally start out with one line, then two, etc., so the