Test Bank For Discrete Mathematics With Applications, 5th Edition
Be exam-ready with Test Bank For Discrete Mathematics With Applications, 5th Edition—a must-have collection of test questions and solutions.
Joseph Martinez
Contributor
4.5
109
about 2 months ago
Preview (30 of 97)
Sign in to access the full document!
Discrete Mathematics with Applications, 5th Edition
by Susanna S. Epp
Answers for Test Bank Questions: Chapters 1-4
Please use caution when using these answers. Small differences in wording, notation, or choice of examples
or counterexamples may be acceptable.
Chapter 1
1. a. a remainder of 1 when it is divided by 4 and a remainder of 3 when it is divided by 7
b. an integer n; n is divided by 7 the remainder is 3
2. a. a positive real number; smaller than r
b. positive real number r; there is a positive real number s
Fill in the blanks to rewrite the following statement with variables:
3. There is an integer whose reciprocal is also an integer.
4. a. have three sides
b. has three sides
c. has three sides
d. is a triangle; has three sides
e. T has three sides
5. a. have additive inverses
b. an additive inverse
c. y is an additive inverse for x
6. a. less than or equal to every positive integer
b. positive integer m; less than or equal to every positive integer
c. less than or equal to n
7. (a) The set of all integers n such that n is a factor of 9.
Or: The set of all elements n in Z such that n is a factor of 9.
Or: The set of all elements n in the set of all integers such that n is a factor of 9.
(b) {1, 3, 9}
8. (a) No
(b) Yes
(c) Yes
(d) No
9. a. {(a, u), (a, v), (b, u), (b, v), (c, u), (c, v)}
b. {(u, a), (v, a), (u, b), (v, b), (u, c), (v, c)}
10. a. Yes; No; No; Yes
b. {(3, 15), (3, 18), (5, 15)}
c. domain is {3, 5, 7}; co-domain is {15, 16, 17, 18}.
d. Draw an arrow diagram for R.
e. No: R fails both conditions for being a function from A to B. (1) Elements 5 and 7 in A are not
related to any elements in B, and (2) there is an element in A, namely 3, that is related to two different
elements in B, namely 15 and 18.
by Susanna S. Epp
Answers for Test Bank Questions: Chapters 1-4
Please use caution when using these answers. Small differences in wording, notation, or choice of examples
or counterexamples may be acceptable.
Chapter 1
1. a. a remainder of 1 when it is divided by 4 and a remainder of 3 when it is divided by 7
b. an integer n; n is divided by 7 the remainder is 3
2. a. a positive real number; smaller than r
b. positive real number r; there is a positive real number s
Fill in the blanks to rewrite the following statement with variables:
3. There is an integer whose reciprocal is also an integer.
4. a. have three sides
b. has three sides
c. has three sides
d. is a triangle; has three sides
e. T has three sides
5. a. have additive inverses
b. an additive inverse
c. y is an additive inverse for x
6. a. less than or equal to every positive integer
b. positive integer m; less than or equal to every positive integer
c. less than or equal to n
7. (a) The set of all integers n such that n is a factor of 9.
Or: The set of all elements n in Z such that n is a factor of 9.
Or: The set of all elements n in the set of all integers such that n is a factor of 9.
(b) {1, 3, 9}
8. (a) No
(b) Yes
(c) Yes
(d) No
9. a. {(a, u), (a, v), (b, u), (b, v), (c, u), (c, v)}
b. {(u, a), (v, a), (u, b), (v, b), (u, c), (v, c)}
10. a. Yes; No; No; Yes
b. {(3, 15), (3, 18), (5, 15)}
c. domain is {3, 5, 7}; co-domain is {15, 16, 17, 18}.
d. Draw an arrow diagram for R.
e. No: R fails both conditions for being a function from A to B. (1) Elements 5 and 7 in A are not
related to any elements in B, and (2) there is an element in A, namely 3, that is related to two different
elements in B, namely 15 and 18.
Discrete Mathematics with Applications, 5th Edition
by Susanna S. Epp
Answers for Test Bank Questions: Chapters 1-4
Please use caution when using these answers. Small differences in wording, notation, or choice of examples
or counterexamples may be acceptable.
Chapter 1
1. a. a remainder of 1 when it is divided by 4 and a remainder of 3 when it is divided by 7
b. an integer n; n is divided by 7 the remainder is 3
2. a. a positive real number; smaller than r
b. positive real number r; there is a positive real number s
Fill in the blanks to rewrite the following statement with variables:
3. There is an integer whose reciprocal is also an integer.
4. a. have three sides
b. has three sides
c. has three sides
d. is a triangle; has three sides
e. T has three sides
5. a. have additive inverses
b. an additive inverse
c. y is an additive inverse for x
6. a. less than or equal to every positive integer
b. positive integer m; less than or equal to every positive integer
c. less than or equal to n
7. (a) The set of all integers n such that n is a factor of 9.
Or: The set of all elements n in Z such that n is a factor of 9.
Or: The set of all elements n in the set of all integers such that n is a factor of 9.
(b) {1, 3, 9}
8. (a) No
(b) Yes
(c) Yes
(d) No
9. a. {(a, u), (a, v), (b, u), (b, v), (c, u), (c, v)}
b. {(u, a), (v, a), (u, b), (v, b), (u, c), (v, c)}
10. a. Yes; No; No; Yes
b. {(3, 15), (3, 18), (5, 15)}
c. domain is {3, 5, 7}; co-domain is {15, 16, 17, 18}.
d. Draw an arrow diagram for R.
e. No: R fails both conditions for being a function from A to B. (1) Elements 5 and 7 in A are not
related to any elements in B, and (2) there is an element in A, namely 3, that is related to two different
elements in B, namely 15 and 18.
by Susanna S. Epp
Answers for Test Bank Questions: Chapters 1-4
Please use caution when using these answers. Small differences in wording, notation, or choice of examples
or counterexamples may be acceptable.
Chapter 1
1. a. a remainder of 1 when it is divided by 4 and a remainder of 3 when it is divided by 7
b. an integer n; n is divided by 7 the remainder is 3
2. a. a positive real number; smaller than r
b. positive real number r; there is a positive real number s
Fill in the blanks to rewrite the following statement with variables:
3. There is an integer whose reciprocal is also an integer.
4. a. have three sides
b. has three sides
c. has three sides
d. is a triangle; has three sides
e. T has three sides
5. a. have additive inverses
b. an additive inverse
c. y is an additive inverse for x
6. a. less than or equal to every positive integer
b. positive integer m; less than or equal to every positive integer
c. less than or equal to n
7. (a) The set of all integers n such that n is a factor of 9.
Or: The set of all elements n in Z such that n is a factor of 9.
Or: The set of all elements n in the set of all integers such that n is a factor of 9.
(b) {1, 3, 9}
8. (a) No
(b) Yes
(c) Yes
(d) No
9. a. {(a, u), (a, v), (b, u), (b, v), (c, u), (c, v)}
b. {(u, a), (v, a), (u, b), (v, b), (u, c), (v, c)}
10. a. Yes; No; No; Yes
b. {(3, 15), (3, 18), (5, 15)}
c. domain is {3, 5, 7}; co-domain is {15, 16, 17, 18}.
d. Draw an arrow diagram for R.
e. No: R fails both conditions for being a function from A to B. (1) Elements 5 and 7 in A are not
related to any elements in B, and (2) there is an element in A, namely 3, that is related to two different
elements in B, namely 15 and 18.
11. a. No; Yes; No; Yes
b. Draw the graph of R in the Cartesian plane.
c. No: R fails both conditions for being a function from R to R. (1) There are many elements in R
that are not related to any element in R. For instance, none of 0, 1/2, and −1 is related to any element
of R. (2) there are elements in R that are related to two different elements in R. For instance 2 is
related to both 1 and −1.
12. a. G(2) = c
b. Draw an arrow diagram for G.
13. F̸ = G. Note that for every real number x,
G(x) = (x − 2)2 − 7 = x2 − 4x + 4 − 7 = x2 − 4x − 3,
whereas
F (x) = (x + 1)(x − 3) = x2 − 2x − 3.
Thus, for instance,
F (1) = (1 + 1)(1 − 3) = −4 whereas G(1) = (1 − 2)2 − 7 = −6.
Chapter 2
1. e
2. e
3. a. The variable S is not undeclared or the data are not out of order.
b. The variable S is not undeclared and the data are not out of order.
c. Al was with Bob on the first, and Al is not innocent.
d. −5 > x or x ≥ 2
4. The statement forms are not logically equivalent.
Truth table: p q ∼ p p ∨ q ∼ p ∧ q p ∨ q → p p ∨ (∼ p ∧ q)
T T F T F T T
T F F T F T T
F T T T T F T
F F T F F T F
Explanation: The truth table shows that p ∨ q → p and p ∨ (∼ p ∧ q) have different truth values in
rows 3 and 4, i.e, when p is false. Therefore p ∨ q → p and p ∨ (∼ p ∧ q) are not logically equivalent.
5. Sample answers:
Two statement forms are logically equivalent if, and only if, they always have the same truth values.
Or: Two statement forms are logically equivalent if, and only if, no matter what statements are
substituted in a consistent way for their statement variables the resulting statements have the same
truth value.
6. Solution 1: The given statements are not logically equivalent. Let p be “Sam bought it at Crown
Books,” and q be “Sam didn’t pay full price.” Then the two statements have the following form:
p → q and p∨ ∼ q.
The truth tables for these statement forms are
p q ∼ q p → q p ∨ ∼ q
T T F T T
T F T F T
F T F T F
F F T T T
2
b. Draw the graph of R in the Cartesian plane.
c. No: R fails both conditions for being a function from R to R. (1) There are many elements in R
that are not related to any element in R. For instance, none of 0, 1/2, and −1 is related to any element
of R. (2) there are elements in R that are related to two different elements in R. For instance 2 is
related to both 1 and −1.
12. a. G(2) = c
b. Draw an arrow diagram for G.
13. F̸ = G. Note that for every real number x,
G(x) = (x − 2)2 − 7 = x2 − 4x + 4 − 7 = x2 − 4x − 3,
whereas
F (x) = (x + 1)(x − 3) = x2 − 2x − 3.
Thus, for instance,
F (1) = (1 + 1)(1 − 3) = −4 whereas G(1) = (1 − 2)2 − 7 = −6.
Chapter 2
1. e
2. e
3. a. The variable S is not undeclared or the data are not out of order.
b. The variable S is not undeclared and the data are not out of order.
c. Al was with Bob on the first, and Al is not innocent.
d. −5 > x or x ≥ 2
4. The statement forms are not logically equivalent.
Truth table: p q ∼ p p ∨ q ∼ p ∧ q p ∨ q → p p ∨ (∼ p ∧ q)
T T F T F T T
T F F T F T T
F T T T T F T
F F T F F T F
Explanation: The truth table shows that p ∨ q → p and p ∨ (∼ p ∧ q) have different truth values in
rows 3 and 4, i.e, when p is false. Therefore p ∨ q → p and p ∨ (∼ p ∧ q) are not logically equivalent.
5. Sample answers:
Two statement forms are logically equivalent if, and only if, they always have the same truth values.
Or: Two statement forms are logically equivalent if, and only if, no matter what statements are
substituted in a consistent way for their statement variables the resulting statements have the same
truth value.
6. Solution 1: The given statements are not logically equivalent. Let p be “Sam bought it at Crown
Books,” and q be “Sam didn’t pay full price.” Then the two statements have the following form:
p → q and p∨ ∼ q.
The truth tables for these statement forms are
p q ∼ q p → q p ∨ ∼ q
T T F T T
T F T F T
F T F T F
F F T T T
2
Rows 2 and 3 of the table show that p → q and p∨ ∼ q do not always have the same truth values, and
so p → q̸ ≡ p∨ ∼ q.
Solution 2 : The given statements are not logically equivalent. Let p be “Sam bought it at Crown
Books,” and q be “Sam paid full price.” Then the two statements have the following form:
p →∼ q and p ∨ q.
The truth tables for these statement forms are
p q ∼ q p →∼ q p ∨ q
T T F F T
T F T T T
F T F T T
F F T T F
Rows 1 and 4 of the table show that p →∼ q and p ∨ q do not always have the same truth values, and
so p →∼ q̸ ≡ p ∨ q.
7. The given statements are not logically equivalent. Let p be “Sam is out of Schlitz,” and q be “Sam is
out of beer.” Then the two statements have the following form:
p → q and ∼ q∨ ∼ p.
The truth tables for these statement forms are
p q ∼ p ∼ q p → q ∼ p∨ ∼ q
T T F F T F
T F F T F T
F T T F T T
F F T T T T
The table shows that p → q and ∼ p ∨ ∼ q sometimes have opposite truth values (shown in rows 1 and
2), and so p → q̸ ≡ ∼ p ∨ ∼ q.
8. Converse: If Jose is Jan’s cousin, then Ann is Jan’s mother
Inverse: If Ann is not Jan’s mother, then Jose is not Jan’s cousin.
Contrapositive: If Jose is not Jan’s cousin, then Ann is not Jan’s mother.
9. Converse: If Liu is Sue’s cousin, then Ed is Sue’s father.
Inverse: If Ed is not Sue’s father, then Liu is not Sue’s cousin
Contrapositive: If Liu is not Sue’s cousin, then Ed is not Sue’s father.
10. Converse: If Jim is Tom’s grandfather, then then Al is Tom’s cousin.
Inverse: If Al is not Tom’s cousin, then Jim is not Tom’s grandfather
Contrapositive: If Jim is not Tom’s grandfather, then then Al is not Tom’s cousin.
11. If someone does not get an answer of 10 for problem 16, then the person will not have solved problem
16 correctly.
Or: If someone solves problem 16 correctly, then the person got an answer of 10.
12. Sample answers:
For a form of argument to be valid means that no matter what statements are substituted for its
statement variables, if the resulting premises are all true, then the conclusion is also true.
Or: For a form of argument to be valid means that no matter what statements are substituted for its
statement variables, it is impossible for all the premises to be true at the same time that the conclusion
is false.
Or: For a form of argument to be valid means that no matter what statements are substituted for its
statement variables, it is impossible for conclusion to be false if all the premises are true.
3
so p → q̸ ≡ p∨ ∼ q.
Solution 2 : The given statements are not logically equivalent. Let p be “Sam bought it at Crown
Books,” and q be “Sam paid full price.” Then the two statements have the following form:
p →∼ q and p ∨ q.
The truth tables for these statement forms are
p q ∼ q p →∼ q p ∨ q
T T F F T
T F T T T
F T F T T
F F T T F
Rows 1 and 4 of the table show that p →∼ q and p ∨ q do not always have the same truth values, and
so p →∼ q̸ ≡ p ∨ q.
7. The given statements are not logically equivalent. Let p be “Sam is out of Schlitz,” and q be “Sam is
out of beer.” Then the two statements have the following form:
p → q and ∼ q∨ ∼ p.
The truth tables for these statement forms are
p q ∼ p ∼ q p → q ∼ p∨ ∼ q
T T F F T F
T F F T F T
F T T F T T
F F T T T T
The table shows that p → q and ∼ p ∨ ∼ q sometimes have opposite truth values (shown in rows 1 and
2), and so p → q̸ ≡ ∼ p ∨ ∼ q.
8. Converse: If Jose is Jan’s cousin, then Ann is Jan’s mother
Inverse: If Ann is not Jan’s mother, then Jose is not Jan’s cousin.
Contrapositive: If Jose is not Jan’s cousin, then Ann is not Jan’s mother.
9. Converse: If Liu is Sue’s cousin, then Ed is Sue’s father.
Inverse: If Ed is not Sue’s father, then Liu is not Sue’s cousin
Contrapositive: If Liu is not Sue’s cousin, then Ed is not Sue’s father.
10. Converse: If Jim is Tom’s grandfather, then then Al is Tom’s cousin.
Inverse: If Al is not Tom’s cousin, then Jim is not Tom’s grandfather
Contrapositive: If Jim is not Tom’s grandfather, then then Al is not Tom’s cousin.
11. If someone does not get an answer of 10 for problem 16, then the person will not have solved problem
16 correctly.
Or: If someone solves problem 16 correctly, then the person got an answer of 10.
12. Sample answers:
For a form of argument to be valid means that no matter what statements are substituted for its
statement variables, if the resulting premises are all true, then the conclusion is also true.
Or: For a form of argument to be valid means that no matter what statements are substituted for its
statement variables, it is impossible for all the premises to be true at the same time that the conclusion
is false.
Or: For a form of argument to be valid means that no matter what statements are substituted for its
statement variables, it is impossible for conclusion to be false if all the premises are true.
3
Loading page 4...
13. The given form of argument is invalid.
premises
z }| { conclusion
z }| {
p q ∼ p ∼ q p →∼ q q →∼ p p ∨ q
T T F F F F T
T F F T T T T
F T T F T T T
F F T T T T F
Row 4 of the truth table shows that it is possible for an argument of this form to have true premises
and a false conclusion.
14. The given form of argument is invalid.
premises
z }| { conclusion
z}|{
p q r ∼ q p ∧ ∼ q p ∧ ∼ q → r p ∨ q q → p r
T T T F F T T T T
T T F F F T T T F
T F T T T T T T T
T F F T T F T T F
F T T F F T T F T
F T F F F T T F F
F F T T F T F T T
F F F T F T F T F
Row 2 of the truth table shows that it is possible for an argument of this form to have true premises
and a false conclusion.
15. Let p be “Hugo is a physics major,” q be “Hugo is a math major,” and r be “Hugo needs to take
calculus.” Then the given argument has the following form:
p ∨ q → r
r ∨ q
Therefore p ∨ q.
Truth table: premises
z }| { conclusion
z}|{
p q r p ∨ q p ∨ q → r r ∨ q p ∨ q
T T T F T T T
T T F F F T T
T F T T T T T
T F F T F F T
F T T T T T T
F T F T F T T
F F T F T T F
F F F F T F F
Row 7 of the truth table shows that it is possible for an argument of this form to have true premises
and a false conclusion. Therefore, the given argument is invalid.
16. Let p be “12 divides 709,438,” q be “3 divides 709,438,” and r be “The sum of the digits of 709,438 is
divisible by 9.” Then the given argument has the following form:
p → q
r → q
∼ r
Therefore ∼ p.
4
premises
z }| { conclusion
z }| {
p q ∼ p ∼ q p →∼ q q →∼ p p ∨ q
T T F F F F T
T F F T T T T
F T T F T T T
F F T T T T F
Row 4 of the truth table shows that it is possible for an argument of this form to have true premises
and a false conclusion.
14. The given form of argument is invalid.
premises
z }| { conclusion
z}|{
p q r ∼ q p ∧ ∼ q p ∧ ∼ q → r p ∨ q q → p r
T T T F F T T T T
T T F F F T T T F
T F T T T T T T T
T F F T T F T T F
F T T F F T T F T
F T F F F T T F F
F F T T F T F T T
F F F T F T F T F
Row 2 of the truth table shows that it is possible for an argument of this form to have true premises
and a false conclusion.
15. Let p be “Hugo is a physics major,” q be “Hugo is a math major,” and r be “Hugo needs to take
calculus.” Then the given argument has the following form:
p ∨ q → r
r ∨ q
Therefore p ∨ q.
Truth table: premises
z }| { conclusion
z}|{
p q r p ∨ q p ∨ q → r r ∨ q p ∨ q
T T T F T T T
T T F F F T T
T F T T T T T
T F F T F F T
F T T T T T T
F T F T F T T
F F T F T T F
F F F F T F F
Row 7 of the truth table shows that it is possible for an argument of this form to have true premises
and a false conclusion. Therefore, the given argument is invalid.
16. Let p be “12 divides 709,438,” q be “3 divides 709,438,” and r be “The sum of the digits of 709,438 is
divisible by 9.” Then the given argument has the following form:
p → q
r → q
∼ r
Therefore ∼ p.
4
Loading page 5...
Truth table:
premises
z }| { conclusion
z}|{
p q r ∼ q p ∧ ∼ q p → q r → q ∼ r ∼ p
T T T F F T T F F
T T F F F T T T F
T F T T T F F F F
T F F T T F T T F
F T T F F T T F T
F T F F F T T T T
F F T T F T F F T
F F F T F T T T T
Row 2 of the truth table shows that it is possible for an argument of this form to have true premises
and a false conclusion. Therefore, the given argument is invalid.
17. The argument has the form
p → q
∼ q
Therefore ∼ p,
which is valid by modus tollens (and the fact that the negation of “17 is not a divisor of 54,587” is “17
is a divisor of 54,587”).
18. The argument has the form
p → q
q
Therefore p,
which is invalid; it exhibits the converse error.
19. A and B are knights, and C is a knave.
Reasoning: A cannot be a knave because if A were a knave his statement would be true, which is
impossible for a knave. Hence A is a knight, and at least one of the three is a knave. That implies
that at most two of the three are knaves, which means that B’s statement is true. Hence B is a knight.
Since at least one of the three is a knave and both A and B are knights, it follows that C is a knave.
20. a. S = 1
b. ∼ (P ∧ Q)∧ (Q ∧ R)
21. 1101012 = 1 · 25 + 1 · 24 + 1 · 22 + 1 · 20 = 32 + 16 + 4 + 1 = 5310
22. 7510 = 64 + 8 + 2 + 1 = 1 · 26 + 0 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 1 · 20 = 10010112.
23. The following circuit corresponds to the given Boolean expression:P
AND
ORQ
NOT
NOT
AND R
5
premises
z }| { conclusion
z}|{
p q r ∼ q p ∧ ∼ q p → q r → q ∼ r ∼ p
T T T F F T T F F
T T F F F T T T F
T F T T T F F F F
T F F T T F T T F
F T T F F T T F T
F T F F F T T T T
F F T T F T F F T
F F F T F T T T T
Row 2 of the truth table shows that it is possible for an argument of this form to have true premises
and a false conclusion. Therefore, the given argument is invalid.
17. The argument has the form
p → q
∼ q
Therefore ∼ p,
which is valid by modus tollens (and the fact that the negation of “17 is not a divisor of 54,587” is “17
is a divisor of 54,587”).
18. The argument has the form
p → q
q
Therefore p,
which is invalid; it exhibits the converse error.
19. A and B are knights, and C is a knave.
Reasoning: A cannot be a knave because if A were a knave his statement would be true, which is
impossible for a knave. Hence A is a knight, and at least one of the three is a knave. That implies
that at most two of the three are knaves, which means that B’s statement is true. Hence B is a knight.
Since at least one of the three is a knave and both A and B are knights, it follows that C is a knave.
20. a. S = 1
b. ∼ (P ∧ Q)∧ (Q ∧ R)
21. 1101012 = 1 · 25 + 1 · 24 + 1 · 22 + 1 · 20 = 32 + 16 + 4 + 1 = 5310
22. 7510 = 64 + 8 + 2 + 1 = 1 · 26 + 0 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 1 · 20 = 10010112.
23. The following circuit corresponds to the given Boolean expression:P
AND
ORQ
NOT
NOT
AND R
5
Loading page 6...
24. One circuit (among many) having the given input/output table is the following:S
P
R
NOT AND OR
AND
Q
NOT
25.
101112
+ 10112
1000102
26. 1001102 = 1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 0 · 20 = 32 + 4 + 2 = 3810
27. 4910 = (32 + 16 + 1)10 = 001100012 −→ 11001110 −→ 11001111.
So the two’s complement is 11001111.
Check: 28 − 49 = 256 − 49 = 207 and
110011112 = 1 · 27 + 1 · 26 + 0 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 1 · 21 + 1 · 20
= 128 + 64 + 8 + 4 + 2 + 1
= 207,
which agrees.
Chapter 3
1. ∀ valid argument x, if x has true premises, then x has a true conclusion.
2. a. ∀ odd integer n, n2 is odd.
b. ∀ integer n, if n is odd then n2 is odd.
c. ∃ an odd integer n such that n2 is not odd.
Or: ∃ an integer n such that n is odd and n2 is not odd.
3. ∀ rational number r, ∃ integers u and v such that r is the ratio of u to v.
Or: ∀ rational number r, ∃ integers u and v such that r = u/v.
4. ∀ even integer n that is greater than 2, ∃ prime numbers p and q such that n = p + q.
Or: ∀ even integer n, if n > 2 then ∃ prime numbers p and q such that n = p + q.
5. e
6. a
7. d
8. g
6
P
R
NOT AND OR
AND
Q
NOT
25.
101112
+ 10112
1000102
26. 1001102 = 1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 0 · 20 = 32 + 4 + 2 = 3810
27. 4910 = (32 + 16 + 1)10 = 001100012 −→ 11001110 −→ 11001111.
So the two’s complement is 11001111.
Check: 28 − 49 = 256 − 49 = 207 and
110011112 = 1 · 27 + 1 · 26 + 0 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 1 · 21 + 1 · 20
= 128 + 64 + 8 + 4 + 2 + 1
= 207,
which agrees.
Chapter 3
1. ∀ valid argument x, if x has true premises, then x has a true conclusion.
2. a. ∀ odd integer n, n2 is odd.
b. ∀ integer n, if n is odd then n2 is odd.
c. ∃ an odd integer n such that n2 is not odd.
Or: ∃ an integer n such that n is odd and n2 is not odd.
3. ∀ rational number r, ∃ integers u and v such that r is the ratio of u to v.
Or: ∀ rational number r, ∃ integers u and v such that r = u/v.
4. ∀ even integer n that is greater than 2, ∃ prime numbers p and q such that n = p + q.
Or: ∀ even integer n, if n > 2 then ∃ prime numbers p and q such that n = p + q.
5. e
6. a
7. d
8. g
6
Loading page 7...
9. a. There is an integer n such that n is prime and n is not odd.
b. ∃ a real number x such that x < 1 and 1
x ≯ 1.
Or: ∃ a real number x such that x < 1 and 1
x ≤ 1.
c. There are integers a and b such that a2 divides b2 and a does not divide b.
d. ∃ a real number x such that x(x − 2) > 0 and x ≯ 2 and x ≮ 0.
Or: ∃ a real number x such that x(x − 2) > 0 and 0 ≤ x ≤ 2.
e. ∃ a real number x such that x(x − 2) > 0 and either 0 > x or x > 2.
Or: ∃ a real number x such that x(x − 2) > 0 and either 0 x or x 2.
f. There are real numbers x and y with x < y such that for all integers n, either x > n or n > y.
Or: There are real numbers x and y with x < y such that for all integers n, either x n or n y.
10. a. ∀ real numbers x, if x + 1 > 0 then −1 < x ≤ 0.
b. ∀ real numbers x, if x + 1 ≤ 0 then −1 ≥ x or x > 0.
Or: ∀ real numbers x, if x + 1 ≯ 0 then −1 ≮ x or x 0.
11. If a graph with n vertices is a tree, then it has n − 1 edges.
12. These two statements are not logically equivalent.
Explanation 1: The first statement is equivalent to “If a real number is less than 1, then its reciprocal
is greater than 1” and the second statement is equivalent to “If the reciprocal of a real number is
greater than 1, then the number is less than 1.” Thus the second statement is the converse of the first,
and a conditional statement and its converse are not logically equivalent.
Explanation 2: The first statment is false. For example, −2 is less than 1, but its reciprocal, − 1
2 is
greater than 1. However, the second statement is true; if the reciprocal of a real number is greater
than 1, then the number itself is positive and is between 0 and 1, and it is impossible for one of a pair
of equivalent statements to be true while the other member of the pair is false.
13. a. For any integer you might choose, you can find an integer such that the sum of the two equals 0.
Or: Every integer has an additive inverse.
b. There is an integer with the property that no matter what integer is chosen, the sum of the two
will be 0.
Or: Some integer has the property that its sum with every integer equals 0.
14. a. Given any real number, there is a real number that is less than the given number.
Or: There is no smallest real number.
b. There is a real number that is less than every real number.
15. The argument is valid by modus tollens.
16. The argument is invalid; it exhibits the inverse error.
Chapter 4
1. Some acceptable answers:
a. An integer n is odd if, and only if, n = 2k + 1 for some integer k.
b. An integer n is odd if, and only if, n equals 2 times some integer plus 1.
c. An integer n is odd if, and only if, there exists an integer m such that n = 2m + 1 .
7
b. ∃ a real number x such that x < 1 and 1
x ≯ 1.
Or: ∃ a real number x such that x < 1 and 1
x ≤ 1.
c. There are integers a and b such that a2 divides b2 and a does not divide b.
d. ∃ a real number x such that x(x − 2) > 0 and x ≯ 2 and x ≮ 0.
Or: ∃ a real number x such that x(x − 2) > 0 and 0 ≤ x ≤ 2.
e. ∃ a real number x such that x(x − 2) > 0 and either 0 > x or x > 2.
Or: ∃ a real number x such that x(x − 2) > 0 and either 0 x or x 2.
f. There are real numbers x and y with x < y such that for all integers n, either x > n or n > y.
Or: There are real numbers x and y with x < y such that for all integers n, either x n or n y.
10. a. ∀ real numbers x, if x + 1 > 0 then −1 < x ≤ 0.
b. ∀ real numbers x, if x + 1 ≤ 0 then −1 ≥ x or x > 0.
Or: ∀ real numbers x, if x + 1 ≯ 0 then −1 ≮ x or x 0.
11. If a graph with n vertices is a tree, then it has n − 1 edges.
12. These two statements are not logically equivalent.
Explanation 1: The first statement is equivalent to “If a real number is less than 1, then its reciprocal
is greater than 1” and the second statement is equivalent to “If the reciprocal of a real number is
greater than 1, then the number is less than 1.” Thus the second statement is the converse of the first,
and a conditional statement and its converse are not logically equivalent.
Explanation 2: The first statment is false. For example, −2 is less than 1, but its reciprocal, − 1
2 is
greater than 1. However, the second statement is true; if the reciprocal of a real number is greater
than 1, then the number itself is positive and is between 0 and 1, and it is impossible for one of a pair
of equivalent statements to be true while the other member of the pair is false.
13. a. For any integer you might choose, you can find an integer such that the sum of the two equals 0.
Or: Every integer has an additive inverse.
b. There is an integer with the property that no matter what integer is chosen, the sum of the two
will be 0.
Or: Some integer has the property that its sum with every integer equals 0.
14. a. Given any real number, there is a real number that is less than the given number.
Or: There is no smallest real number.
b. There is a real number that is less than every real number.
15. The argument is valid by modus tollens.
16. The argument is invalid; it exhibits the inverse error.
Chapter 4
1. Some acceptable answers:
a. An integer n is odd if, and only if, n = 2k + 1 for some integer k.
b. An integer n is odd if, and only if, n equals 2 times some integer plus 1.
c. An integer n is odd if, and only if, there exists an integer m such that n = 2m + 1 .
7
Loading page 8...
2. Counterexample: Let a = 1, b = 2, c = 1, and d = 2. Then
a
b + c
d = 1
2 + 1
2 = 1, whereas a + c
b + d = 1 + 1
2 + 2 = 2
4 = 1
2 .
(This is one counterexample among many.)
3. a. ∃ integers m and n such that 2m + n is odd and m and n are not both odd. In other words, ∃
integers m and n such that 2m + n is odd and at least one of m and n is even.
b. Statement A can be shown to be false by giving a counterexample.
Counterexample: Let m = 1 and n = 2. Then 2m + n = 2 · 1 + 2 = 4, which is even, but it is not the
case that both m and n are odd because n is even.(This is one counterexample among many.)
4. No matter what integers replace m and n in the expression 6m2 + 34n − 18, the result will always be
an even integer. To see this, observe that
6m2 + 34n − 18 = 2(m2 + 17n − 9).
Since products, sums, and differences of integers are integers, m2 + 17n − 9 is an integer. Thus
6m2 + 34n − 18 can be written as 2 times an integer, and so it is an even integer.
5. Counterexample: Let a = b = √2. Then a and b are irrational, and ab = √2 · √2 = 2, which is rational.
6. Some acceptable answers:
a. A real number r is rational if, and only if, r = a
b for some integers a and b with b̸ = 0.
b. A real number r is rational if, and only if, there exist integers a and b such that r = a
b and b̸ = 0.
c. A real number r is rational if, and only if, r can be written as a ratio of integers with a nonzero
denominator.
7. 605.83 is a rational number because 605.83 = 60583
100 .
8. 56.745 a rational number because 56.745 = 56745
1000 .
9. Some acceptable answers:
a.An integer n is divisible by an integer d if, and only if, n = dk for some integer k.
b. An integer n is divisible by an integer d if, and only if, there exists an integer k so that n = dk.
c. An integer n is divisible by an integer d if, and only if, n is equal to d times some integer.
10. 0 is divisible by 3 because 0 = 3 · 0.
11. 12 divides 72 because 72 = 12 · 6.
12. Proof: Suppose r and s, are any [particular but arbitarily chosen] rational numbers.
We must show that r − s is rational.
13. Proof: Suppose r and s, are any rational numbers with s̸ = 0. [We must show that 2r
5s is a rational
number.] By definition of rational, there exist integers a, b, c, and d with b̸ = 0 and d̸ = 0 such that
r = a
b and s = c
d .
In addition, since c = s · d and since neither s nor d equals 0, then c̸ = 0 by the zero product property.
Then
2r
5s =
2 · a
b
5 · c
d
= 2ad
5bc .
Now both 2ad and 5bc are integers because they are products of integers, and 5bc̸ = 0 by the zero
product property. Hence 2r
5s is a ratio of integers with a nonzero denominator, and so 2r
5s is a rational
number by definition of rational [as was to be shown].
8
a
b + c
d = 1
2 + 1
2 = 1, whereas a + c
b + d = 1 + 1
2 + 2 = 2
4 = 1
2 .
(This is one counterexample among many.)
3. a. ∃ integers m and n such that 2m + n is odd and m and n are not both odd. In other words, ∃
integers m and n such that 2m + n is odd and at least one of m and n is even.
b. Statement A can be shown to be false by giving a counterexample.
Counterexample: Let m = 1 and n = 2. Then 2m + n = 2 · 1 + 2 = 4, which is even, but it is not the
case that both m and n are odd because n is even.(This is one counterexample among many.)
4. No matter what integers replace m and n in the expression 6m2 + 34n − 18, the result will always be
an even integer. To see this, observe that
6m2 + 34n − 18 = 2(m2 + 17n − 9).
Since products, sums, and differences of integers are integers, m2 + 17n − 9 is an integer. Thus
6m2 + 34n − 18 can be written as 2 times an integer, and so it is an even integer.
5. Counterexample: Let a = b = √2. Then a and b are irrational, and ab = √2 · √2 = 2, which is rational.
6. Some acceptable answers:
a. A real number r is rational if, and only if, r = a
b for some integers a and b with b̸ = 0.
b. A real number r is rational if, and only if, there exist integers a and b such that r = a
b and b̸ = 0.
c. A real number r is rational if, and only if, r can be written as a ratio of integers with a nonzero
denominator.
7. 605.83 is a rational number because 605.83 = 60583
100 .
8. 56.745 a rational number because 56.745 = 56745
1000 .
9. Some acceptable answers:
a.An integer n is divisible by an integer d if, and only if, n = dk for some integer k.
b. An integer n is divisible by an integer d if, and only if, there exists an integer k so that n = dk.
c. An integer n is divisible by an integer d if, and only if, n is equal to d times some integer.
10. 0 is divisible by 3 because 0 = 3 · 0.
11. 12 divides 72 because 72 = 12 · 6.
12. Proof: Suppose r and s, are any [particular but arbitarily chosen] rational numbers.
We must show that r − s is rational.
13. Proof: Suppose r and s, are any rational numbers with s̸ = 0. [We must show that 2r
5s is a rational
number.] By definition of rational, there exist integers a, b, c, and d with b̸ = 0 and d̸ = 0 such that
r = a
b and s = c
d .
In addition, since c = s · d and since neither s nor d equals 0, then c̸ = 0 by the zero product property.
Then
2r
5s =
2 · a
b
5 · c
d
= 2ad
5bc .
Now both 2ad and 5bc are integers because they are products of integers, and 5bc̸ = 0 by the zero
product property. Hence 2r
5s is a ratio of integers with a nonzero denominator, and so 2r
5s is a rational
number by definition of rational [as was to be shown].
8
Loading page 9...
14. Proof : Suppose a, b, and c are any integers such that a | b and a | c. [We must show that a | (5b + 3c).]
By definition of divisibility, b = ar and c = as for some integers r and s. Then
5b + 3c = 5(ar) + 3(as) by substitution
= a(5r + 3s) by the commutative and associative laws of algebra.
Let t = 5r+3s. Then t is an integer because products and sums of integers are integers, and 5b+3c = at.
Thus, by definition of divisibility, a | (5b + 3c) [as was to be shown].
Prove the following statement directly from the definitions of the terms. Do not use any other facts
previously proved in class or in the text or in the exercises.
For all integers a, b, and c, if a | b and a | c, then a | (5b + 3c).
15. Proof (Version 1): Suppose a and b are integers and a divides b. By definition of divisibility, b = a · k
for some integer k. Raising both sides to the third power gives
b3 = (a · k)3
= a3 · k3 by the commutative and associative laws of algebra.
Observe that k3 is an integer because it is a product of integers. Hence b3 equals a3 times an integer,
and so by definition of divisibility, a3 divides b3.
Proof (Version 2): Suppose a and b are integers and a divides b. By definition of divisibility, b = a · k
for some integer k. Raising both sides to the third power gives
b3 = (a · k)3
= a3 · k3 by the commutative and associative laws of algebra.
Let t = k3. Then t is an integer because it is a product of integers. Hence b3 = a3 · t, where t is an
integer, and so by definition of divisibility, a3 divides b3.
16. Proof: Suppose n is any integer. By the parity principle, either n is even or n is odd, so we consider
two cases.
Case 1 (n is even): By definition of even, there is an integer u such that n = 2u. Then
n2 + n + 1 = (2u)2 + 2u + 1 = 4u2 + 2u + 1 = 2(2u2 + u) + 1.
Now 2u2 + u is an integer because products and sums of integers are integers. Thus n2 + n + 1 equals
2 times an integer plus 1, and so n2 + n + 1 is odd by definition of odd.
Case 2 (n is odd): By definition of odd, there is an integer u such that n = 2u + 1. Then
n2 + n + 1 = (2u + 1)2 + (2u + 1) + 1 = 4u2 + 4u + 1 + 2u + 1 + 1 = 4u2 + 6u + 2 + 1 = 2(2u2 + u + 1) + 1.
Now 2u2 + u + 1 is an integer because products and sums of integers are integers. Thus n2 + n + 1
equals 2 times an integer plus 1, and so n2 + n + 1 is odd by definition of odd.
Conclusion: In both possible cases n2 + n + 1 is odd.
17. Proof: Suppose n is any integer. By the parity principle, either n is even or n is odd, so we consider
two cases.
Case 1 (n is even): By definition of even, there is an integer a such that n = 2a. The next
consecutive integer after n is n + 1, and so
n + (n + 1) = 2a + (2a + 1) = 4a + 1 = 2(2a) + 1.
Now 2a is an integer because products of integers are integers. Thus n + (n + 1) equals 2 times an
integer plus 1, and so n + (n + 1) is odd by definition of odd.
9
By definition of divisibility, b = ar and c = as for some integers r and s. Then
5b + 3c = 5(ar) + 3(as) by substitution
= a(5r + 3s) by the commutative and associative laws of algebra.
Let t = 5r+3s. Then t is an integer because products and sums of integers are integers, and 5b+3c = at.
Thus, by definition of divisibility, a | (5b + 3c) [as was to be shown].
Prove the following statement directly from the definitions of the terms. Do not use any other facts
previously proved in class or in the text or in the exercises.
For all integers a, b, and c, if a | b and a | c, then a | (5b + 3c).
15. Proof (Version 1): Suppose a and b are integers and a divides b. By definition of divisibility, b = a · k
for some integer k. Raising both sides to the third power gives
b3 = (a · k)3
= a3 · k3 by the commutative and associative laws of algebra.
Observe that k3 is an integer because it is a product of integers. Hence b3 equals a3 times an integer,
and so by definition of divisibility, a3 divides b3.
Proof (Version 2): Suppose a and b are integers and a divides b. By definition of divisibility, b = a · k
for some integer k. Raising both sides to the third power gives
b3 = (a · k)3
= a3 · k3 by the commutative and associative laws of algebra.
Let t = k3. Then t is an integer because it is a product of integers. Hence b3 = a3 · t, where t is an
integer, and so by definition of divisibility, a3 divides b3.
16. Proof: Suppose n is any integer. By the parity principle, either n is even or n is odd, so we consider
two cases.
Case 1 (n is even): By definition of even, there is an integer u such that n = 2u. Then
n2 + n + 1 = (2u)2 + 2u + 1 = 4u2 + 2u + 1 = 2(2u2 + u) + 1.
Now 2u2 + u is an integer because products and sums of integers are integers. Thus n2 + n + 1 equals
2 times an integer plus 1, and so n2 + n + 1 is odd by definition of odd.
Case 2 (n is odd): By definition of odd, there is an integer u such that n = 2u + 1. Then
n2 + n + 1 = (2u + 1)2 + (2u + 1) + 1 = 4u2 + 4u + 1 + 2u + 1 + 1 = 4u2 + 6u + 2 + 1 = 2(2u2 + u + 1) + 1.
Now 2u2 + u + 1 is an integer because products and sums of integers are integers. Thus n2 + n + 1
equals 2 times an integer plus 1, and so n2 + n + 1 is odd by definition of odd.
Conclusion: In both possible cases n2 + n + 1 is odd.
17. Proof: Suppose n is any integer. By the parity principle, either n is even or n is odd, so we consider
two cases.
Case 1 (n is even): By definition of even, there is an integer a such that n = 2a. The next
consecutive integer after n is n + 1, and so
n + (n + 1) = 2a + (2a + 1) = 4a + 1 = 2(2a) + 1.
Now 2a is an integer because products of integers are integers. Thus n + (n + 1) equals 2 times an
integer plus 1, and so n + (n + 1) is odd by definition of odd.
9
Loading page 10...
Case 2 (n is odd): By definition of odd, there is an integer a such that n = 2a + 1. Then
n + (n + 1) = (2a + 1) + [(2a + 1) + 1] = 4a + 2 + 1 = 2(2a + 1) + 1.
Now 2a + 1 is an integer because products and sums of integers are integers. Thus n + (n + 1) equals
2 times an integer plus 1, and so n + (n + 1) is odd by definition of odd.
Conclusion: In both possible cases n + (n + 1) is odd.
Prove the following statement: The sum of any two consecutive integers can be written in the form
4n + 1 for some integer n.
18. Proof: Suppose x is any real number. By definition of floor,
⌊x − 2⌋ = n if,and only if, n ≤ x − 2 < n + 1.
Adding 2 to all parts of the inequality gives
n + 2 ≤ x < n + 3.
Thus, by definition of floor,
⌊x⌋ = n + 2, and so ⌊x⌋ − 2 = n.
Thus both ⌊x − 2⌋ and ⌊x⌋ − 2 equal the same quantity (namely n), and so ⌊x − 2⌋ = ⌊x⌋ − 2.
19. Proof (by contradiction): Suppose not. That is, suppose there is a smallest positive rational number;
call it r. [We must show that this supposition leads logically to a contradiction.] By definition of
rational, there exist integers u and v with v̸ = 0 such that r = u
v . Then
r
2 =
u
v
2 = u
2v .
Now both u and 2v are integers because products of integers are integers, and 2v̸ = 0 by the zero
product property. Thus r
2 is a raional number.
In addition, since r is positive, 0 < r. Hence, by adding r to both sides, r < 2r, and dividing both sides
by 2 gives that r
2 < r, so r
2 is less than r.
Moreover, dividing both sides of 0 < r by 2 gives that 0 < r
2 , so r
2 is positive.
In summary: r
2 is a positive rational number that is less than r, which contradicts the supposition that
r is the smallest positive rational number. [Hence the supposition is false and the given statement is
true.]
20. Proof (by contradiction):Suppose not. That is, suppose there are real numbers r and s such that r is
rational and s is irrational and r + 2s is rational. [We must show that this supposition leads logically
to a contradiction.] By definition of rational,
r = a
b and r + 2s = c
d for some integers a, b, c, and d with b̸ = 0 and d̸ = 0.
Then, by substitution, a
b + 2s = c
d .
Solve this equation for s to obtain
s = 1
2
( c
d − a
b
)
= 1
2
( bc
bd − ad
bd
)
= bc − ad
2bd .
But both bc − ad and 2bd are integers because products and differences of integers are integers, and
2bd̸ = 0 by the zero product property.
Hence s is a ratio of integers with a nonzero denominator, and so s is rational by definition of rational.
This contradicts the supposition that x is irrational. [Hence the supposition is false and the given
statement is true.]
10
n + (n + 1) = (2a + 1) + [(2a + 1) + 1] = 4a + 2 + 1 = 2(2a + 1) + 1.
Now 2a + 1 is an integer because products and sums of integers are integers. Thus n + (n + 1) equals
2 times an integer plus 1, and so n + (n + 1) is odd by definition of odd.
Conclusion: In both possible cases n + (n + 1) is odd.
Prove the following statement: The sum of any two consecutive integers can be written in the form
4n + 1 for some integer n.
18. Proof: Suppose x is any real number. By definition of floor,
⌊x − 2⌋ = n if,and only if, n ≤ x − 2 < n + 1.
Adding 2 to all parts of the inequality gives
n + 2 ≤ x < n + 3.
Thus, by definition of floor,
⌊x⌋ = n + 2, and so ⌊x⌋ − 2 = n.
Thus both ⌊x − 2⌋ and ⌊x⌋ − 2 equal the same quantity (namely n), and so ⌊x − 2⌋ = ⌊x⌋ − 2.
19. Proof (by contradiction): Suppose not. That is, suppose there is a smallest positive rational number;
call it r. [We must show that this supposition leads logically to a contradiction.] By definition of
rational, there exist integers u and v with v̸ = 0 such that r = u
v . Then
r
2 =
u
v
2 = u
2v .
Now both u and 2v are integers because products of integers are integers, and 2v̸ = 0 by the zero
product property. Thus r
2 is a raional number.
In addition, since r is positive, 0 < r. Hence, by adding r to both sides, r < 2r, and dividing both sides
by 2 gives that r
2 < r, so r
2 is less than r.
Moreover, dividing both sides of 0 < r by 2 gives that 0 < r
2 , so r
2 is positive.
In summary: r
2 is a positive rational number that is less than r, which contradicts the supposition that
r is the smallest positive rational number. [Hence the supposition is false and the given statement is
true.]
20. Proof (by contradiction):Suppose not. That is, suppose there are real numbers r and s such that r is
rational and s is irrational and r + 2s is rational. [We must show that this supposition leads logically
to a contradiction.] By definition of rational,
r = a
b and r + 2s = c
d for some integers a, b, c, and d with b̸ = 0 and d̸ = 0.
Then, by substitution, a
b + 2s = c
d .
Solve this equation for s to obtain
s = 1
2
( c
d − a
b
)
= 1
2
( bc
bd − ad
bd
)
= bc − ad
2bd .
But both bc − ad and 2bd are integers because products and differences of integers are integers, and
2bd̸ = 0 by the zero product property.
Hence s is a ratio of integers with a nonzero denominator, and so s is rational by definition of rational.
This contradicts the supposition that x is irrational. [Hence the supposition is false and the given
statement is true.]
10
Loading page 11...
21. Solution 1:
a. Proof (by contradiction): Suppose not. That is, suppose there is an integer n such that n3 is even
and n is odd.
[We must show that this supposition leads logically to a contradiction.]
By definition of odd, n = 2a + 1 for some integer a.
Thus, by substitution and algebra,
n3 = (2a + 1)3 = (2a + 1)2(2a + 1) = (4a2 + 4a + 1)(2a + 1) = 8a3 + 12a2 + 6a + 1 = 2(4a3 + 6a2 + 3a) + 1.
Let t = 4a3 + 6a2 + 3a. Then n3 = 2t + 1, and t is an integer because it is a sum of products of integers.
It follows that n3 is odd by definition of odd, which contradicts the supposition that n3 is even.
[Hence the supposition is false and the given statement is true.]
b. Outline of proof by contraposition:
Starting point: Suppose n is any integer such that n is odd. (Or: Suppose n is any odd integer.)
Conclusion to be shown: n3 is odd.
Solution 2:
a. Proof (by contraposition): Suppose n is any integer such that n is odd. (Or: Suppose n is any odd
integer.) [We must show that n3 is odd.]
By definition of odd, n = 2a + 1 for some integer a.
Thus n3 = (2a+1)3 = (2a+1)2(2a+1) = (4a2+4a+1)(2a+1) = 8a3+12a2+6a+1 = 2(4a3+6a2+3a)+1.
Let t = 4a3 + 6a2 + 3a. Then n3 = 2t + 1, and t is an integer because it is a sum of products of integers.
It follows that n3 is odd by definition of odd [as was to be shown].
b. Outline of proof by contradiction:
Starting point: Suppose not. That is, suppose there is an integer n such that n3 is even and n is odd.
Conclusion to be shown: We must show that this supposition leads logically to a contradiction.
22. Solution 1:
a. Proof (by contradiction): Suppose not. That is, suppose there is a real number r such that r3 is
irrational and r is rational.
[We must show that this supposition leads logically to a contradiction.]
By definition of rational, there exist integers a and b with b̸ = 0 such that r = a
b .
By substitution, r3 =
( a
b
)3
= a3
b3 .
Now both a3 and b3 are integers because products of integers are integers, and b3̸ = 0 by the zero
product property.
Thus r3 is a ratio of integers with a nonzero denominator, and so r3 is rational by definition of rational.
This contradicts the supposition that r3 is irrational. [Hence the supposition is false and the given
statement is true.]
b. Outline of proof by contraposition:
Starting point: Suppose r is any real number such that r is rational. (Or: Suppose r is any rational
number.)
Conclusion to be shown: r3 is rational.
Solution 2:
a. Proof (by contraposition): Suppose r is any real number such that r is rational. (Or: Suppose r is
any rational number.)
[We must show that r3 is rational.]
11
a. Proof (by contradiction): Suppose not. That is, suppose there is an integer n such that n3 is even
and n is odd.
[We must show that this supposition leads logically to a contradiction.]
By definition of odd, n = 2a + 1 for some integer a.
Thus, by substitution and algebra,
n3 = (2a + 1)3 = (2a + 1)2(2a + 1) = (4a2 + 4a + 1)(2a + 1) = 8a3 + 12a2 + 6a + 1 = 2(4a3 + 6a2 + 3a) + 1.
Let t = 4a3 + 6a2 + 3a. Then n3 = 2t + 1, and t is an integer because it is a sum of products of integers.
It follows that n3 is odd by definition of odd, which contradicts the supposition that n3 is even.
[Hence the supposition is false and the given statement is true.]
b. Outline of proof by contraposition:
Starting point: Suppose n is any integer such that n is odd. (Or: Suppose n is any odd integer.)
Conclusion to be shown: n3 is odd.
Solution 2:
a. Proof (by contraposition): Suppose n is any integer such that n is odd. (Or: Suppose n is any odd
integer.) [We must show that n3 is odd.]
By definition of odd, n = 2a + 1 for some integer a.
Thus n3 = (2a+1)3 = (2a+1)2(2a+1) = (4a2+4a+1)(2a+1) = 8a3+12a2+6a+1 = 2(4a3+6a2+3a)+1.
Let t = 4a3 + 6a2 + 3a. Then n3 = 2t + 1, and t is an integer because it is a sum of products of integers.
It follows that n3 is odd by definition of odd [as was to be shown].
b. Outline of proof by contradiction:
Starting point: Suppose not. That is, suppose there is an integer n such that n3 is even and n is odd.
Conclusion to be shown: We must show that this supposition leads logically to a contradiction.
22. Solution 1:
a. Proof (by contradiction): Suppose not. That is, suppose there is a real number r such that r3 is
irrational and r is rational.
[We must show that this supposition leads logically to a contradiction.]
By definition of rational, there exist integers a and b with b̸ = 0 such that r = a
b .
By substitution, r3 =
( a
b
)3
= a3
b3 .
Now both a3 and b3 are integers because products of integers are integers, and b3̸ = 0 by the zero
product property.
Thus r3 is a ratio of integers with a nonzero denominator, and so r3 is rational by definition of rational.
This contradicts the supposition that r3 is irrational. [Hence the supposition is false and the given
statement is true.]
b. Outline of proof by contraposition:
Starting point: Suppose r is any real number such that r is rational. (Or: Suppose r is any rational
number.)
Conclusion to be shown: r3 is rational.
Solution 2:
a. Proof (by contraposition): Suppose r is any real number such that r is rational. (Or: Suppose r is
any rational number.)
[We must show that r3 is rational.]
11
Loading page 12...
By definition of rational, there exist integers a and b with b̸ = 0 such that r = a
b .
By substitution, r3 =
( a
b
)3
= a3
b3 .
Now both a3 and b3 are integers because products of integers are integers, and b3̸ = 0 by the zero
product property.
Thus r3 is a ratio of integers with a nonzero denominator, and so r3 is rational by definition of rational
[as was to be shown].
b. Outline of proof by contradiction:
Starting point: Suppose not. That is, suppose there is a real number r such that r3 is irrational and r
is rational.
Conclusion to be shown: We must show that this supposition leads logically to a contradiction.
23. Solution 1:
a. Proof (by contradiction): Suppose not. That is, suppose there is an integer n such that n3 is odd
and n is even.
[We must show that this supposition leads logically to a contradiction.]
By definition of even, there is an integer a such that n = 2a.
Thus, by substitution and algebra,
n3 = (2a)3 = 8a3 = 2(4a3).
Let t = 4a3. Then n3 = 2t, and t is an integer because it is a product of integers.
It follows that n3 is even by definition of even, which contradicts the supposition that n3 is odd.
[Hence the supposition is false and the given statement is true.]
b. Outline of proof by contraposition:
Starting point: Suppose n is any integer such that n is even. (Or: Suppose n is any even integer.)
Conclusion to be shown: n3 is even.
Solution 2:
a. Proof (by contraposition): Suppose n is any integer such that n is even. (Or: Suppose n is any
even integer.) [We must show that n3 is even.]
By definition of even, there is an integer a such that n = 2a.
Thus, by substitution and algebra,
n3 = (2a)3 = 8a3 = 2(4a3).
Let t = 4a3. Then n3 = 2t, and t is an integer because it is a product of integers.
It follows that n3 is even by definition of even [as was to be shown].
b. Outline of proof by contradiction:
Starting point: Suppose not. That is, suppose there is an integer n such that n3 is odd and n is even.
Conclusion to be shown: We must show that this supposition leads logically to a contradiction.
24. The given statement is false.
Counterexample: Let r = √2. Then r is irrational, but r2 = (√2)2 = 2 is rational.
25. (i). rational
(ii). a and b are integers and b̸ = 0
(iii). a − 7b
(iv). a − 7b
4b
(v). both a − 7b and 4b are integers (since products and differences of integers are integers) and so √2
would be a rational number
(vi). the supposition is false and the given statement is true.
12
b .
By substitution, r3 =
( a
b
)3
= a3
b3 .
Now both a3 and b3 are integers because products of integers are integers, and b3̸ = 0 by the zero
product property.
Thus r3 is a ratio of integers with a nonzero denominator, and so r3 is rational by definition of rational
[as was to be shown].
b. Outline of proof by contradiction:
Starting point: Suppose not. That is, suppose there is a real number r such that r3 is irrational and r
is rational.
Conclusion to be shown: We must show that this supposition leads logically to a contradiction.
23. Solution 1:
a. Proof (by contradiction): Suppose not. That is, suppose there is an integer n such that n3 is odd
and n is even.
[We must show that this supposition leads logically to a contradiction.]
By definition of even, there is an integer a such that n = 2a.
Thus, by substitution and algebra,
n3 = (2a)3 = 8a3 = 2(4a3).
Let t = 4a3. Then n3 = 2t, and t is an integer because it is a product of integers.
It follows that n3 is even by definition of even, which contradicts the supposition that n3 is odd.
[Hence the supposition is false and the given statement is true.]
b. Outline of proof by contraposition:
Starting point: Suppose n is any integer such that n is even. (Or: Suppose n is any even integer.)
Conclusion to be shown: n3 is even.
Solution 2:
a. Proof (by contraposition): Suppose n is any integer such that n is even. (Or: Suppose n is any
even integer.) [We must show that n3 is even.]
By definition of even, there is an integer a such that n = 2a.
Thus, by substitution and algebra,
n3 = (2a)3 = 8a3 = 2(4a3).
Let t = 4a3. Then n3 = 2t, and t is an integer because it is a product of integers.
It follows that n3 is even by definition of even [as was to be shown].
b. Outline of proof by contradiction:
Starting point: Suppose not. That is, suppose there is an integer n such that n3 is odd and n is even.
Conclusion to be shown: We must show that this supposition leads logically to a contradiction.
24. The given statement is false.
Counterexample: Let r = √2. Then r is irrational, but r2 = (√2)2 = 2 is rational.
25. (i). rational
(ii). a and b are integers and b̸ = 0
(iii). a − 7b
(iv). a − 7b
4b
(v). both a − 7b and 4b are integers (since products and differences of integers are integers) and so √2
would be a rational number
(vi). the supposition is false and the given statement is true.
12
Loading page 13...
26. Proof: Suppose not. That is, suppose that 4 + 3√2 is rational. By definition of rational, 7 + 4√2 = a
b ,
where a and b are integers and b̸ = 0. Multiplying both sides by b gives
4b + 3b√2 = a,
so if we subtract 4b from both sides we have
3b√2 = a − 4b.
Dividing both sides by 3b gives
√2 = a − 4b
3b .
But then √2 would be a rational number because both a − 4b and 3b are integers (since products
and differences of integers are integers) and so √2 would be a rational number. This contradicts our
knowledge that √2 is irrational. Hence the supposition is false and the given statement is true.
27. 1
168⌈ 284 So 284 = 168 · 1 + 116, and hence gcd(284, 168) = gcd(168, 116)
168
116
1
116⌈ 168 So 168 = 116 · 1 + 52, and hence gcd(168, 116) = gcd(116, 52)
116
52
2
52⌈ 116 So 116 = 52 · 2 + 12, and hence gcd(116, 52) = gcd(52, 12)
104
12
4
12 ⌈ 52 So 52 = 12 · 4 + 4, and hence gcd(52, 12) = gcd(12, 4)
48
4
3
4 ⌈12 So 12 = 4 · 3 + 0, and hence gcd(12, 4) = gcd(4, 0)
12
0
But gcd(4, 0) = 4. So gcd(284, 168) = 4.
13
b ,
where a and b are integers and b̸ = 0. Multiplying both sides by b gives
4b + 3b√2 = a,
so if we subtract 4b from both sides we have
3b√2 = a − 4b.
Dividing both sides by 3b gives
√2 = a − 4b
3b .
But then √2 would be a rational number because both a − 4b and 3b are integers (since products
and differences of integers are integers) and so √2 would be a rational number. This contradicts our
knowledge that √2 is irrational. Hence the supposition is false and the given statement is true.
27. 1
168⌈ 284 So 284 = 168 · 1 + 116, and hence gcd(284, 168) = gcd(168, 116)
168
116
1
116⌈ 168 So 168 = 116 · 1 + 52, and hence gcd(168, 116) = gcd(116, 52)
116
52
2
52⌈ 116 So 116 = 52 · 2 + 12, and hence gcd(116, 52) = gcd(52, 12)
104
12
4
12 ⌈ 52 So 52 = 12 · 4 + 4, and hence gcd(52, 12) = gcd(12, 4)
48
4
3
4 ⌈12 So 12 = 4 · 3 + 0, and hence gcd(12, 4) = gcd(4, 0)
12
0
But gcd(4, 0) = 4. So gcd(284, 168) = 4.
13
Loading page 14...
28. 1
10673⌈11284 So 11284 = 10673 · 1 + 611, and hence gcd(11284, 10673) = gcd(10673, 611)
10673
611
17
611⌈10673 So 10673 = 611 · 17 + 286, and hence gcd(10673, 611) = gcd(611, 286)
10387
286
2
286 ⌈ 611 So 611 = 52 · 2 + 12, and hence gcd(611, 286) = gcd(286, 39)
572
39
7
39 ⌈ 286 So 286 = 39 · 4 + 4, and hence gcd(286, 39) = gcd(39, 13)
273
13
3
13 ⌈39 So 39 = 13 · 3 + 0, and hence gcd(39, 13) = gcd(13, 0)
39
0
But gcd(13, 0) = 13. So gcd(11284, 10673) = 13.
14
10673⌈11284 So 11284 = 10673 · 1 + 611, and hence gcd(11284, 10673) = gcd(10673, 611)
10673
611
17
611⌈10673 So 10673 = 611 · 17 + 286, and hence gcd(10673, 611) = gcd(611, 286)
10387
286
2
286 ⌈ 611 So 611 = 52 · 2 + 12, and hence gcd(611, 286) = gcd(286, 39)
572
39
7
39 ⌈ 286 So 286 = 39 · 4 + 4, and hence gcd(286, 39) = gcd(39, 13)
273
13
3
13 ⌈39 So 39 = 13 · 3 + 0, and hence gcd(39, 13) = gcd(13, 0)
39
0
But gcd(13, 0) = 13. So gcd(11284, 10673) = 13.
14
Loading page 15...
Discrete Mathematics with Applications, 5th 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
2k = 1
20 + 1
21 + 1
22 + 1
23 (= 1 + 1
2 + 1
4 + 1
8 = 15
8 )
2.
4∑
k=1
k2 = 12 + 22 + 32 + 42(= 1 + 4 + 9 + 16 = 30)
3. 13 − 23 + 33 − 43 + 53 =
5∑
k=1
(−1)k−1k2 (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
k2
n = (j − 1)2
n .
Therefore, n∑
k=1
k2
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
k2
k + n = (i − 1)2
i − 1 + n .
Therefore, n∑
k=0
k2
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.
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
2k = 1
20 + 1
21 + 1
22 + 1
23 (= 1 + 1
2 + 1
4 + 1
8 = 15
8 )
2.
4∑
k=1
k2 = 12 + 22 + 32 + 42(= 1 + 4 + 9 + 16 = 30)
3. 13 − 23 + 33 − 43 + 53 =
5∑
k=1
(−1)k−1k2 (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
k2
n = (j − 1)2
n .
Therefore, n∑
k=1
k2
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
k2
k + n = (i − 1)2
i − 1 + n .
Therefore, n∑
k=0
k2
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.
Loading page 16...
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 =
( 2m+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
= k2 + k − 6
2 + 2k + 2
2
by multiplying out
= k2 + k − 6 + 2k + 2
2
by adding the fractions
= k2 + 3k − 4
2
by combining like terms.
And the right-hand side of P (k + 1) is
2
( 2(m−1)+1 − 1
2 − 1
)
= 2(2m − 1).
Alternative answer:
2 + 22 + 23 + · · · + 2m = (1 + 2 + 22 + · · · + 2m) − 1 =
( 2m+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
= k2 + k − 6
2 + 2k + 2
2
by multiplying out
= k2 + k − 6 + 2k + 2
2
by adding the fractions
= k2 + 3k − 4
2
by combining like terms.
And the right-hand side of P (k + 1) is
2
Loading page 17...
(k − 1)(k + 4)
2 = k2 + 4k − k − 4
2 = k2 + 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)(k2 + 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)(k2 + 2k + 1 + 2k + 2 + 3)
3 =
(k − 1)(k2 + 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)(k2 + 2k + 3)
3 . ← P (k)
inductive hypothesis
We must show that
2 · 3 + 3 · 4 + · · · + k(k + 1) = (k − 1)(k2 + 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)(k2 + 2k + 3)
3 + k(k + 1)
by inductive hypothesis
= k3 + 2k2 + 3k − 2k2 − 4k − 6
3 + 3k(k + 1)
3
by creating a common denominator and multiplying out
= k3 − k − 6
3 + 3k2 + 3k
3
by multiplying out and combining like terms
= k3 + 3k2 + 2k − 6
3
by adding the fractions and combining like terms.
And the right-hand side of P (k + 1) is
(k − 1)(k2 + 4k + 6)
3 = k3 + 4k2 + 6k − k2 − 4k − 6
3 = k3 + 3k2 + 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 = 3n+1 − 1
2 . ← P (n)
3
2 = k2 + 4k − k − 4
2 = k2 + 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)(k2 + 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)(k2 + 2k + 1 + 2k + 2 + 3)
3 =
(k − 1)(k2 + 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)(k2 + 2k + 3)
3 . ← P (k)
inductive hypothesis
We must show that
2 · 3 + 3 · 4 + · · · + k(k + 1) = (k − 1)(k2 + 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)(k2 + 2k + 3)
3 + k(k + 1)
by inductive hypothesis
= k3 + 2k2 + 3k − 2k2 − 4k − 6
3 + 3k(k + 1)
3
by creating a common denominator and multiplying out
= k3 − k − 6
3 + 3k2 + 3k
3
by multiplying out and combining like terms
= k3 + 3k2 + 2k − 6
3
by adding the fractions and combining like terms.
And the right-hand side of P (k + 1) is
(k − 1)(k2 + 4k + 6)
3 = k3 + 4k2 + 6k − k2 − 4k − 6
3 = k3 + 3k2 + 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 = 3n+1 − 1
2 . ← P (n)
3
Loading page 18...
(Recall that by definition 1 + 3 + 32 + · · · + 3n =
n∑
i=0
3i.)
(a) P (0):
0∑
i=0
3i = 30+1 − 1
2
P (0) is true because the left-hand side equals
0∑
i=0
3i = 30 = 1, and the right-hand side
equals 30+1 − 1
2 = 3 − 1
2 = 1 also.
(b) P (k): 1 + 3 + 32 + · · · + 3k = 3k+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 = 3k+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 = 3k+1 − 1
2 . ← P (k)
inductive hypothesis
We must show that
1 + 3 + 32 + · · · + 3k+1 = 3k+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
= 3k+1 − 1
2 + 3k+1
by inductive hypothesis
= 3k+1 − 1
2 + 2 · 3k+1
2
by creating a common denominator
= 3 · 3k+1 − 1
2
by adding the fractions and combining like terms
= 3k+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 = 2n2 + 2n. ← P (n)
Note that 4 + 8 + 12 + · · · + 4n =
n∑
i=1
4i.
4
n∑
i=0
3i.)
(a) P (0):
0∑
i=0
3i = 30+1 − 1
2
P (0) is true because the left-hand side equals
0∑
i=0
3i = 30 = 1, and the right-hand side
equals 30+1 − 1
2 = 3 − 1
2 = 1 also.
(b) P (k): 1 + 3 + 32 + · · · + 3k = 3k+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 = 3k+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 = 3k+1 − 1
2 . ← P (k)
inductive hypothesis
We must show that
1 + 3 + 32 + · · · + 3k+1 = 3k+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
= 3k+1 − 1
2 + 3k+1
by inductive hypothesis
= 3k+1 − 1
2 + 2 · 3k+1
2
by creating a common denominator
= 3 · 3k+1 − 1
2
by adding the fractions and combining like terms
= 3k+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 = 2n2 + 2n. ← P (n)
Note that 4 + 8 + 12 + · · · + 4n =
n∑
i=1
4i.
4
Loading page 19...
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 · 12 + 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 = 2k2 + 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
= (2k2 + 2k) + 4(k + 1)
by inductive hypothesis
= 2k2 + 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(k2 + 2k + 1) + 2k + 2 = 2k2 + 4k + 2 + 2k + 2 = 2k2 + 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 right-
hand 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
1∑
i=1
4i = 4 · 1 = 4 and the
right-hand side is 2 · 12 + 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 = 2k2 + 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
= (2k2 + 2k) + 4(k + 1)
by inductive hypothesis
= 2k2 + 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(k2 + 2k + 1) + 2k + 2 = 2k2 + 4k + 2 + 2k + 2 = 2k2 + 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 right-
hand 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
Loading page 20...
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
= k2 + k − 6
2 + 2k + 2
2
by multiplying out
= k2 + 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 = k2 + 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)(n2 + 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)(k2 + 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
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
= k2 + k − 6
2 + 2k + 2
2
by multiplying out
= k2 + 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 = k2 + 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)(n2 + 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)(k2 + 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
Loading page 21...
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)(k2 + 2k + 3)
3 + k · (k + 1)
by inductive hypothesis
= k3 + 2k2 + 3k − 2k2 − 4k − 6
3 + k2 + k
by combining like terms
= k3 − k − 6
3 + 3 · (k2 + k)
3
by creating a common denominator
= k3 − k − 6
3 + 3k2 + 3k
3
by multiplying out
= k3 + 3k2 + 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)(k2 + 2k + 1 + 2k + 2 + 3)
3
= (k − 1)(k2 + 4k + 6)
3 = (k − 1)(k2 + 4k + 6)
3
= k3 + 4k2 + 6k − k2 − 4k − 6
3 = k3 + 3k2 + 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 = 3n+1 − 1
2 . . ← P (n)
Note that 1 + 3 + 32 + · · · + 3n =
n∑
i=0
3i.
Show that P(0) is true: P (0) is true because the left-hand side is
0∑
i=0
3i = 30 = 1, and the
right-hand side is 30+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 = 3k+1 − 1
2 . ← P (k)
inductive hypothesis
We must show that
1 + 3 + 32 + · · · + 3k+1 = 3(k+1)+1 − 1
2 .
Or, equivalently, that
1 + 3 + 32 + · · · + 3k+1 = 3k+2 − 1
2 ← P (k + 1)
.
7
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)(k2 + 2k + 3)
3 + k · (k + 1)
by inductive hypothesis
= k3 + 2k2 + 3k − 2k2 − 4k − 6
3 + k2 + k
by combining like terms
= k3 − k − 6
3 + 3 · (k2 + k)
3
by creating a common denominator
= k3 − k − 6
3 + 3k2 + 3k
3
by multiplying out
= k3 + 3k2 + 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)(k2 + 2k + 1 + 2k + 2 + 3)
3
= (k − 1)(k2 + 4k + 6)
3 = (k − 1)(k2 + 4k + 6)
3
= k3 + 4k2 + 6k − k2 − 4k − 6
3 = k3 + 3k2 + 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 = 3n+1 − 1
2 . . ← P (n)
Note that 1 + 3 + 32 + · · · + 3n =
n∑
i=0
3i.
Show that P(0) is true: P (0) is true because the left-hand side is
0∑
i=0
3i = 30 = 1, and the
right-hand side is 30+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 = 3k+1 − 1
2 . ← P (k)
inductive hypothesis
We must show that
1 + 3 + 32 + · · · + 3k+1 = 3(k+1)+1 − 1
2 .
Or, equivalently, that
1 + 3 + 32 + · · · + 3k+1 = 3k+2 − 1
2 ← P (k + 1)
.
7
Loading page 22...
(a) 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
= 3k+1 − 1
2 + 3k+1
by inductive hypothesis
= 3k+1 − 1
2 + 2 · 3k+1
2
by creating a common denominator
= 3 · 3k+1 − 1
2
by adding the fractions and combining like terms
= 3k+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].
16. Proof (by mathematical induction): Let the property P (n) be the sentence
8n − 1 is divisible by 7. ← P (n)
We will prove that P (n) is true for all integers n ≥ 0.
Show that P(0) is true: P (0) is true because because 80 − 1 = 1 − 1 = 0 and 0 is divisible
by 7 (since 0 = 0 · 7).
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
8k − 1 is divisible by 7. ← P (k)
inductive hypothesis
We must show that
8k+1 − 1 is divisible by 7. ← P (k + 1)
By definition of divisibility, the inductive hypothesis is equivalent to the statement that there
is an integer r with
8k − 1 = 7r.
Then 8k+1 − 1 = 8 · 8k − 1
= (7 + 1)8k − 1
= 7 · 8k + (8k − 1) by algebra
= 7 · 8k + 7r by inductive hypothesis
= 7(8k + r) by algebra.
Now 8k + r is an integer because products and sums of integers are integers.Thus, by definition
of divisibility, 8k+1 − 1 is divisible by 7 [as was to be shown].
17. Proof (by mathematical induction): Let the property P (n) be the inequality
1 + 4n < 2n. ← P (n)
We will prove that P (n) is true for all integers n ≥ 5.
8
1 + 3 + 32 + · · · + 3k+1 = 1 + 3 + 32 + · · · + 3k + 3k+1
by making the next-to-last term explicit
= 3k+1 − 1
2 + 3k+1
by inductive hypothesis
= 3k+1 − 1
2 + 2 · 3k+1
2
by creating a common denominator
= 3 · 3k+1 − 1
2
by adding the fractions and combining like terms
= 3k+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].
16. Proof (by mathematical induction): Let the property P (n) be the sentence
8n − 1 is divisible by 7. ← P (n)
We will prove that P (n) is true for all integers n ≥ 0.
Show that P(0) is true: P (0) is true because because 80 − 1 = 1 − 1 = 0 and 0 is divisible
by 7 (since 0 = 0 · 7).
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
8k − 1 is divisible by 7. ← P (k)
inductive hypothesis
We must show that
8k+1 − 1 is divisible by 7. ← P (k + 1)
By definition of divisibility, the inductive hypothesis is equivalent to the statement that there
is an integer r with
8k − 1 = 7r.
Then 8k+1 − 1 = 8 · 8k − 1
= (7 + 1)8k − 1
= 7 · 8k + (8k − 1) by algebra
= 7 · 8k + 7r by inductive hypothesis
= 7(8k + r) by algebra.
Now 8k + r is an integer because products and sums of integers are integers.Thus, by definition
of divisibility, 8k+1 − 1 is divisible by 7 [as was to be shown].
17. Proof (by mathematical induction): Let the property P (n) be the inequality
1 + 4n < 2n. ← P (n)
We will prove that P (n) is true for all integers n ≥ 5.
8
Loading page 23...
Show that P(5) is true: P (5) is true because the left-hand side is 1 + 4 · 5 = 21 and the
right-hand side is 25 = 32, and 21 < 32.
Show that for all integers k ≥ 5, if P(k ) is true then P (k + 1) is true: Let k be
any integer with k ≥ 5, and suppose
1 + 4k < 2k. ← P (k)
inductive hypothesis
We must show that
1 + 4(k + 1) < 2k+1. ← P (k + 1)
By algebra and the inductive hypothesis we have that
1 + 4(k + 1) = 1 + 4k + 4 < 2k + 4.
So
1 + 4(k + 1) < 2k + 4. (*)
Now, since k ≥ 5,
4 < 2k = 2k(2 − 1) = 2k+1 − 2k,
and thus,
2k + 4 < 2k+1. (**)
Using the transitive property of order to combine inequalities (*) and (**) gives that
1 + 4(k + 1) < 2k+1,
[as was to be shown].
[Here is the scratch work used to motivate some steps: Given that inequality (*) is established,
we will be finished if we can show that 2k + 4 < 2k+1. Now
2k + 4 < 2k+1 ⇔ 4 < 2k+1 − 2k = 2 · 2k − 2k = 2k(2 − 1) = 2k.
But when k ≥ 5, 4 < 2k, so the desired inequality is true.]
18. Proof (by mathematical induction): Let the property P (n) be the sentence
If a1, a2, . . . , an and b1, b2, . . . , bn are any real
numbers, then ∑n
k=1(2ak − 3bk) = 2 ∑n
k=1 ak − 3 ∑n
k=1 bk.. ← P (n)
Show that P(1) is true: Let a1 and b1 be any real numbers. By the recursive definition of
summation, 1∑
k=1
(2ak − 3bk) = 2a1 − 3b1, 2
1∑
k=1
ak = 2a1, 3
1∑
k=1
bk = 3b1,
and so 1∑
k=1
(2ak − 3bk) = 2
1∑
k=1
ak − 3
1∑
k=1
bk.
Hence P (1) is true.
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
If a1, a2, . . . , am and b1, b2, . . . , bm are any real
numbers, then ∑m
k=1(2ak − 3bk) = 2 ∑m
k=1 ak − 3 ∑m
k=1 bk. ← P (m)
inductive hypothesis
9
right-hand side is 25 = 32, and 21 < 32.
Show that for all integers k ≥ 5, if P(k ) is true then P (k + 1) is true: Let k be
any integer with k ≥ 5, and suppose
1 + 4k < 2k. ← P (k)
inductive hypothesis
We must show that
1 + 4(k + 1) < 2k+1. ← P (k + 1)
By algebra and the inductive hypothesis we have that
1 + 4(k + 1) = 1 + 4k + 4 < 2k + 4.
So
1 + 4(k + 1) < 2k + 4. (*)
Now, since k ≥ 5,
4 < 2k = 2k(2 − 1) = 2k+1 − 2k,
and thus,
2k + 4 < 2k+1. (**)
Using the transitive property of order to combine inequalities (*) and (**) gives that
1 + 4(k + 1) < 2k+1,
[as was to be shown].
[Here is the scratch work used to motivate some steps: Given that inequality (*) is established,
we will be finished if we can show that 2k + 4 < 2k+1. Now
2k + 4 < 2k+1 ⇔ 4 < 2k+1 − 2k = 2 · 2k − 2k = 2k(2 − 1) = 2k.
But when k ≥ 5, 4 < 2k, so the desired inequality is true.]
18. Proof (by mathematical induction): Let the property P (n) be the sentence
If a1, a2, . . . , an and b1, b2, . . . , bn are any real
numbers, then ∑n
k=1(2ak − 3bk) = 2 ∑n
k=1 ak − 3 ∑n
k=1 bk.. ← P (n)
Show that P(1) is true: Let a1 and b1 be any real numbers. By the recursive definition of
summation, 1∑
k=1
(2ak − 3bk) = 2a1 − 3b1, 2
1∑
k=1
ak = 2a1, 3
1∑
k=1
bk = 3b1,
and so 1∑
k=1
(2ak − 3bk) = 2
1∑
k=1
ak − 3
1∑
k=1
bk.
Hence P (1) is true.
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
If a1, a2, . . . , am and b1, b2, . . . , bm are any real
numbers, then ∑m
k=1(2ak − 3bk) = 2 ∑m
k=1 ak − 3 ∑m
k=1 bk. ← P (m)
inductive hypothesis
9
Loading page 24...
We must show that
If a1, a2, . . . , am+1 and b1, b2, . . . , bm+1 are any real
numbers, then ∑m+1
k=1 (2ak − 3bk) = 2 ∑m+1
k=1 ak − 3 ∑m+1
k=1 bk.. ← P (m + 1)
So suppose a1, a2, . . . , am+1 and b1, b2, . . . , bm+1 are any real numbers. Then
∑m+1
k=1 (2ak − 3bk)
= ∑m
k=1(2ak − 3bk) + (2am+1 − 3bm+1) by the recursive definition of summation
= (2 ∑m
k=1 ak − 3 ∑m
k=1 bk) + (2am+1 − 3bm+1) by substitution from the inductive
hypothesis
= (2 ∑m
k=1 ak + 2am+1) − (3 ∑m
k=1 bk + 3bm+1) by the associative and commutative
laws of algebra
= 2 ∑m+1
k=1 ak − 3 ∑m+1
k=1 bk by the recursive definition of summation
[This is what was to be shown.]
19. Proof (by strong mathematical induction): Let the property P (n) be the sentence
n is either a prime number or a product of prime numbers.
We will prove that P (n) is true for all integers n ≥ 2.
Show that P(2 ) is true: When n = 2, the sentence is “2 is either a prime number or a
product of prime numbers.” This sentence is true because 2 is prime. Hence P (2) is true.
Show that if k ≥ 2 and P(i ) is true for all integers i from 2 through k , then
P(k + 1) is true: Let be any integer with k ≥ 2, and suppose that
For all integers i with 2 ≤ i ≤ k, i is either
a prime number or a product of prime numbers. ← inductive hypothesis
We must show that
k + 1 is either a prime number or a product of prime numbers.
In case k + 1 is prime, the sentence is true. So suppose k + 1 is not prime. Then, by definition
of prime, k + 1 = rs for some positive integers r and s with r̸ = 1 and s̸ = 1. By Theorem
4.3.1, r ≤ k and s ≤ k, and, because neither r nor s equals 1, r < k and s < k. Thus, by
inductive hypothesis, each of r and s is either a prime number or a product of prime numbers.
So, because k + 1 is the product of r and s, k + 1 is a product of prime numbers [as was to be
shown].
20. Proof (by strong mathematical induction): A sequence a0, a1, a2, . . . is defined recursively as
follows:
a0 = 2, a1 = 9
ak = 5ak−1 − 6ak−2 for all integers k ≥ 2.
Let the property P (n) be the equation
an = 5 · 3n − 3 · 2n. ← P (n)
We will prove that P (n) is true for all integers n ≥ 0.
Show that P(0) and P(1) are true: By definition of a0, a1, a2, . . ., we have that a0 = 2
and a1 = 9. Since 5· 30 − 3· 20 = 5 − 3 = 2 and 5· 31 − 3· 21 = 15 − 6 = 9, P (0) and P (1) are
both true.
10
If a1, a2, . . . , am+1 and b1, b2, . . . , bm+1 are any real
numbers, then ∑m+1
k=1 (2ak − 3bk) = 2 ∑m+1
k=1 ak − 3 ∑m+1
k=1 bk.. ← P (m + 1)
So suppose a1, a2, . . . , am+1 and b1, b2, . . . , bm+1 are any real numbers. Then
∑m+1
k=1 (2ak − 3bk)
= ∑m
k=1(2ak − 3bk) + (2am+1 − 3bm+1) by the recursive definition of summation
= (2 ∑m
k=1 ak − 3 ∑m
k=1 bk) + (2am+1 − 3bm+1) by substitution from the inductive
hypothesis
= (2 ∑m
k=1 ak + 2am+1) − (3 ∑m
k=1 bk + 3bm+1) by the associative and commutative
laws of algebra
= 2 ∑m+1
k=1 ak − 3 ∑m+1
k=1 bk by the recursive definition of summation
[This is what was to be shown.]
19. Proof (by strong mathematical induction): Let the property P (n) be the sentence
n is either a prime number or a product of prime numbers.
We will prove that P (n) is true for all integers n ≥ 2.
Show that P(2 ) is true: When n = 2, the sentence is “2 is either a prime number or a
product of prime numbers.” This sentence is true because 2 is prime. Hence P (2) is true.
Show that if k ≥ 2 and P(i ) is true for all integers i from 2 through k , then
P(k + 1) is true: Let be any integer with k ≥ 2, and suppose that
For all integers i with 2 ≤ i ≤ k, i is either
a prime number or a product of prime numbers. ← inductive hypothesis
We must show that
k + 1 is either a prime number or a product of prime numbers.
In case k + 1 is prime, the sentence is true. So suppose k + 1 is not prime. Then, by definition
of prime, k + 1 = rs for some positive integers r and s with r̸ = 1 and s̸ = 1. By Theorem
4.3.1, r ≤ k and s ≤ k, and, because neither r nor s equals 1, r < k and s < k. Thus, by
inductive hypothesis, each of r and s is either a prime number or a product of prime numbers.
So, because k + 1 is the product of r and s, k + 1 is a product of prime numbers [as was to be
shown].
20. Proof (by strong mathematical induction): A sequence a0, a1, a2, . . . is defined recursively as
follows:
a0 = 2, a1 = 9
ak = 5ak−1 − 6ak−2 for all integers k ≥ 2.
Let the property P (n) be the equation
an = 5 · 3n − 3 · 2n. ← P (n)
We will prove that P (n) is true for all integers n ≥ 0.
Show that P(0) and P(1) are true: By definition of a0, a1, a2, . . ., we have that a0 = 2
and a1 = 9. Since 5· 30 − 3· 20 = 5 − 3 = 2 and 5· 31 − 3· 21 = 15 − 6 = 9, P (0) and P (1) are
both true.
10
Loading page 25...
Show that if k ≥ 1 and P(i ) is true for all integers i from 0 through k, then
P(k + 1) is true: Let k be any integer with k ≥ 1, and suppose
ai = 5 · 3i − 3 · 2i for all integers i with 0 ≤ i ≤ k. ← inductive hypothesis
We must show that
ak+1 = 5 · 3k+1 − 3 · 2k+1.
But
ak+1 = 5ak − 6ak−1 by definition of a0, a1, a2, . . .
= 5(5 · 3k − 3 · 2k) − 6(5 · 3k−1 − 3 · 2k−1) by inductive hypothesis
= 5(5 · 3 · 3k−1 − 3 · 2 · 2k−1) − 6(5 · 3k−1 − 3 · 2k−1) because 3k= 3 · 3k−1 and 2k= 2 · 2k−1
= (75· 3k−1 − 30· 2k−1) − (30· 3k−1 − 18· 2k−1)
= (75 − 30)· 3k−1 − (30 − 18)· 2k−1
= 45· 3k−1 + 12· 2k−1
= 5· 32 · 3k−1 + 3· 22 · 2k−1
= 5· 3k+1 + 3· 2k+1 by algebra,
[as was to be shown].
[Since both the basis and the inductive steps have been proved, we conclude that P (n) is true
for all integers n ≥ 0.]
21. Proof (by strong mathematical induction):A sequence s1, s2, s3, ... is defined recursively as fol-
lows: sk = 5sk−1 + (sk−2)2 for all integers k ≥ 3
s1 = 4
s2 = 8
Let the property P (n) be the sentence
sn is divisible by 4. ← P (n)
We will prove that P (n) is true for all integers n ≥ 1.
Show that P(1) and P(2) are true: By definition of s1, s2, s3, ..., we have that s1 = 4 and
s2 = 8. Since both 4 and 8 are divisible by 4, P (1) and P (2) are both true.
Show that if k ≥ 2 and P(i ) is true for all integers i from 0 through k, then
P(k + 1) is true: Let k be any integer with k ≥ 2, and suppose
sk is divisible by 4 for all integers i with 0 ≤ i ≤ k. ← inductive hypothesis
We must show that
sk+1 is divisible by 4.
Now, by definition of s1, s2, s3, ..,
sk+1 = 5sk + (sk−1)2.
By inductive hypothesis,both sk and sk−1 are divisible by 4. Hence, there exist integers a and
b so that
sk = 4a and sk−1 = 4b.
Then
sk+1 = 5sk + (sk−1)2
= 5(4a) + (4b)2 by substitution
= 4(5a) + 4(4b2) because 3k= 3 · 3k−1 and 2k= 2 · 2k−1
= 4(5a + 4b2) by algebra.
11
P(k + 1) is true: Let k be any integer with k ≥ 1, and suppose
ai = 5 · 3i − 3 · 2i for all integers i with 0 ≤ i ≤ k. ← inductive hypothesis
We must show that
ak+1 = 5 · 3k+1 − 3 · 2k+1.
But
ak+1 = 5ak − 6ak−1 by definition of a0, a1, a2, . . .
= 5(5 · 3k − 3 · 2k) − 6(5 · 3k−1 − 3 · 2k−1) by inductive hypothesis
= 5(5 · 3 · 3k−1 − 3 · 2 · 2k−1) − 6(5 · 3k−1 − 3 · 2k−1) because 3k= 3 · 3k−1 and 2k= 2 · 2k−1
= (75· 3k−1 − 30· 2k−1) − (30· 3k−1 − 18· 2k−1)
= (75 − 30)· 3k−1 − (30 − 18)· 2k−1
= 45· 3k−1 + 12· 2k−1
= 5· 32 · 3k−1 + 3· 22 · 2k−1
= 5· 3k+1 + 3· 2k+1 by algebra,
[as was to be shown].
[Since both the basis and the inductive steps have been proved, we conclude that P (n) is true
for all integers n ≥ 0.]
21. Proof (by strong mathematical induction):A sequence s1, s2, s3, ... is defined recursively as fol-
lows: sk = 5sk−1 + (sk−2)2 for all integers k ≥ 3
s1 = 4
s2 = 8
Let the property P (n) be the sentence
sn is divisible by 4. ← P (n)
We will prove that P (n) is true for all integers n ≥ 1.
Show that P(1) and P(2) are true: By definition of s1, s2, s3, ..., we have that s1 = 4 and
s2 = 8. Since both 4 and 8 are divisible by 4, P (1) and P (2) are both true.
Show that if k ≥ 2 and P(i ) is true for all integers i from 0 through k, then
P(k + 1) is true: Let k be any integer with k ≥ 2, and suppose
sk is divisible by 4 for all integers i with 0 ≤ i ≤ k. ← inductive hypothesis
We must show that
sk+1 is divisible by 4.
Now, by definition of s1, s2, s3, ..,
sk+1 = 5sk + (sk−1)2.
By inductive hypothesis,both sk and sk−1 are divisible by 4. Hence, there exist integers a and
b so that
sk = 4a and sk−1 = 4b.
Then
sk+1 = 5sk + (sk−1)2
= 5(4a) + (4b)2 by substitution
= 4(5a) + 4(4b2) because 3k= 3 · 3k−1 and 2k= 2 · 2k−1
= 4(5a + 4b2) by algebra.
11
Loading page 26...
Now 5a + 4b2 is an integer because products and sums of integers are integers, and thus sk+1
is divisible by 4 by definition of divisibility. [This is what was to be shown.]
[Since both the basis and the inductive steps have been proved, we conclude that P (n) is true
for all integers n ≥ 0.]
22. Proof:
I. Basis Property: I(0) is the statement
i = 0 + 1 = 1 and product := A[1].
According to the pre-condition this statement is true.
II. Inductive Property: The guard G is the condition i̸ = m. Suppose k is any nonnegative
integer such that G ∧ I(k) is true before an iteration of the loop. Then when execution comes
to the top of the loop, i̸ = m,
product = A[1]· A[2] · · · A[k + 1] and i = k + 1.
Since i̸ = m, the guard is passed and statement 1 is executed. Now before execution of
statement 1, iold = k + 1. So after execution of statement 1,
inew = iold + 1 = (k + 1) + 1 = k + 2.
Also before statement 2 is executed,
productold = A[1]· A[2] · · · A[k + 1]
Statement 2 states that
productnew := productold · A[inew],
Since
A[inew] = A[k + 2],
after statement 2 is executed we have that
productnew = productold · A[k + 2] = A[1]· A[2] · · · A[k + 1] · A[k + 2].
Hence I(k + 1) is true.
III. Eventual Falsity of Guard: The guard G is the condition i̸ = m. By I and II, it is
known that for all integers n ≥ 1, after n iterations of the loop I(n) is true. Hence after m − 1
iterations of the loop I(m) is true, which implies that i = m and G is false.
IV. Correctness of the Post-Condition: Suppose that N is the least number of iterations
after which G is false and I(N ) is true. Then (since G is false) i = m and (since I(N ) is true)
i = N + 1 and product = A[1]· A[2] · · · A[N + 1] and i = m.
Putting these together gives m = N + 1 and so
product = A[1]· A[2] · · · A[m],
which is the post-condition.
23. a. s1 = 4 (two move to transfer the two disks to pole B and two more moves to transfer them
to pole C)
s2 = 16 (by the reasoning above, 4 moves are needed to transfer the top two disks from pole
A to pole C, then 2 moves are needed to transfer the two bottom disks from pole A to pole B,
another 4 moves to transfer the top two disks back to pole A, then 2 more to transfer the two
12
is divisible by 4 by definition of divisibility. [This is what was to be shown.]
[Since both the basis and the inductive steps have been proved, we conclude that P (n) is true
for all integers n ≥ 0.]
22. Proof:
I. Basis Property: I(0) is the statement
i = 0 + 1 = 1 and product := A[1].
According to the pre-condition this statement is true.
II. Inductive Property: The guard G is the condition i̸ = m. Suppose k is any nonnegative
integer such that G ∧ I(k) is true before an iteration of the loop. Then when execution comes
to the top of the loop, i̸ = m,
product = A[1]· A[2] · · · A[k + 1] and i = k + 1.
Since i̸ = m, the guard is passed and statement 1 is executed. Now before execution of
statement 1, iold = k + 1. So after execution of statement 1,
inew = iold + 1 = (k + 1) + 1 = k + 2.
Also before statement 2 is executed,
productold = A[1]· A[2] · · · A[k + 1]
Statement 2 states that
productnew := productold · A[inew],
Since
A[inew] = A[k + 2],
after statement 2 is executed we have that
productnew = productold · A[k + 2] = A[1]· A[2] · · · A[k + 1] · A[k + 2].
Hence I(k + 1) is true.
III. Eventual Falsity of Guard: The guard G is the condition i̸ = m. By I and II, it is
known that for all integers n ≥ 1, after n iterations of the loop I(n) is true. Hence after m − 1
iterations of the loop I(m) is true, which implies that i = m and G is false.
IV. Correctness of the Post-Condition: Suppose that N is the least number of iterations
after which G is false and I(N ) is true. Then (since G is false) i = m and (since I(N ) is true)
i = N + 1 and product = A[1]· A[2] · · · A[N + 1] and i = m.
Putting these together gives m = N + 1 and so
product = A[1]· A[2] · · · A[m],
which is the post-condition.
23. a. s1 = 4 (two move to transfer the two disks to pole B and two more moves to transfer them
to pole C)
s2 = 16 (by the reasoning above, 4 moves are needed to transfer the top two disks from pole
A to pole C, then 2 moves are needed to transfer the two bottom disks from pole A to pole B,
another 4 moves to transfer the top two disks back to pole A, then 2 more to transfer the two
12
Loading page 27...
bottom disks from pole B to pole C, and finally 4 moves to transfer the two top disks from
pole A to pole C)
b. sk = sk−1 (moves to transfer the top 2(k − 1) disks from pole A to pole C)
+2 (moves to transfer the two bottom disks from pole A to pole B)
+sk−1 (moves to transfer the top 2(k − 1) disks from pole C to pole A)
+2 (move to transfer the two bottom disks from pole B to pole C)
+sk−1 (moves to transfer the top 2(k − 1) disks from pole A to pole C).
So sk = 3sk−1 + 4 for all integers k ≥ 2.
24. a. t1 = 3, t2 = 3 + 3 + 3 = 9
b. For all integers k ≥ 2,
tk = tk−1 (moves to transfer the top 3k − 3 disks from pole A to pole B)
+3 (moves to transfer the bottom two disks from pole A to pole C)
+tk−1 (moves to transfer the top 3k − 3 disks from pole B to pole C)
= 2tk−1 + 3.
Note that transferring the stack of 3k disks from pole A to pole C requires at least two transfers
of the top 3(k − 1) disks: one to transfer them off the bottom two disks to free the bottom
disks so that they can be moved to pole C and another to transfer the top 3(k − 1) disks
back on top of the bottom two disks. Thus at least 3tk−1 moves are needed to effect these
two transfers. Three more moves are needed to transfer the bottom three disks from pole A
to pole C, and this transfer cannot be effected in fewer than three moves. It follows that the
sequence of moves indicated in the description of the equation above is, in fact, minimal.
25. s0 = 1 because there is one rabbit pair at the beginning of the first month (i.e., at the end of
month 0), and s1 = 1 and s2 = 1 because rabbits are not fertile during their first two months
of life. Thereafter, sk = sk−1 + 4sk−3 for all integers k ≥ 3.
The reason is that for k ≥ 3,
sk =
[ the number of pairs of rabbits
alive at the end of month k − 1
]
+ 4·
[ the number of pairs of rabbits
that are fertile during month k
]
=
[ the number of pairs of rabbits
alive at the end of month k − 1
]
+ 4·
[ the number of pairs of rabbits
alive at the end of month k − 3
]
= sk−1 + 4sk−3.
26. a. When 4% interest is compounded quarterly, the interest rate per quarter is 0.04
4 = 0.01. If
Sk is the amount on deposit at the end of the kth quarter, then
Sk = Sk−1 + (0.01)Sk−1 = (1 + 0.01) Sk−1 = (1.01) Sk−1 for each integer k ≥ 1.
b. Because 3 years is 12 quarters, we need to compute S12. Now S0 = $5000, and so
S12 = (1.01) S11
= (1.01) [(1.01) S10] = (1.01)2 S10 = (1.01)2 [(1.01) S9] = (1.01)3 S9
= (1.01)3 [(1.01) S8] = (1.01)4 S8 = (1.01)4 [(1.01) S7] = (1.01)5 S7
= (1.01)5 [(1.01) S6] = (1.01)6 S6 = (1.01)6 [(1.01) S5] = (1.01)7 S5
= (1.01)7 [(1.01) S4] = (1.01)8 S4 = (1.01)8 [(1.01) S3] = (1.01)9 S3
= (1.01)9 [(1.01) S2] = (1.01)10 S2 = (1.01)10 [(1.01) S1] = (1.01)11 S1
= (1.01)11 [(1.01) S0] = (1.01)12 S0 = (1.01)12 · 5000 ∼= 5634.13 dollars.
13
pole A to pole C)
b. sk = sk−1 (moves to transfer the top 2(k − 1) disks from pole A to pole C)
+2 (moves to transfer the two bottom disks from pole A to pole B)
+sk−1 (moves to transfer the top 2(k − 1) disks from pole C to pole A)
+2 (move to transfer the two bottom disks from pole B to pole C)
+sk−1 (moves to transfer the top 2(k − 1) disks from pole A to pole C).
So sk = 3sk−1 + 4 for all integers k ≥ 2.
24. a. t1 = 3, t2 = 3 + 3 + 3 = 9
b. For all integers k ≥ 2,
tk = tk−1 (moves to transfer the top 3k − 3 disks from pole A to pole B)
+3 (moves to transfer the bottom two disks from pole A to pole C)
+tk−1 (moves to transfer the top 3k − 3 disks from pole B to pole C)
= 2tk−1 + 3.
Note that transferring the stack of 3k disks from pole A to pole C requires at least two transfers
of the top 3(k − 1) disks: one to transfer them off the bottom two disks to free the bottom
disks so that they can be moved to pole C and another to transfer the top 3(k − 1) disks
back on top of the bottom two disks. Thus at least 3tk−1 moves are needed to effect these
two transfers. Three more moves are needed to transfer the bottom three disks from pole A
to pole C, and this transfer cannot be effected in fewer than three moves. It follows that the
sequence of moves indicated in the description of the equation above is, in fact, minimal.
25. s0 = 1 because there is one rabbit pair at the beginning of the first month (i.e., at the end of
month 0), and s1 = 1 and s2 = 1 because rabbits are not fertile during their first two months
of life. Thereafter, sk = sk−1 + 4sk−3 for all integers k ≥ 3.
The reason is that for k ≥ 3,
sk =
[ the number of pairs of rabbits
alive at the end of month k − 1
]
+ 4·
[ the number of pairs of rabbits
that are fertile during month k
]
=
[ the number of pairs of rabbits
alive at the end of month k − 1
]
+ 4·
[ the number of pairs of rabbits
alive at the end of month k − 3
]
= sk−1 + 4sk−3.
26. a. When 4% interest is compounded quarterly, the interest rate per quarter is 0.04
4 = 0.01. If
Sk is the amount on deposit at the end of the kth quarter, then
Sk = Sk−1 + (0.01)Sk−1 = (1 + 0.01) Sk−1 = (1.01) Sk−1 for each integer k ≥ 1.
b. Because 3 years is 12 quarters, we need to compute S12. Now S0 = $5000, and so
S12 = (1.01) S11
= (1.01) [(1.01) S10] = (1.01)2 S10 = (1.01)2 [(1.01) S9] = (1.01)3 S9
= (1.01)3 [(1.01) S8] = (1.01)4 S8 = (1.01)4 [(1.01) S7] = (1.01)5 S7
= (1.01)5 [(1.01) S6] = (1.01)6 S6 = (1.01)6 [(1.01) S5] = (1.01)7 S5
= (1.01)7 [(1.01) S4] = (1.01)8 S4 = (1.01)8 [(1.01) S3] = (1.01)9 S3
= (1.01)9 [(1.01) S2] = (1.01)10 S2 = (1.01)10 [(1.01) S1] = (1.01)11 S1
= (1.01)11 [(1.01) S0] = (1.01)12 S0 = (1.01)12 · 5000 ∼= 5634.13 dollars.
13
Loading page 28...
So approximately $5,634.13 is in the account at the end of three years.
c. The APR is the percentage increase in the account after one year. Because one year
is four quarters, we need to calculate S4 − S0
S0
. Now, by a similar computation as above,
S4 = (1.01)4 S0, and so
APR = S4 − S0
S0
∼= (1.01)4 S0 − S0
S0
= (1.01)4 − 1 ∼= 4.06%.
27. a. a1 = 3, a2 = 4a1 + 2 = 4 · 3 + 2 = 14, and a3 = 4a2 + 2 = 4 · 14 + 2 = 58
b. a6 = 4a5 + 2 = 4(44 · 3 + 43 · 2 + 42 · 2 + 4 · 2 + 2) + 2
= 4 · 44 · 3 + 4 · 43 · 2 + 4 · 42 · 2 + 4 · 2 + 4 · 2 + 2
= 45 · 3 + 44 · 2 + 43 · 2 + 42 · 2 + 4 · 2 + 2
c. Guess: an = 4n−1 · 3 + 4n−2 · 2 + 4n−3 · 2 + · · · + 42 · 2 + 4 · 2 + 2
= 4n−1 · 3 + 2 (4n−2 + 4n−3 + · · · + 42 + 4 + 1)
= 4n−1 · 3 + 2
( 4(n−2)+1 − 1
4 − 1
)
= 4n−1 · 3 + 2
( 4n−1 − 1
3
)
= 3 · 4n−1 + 2
3 · 4n−1 − 2
3
= 9
3 · 4n−1 + 2
3 · 4n−1 − 2
3 = 11
3 · 4n−1 − 2
3
28. a. c0 = 1, and so c1 = 7c0 + 2 = 7 · 1 + 2 = 9 and c2 = 7c1 + 2 = 7 · 9 + 2 = 65
b. 7n + 2 · 7n−1 + · · · + 2 · 72 + 2 · 7 + 2 = 7n + 2(7n−1 + · · · + 72 + 7 + 1)
= 7n + 2
( 7(n−1)+1 − 1
7 − 1
)
= 7n + 2
( 7n − 1
6
)
= 3 · 7n
3 + 7n − 1
3
= 4 · 7n − 1
3
14
c. The APR is the percentage increase in the account after one year. Because one year
is four quarters, we need to calculate S4 − S0
S0
. Now, by a similar computation as above,
S4 = (1.01)4 S0, and so
APR = S4 − S0
S0
∼= (1.01)4 S0 − S0
S0
= (1.01)4 − 1 ∼= 4.06%.
27. a. a1 = 3, a2 = 4a1 + 2 = 4 · 3 + 2 = 14, and a3 = 4a2 + 2 = 4 · 14 + 2 = 58
b. a6 = 4a5 + 2 = 4(44 · 3 + 43 · 2 + 42 · 2 + 4 · 2 + 2) + 2
= 4 · 44 · 3 + 4 · 43 · 2 + 4 · 42 · 2 + 4 · 2 + 4 · 2 + 2
= 45 · 3 + 44 · 2 + 43 · 2 + 42 · 2 + 4 · 2 + 2
c. Guess: an = 4n−1 · 3 + 4n−2 · 2 + 4n−3 · 2 + · · · + 42 · 2 + 4 · 2 + 2
= 4n−1 · 3 + 2 (4n−2 + 4n−3 + · · · + 42 + 4 + 1)
= 4n−1 · 3 + 2
( 4(n−2)+1 − 1
4 − 1
)
= 4n−1 · 3 + 2
( 4n−1 − 1
3
)
= 3 · 4n−1 + 2
3 · 4n−1 − 2
3
= 9
3 · 4n−1 + 2
3 · 4n−1 − 2
3 = 11
3 · 4n−1 − 2
3
28. a. c0 = 1, and so c1 = 7c0 + 2 = 7 · 1 + 2 = 9 and c2 = 7c1 + 2 = 7 · 9 + 2 = 65
b. 7n + 2 · 7n−1 + · · · + 2 · 72 + 2 · 7 + 2 = 7n + 2(7n−1 + · · · + 72 + 7 + 1)
= 7n + 2
( 7(n−1)+1 − 1
7 − 1
)
= 7n + 2
( 7n − 1
6
)
= 3 · 7n
3 + 7n − 1
3
= 4 · 7n − 1
3
14
Loading page 29...
c. c0 = 1
c1 = 7c0 + 2 = 7 · 1 + 2 = 7 + 2
c2 = 7c1 + 2 = 7(7 + 2) + 2 = 72 + 7 · 2 + 2
c3 = 7c2 + 2 = 7(72 + 7 · 2 + 2) + 2 = 73 + 72 · 2 + 7 · 2 + 2
c4 = 7c3 + 2 = 7(73 + 72 · 2 + 7 · 2 + 2) + 2 = 74 + 73 · 2 + 72 · 2 + 7 · 2 + 2
.
.
.
Guess: cn = 7n + 7n−1 · 2 + 7n−2 · 2 + · · · + 72 · 2 + 7 · 2 + 2
= 4 · 7n − 1
3 by part (b).
29.
b0 = 1
b1 = 2b0 + 3 = 2 · 1 + 3 = 2 + 3
b2 = 2b1 + 3 = 2 · (2 + 3) + 3 = 22 + 2 · 3 + 3
b3 = 2b2 + 3 = 2 · (22 + 2 · 3 + 3) + 3 = 23 + 22 · 3 + 2 · 3 + 3
b4 = 2b3 + 3 = 2 · (23 + 22 · 3 + 2 · 3 + 3) + 3 = 24 + 23 · 3 + 22 · 3 + 2 · 3 + 3
.
.
.
Guess:
bn = 2n + 2n−1 · 3 + · · · + 22 · 3 + 2 · 3 + 3 = 2n + 3(2n−1 + · · · + 22 + 2 + 1)
= 2n + 3
( 2n−1
2−1
)
= 2n + 3 · 2n − 3 = 4 · 2n − 3 = 2n+2 − 3.
30. Proof (by mathematical induction): : Let a0, a1, a2, . . . . be a sequence that satisfies the
recurrence relation ak = 4ak−1 + 1 for all k ≥ 1, with initial condition a0 = 2, and let the
property P (n) be the equation
an = 7 · 4n − 1
3 . ← P (n)
Show that P(0) is true: P (0) is the equation
a0 = 7 · 40 − 1
3 .
The right-hand side of P (0) is 7 · 40 − 1
3 = 7 − 1
3 = 2. This equals a0, which is the left-hand
side of P (0). So P (0) is true.
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
ak = 7 · 4k − 1
3 . ← P (k)
inductive hypothesis
We must show that
ak+1 = 7 · 4k+1 − 1
3 . ← P (k + 1)
15
c1 = 7c0 + 2 = 7 · 1 + 2 = 7 + 2
c2 = 7c1 + 2 = 7(7 + 2) + 2 = 72 + 7 · 2 + 2
c3 = 7c2 + 2 = 7(72 + 7 · 2 + 2) + 2 = 73 + 72 · 2 + 7 · 2 + 2
c4 = 7c3 + 2 = 7(73 + 72 · 2 + 7 · 2 + 2) + 2 = 74 + 73 · 2 + 72 · 2 + 7 · 2 + 2
.
.
.
Guess: cn = 7n + 7n−1 · 2 + 7n−2 · 2 + · · · + 72 · 2 + 7 · 2 + 2
= 4 · 7n − 1
3 by part (b).
29.
b0 = 1
b1 = 2b0 + 3 = 2 · 1 + 3 = 2 + 3
b2 = 2b1 + 3 = 2 · (2 + 3) + 3 = 22 + 2 · 3 + 3
b3 = 2b2 + 3 = 2 · (22 + 2 · 3 + 3) + 3 = 23 + 22 · 3 + 2 · 3 + 3
b4 = 2b3 + 3 = 2 · (23 + 22 · 3 + 2 · 3 + 3) + 3 = 24 + 23 · 3 + 22 · 3 + 2 · 3 + 3
.
.
.
Guess:
bn = 2n + 2n−1 · 3 + · · · + 22 · 3 + 2 · 3 + 3 = 2n + 3(2n−1 + · · · + 22 + 2 + 1)
= 2n + 3
( 2n−1
2−1
)
= 2n + 3 · 2n − 3 = 4 · 2n − 3 = 2n+2 − 3.
30. Proof (by mathematical induction): : Let a0, a1, a2, . . . . be a sequence that satisfies the
recurrence relation ak = 4ak−1 + 1 for all k ≥ 1, with initial condition a0 = 2, and let the
property P (n) be the equation
an = 7 · 4n − 1
3 . ← P (n)
Show that P(0) is true: P (0) is the equation
a0 = 7 · 40 − 1
3 .
The right-hand side of P (0) is 7 · 40 − 1
3 = 7 − 1
3 = 2. This equals a0, which is the left-hand
side of P (0). So P (0) is true.
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
ak = 7 · 4k − 1
3 . ← P (k)
inductive hypothesis
We must show that
ak+1 = 7 · 4k+1 − 1
3 . ← P (k + 1)
15
Loading page 30...
29 more pages available. Scroll down to load them.
Preview Mode
Sign in to access the full document!
100%
Study Now!
XY-Copilot AI
Unlimited Access
Secure Payment
Instant Access
24/7 Support
AI Assistant
Document Details
Subject
Mathematics