Section 2.2 Induction
113
In this family, each offspring has two children; thus the number of offspring at
generation k + 1 will be twice the number at generation k, or P(k + 1) = 2P(k).
By the inductive assumption, P(k) = 2
k
, so
P(k + 1) = 2P(k) = 2(2
k
) = 2
k+1
and so indeed
P(k + 1) = 2
k+1
This completes our proof. Now that we have set our mind at ease about the
Smith clan, we can apply the inductive proof technique to less obvious problems.
eXAMPLe 14
Prove that the equation
1 + 3 + 5 + c + (2n − 1) = n
2
(1)
is true for any positive integer n. Here the property P(n) is equation (1). (Notice
that P(n) is a property of n, or—in language from Chapter 1—a unary predicate. It
is a statement about n, expressed here as an equation. Thus it is incorrect to write
something like P(n) = 1 + 3 + 5 + g+ (2n − 1).)
The left side of this equation is the sum of all the odd integers from 1 to
2n − 1. The right side is a formula for the value of this sum. Although we can
verify the truth of this equation for any particular value of n by substituting that
value for n, we cannot substitute all possible positive integer values. Thus a proof
by exhaustion does not work. A proof by mathematical induction is appropriate.
The basis step is to establish P(1), which is equation (1) when n has the value
1. When we substitute 1 for n in the left side of equation (1), we get the sum of all
the odd integers starting at 1 and ending at 2(1) − 1 = 1. The sum of all the odd
numbers from 1 to 1 equals 1. When we substitute 1 for n in the formula on the
right side of this equation, we get (1)
2
. Therefore
P(1): 1 = 1
2
This is certainly true. For the inductive hypothesis, we assume P(k) for an arbitrary
positive integer k, which is equation (1) when n has the value k, or
P(k): 1 + 3 + 5 + c + (2k − 1) = k
2
(2)
(Note that P(k) is not the equation (2k − 1) = k
2
, which is true only for k = 1.)
Using the inductive hypothesis, we want to show P(k + 1), which is equation (1)
when n has the value k + 1, or
P(k + 1): 1 + 3 + 5 + c + 32(k + 1) − 1 4 0 (k + 1)
2
(3)
(The question mark over the equals sign is to remind us that this is the fact we want
to prove, as opposed to something we already know.)
113
In this family, each offspring has two children; thus the number of offspring at
generation k + 1 will be twice the number at generation k, or P(k + 1) = 2P(k).
By the inductive assumption, P(k) = 2
k
, so
P(k + 1) = 2P(k) = 2(2
k
) = 2
k+1
and so indeed
P(k + 1) = 2
k+1
This completes our proof. Now that we have set our mind at ease about the
Smith clan, we can apply the inductive proof technique to less obvious problems.
eXAMPLe 14
Prove that the equation
1 + 3 + 5 + c + (2n − 1) = n
2
(1)
is true for any positive integer n. Here the property P(n) is equation (1). (Notice
that P(n) is a property of n, or—in language from Chapter 1—a unary predicate. It
is a statement about n, expressed here as an equation. Thus it is incorrect to write
something like P(n) = 1 + 3 + 5 + g+ (2n − 1).)
The left side of this equation is the sum of all the odd integers from 1 to
2n − 1. The right side is a formula for the value of this sum. Although we can
verify the truth of this equation for any particular value of n by substituting that
value for n, we cannot substitute all possible positive integer values. Thus a proof
by exhaustion does not work. A proof by mathematical induction is appropriate.
The basis step is to establish P(1), which is equation (1) when n has the value
1. When we substitute 1 for n in the left side of equation (1), we get the sum of all
the odd integers starting at 1 and ending at 2(1) − 1 = 1. The sum of all the odd
numbers from 1 to 1 equals 1. When we substitute 1 for n in the formula on the
right side of this equation, we get (1)
2
. Therefore
P(1): 1 = 1
2
This is certainly true. For the inductive hypothesis, we assume P(k) for an arbitrary
positive integer k, which is equation (1) when n has the value k, or
P(k): 1 + 3 + 5 + c + (2k − 1) = k
2
(2)
(Note that P(k) is not the equation (2k − 1) = k
2
, which is true only for k = 1.)
Using the inductive hypothesis, we want to show P(k + 1), which is equation (1)
when n has the value k + 1, or
P(k + 1): 1 + 3 + 5 + c + 32(k + 1) − 1 4 0 (k + 1)
2
(3)
(The question mark over the equals sign is to remind us that this is the fact we want
to prove, as opposed to something we already know.)