Section 2.2 Induction
117
should be rewritten to show that it is a direct proof of P(n) for any n, not a proof
by induction.
An inductive proof may be called for when its application is not as obvious as
in the above examples. The problem statement may not directly say “prove something about nonnegative integers.” Instead, there is some quantity in the statement
to be proved that can take on arbitrary nonnegative integer values.
eXAMPLe 19
A programming language might be designed with the following convention regarding multiplication: A single factor requires no parentheses, but the product “a
times b” must be written as (a)b. So the product
a # b # c # d # e # f # g
could be written in this language as
((((((a)b)c)d )e) f )g
or, for example,
((a)b)(((c)d )(e) f )g
depending on the order in which the products are formed. The result is the same
in either case.
We want to show that any product of factors can be written with an even number
of parentheses. The proof is by induction on the number of factors (this is where the
nonnegative integer comes in—it represents the number of factors in any product of
factors). For a single factor, there are 0 parentheses, an even number. Assume that
for any product of k factors there is an even number of parentheses. Now consider
a product P of k + 1 factors. P can be thought of as r times s where r has k factors
and s is a single factor. By the inductive hypothesis, r has an even number of parentheses. Then we write r times s as (r)s. This adds 2 more parentheses to the even
number of parentheses in r, giving P an even number of parentheses.
Here’s an important observation about the proof in Example 19: There are no
algebraic expressions! The entire proof is a verbal argument. For some proofs, we
can’t rely on just the crutch of nonverbal mathematical manipulations; we have to
use words.
eXAMPLe 20
A “tiling” problem gives a nice illustration of induction in a geometric setting.
An angle iron is an L-shaped piece that can cover 3 squares on a checkerboard
(Figure 2.3a). The problem is to show that for any positive integer n, a 2
n
× 2
n
checkerboard with one square removed can be tiled—completely covered—by
angle irons.
The base case is n = 1, which gives a 2 × 2 checkerboard. Figure 2.3b shows the
solution to this case if the upper right corner is removed. Removing any of the other
three corners works the same way. Assume that any 2
k
× 2
k
checkerboard with one
square removed can be tiled using angle irons. Now consider a checkerboard with
117
should be rewritten to show that it is a direct proof of P(n) for any n, not a proof
by induction.
An inductive proof may be called for when its application is not as obvious as
in the above examples. The problem statement may not directly say “prove something about nonnegative integers.” Instead, there is some quantity in the statement
to be proved that can take on arbitrary nonnegative integer values.
eXAMPLe 19
A programming language might be designed with the following convention regarding multiplication: A single factor requires no parentheses, but the product “a
times b” must be written as (a)b. So the product
a # b # c # d # e # f # g
could be written in this language as
((((((a)b)c)d )e) f )g
or, for example,
((a)b)(((c)d )(e) f )g
depending on the order in which the products are formed. The result is the same
in either case.
We want to show that any product of factors can be written with an even number
of parentheses. The proof is by induction on the number of factors (this is where the
nonnegative integer comes in—it represents the number of factors in any product of
factors). For a single factor, there are 0 parentheses, an even number. Assume that
for any product of k factors there is an even number of parentheses. Now consider
a product P of k + 1 factors. P can be thought of as r times s where r has k factors
and s is a single factor. By the inductive hypothesis, r has an even number of parentheses. Then we write r times s as (r)s. This adds 2 more parentheses to the even
number of parentheses in r, giving P an even number of parentheses.
Here’s an important observation about the proof in Example 19: There are no
algebraic expressions! The entire proof is a verbal argument. For some proofs, we
can’t rely on just the crutch of nonverbal mathematical manipulations; we have to
use words.
eXAMPLe 20
A “tiling” problem gives a nice illustration of induction in a geometric setting.
An angle iron is an L-shaped piece that can cover 3 squares on a checkerboard
(Figure 2.3a). The problem is to show that for any positive integer n, a 2
n
× 2
n
checkerboard with one square removed can be tiled—completely covered—by
angle irons.
The base case is n = 1, which gives a 2 × 2 checkerboard. Figure 2.3b shows the
solution to this case if the upper right corner is removed. Removing any of the other
three corners works the same way. Assume that any 2
k
× 2
k
checkerboard with one
square removed can be tiled using angle irons. Now consider a checkerboard with