2.3 METHODS OF ARGUMENT 49R (abbreviating left and right, respectively). It may tum out that one of Lor R doesn't
exist (this will happen if n = 4), but that doesn't matter for what follows. Color the
vertices of L red, white, and blue in such a way that none of its adjacent vertices are
the same color. We know that this can be done by the inductive hypothesis!Note that we have also colored two of the vertices (x and y) of T, and one of these
vertices is also a vertex of R. Without loss of generality, let us assume that x is blueand y is white.
By the inductive hypothesis, it is possible to 3-color R using red, white and blue so
that no two of its vertices are the same color. But we have to be careful, since R sharestwo vertices (y and z) with T, one of which is already colored white. Consequently,
vertex z must be red. If we are lucky, the coloring of R will coincide with the coloring
of T. But what if it doesn't? No problem. Just rename the colors! In other words,
interchange the roles of red, blue, and white in our coloring of R. For example, if theoriginal coloring of R made y red and z blue, just recolor all of R's red vertices to be
white and all blue vertices red.
We're done; we've successfully 3-colored an arbitrarily triangulated (n+ I)-gonso that no two adjacent vertices are the same color. So P{n + 1) is true. _
TL·· ·
·\ i ,,'/
\,:,,1
yRNotice that we really needed the stronger inductive hypothesis in this proof. Per
haps we could have arranged things as in Example 2.3.5 on page 45 so that we decomposed the (n + 1 )-gon into a triangle and an n-gon. But it is not immediately obvious
that among the triangles of the triangulation, there is a "boundary" triangle that we can
pick. It is just easier to pick an arbitrary edge, and assume the truth of P{k) for all
k �n.
Behind the idea of strong induction is the notion that one should stay flexible in
defining hypotheses and conclusions. In the following example, we need an unusually
strong inductive hypothesis in order to make progress.
Example 2.3. 10 Prove that
Solution: We begin innocently by letting P{n) denote the above assertion. P(I) is
true, since I / 2 � 1/ V3. Now we try to prove P(n + I), given the inductive hypothesis
that P{n) is true. We would like to show that
{ (^1 ) (^3 ) (2n - I ) } (2n + I )^1
2 4
···
2;;- 2n+ 2 � y'3n+ 3·