Test bank for Discrete Mathematics with Application 4th Edition

Test bank for Discrete Mathematics with Application 4th Edition

Discrete Mathematics with Applications, 4th Edition
by Susanna S. Epp
Answers for Test Bank Questions: Chapters 5-8
Please use caution when using these answers. Small differences in wording, notation, or choice of
examples or counterexamples may be acceptable.
Chapter 5
1. ∑
3
k=0
1
2
k
=
1
2
0
+
1
2
1
+
1
2
2
+
1
2
3
(= 1 + 1
2
+
1
4
+
1
8
=
15
8
)
2. ∑
4
k=1
k
2 = 12 + 22 + 32 + 42
(= 1 + 4 + 9 + 16 = 30)
3. 1
3 − 2
3 + 33 − 4
3 + 53 =
∑
5
k=1
(−1)k−1k
2
(This is just one of a number of correct answers to this
question.)
4. 1 −
1
2
+
1
3
−
1
4
+
1
5
−
1
6
=
∑
5
i=1
(−1)i+1 1
i
(This is just one of a number of correct answers to this
question.)
5. When k = 1, j = 1 + 1 = 2. When k = n, j = n + 1. Since j = k + 1, then k = j − 1. So
k
2
n
=
(j − 1)2
n
.
Therefore,
∑n
k=1
k
2
n
=
n∑
+1
j=2
(j − 1)2
n
.
6. When k = 0, i = 0 + 1 = 1. When k = n, i = n + 1. Since i = k + 1, then k = i − 1. So
k
2
k + n
=
(i − 1)2
i − 1 + n
.
Therefore,
∑n
k=0
k
2
k + n
=
n∑
+1
i=1
(i − 1)2
i − 1 + n
.
7.
2
2
2
2
2
2
2
0
1
3
6
12
25
51
103
remainder = r[6] = 1
remainder = r[5] = 1
remainder = r[4] = 0
remainder = r[3] = 0
remainder = r[2] = 1
remainder = r[1] = 1
remainder = r[0] = 1
Hence 10310 = 11001112.
8. 2 + 22 + 23 + · · · + 2m = 2(1 + 2 + 22 + · · · + 2m−1
) = 2 (
2
(m−1)+1 − 1
2 − 1
)
= 2(2m − 1).
Alternative answer:
2 + 22 + 23 + · · · + 2m = (1 + 2 + 22 + · · · + 2m) − 1 = (
2
m+1 − 1
2 − 1
)
− 1
= 2m+1 − 1 − 1 = 2m+1 − 2 [= 2(2m − 1)]
9. a. P(3) : ∑
3
i=3
i =
(3 − 2)(3 + 3)
2
P(3) is true because the left-hand side equals ∑
3
i=3
i = 3 and the right-hand side equals
(3 − 2)(3 + 3)
2
=
1 · 6
2
= 3 also.
b. (i) P(k): 3 + 4 + 5 + · · · + k =
(k − 2)(k + 3)
2
;
(ii) P(k + 1): 3 + 4 + 5 + · · · + (k + 1) = ((k + 1) − 2)((k + 1) + 3)
2
Or, equivalently, P(k + 1) is 3 + 4 + 5 + · · · + (k + 1) = (k − 1)(k + 4)
2
c. Proof that for all integers k ≥ 3, if P(k) is true then P(k + 1) is true:
Let k be any integer that is greater than or equal to 3, and suppose that
3 + 4 + 5 + · · · + k =
(k − 2)(k + 3)
2
←
P(k)
inductive hypothesis
We must show that
3 + 4 + 5 + · · · + (k + 1) = ((k + 1) − 2)((k + 1) + 3)
2
,
or, equivalently,
3 + 4 + 5 + · · · + (k + 1) = (k − 1)(k + 4)
2
. ← P(k + 1)
Now the left-hand side of P(k + 1) is
3 + 4 + 5 + · · · + (k + 1) = 3 + 4 + 5 + · · · + k + (k + 1)
by making the next-to-last term explicit
=
(k − 2)(k + 3)
2
+ (k + 1)
by inductive hypothesis
=
(k − 2)(k + 3)
2
+
2(k + 1)
2
by creating a common denominator
=
k
2 + k − 6
2
+
2k + 2
2
by multiplying out
=
k
2 + k − 6 + 2k + 2
2
by adding the fractions
=
k
2 + 3k − 4
2
by combining like terms.
And the right-hand side of P(k + 1) is
2
(k − 1)(k + 4)
2
=
k
2 + 4k − k − 4
2
=
k
2 + 3k − 4
2
.
Thus the left-hand and right-hand sides of P(k + 1) are equal [as was to be shown].
10. a. P(3): ∑
3
i=3
(i − 1) · i =
(3 − 2)(32 + 2 · 3 + 3)
3
P(3) is true because the left-hand side equals ∑
3
i=3
(i − 1) · i = (3 − 1) · 3 = 2 · 3 = 6, and the
right-hand side equals (3 − 2)(32 + 2 · 3 + 3)
3
=
1 · (9 + 6 + 3)
3
=
1 · 18
3
= 6 also.
b. P(k): 2 · 3 + 3 · 4 + · · · + (k − 1) · k =
(k − 2)(k
2 + 2k + 3)
3
;
P(k + 1): 2 · 3 + 3 · 4 + · · · + ((k + 1) − 1) · (k + 1) = ((k + 1) − 2)((k + 1)2 + 2(k + 1) + 3)
3
Or, equivalently, P(k + 1) is 2 · 3 + 3 · 4 + · · · + k(k + 1) = (k − 1)(k
2 + 2k + 1 + 2k + 2 + 3)
3
=
(k − 1)(k
2 + 4k + 6)
3
c. Proof that for all integers k ≥ 3, if P(k) is true then P(k + 1) is true:
Let k be any integer that is greater than or equal to 3, and suppose that
2 · 3 + 3 · 4 + · · · + (k − 1) · k =
(k − 2)(k
2 + 2k + 3)
3
. ←
P(k)
inductive hypothesis
We must show that
2 · 3 + 3 · 4 + · · · + k(k + 1) = (k − 1)(k
2 + 4k + 6)
3
. ← P(k + 1)
Now the left-hand side of P(k + 1) is
2 · 3 + 3 · 4 + · · · + k(k + 1) = 2 · 3 + 3 · 4 + · · · + (k − 1)k + k(k + 1)
by making the next-to-last term explicit
=
(k − 2)(k
2 + 2k + 3)
3
+ k(k + 1)
by inductive hypothesis
=
k
3 + 2k
2 + 3k − 2k
2 − 4k − 6
3
+
3k(k + 1)
3
by creating a common denominator and multiplying out
=
k
3 − k − 6
3
+
3k
2 + 3k
3
by multiplying out and combining like terms
=
k
3 + 3k
2 + 2k − 6
3
by adding the fractions and combining like terms.
And the right-hand side of P(k + 1) is
(k − 1)(k
2 + 4k + 6)
3
=
k
3 + 4k
2 + 6k − k
2 − 4k − 6
3
=
k
3 + 3k
2 + 2k − 6
3
.
Thus the left-hand and right-hand sides of P(k + 1) are equal [as was to be shown].
11. For each integer n ≥ 0, let P(n) be the equation
1 + 3 + 32 + · · · + 3n =
3
n+1 − 1
2
. ← P(n)
3
(Recall that by definition 1 + 3 + 32 + · · · + 3n =
∑n
i=0
3
i
.)
(a) P(0): ∑
0
i=0
3
i =
3
0+1 − 1
2
P(0) is true because the left-hand side equals ∑
0
i=0
3
i = 30 = 1, and the right-hand side
equals 3
0+1 − 1
2
=
3 − 1
2
= 1 also.
(b) P(k): 1 + 3 + 32 + · · · + 3k =
3
k+1 − 1
2
P(k + 1): 1 + 3 + 32 + · · · + 3k+1 =
3
(k+1)+1 − 1
2
,
Or, equivalently, P(k + 1) is 1 + 3 + 32 + · · · + 3k+1 =
3
k+2 − 1
2
.
(c) Proof that for all integers k ≥ 0, if P(k) is true then P(k + 1) is true:
Let k be any integer that is greater than or equal to 0, and suppose that
1 + 3 + 32 + · · · + 3k =
3
k+1 − 1
2
. ←
P(k)
inductive hypothesis
We must show that
1 + 3 + 32 + · · · + 3k+1 =
3
k+2 − 1
2
. ← P(k + 1)
Now the left-hand side of P(k + 1) is
1 + 3 + 32 + · · · + 3k+1 = 1 + 3 + 32 + · · · + 3k + 3k+1
by making the next-to-last term explicit
=
3
k+1 − 1
2
+ 3k+1
by inductive hypothesis
=
3
k+1 − 1
2
+
2 · 3
k+1
2
by creating a common denominator
=
3 · 3
k+1 − 1
2
by adding the fractions and combining like terms
=
3
k+2 − 1
2
by a law of exponents,
which equals the right-hand side of P(k + 1).
Thus the left-hand and right-hand sides of P(k + 1) are equal [as was to be shown].
12. Proof (by mathematical induction): Let the property P(n) be the equation
4 + 8 + 12 + · · · + 4n = 2n
2 + 2n. ← P(n)
Note that 4 + 8 + 12 + · · · + 4n =
∑n
i=1
4i.
4
Show that P(1) is true: P(1) is true because the left-hand side is ∑
1
i=1
4i = 4 · 1 = 4 and the
right-hand side is 2 · 1
2 + 2 · 1 = 4 also.
Show that for all integers k ≥ 1, if P(k) is true then P (k + 1) is true: Let k be
any integer with k ≥ 1, and suppose that
4 + 8 + 12 + · · · + 4k = 2k
2 + 2k. ←
P(k)
inductive hypothesis
We must show that
4 + 8 + 12 + · · · + 4(k + 1) = 2(k + 1)2 + 2(k + 1). ← P(k + 1)
Now the left-hand side of P(k + 1) is
4 + 8 + 12 + · · · + 4(k + 1) = 4 + 8 + 12 + · · · + 4k + 4(k + 1)
by making the next-to-last term explicit
= (2k
2 + 2k) + 4(k + 1)
by inductive hypothesis
= 2k
2 + 6k + 4
by multiplying out and combining like terms.
And the right-hand side of P(k + 1) is
2(k + 1)2 + 2(k + 1) = 2(k
2 + 2k + 1) + 2k + 2 = 2k
2 + 4k + 2 + 2k + 2 = 2k
2 + 6k + 4.
Thus the left-hand and right-hand sides of P(k + 1) are equal [as was to be shown].
13. Proof (by mathematical induction): Let the property P(n) be the equation
3 + 4 + 5 + · · · + n =
(n − 2)(n + 3)
2
. ← P(n)
Note that 3 + 4 + 5 + · · · + n =
∑n
i=3
i.
Show that P(3) is true: P(3) is true because the left-hand side is ∑
3
i=3
i = 3 and the righthand side is (3 − 2)(3 + 3)
2
= 3 also.
Show that for all integers k ≥ 3, if P(k) is true then P (k + 1) is true: Let k be
any integer with k ≥ 1, and suppose that
3 + 4 + 5 + · · · + k =
(k − 2)(k + 3)
2
. ←
P(k)
inductive hypothesis
We must show that
3 + 4 + 5 + · · · + (k + 1) = [(k + 1) − 2][(k + 1) + 3]
2
. ← P(k + 1)
Now the left-hand side of P(k + 1) is
5
3 + 4 + 5 + · · · + (k + 1) = 3 + 4 + 5 + · · · + k + (k + 1)
by making the next-to-last term explicit
=
(k − 2)(k + 3)
2
+ (k + 1)
by inductive hypothesis
=
(k − 2)(k + 3)
2
+
2 · (k + 1)
2
by creating a common denominator
=
k
2 + k − 6
2
+
2k + 2
2
by multiplying out
=
k
2 + 3k − 4
2
by adding fractions and combining like terms.
And the right-hand side of P(k + 1) is
[(k + 1) − 2][(k + 1) + 3]
2
=
(k − 1)(k + 4)
2
=
k
2 + 3k − 4
2
.
Thus the left-hand and right-hand sides of P(k + 1) are equal [as was to be shown].
14. Proof (by mathematical induction): Let the property P(n) be the equation
2 · 3 + 3 · 4 + · · · + (n − 1) · n =
(n − 2)(n
2 + 2n + 3)
3
. ← P(n)
Note that 2 · 3 + 3 · 4 + · · · + (n − 1) · n =
∑n
i=3
(i − 1) · i.
Show that P(3) is true: P(3) is true because the left-hand side is ∑
3
i=3
(i−1)·i = (3−1)·3 = 6
and the right-hand side is (3 − 2)(32 + 2 · 3 + 3)
3
=
1 · (9 + 6 + 3)
3
= 6 also.
Show that for all integers k ≥ 3, if P(k) is true then P (k + 1) is true: Let k be
any integer with k ≥ 1, and suppose that
2·3+3·4+· · ·+(k−1)·k =
(k − 2)(k
2 + 2k + 3)
3
. ←
P(k)
inductive hypothesis
We must show that
2·3+3·4+· · ·+((k+1)−1)·(k+1) = ((k + 1) − 2)((k + 1)2 + 2(k + 1) + 3)
3
. ← P(k + 1)
6
Now the left-hand side of P(k + 1) is
2 · 3 + 3 · 4 + · · · + ((k + 1) − 1) · (k + 1)
= 2 · 3 + 3 · 4 + · · · + (k − 1) · k + k · (k + 1)
by simplifying the last term and making the next-to-last term explicit
=
(k − 2)(k
2 + 2k + 3)
3
+ k · (k + 1)
by inductive hypothesis
=
k
3 + 2k
2 + 3k − 2k
2 − 4k − 6
3
+ k
2 + k
by combining like terms
=
k
3 − k − 6
3
+
3 · (k
2 + k)
3
by creating a common denominator
=
k
3 − k − 6
3
+
3k
2 + 3k
3
by multiplying out
=
k
3 + 3k
2 + 2k − 6
3
by adding fractions and combining like terms.
And the right-hand side of P(k + 1) is
((k + 1) − 2)((k + 1)2 + 2(k + 1) + 3)
3
=
(k − 1)(k
2 + 2k + 1 + 2k + 2 + 3)
3
=
(k − 1)(k
2 + 4k + 6)
3
=
(k − 1)(k
2 + 4k + 6)
3
=
k
3 + 4k
2 + 6k − k
2 − 4k − 6
3
=
k
3 + 3k
2 + 2k − 6
3
.
Thus the left-hand and right-hand sides of P(k + 1) are equal [as was to be shown].
15. Proof (by mathematical induction): Let the property P(n) be the equation
1 + 3 + 32 + · · · + 3n =
3
n+1 − 1
2
. . ← P(n)
Note that 1 + 3 + 32 + · · · + 3n =
∑n
i=0
3
i
.
Show that P(0) is true: P(0) is true because the left-hand side is ∑
0
i=0
3
i = 30 = 1, and the
right-hand side is 3
0+1 − 1
2
=
3 − 1
2
= 1 also.
Show that for all integers k ≥ 0, if P(k) is true then P (k + 1) is true: Let k be
any integer with k ≥ 0, and suppose that
1 + 3 + 32 + · · · + 3k =
3
k+1 − 1
2
. ←
P(k)
inductive hypothesis