chap mathematical preliminaries figure two-coloring for the regions formed by three lines in the plane lines unfortunatelythe regions newly split by the nth line violate the rule for two-coloring take all regions on one side of the nth line and reverse their coloring (after doing sothis half-plane is still two-coloredthose regions split by the nth line are now properly two-coloredbecause the part of the region to one side of the line is now black and the region to the other side is now white thusby mathematical inductionthe entire plane is two-colored compare the proof of theorem with that of theorem for theorem we took collection of stamps of size (whichby the induction hypothesismust have the desired propertyand from that "builta collection of size that has the desired property we therefore proved the existence of some collection of stamps of size with the desired property for theorem we must prove that any collection of lines has the desired property thusour strategy is to take an arbitrary collection of linesand "reduceit so that we have set of lines that must have the desired property because it matches the induction hypothesis from therewe merely need to show that reversing the original reduction process preserves the desired property in contrastconsider what would be required if we attempted to "buildfrom set of lines of size to one of size we would have great difficulty justifying that all possible collections of lines are covered by our building process by reducing from an arbitrary collection of lines to something lesswe avoid this problem this section' final example shows how induction can be used to prove that recursive function produces the correct result