Hungerford T.W., Shaw D.J. Contemporary Precalculus: A Graphing Approach
Подождите немного. Документ загружается.
We have proved that claim
is valid for each positive integer k. We have not
proved that the original statement is true for any value of n, but only that if
it is true for n k, then it is also true for n k 1. Applying this fact when
k 1, 2, 3, . . . , we see that
If the statement is true for n 1, then it is also true for
n 1 1 2;
If the statement is true for n 2, then it is also true for
n 2 1 3;
If the statement is true for n 3, then it is also true for
n 3 1 4;
.
.
.
If the statement is true for n 50, then it is also true for
n 50 1 51;
If the statement is true for n 51, then it is also true for
n 51 1 52;
.
.
.
and so on.
We are finally in a position to prove the original statement:
1 2 3
n n(n 1)/2.
Obviously, it is true for n 1, since 1 1(2)/2. Now apply in turn each of the
propositions on list . Since the statement is true for n 1, it must also be true
for n 2, and hence for n 3, and hence for n 4, and so on, for every value
of n. Therefore, the original statement is true for every positive integer n.
The preceding proof is an illustration of the following principle.
Property (i) is simply a statement of fact. To verify that it holds, you must
prove the given statement is true for n 1. This is usually easy, as in the preced-
ing example.
Property (ii) is a conditional property. It does not assert that the given state-
ment is true for n k, but only that if it is true for n k, then it is also true for n
k 1. So to verify that property (ii) holds, you need only prove this conditional
proposition.
If the statement is true for n k, then it is also true for n k 1.
To prove this or any conditional proposition, you must proceed as in the previous
example: Assume the “if” part and use this assumption to prove the “then” part.
As we saw earlier, the same argument will usually work for any possible k. Once
this conditional proposition has been proved, you can use it together with prop-
erty (i) to conclude that the given statement is necessarily true for every n, just as
in the preceding example.
866 CHAPTER 12 Discrete Algebra
144444442444444443
Principle of
Mathematical
Induction
Suppose there is given a statement involving the positive integer n and that
(i) The statement is true for n 1.
(ii) If the statement is true for n k (where k is any positive integer), then
the statement is also true for n k 1.
Then the statement is true for every positive integer n.
Thus proof by mathematical induction reduces to two steps.
Step 1 Prove that the given statement is true for n 1.
Step 2 Let k be a positive integer. Assume that the given statement is true for
n k. Use this assumption to prove that the statement is true for n
k 1.
Step 2 may be performed before step 1 if you wish. Step 2 is sometimes referred
to as the inductive step. The assumption that the given statement is true for
n k in this inductive step is called the induction hypothesis.
EXAMPLE 1
Prove that 2
n
n for every positive integer n.
SOLUTION Here, the statement involving n is 2
n
n.
Step 1 When n 1, we have the statement 2
1
1. This is obviously true.
Step 2 Let k be any positive integer. We assume that the statement is true for
n k, that is, we assume that 2
k
k. We shall use this assumption to
prove that the statement is true for n k 1, that is, that 2
k1
k 1.
We begin with the induction hypothesis: 2
k
k.* Multiplying both sides of this
inequality by 2 yields
2
2
k
2k
2
k1
2k.
Since k is a positive integer, we know that k 1. Adding k to each side of the
inequality k 1, we have
k k k 1
2k k 1.
Combining this result with inequality , we see that
2
k1
2k k 1.
The first and last terms of this inequality show that 2
k1
k 1. Therefore, the
statement is true for n k 1. This argument works for any positive integer k.
Thus, we have completed the inductive step. By the Principle of Mathematical
Induction, we conclude that 2
n
n for every positive integer n. ■
EXAMPLE 2
The first n positive even integers are 2, 4, 6, 8, . . . , 2n. Prove that their sum is
n
2
n.
SOLUTION The statement to be proved is this: for each positive integer n,
2 4 6 8 2n n
2
n.
SECTION 12.5 Mathematical Induction 867
*This is the point at which you usually must do some work. Remember that what follows is the
“finished proof.” It does not include all the thought, scratch work, false starts, and so on that were done
before this proof was actually found.
Step 1 When n 1, the statement is 2 1
2
1, which is certainly true.
Step 2 Let k be a positive integer and assume that the statement is true for
n k. In other words, the induction hypothesis is
(
*
) 2 4 6 2k k
2
k.
We must use this to show that the statement is true for n k 1, that
is, we must show that
(
**
) 2 4 6 2k 2(k 1) (k 1)
2
(k 1).
We begin with the left side of equation (
**
) and use algebra and the
induction hypothesis to show that it equals the right side.
2 4 6 2k 2(k 1)
(2 4 6 2k) 2(k 1) [Regroup.]
(k
2
k) 2(k 1) [Induction hypothesis]
k
2
k 2k 2 [Expand.]
†
(k
2
2k 1) (k 1) [Rearrange terms.]
(k 1)
2
(k 1) [Factor first expression.]
The first and last lines of the preceding computation form equation
(
**
), so we have proved that if the original statement is true for n
k, then it is also true for n k 1. By the Principle of Mathematical
Induction we conclude that
2 4 6 8 2n n
2
n for every positive integer n. ■
EXAMPLE 3
Simple arithmetic shows that
7
2
3
2
49 9 40 4
10
and
7
3
3
3
343 27 316 4
79.
In each case, 4 is a factor. These examples suggest that
For each positive integer n, 4 is a factor of 7
n
3
n
.
This conjecture can be proved by induction as follows.
Step 1 When n 1, the statement is “4 is a factor of 7
1
3
1
.” Since
7
1
3
1
4 4
1, the statement is true for n 1.
Step 2 Let k be a positive integer and assume that the statement is true for
n k, that is, that 4 is a factor of 7
k
3
k
. Let us denote the other fac-
tor by D, so that the induction hypothesis is: 7
k
3
k
4D. We must
868 CHAPTER 12 Discrete Algebra
†
At this point, some algebraic trial and error (which is omitted) was used to find the next step in
showing that this expression is the same as the right side of equation (
**
). We were guided by the fact
that (k 1)
2
k
2
2k 1.
use this assumption to prove that the statement is true for
n k 1, that is, that 4 is a factor of 7
k1
3
k1
. Here is the proof.
7
k1
3
k1
7
k1
7
3
k
7
3
k
3
k1
[Since 7
3
k
7
3
k
0]
†
7(7
k
3
k
) (7 3)3
k
[Factor]
7(4D) (7 3)3
k
[Induction hypothesis]
7(4D) 4
3
k
[7 3 4]
4(7D 3
k
). [Factor out 4]
From this last line, we see that 4 is a factor of 7
k1
3
k1
. Thus, the statement is
true for n k 1, and the inductive step is complete. Therefore, by the Principle
of Mathematical Induction, the conjecture is actually true for every positive
integer n. ■
Another example of mathematical induction, the proof of the Binomial The-
orem, is given at the end of this section.
Sometimes a statement involving the integer n may be false for n 1 and
(possibly) other small values of n but true for all values of n beyond a particular
number. For instance, the statement 2
n
n
2
is false for n 1, 2, 3, and 4. But it
is true for n 5 and all larger values of n. A variation on the Principle of Mathe-
matical Induction can be used to prove this fact and similar statements. See Exer-
cise 28 for details.
A COMMON MISTAKE WITH INDUCTION
It is sometimes tempting to omit step 2 of an inductive proof when the given state-
ment can easily be verified for small values of n, especially if a clear pattern
seems to be developing. As the next example shows, however, omitting step 2 may
lead to error.
EXAMPLE 4
An integer ( 1) is said to be prime if its only positive integer factors are itself and
1. For instance, 11 is prime, since its only positive integer factors are 11 and 1. But
15 is not prime because it has factors other than 15 and 1 (namely, 3 and 5). For
each positive integer n, consider the number
f(n) n
2
n 11.
You can readily verify that
f(1) 11, f(2) 13, f(3) 17, f(4) 23, f(5) 31
and that each of these numbers is prime. Furthermore, there is a clear pattern:
The first two numbers (11 and 13) differ by 2; the next two (13 and 17) differ by 4;
the next two (17 and 23) differ by 6; and so on. On the basis of this evidence, we
might conjecture that
For each positive integer n, the number f (n) n
2
n 11 is prime.
SECTION 12.5 Mathematical Induction 869
†
Adding and subtracting the same quantity is often a useful technique to rewrite an expression without
changing its value.
We have seen that this conjecture is true for n 1, 2, 3, 4, 5. Unfortunately, how-
ever, it is false for some values of n. For instance, when n 11,
f (11) 11
2
11 11 11
2
121.
But 121 is obviously not prime, since it has a factor other than 121 and 1, namely,
11. You can verify that the statement is also false for n 12 but true for n 13.
■
In the preceding example, the proposition
If the statement is true for n k, then it is true for n k 1
is false when k 10 and k 1 11. If you were not aware of this and tried to
complete step 2 of an inductive proof, you would not have been able to find a
valid proof for it. Of course, the fact that you can’t find a proof of a proposition
doesn’t always mean that no proof exists. But when you are unable to complete
step 2, you are warned that there is a possibility that the given statement may be
false for some values of n. This warning should prevent you from drawing any
wrong conclusions.
PROOF OF THE BINOMIAL THEOREM
We shall use induction to prove that for every positive integer n,
(x y)
n
x
n
n
1
x
n1
y
n
2
x
n2
y
2
n
3
x
n3
y
3
n
n 1
xy
n1
y
n
.
This theorem was discussed and its notation explained in Section 12.4.
Step 1 When n 1, there are only two terms on the right side of
the preceding equation, and the statement reads (x y)
1
x
1
y
1
.
This is certainly true.
Step 2 Let k be any positive integer and assume that the theorem is true for
n k, that is, that
(x y)
k
x
k
1
k
x
k1
y
2
k
x
k2
y
2
k
r
x
kr
y
r
k
k
1
xy
k1
y
k
.
[On the right side of this equation, we have included a typical middle term
k
r
x
kr
y
r
. The sum of the exponents is k, and the bottom part of the binomial
coefficient is the same as the y exponent.] We shall use this assumption to prove
that the theorem is true for n k 1, that is, that
(x y)
k1
x
k1
k
1
1
x
k
y
k
2
1
x
k1
y
2
k
r
1
1
x
kr
y
r1
k
k
1
xy
k
y
k1
.
We have simplified some of the terms on the right side; for instance,
(k 1) 1 k and (k 1) (r 1) k r. But this is the correct statement
870 CHAPTER 12 Discrete Algebra
for n k 1: The coefficients of the middle terms are
k
1
1
,
k
2
1
,
k
3
1
, and so on; the sum of the exponents of each middle term is k 1, and
the bottom part of each binomial coefficient is the same as the y exponent.
To prove the theorem for n k 1, we shall need this fact about binomial
coefficients: For any integers r and k with 0 r k,
r
k
1
k
r
k
r
1
1
.
A proof of this fact is outlined in Exercise 69 on page 864.
To prove the theorem for n k 1, we first note that
(x y)
k1
(x y)(x y)
k
.
Applying the induction hypothesis to (x y)
k
, we see that
(x y)
k1
(x y)
x
k
1
k
x
k1
y
2
k
x
k2
y
2
k
r
x
kr
y
r
r
k
1
x
k(r1)
y
r1
k
k
1
xy
k1
y
k
x
x
k
1
k
x
k1
y y
k
y
x
k
1
k
x
k1
y y
k
.
Next we multiply out the right side. Remember that multiplying by x increases the
x exponent by 1 and multiplying by y increases the y exponent by 1.
(x y)
k1
x
k1
1
k
x
k
y
2
k
x
k1
y
2
k
r
x
kr1
y
r
r
k
1
x
kr
y
r1
k
k
1
x
2
y
k1
xy
k
x
k
y
1
k
x
k1
y
2
2
k
x
k2
y
3
k
r
x
kr
y
r1
r
k
1
x
k(r1)
y
r2
k
k
1
xy
k
y
k1
x
k1
1
k
1
x
k
y
2
k
1
k
x
k1
y
2
r
k
1
k
r
x
kr
y
r1
1
k
k
1
xy
k
y
k1
.
Now apply statement to each of the coefficients of the middle terms. For
instance, with r 1, statement shows that
2
k
1
k
k
2
1
.
Similarly, with r 0,
1
k
1
1
k
0
k
k
1
1
,
SECTION 12.5 Mathematical Induction 871
and so on. Then the expression above for (x y)
k1
becomes
(x y)
k1
x
k1
k
1
1
x
k
y
k
2
1
x
k1
y
2
k
r
1
1
x
kr
y
r1
k
k
1
xy
k
y
k1
.
Since this last statement says that the theorem is true for n k 1, the inductive
step is complete. By the Principle of Mathematical Induction, the theorem is true
for every positive integer n.
872 CHAPTER 12 Discrete Algebra
EXERCISES 12.5
In Exercises 1–18, use mathematical induction to prove that
each of the given statements is true for every positive integer n.
1. 1 2 2
2
2
3
2
4
2
n1
2
n
1
2. 1 3 3
2
3
3
3
4
3
n1
3
n
2
1
3. 1 3 5 7 (2n 1) n
2
4. 1
2
2
2
3
2
n
2
n(n 1)
6
(2n 1)
5.
1
2
1
4
1
8
2
1
n
1
2
1
n
6.
1
3
1
9
2
1
7
3
1
n
1
2
2
1
3
n
7.
1
1
2
2
1
3
3
1
4
n(n
1
1)
n
n
1
8.
1
1
1
1
1
2
1
1
3
1
1
n
n 1
9. n 2 n 10. 2n 2 n
11. 3
n
3n 12. 3
n
1 2n
13. 3n n 1 14.
3
2
n
n
15. 3 is a factor of 2
2n1
1
16. 5 is a factor of 2
4n2
1
17. 64 is a factor of 3
2n2
8n 9
18. 64 is a factor of 9
n
8n 1
19. Let c and d be fixed real numbers. Prove that
c (c d) (c 2d) (c 3d)
[c (n 1)d ]
n[2c (
2
n 1)d]
20. Let r be a fixed real number with r 1. Prove that
1 r r
2
r
3
r
n1
r
r
n
1
1
.
[Remember: 1 r
0
; so when n 1, the left side reduces to
r
0
1.]
21. (a) Write each of x
2
y
2
, x
3
y
3
, and x
4
y
4
as a prod-
uct of x y and another factor.
(b) Make a conjecture as to how x
n
y
n
can be written as a
product of x y and another factor. Use induction to
prove your conjecture.
22. Let x
1
2
; x
2
2
2
;
x
3
2
2
2
; and so on. Prove that x
n
2 for
every positive integer n.
In Exercises 23–27, if the given statement is true, prove it. If it
is false, give a counterexample.
23. Every odd positive integer is prime.
24. The number n
2
n 17 is prime for every positive
integer n.
25. (n 1)
2
n
2
1 for every positive integer n.
26. 3 is a factor of the number n
3
n 3 for every positive
integer n.
27. 4 is a factor of the number n
4
n 4 for every positive
integer n.
28. Let q be a fixed integer. Suppose a statement involving the
integer n has these two properties:
(i) The statement is true for n q.
(ii) If the statement is true for n k (where k is any integer
with k q), then the statement is also true for
n k 1.
Then we claim that the statement is true for every integer n
greater than or equal to q.
(a) Give an informal explanation that shows why this claim
should be valid. Note that when q 1, this claim is pre-
cisely the Principle of Mathematical Induction.
(b) The claim made before part (a) will be called the
Extended Principle of Mathematical Induction. State
the two steps necessary to use this principle to prove
that a given statement is true for all n q. (See the
discussion on pages 866–867.)
CHAPTER 12 Review 873
In Exercises 29–34, use the Extended Principle of Mathemati-
cal Induction (Exercise 28) to prove the given statement.
29. 2n 4 n for every n 5. (Use 5 for q here.)
30. Let r be a fixed real number with r 1. Then
(1 r)
n
1 nr for every integer n 2.
(Use 2 for q here.)
31. n
2
n for all n 2 32. 2
n
n
2
for all n 5
33. 3
n
2
n
10n for all n 4
34. 2n n! for all n 4
THINKERS
35. Let n be a positive integer. Suppose that there are three pegs
and on one of them, n rings are stacked, each ring being
smaller in diameter than the one below it (see the figure).
We want to transfer the stack of rings to another peg
according to these rules: (i) Only one ring may be moved at
a time; (ii) a ring can be moved to any peg, provided that it
is never placed on top of a smaller ring; (iii) the final order
of the rings on the new peg must be the same as the original
order on the first peg.
(a) What is the smallest possible number of moves when
n 2? n 3? n 4?
(b) Make a conjecture as to the smallest possible number of
moves required for any n. Prove your conjecture by
induction.
36. The basic formula for compound interest T(x) P(1 r)
x
was discussed on page 369. Prove by induction that the for-
mula is valid whenever x is a positive integer. [Note: P and
r are assumed to be constant.]
37. Use induction to prove DeMoivre’s Theorem: For any com-
plex number z r(cos u i sin u) and any positive integer n,
z
n
r
n
[cos(nu) i sin(nu)].
Chapter 12 Review
IMPORTANT CONCEPTS
Section 12.1
Sequence 826
Term 826
Constant sequence 828
Recursively defined sequence 829
Fibonacci sequence 830
Summation notation 831
Summation index 832
Partial sum 834
Section 12.2
Arithmetic sequence 837
Common difference 838
nth term formula 838–839
Partial sum formulas 840
Section 12.3
Geometric sequence 844
Common ratio 844
nth term formula 845
Partial sum formula 847
Special Topics: 12.3.A
Infinite series 852
Infinite geometric series 853
Section 12.4
n factorial (n!) 857
Binomial coefficient 858
Pascal’s triangle 859
Binomial Theorem 860
Section 12.5
Principle of Mathematical Induction
866
Inductive step 867
Induction hypothesis 867
IMPORTANT FACTS & FORMULAS
■
In an arithmetic sequence {a
n
} with common difference d,
a
n
a
1
(n 1)d,
k
n1
a
n
2
k
(a
1
a
k
),
k
n1
a
n
ka
1
k(k
2
1)
d.
874 CHAPTER 12 Discrete Algebra
■
In a geometric sequence {a
n
} with common ratio r 1,
a
n
r
n1
a
1
,
k
n1
a
n
a
1
1
1
r
r
k
.
■
The sum of the infinite geometric series a
1
ra
1
r
2
a
1
(with |r | 1) is
1
a
1
r
.
■
n! 1
2
3
(n 2)(n 1)n
■
n
r
r!(n
n
!
r)!
n
C
r
■
The Binomial Theorem:
(x y)
n
x
n
n
1
x
n1
y
n
2
x
n2
y
2
n
3
x
n3
y
3
n
n
1
xy
n1
y
n
n
j0
n
j
x
nj
y
j
In Questions 1–4, find the first four terms of the sequence {a
n
}.
1. a
n
2n 5 2. a
n
3
n
27
3. a
n
n
1
2
4. a
n
(1)
n1
(n 1)
In Questions 5 and 6, find a formula for the nth term of the
sequence.
5.
2
5
,
2
4
5
,
1
8
25
,
6
1
2
6
5
,
6.
4
,
10
,
28
,
82
, [Hint: 4 3 1 and 10
9 1.]
7. The Pension Benefit Guaranty Corporation (PBGC) is the
government agency that insures pensions. Data and projec-
tions from the Center on Federal Financial Institutions show
that PBGC’s annual cash payouts (in billions of dollars) are
approximated by the sequence {a
n
}, where
a
n
.0035x
2
.5x 2.5 (n 4),
and n 4 corresponds to 2004.
(a) How much did PBGC pay out in 2004? In 2006? What
will it pay out in 2010?
(b) Approximately when will the yearly cash payout
exceed $9.6 billion?
In Questions 8 and 9, express the given sum in summation
notation. Do not find the sum.
8.
ln
1
2
ln
1
4
ln
1
8
ln
1
16
ln
1
256
9.
1
2
2
3
3
4
4
5
1
9
0
In Questions 10–12, find the sum.
10.
4
n0
2
n
(n 1) ? 11.
4
n2
(3n
2
n 1) ?
12.
4
n1
n
2
9
n5
(n 1)
2
13. Find the fourth partial sum of the sequence {a
n
}, where
a
1
1/9 and a
n
3a
n1
.
14. Find the fifth partial sum of the sequence {a
n
}, where a
1
4 and a
n
3a
n1
2.
15. Average tuition and fees each year in private colleges can be
approximated by the sequence given by
b
n
11,561.7
e
.05642n
,
where n 0 corresponds to the 1990–1991 school year.*
(a) What were the average tuition and fees in 2004–2005?
What are they this year?
(b) If you started at a private college with average tuition
and fees in Fall 1990 and graduated after four years,
what was the total that you (or your parents) spent on
tuition and fees?
(c) Do part (b), assuming that you started in Fall 2004.
16. Find the total cash payout by PBGC in Question 7 for the
years 2004–2008 (inclusive).
In Questions 17–20, find a formula for a
n
; assume that the
sequence is arithmetic.
17. a
1
3 and the common difference is 6.
18. a
2
4 and the common difference is 3.
19. a
1
5 and a
3
7.
20. a
3
2 and a
7
1.
21. Find the 11th partial sum of the arithmetic sequence with
a
1
5 and common difference 2.
22. Find the 12th partial sum of the arithmetic sequence with
a
1
3 and a
12
16.
REVIEW QUESTIONS
*Based on data from the U.S. Center for Educational Statistics.
CHAPTER 12 Review 875
*Based on data from TI annual reports.
†
Based on data from the Statistical Abstracts of the United States 2007.
In Questions 23–26, find a formula for a
n
; assume that the
sequence is geometric.
23. a
1
2 and the common ratio is 3.
24. a
1
5 and the common ratio is 1/2.
25. a
2
192 and a
7
6.
26. a
3
9/2 and a
6
243/16.
27. Find the fifth partial sum of the geometric sequence with
a
1
1/4 and common ratio 3.
28. Find the sixth partial sum of the geometric sequence with
a
1
5 and common ratio 1/2.
29. Find numbers b, c, d such that 4, b, c, d, 23 are the first five
terms of an arithmetic sequence.
30. Find numbers c and d such that 8, c, d, 27 are the first four
terms of a geometric sequence.
31. The net revenue in year n (in billions of dollars) of Texas
Instruments is approximated by a geometric series {a
n
} in
which n 1 corresponds to 2001.*
(a) If net revenues were $7.898 billion in 2001 and $8.972
billion in 2002, find a formula for a
n
in which the com-
mon ratio r is rounded to three decimal places.
(b) What were net revenues in 2005?
(c) What were the total net revenues from 2001 to 2006
(inclusive)?
32. Retail expenditures on boating (in billions of dollars) is ap-
proximated by an arithmetic sequence {b
n
} in which n 1
corresponds to 2000.
†
(a) If expenditures were $27.217 billion in 2000 and
$28.923 billion in 2001, find the expenditures in 2006.
(b) What were the total expenditures from 2000 to 2005
(inclusive)?
33. When a patient is given a 100 mg dose of furocimide, the
amount of the drug remaining in the bloodstream t hours
later is given by C(t) 100 e
1.3863t
. Suppose the patient
receives a 100 mg dose every two hours and let b
n
denote
the total amount of furocimide in the bloodstream after
n doses.
(a) Find a formula for the nth term of the sequence {b
n
}.
(b) How much furocimide is in the patient’s bloodstream
after the 5
th
dose?
(c) Find the approximate steady state amount of furocimide
when the doses are given every two hours for a long
time.
In Questions 34–36, find the sums, if they exist.
34.
n1
3
2
n1
35.
n1
2
n
1
1
36.
n1
4
n
1
37.
1
1
5
2
?
38.
1
3
8
?
39.
2
6
0
!1
!5
7
!
!
? 40.
7!
4!
5!
?
41. Let n be a positive integer. Simplify
n
n
1
.
42. Use the Binomial Theorem to expand (
x
1)
5
. Simplify
your answer.
43. If f(x) x
3
2x
2
3x 1 and g(x) f(x 1), find and
simplify the rule of g(x).
44. Factor x
5
5x
4
10x
3
10x
2
5x 1. [Hint: Think
Binomial.]
45. Find the coefficient of x
2
y
4
in the expansion of
(2y x
2
)
5
.
46. Prove that for every positive integer n,
1
3
2
3
3
3
n
3
n
2
(n
4
1)
2
.
47. Prove that for every positive integer n,
1 5 5
2
5
3
5
n1
5
n
4
1
.
48. Prove that 2
n
2n for every positive integer n.
49. If x is a real number with x 1, then prove that
x
n
1 for all n 1.
50. Prove that for any positive integer n,
1 5 9 (4n 3) n(2n 1).
51. Prove that for any positive integer n,
1 4 4
2
4
3
4
n1
1
3
(4
n
1).
52. Prove that 3n n! for every n 4.
53. Prove that for every positive integer n, 8 is a factor
of 9
n
8n 1.