Here we introduce the symbol that is used in this book to denote the end of
a proof.
Inductive reasoning can be difficult to grasp. It helps to notice the close
connection between induction and recursion in programming. For example, the
recursive definition of a function f (n), where n is any positive integer, often has
two parts. One involves the definition of f (n +1) in terms of f (n), f (n − 1),…,f
(1). This corresponds to the inductive step. The second part is the “escape” from
the recursion, which is accomplished by defining f (1), f (2),…, f (k)
nonrecursively. This corresponds to the basis of induction. As in induction,
recursion allows us to draw conclusions about all instances of the problem, given
only a few starting values and using the recursive nature of the problem.
Sometimes, a problem looks difficult until we look at it in just the right way.
Often looking at it recursively simplifies matters greatly.
Example 1.6
A set l 1 , l 2 ,…, l n of mutually intersecting straight lines divides the plane into a
number of separated regions. A single line divides the plane into two parts, two
lines generate four regions, three lines make seven regions, and so on. This is
easily checked visually for up to three lines, but as the number of lines increases
it becomes difficult to spot a pattern. Let us try to solve this problem recursively.
Look at Figure 1.3 to see what happens if we add a new line l n+1 to existing n
lines. The region to the left of l 1 is divided into two new regions, so is the region
to the left of l 2 , and so on until we get to the last line. At the last line, the region
to the right of l n is also divided. Each of the n intersections then generates one
new region, with one extra at the end. So,
Figure 1.3
a proof.
Inductive reasoning can be difficult to grasp. It helps to notice the close
connection between induction and recursion in programming. For example, the
recursive definition of a function f (n), where n is any positive integer, often has
two parts. One involves the definition of f (n +1) in terms of f (n), f (n − 1),…,f
(1). This corresponds to the inductive step. The second part is the “escape” from
the recursion, which is accomplished by defining f (1), f (2),…, f (k)
nonrecursively. This corresponds to the basis of induction. As in induction,
recursion allows us to draw conclusions about all instances of the problem, given
only a few starting values and using the recursive nature of the problem.
Sometimes, a problem looks difficult until we look at it in just the right way.
Often looking at it recursively simplifies matters greatly.
Example 1.6
A set l 1 , l 2 ,…, l n of mutually intersecting straight lines divides the plane into a
number of separated regions. A single line divides the plane into two parts, two
lines generate four regions, three lines make seven regions, and so on. This is
easily checked visually for up to three lines, but as the number of lines increases
it becomes difficult to spot a pattern. Let us try to solve this problem recursively.
Look at Figure 1.3 to see what happens if we add a new line l n+1 to existing n
lines. The region to the left of l 1 is divided into two new regions, so is the region
to the left of l 2 , and so on until we get to the last line. At the last line, the region
to the right of l n is also divided. Each of the n intersections then generates one
new region, with one extra at the end. So,
Figure 1.3