if we let A (n) denote the number of regions generated by n lines, we see that
with A (1) = 2. From this simple recursion we then calculate A (2) = 4, A (3) = 7,
A (4) = 11, and so on.
To get a formula for A (n) and to show that it is correct, we use induction. If
we conjecture that
then
justifies the inductive step. The basis is easily checked, completing the
argument.
In this example we have been a little less formal in identifying the basis,
inductive assumption, and inductive step, but they are there and are essential. To
keep our subsequent discussions from becoming too formal, we will generally
prefer the style of this second example. However, if you have difficulty in
following or constructing a proof, go back to the more explicit form of Example
1.5.
Proof by contradiction is another powerful technique that often works when
everything else fails. Suppose we want to prove that some statement P is true.
We then assume, for the moment, that P is false and see where that assumption
leads us. If we arrive at a conclusion that we know is incorrect, we can lay the
blame on the starting assumption and conclude that P must be true. The
following is a classic and elegant example.
Example 1.7
A rational number is a number that can be expressed as the ratio of two integers