Java Reference
In-Depth Information
Figure2.3
A two-coloring for the regions formed by three lines in the plane.
n but greater than 1. The induction hypothesis tells us that a is divisible by
some prime number. That same prime number must also divide n. Thus,
by mathematical induction, the theorem is correct.
2
Our next example of mathematical induction proves a theorem from geometry.
It also illustrates a standard technique of induction proof where we take n objects
and remove some object to use the induction hypothesis.
Example2.16
Define a two-coloring for a set of regions as a way of as-
signing one of two colors to each region such that no two regions sharing a
side have the same color. For example, a chessboard is two-colored. Fig-
ure 2.3 shows a two-coloring for the plane with three lines. We will assume
that the two colors to be used are black and white.
Theorem2.7
The set of regions formed by n infinite lines in the plane can
be two-colored.
Proof:
Consider the base case of a single infinite line in the plane. This line
splits the plane into two regions. One region can be colored black and the
other white to get a valid two-coloring. The induction hypothesis is that the
set of regions formed by n 1 infinite lines can be two-colored. To prove
the theorem for n, consider the set of regions formed by the n 1 lines
remaining when any one of the n lines is removed. By the induction hy-
pothesis, this set of regions can be two-colored. Now, put the nth line back.
This splits the plane into two half-planes, each of which (independently)
has a valid two-coloring inherited from the two-coloring of the plane with
n 1 lines. Unfortunately, the regions newly split by the nth line violate
the rule for a two-coloring. Take all regions on one side of the nth line and
reverse their coloring (after doing so, this half-plane is still two-colored).
Those regions split by the nth line are now properly two-colored, because
