Skip to content
Exam Guides

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.

Preview 30 of 97 pages

See the first 30 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Discrete Mathematics with Applications, 5 th 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.

  2. Page 2
  3. Page 3
    Read page 3 as text

    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 = x 2 − 4 x + 4 − 7 = x 2 − 4 x − 3 , whereas F ( x ) = ( x + 1)( x − 3) = x 2 − 2 x − 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

  4. Page 4
    Read page 4 as text

    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

  5. Page 5
    Read page 5 as text

    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

  6. Page 6
    Read page 6 as text

    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. 110101 2 = 1 · 2 5 + 1 · 2 4 + 1 · 2 2 + 1 · 2 0 = 32 + 16 + 4 + 1 = 53 10 22. 75 10 = 64 + 8 + 2 + 1 = 1 · 2 6 + 0 · 2 5 + 0 · 2 4 + 1 · 2 3 + 0 · 2 2 + 1 · 2 1 + 1 · 2 0 = 1001011 2 . 23. The following circuit corresponds to the given Boolean expression: P AND OR Q NOT NOT AND R 5

  7. Page 7
    Read page 7 as text

    24. One circuit (among many) having the given input/output table is the following: S P R NOT AND OR AND Q NOT 25. 10111 2 + 1011 2 100010 2 26. 100110 2 = 1 · 2 5 + 0 · 2 4 + 0 · 2 3 + 1 · 2 2 + 1 · 2 1 + 0 · 2 0 = 32 + 4 + 2 = 38 10 27. 49 10 = (32 + 16 + 1) 10 = 00110001 2 −→ 11001110 −→ 11001111. So the two’s complement is 11001111. Check: 2 8 − 49 = 256 − 49 = 207 and 11001111 2 = 1 · 2 7 + 1 · 2 6 + 0 · 2 5 + 0 · 2 4 + 1 · 2 3 + 1 · 2 2 + 1 · 2 1 + 1 · 2 0 = 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 , n 2 is odd. b. ∀ integer n , if n is odd then n 2 is odd. c. ∃ an odd integer n such that n 2 is not odd. Or: ∃ an integer n such that n is odd and n 2 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

  8. Page 8
    Read page 8 as text

    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 a 2 divides b 2 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 = 2 k + 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 = 2 m + 1 . 7

  9. Page 9
    Read page 9 as text

    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 2 m + n is odd and m and n are not both odd. In other words, ∃ integers m and n such that 2 m + 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 2 m + 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 6 m 2 + 34 n − 18, the result will always be an even integer. To see this, observe that 6 m 2 + 34 n − 18 = 2( m 2 + 17 n − 9) . Since products, sums, and differences of integers are integers, m 2 + 17 n − 9 is an integer. Thus 6 m 2 + 34 n − 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 2 r 5 s 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 2 r 5 s = 2 · a b 5 · c d = 2 ad 5 bc . Now both 2 ad and 5 bc are integers because they are products of integers, and 5 bc ̸ = 0 by the zero product property. Hence 2 r 5 s is a ratio of integers with a nonzero denominator, and so 2 r 5 s is a rational number by definition of rational [as was to be shown] . 8

  10. Page 10
    Read page 10 as text

    14. Proof : Suppose a , b , and c are any integers such that a | b and a | c . [We must show that a | (5 b + 3 c ) .] By definition of divisibility, b = ar and c = as for some integers r and s . Then 5 b + 3 c = 5( ar ) + 3( as ) by substitution = a (5 r + 3 s ) by the commutative and associative laws of algebra. Let t = 5 r +3 s . Then t is an integer because products and sums of integers are integers, and 5 b +3 c = at . Thus, by definition of divisibility, a | (5 b + 3 c ) [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 | (5 b + 3 c ) . 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 b 3 = ( a · k ) 3 = a 3 · k 3 by the commutative and associative laws of algebra. Observe that k 3 is an integer because it is a product of integers. Hence b 3 equals a 3 times an integer, and so by definition of divisibility, a 3 divides b 3 . 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 b 3 = ( a · k ) 3 = a 3 · k 3 by the commutative and associative laws of algebra. Let t = k 3 . Then t is an integer because it is a product of integers. Hence b 3 = a 3 · t, where t is an integer, and so by definition of divisibility, a 3 divides b 3 . 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 = 2 u . Then n 2 + n + 1 = (2 u ) 2 + 2 u + 1 = 4 u 2 + 2 u + 1 = 2(2 u 2 + u ) + 1 . Now 2 u 2 + u is an integer because products and sums of integers are integers. Thus n 2 + n + 1 equals 2 times an integer plus 1, and so n 2 + 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 = 2 u + 1. Then n 2 + n + 1 = (2 u + 1) 2 + (2 u + 1) + 1 = 4 u 2 + 4 u + 1 + 2 u + 1 + 1 = 4 u 2 + 6 u + 2 + 1 = 2(2 u 2 + u + 1) + 1 . Now 2 u 2 + u + 1 is an integer because products and sums of integers are integers. Thus n 2 + n + 1 equals 2 times an integer plus 1, and so n 2 + n + 1 is odd by definition of odd. Conclusion: In both possible cases n 2 + 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 = 2 a . The next consecutive integer after n is n + 1, and so n + ( n + 1) = 2 a + (2 a + 1) = 4 a + 1 = 2(2 a ) + 1 . Now 2 a 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

  11. Page 11
    Read page 11 as text

    Case 2 (n is odd): By definition of odd, there is an integer a such that n = 2 a + 1. Then n + ( n + 1) = (2 a + 1) + [(2 a + 1) + 1] = 4 a + 2 + 1 = 2(2 a + 1) + 1 . Now 2 a + 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 4 n + 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 2 v . Now both u and 2 v are integers because products of integers are integers, and 2 v ̸ = 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 < 2 r , 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 + 2 s is rational. [We must show that this supposition leads logically to a contradiction.] By definition of rational, r = a b and r + 2 s = c d for some integers a , b , c , and d with b ̸ = 0 and d ̸ = 0 . Then, by substitution, a b + 2 s = c d . Solve this equation for s to obtain s = 1 2 ( c d − a b ) = 1 2 ( bc bd − ad bd ) = bc − ad 2 bd . But both bc − ad and 2 bd are integers because products and differences of integers are integers, and 2 bd ̸ = 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

  12. Page 12
    Read page 12 as text

    21. Solution 1: a. Proof (by contradiction): Suppose not. That is, suppose there is an integer n such that n 3 is even and n is odd. [We must show that this supposition leads logically to a contradiction.] By definition of odd, n = 2 a + 1 for some integer a . Thus, by substitution and algebra, n 3 = (2 a + 1) 3 = (2 a + 1) 2 (2 a + 1) = (4 a 2 + 4 a + 1)(2 a + 1) = 8 a 3 + 12 a 2 + 6 a + 1 = 2(4 a 3 + 6 a 2 + 3 a ) + 1 . Let t = 4 a 3 + 6 a 2 + 3 a . Then n 3 = 2 t + 1, and t is an integer because it is a sum of products of integers. It follows that n 3 is odd by definition of odd, which contradicts the supposition that n 3 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: n 3 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 n 3 is odd.] By definition of odd, n = 2 a + 1 for some integer a . Thus n 3 = (2 a +1) 3 = (2 a +1) 2 (2 a +1) = (4 a 2 +4 a +1)(2 a +1) = 8 a 3 +12 a 2 +6 a +1 = 2(4 a 3 +6 a 2 +3 a )+1 . Let t = 4 a 3 + 6 a 2 + 3 a . Then n 3 = 2 t + 1, and t is an integer because it is a sum of products of integers. It follows that n 3 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 n 3 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 r 3 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, r 3 = ( a b ) 3 = a 3 b 3 . Now both a 3 and b 3 are integers because products of integers are integers, and b 3 ̸ = 0 by the zero product property. Thus r 3 is a ratio of integers with a nonzero denominator, and so r 3 is rational by definition of rational. This contradicts the supposition that r 3 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: r 3 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 r 3 is rational.] 11

  13. Page 13
    Read page 13 as text

    By definition of rational, there exist integers a and b with b ̸ = 0 such that r = a b . By substitution, r 3 = ( a b ) 3 = a 3 b 3 . Now both a 3 and b 3 are integers because products of integers are integers, and b 3 ̸ = 0 by the zero product property. Thus r 3 is a ratio of integers with a nonzero denominator, and so r 3 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 r 3 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 n 3 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 = 2 a . Thus, by substitution and algebra, n 3 = (2 a ) 3 = 8 a 3 = 2(4 a 3 ) . Let t = 4 a 3 . Then n 3 = 2 t , and t is an integer because it is a product of integers. It follows that n 3 is even by definition of even, which contradicts the supposition that n 3 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: n 3 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 n 3 is even.] By definition of even, there is an integer a such that n = 2 a . Thus, by substitution and algebra, n 3 = (2 a ) 3 = 8 a 3 = 2(4 a 3 ) . Let t = 4 a 3 . Then n 3 = 2 t , and t is an integer because it is a product of integers. It follows that n 3 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 n 3 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 r 2 = ( √ 2) 2 = 2 is rational. 25. (i). rational (ii). a and b are integers and b ̸ = 0 (iii). a − 7 b (iv). a − 7 b 4 b (v). both a − 7 b and 4 b 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

  14. Page 14
    Read page 14 as text

    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 4 b + 3 b √ 2 = a, so if we subtract 4 b from both sides we have 3 b √ 2 = a − 4 b. Dividing both sides by 3 b gives √ 2 = a − 4 b 3 b . But then √ 2 would be a rational number because both a − 4 b and 3 b 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

  15. Page 15
    Read page 15 as text

    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

  16. Page 16
    Read page 16 as text

    Discrete Mathematics with Applications, 5 th Edition by Susanna S. Epp Answers for Test Bank Questions: Chapters 5-8 Please use caution when using these answers. Small differences in wording, notation, or choice of examples or counterexamples may be acceptable. Chapter 5 1. 3 ∑ k =0 1 2 k = 1 2 0 + 1 2 1 + 1 2 2 + 1 2 3 (= 1 + 1 2 + 1 4 + 1 8 = 15 8 ) 2. 4 ∑ k =1 k 2 = 1 2 + 2 2 + 3 2 + 4 2 (= 1 + 4 + 9 + 16 = 30) 3. 1 3 − 2 3 + 3 3 − 4 3 + 5 3 = 5 ∑ k =1 ( − 1) k − 1 k 2 (This is just one of a number of correct answers to this question.) 4. 1 − 1 2 + 1 3 − 1 4 + 1 5 − 1 6 = 5 ∑ i =1 ( − 1) i +1 1 i (This is just one of a number of correct answers to this question.) 5. When k = 1, j = 1 + 1 = 2. When k = n , j = n + 1. Since j = k + 1, then k = j − 1. So k 2 n = ( j − 1) 2 n . Therefore, n ∑ k =1 k 2 n = n +1 ∑ j =2 ( j − 1) 2 n . 6. When k = 0, i = 0 + 1 = 1. When k = n , i = n + 1. Since i = k + 1, then k = i − 1. So k 2 k + n = ( i − 1) 2 i − 1 + n . Therefore, n ∑ k =0 k 2 k + n = n +1 ∑ i =1 ( i − 1) 2 i − 1 + n . 7. 2 2 2 2 2 2 2 0 1 3 6 12 25 51 103 remainder = r [6] = 1 remainder = r [5] = 1 remainder = r [4] = 0 remainder = r [3] = 0 remainder = r [2] = 1 remainder = r [1] = 1 remainder = r [0] = 1 Hence 103 10 = 1100111 2 .

  17. Page 17
    Read page 17 as text

    8. 2 + 2 2 + 2 3 + · · · + 2 m = 2(1 + 2 + 2 2 + · · · + 2 m − 1 ) = 2 ( 2 ( m − 1)+1 − 1 2 − 1 ) = 2(2 m − 1) . Alternative answer: 2 + 2 2 + 2 3 + · · · + 2 m = (1 + 2 + 2 2 + · · · + 2 m ) − 1 = ( 2 m +1 − 1 2 − 1 ) − 1 = 2 m +1 − 1 − 1 = 2 m +1 − 2 [= 2(2 m − 1)] 9. a. P (3) : 3 ∑ i =3 i = (3 − 2)(3 + 3) 2 P (3) is true because the left-hand side equals 3 ∑ i =3 i = 3 and the right-hand side equals (3 − 2)(3 + 3) 2 = 1 · 6 2 = 3 also. b. (i) P ( k ): 3 + 4 + 5 + · · · + k = ( k − 2)( k + 3) 2 ; (ii) P ( k + 1): 3 + 4 + 5 + · · · + ( k + 1) = (( k + 1) − 2)(( k + 1) + 3) 2 Or, equivalently, P ( k + 1) is 3 + 4 + 5 + · · · + ( k + 1) = ( k − 1)( k + 4) 2 c. Proof that for all integers k ≥ 3, if P ( k ) is true then P ( k + 1) is true : Let k be any integer that is greater than or equal to 3, and suppose that 3 + 4 + 5 + · · · + k = ( k − 2)( k + 3) 2 ← P ( k ) inductive hypothesis We must show that 3 + 4 + 5 + · · · + ( k + 1) = (( k + 1) − 2)(( k + 1) + 3) 2 , or, equivalently, 3 + 4 + 5 + · · · + ( k + 1) = ( k − 1)( k + 4) 2 . ← P ( k + 1) Now the left-hand side of P ( k + 1) is 3 + 4 + 5 + · · · + ( k + 1) = 3 + 4 + 5 + · · · + k + ( k + 1) by making the next-to-last term explicit = ( k − 2)( k + 3) 2 + ( k + 1) by inductive hypothesis = ( k − 2)( k + 3) 2 + 2( k + 1) 2 by creating a common denominator = k 2 + k − 6 2 + 2 k + 2 2 by multiplying out = k 2 + k − 6 + 2 k + 2 2 by adding the fractions = k 2 + 3 k − 4 2 by combining like terms. And the right-hand side of P ( k + 1) is 2

  18. Page 18
    Read page 18 as text

    ( k − 1)( k + 4) 2 = k 2 + 4 k − k − 4 2 = k 2 + 3 k − 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)(3 2 + 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)(3 2 + 2 · 3 + 3) 3 = 1 · (9 + 6 + 3) 3 = 1 · 18 3 = 6 also. b. P ( k ): 2 · 3 + 3 · 4 + · · · + ( k − 1) · k = ( k − 2)( k 2 + 2 k + 3) 3 ; P ( k + 1): 2 · 3 + 3 · 4 + · · · + (( k + 1) − 1) · ( k + 1) = (( k + 1) − 2)(( k + 1) 2 + 2( k + 1) + 3) 3 Or, equivalently, P ( k + 1) is 2 · 3 + 3 · 4 + · · · + k ( k + 1) = ( k − 1)( k 2 + 2 k + 1 + 2 k + 2 + 3) 3 = ( k − 1)( k 2 + 4 k + 6) 3 c. Proof that for all integers k ≥ 3, if P ( k ) is true then P ( k + 1) is true : Let k be any integer that is greater than or equal to 3, and suppose that 2 · 3 + 3 · 4 + · · · + ( k − 1) · k = ( k − 2)( k 2 + 2 k + 3) 3 . ← P ( k ) inductive hypothesis We must show that 2 · 3 + 3 · 4 + · · · + k ( k + 1) = ( k − 1)( k 2 + 4 k + 6) 3 . ← P ( k + 1) Now the left-hand side of P ( k + 1) is 2 · 3 + 3 · 4 + · · · + k ( k + 1) = 2 · 3 + 3 · 4 + · · · + ( k − 1) k + k ( k + 1) by making the next-to-last term explicit = ( k − 2)( k 2 + 2 k + 3) 3 + k ( k + 1) by inductive hypothesis = k 3 + 2 k 2 + 3 k − 2 k 2 − 4 k − 6 3 + 3 k ( k + 1) 3 by creating a common denominator and multiplying out = k 3 − k − 6 3 + 3 k 2 + 3 k 3 by multiplying out and combining like terms = k 3 + 3 k 2 + 2 k − 6 3 by adding the fractions and combining like terms. And the right-hand side of P ( k + 1) is ( k − 1)( k 2 + 4 k + 6) 3 = k 3 + 4 k 2 + 6 k − k 2 − 4 k − 6 3 = k 3 + 3 k 2 + 2 k − 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 + 3 2 + · · · + 3 n = 3 n +1 − 1 2 . ← P ( n ) 3

  19. Page 19
    Read page 19 as text

    (Recall that by definition 1 + 3 + 3 2 + · · · + 3 n = n ∑ i =0 3 i . ) (a) P (0): 0 ∑ i =0 3 i = 3 0+1 − 1 2 P (0) is true because the left-hand side equals 0 ∑ i =0 3 i = 3 0 = 1, and the right-hand side equals 3 0+1 − 1 2 = 3 − 1 2 = 1 also. (b) P ( k ): 1 + 3 + 3 2 + · · · + 3 k = 3 k +1 − 1 2 P ( k + 1): 1 + 3 + 3 2 + · · · + 3 k +1 = 3 ( k +1)+1 − 1 2 , Or, equivalently, P ( k + 1) is 1 + 3 + 3 2 + · · · + 3 k +1 = 3 k +2 − 1 2 . (c) Proof that for all integers k ≥ 0, if P ( k ) is true then P ( k + 1) is true : Let k be any integer that is greater than or equal to 0, and suppose that 1 + 3 + 3 2 + · · · + 3 k = 3 k +1 − 1 2 . ← P ( k ) inductive hypothesis We must show that 1 + 3 + 3 2 + · · · + 3 k +1 = 3 k +2 − 1 2 . ← P ( k + 1) Now the left-hand side of P ( k + 1) is 1 + 3 + 3 2 + · · · + 3 k +1 = 1 + 3 + 3 2 + · · · + 3 k + 3 k +1 by making the next-to-last term explicit = 3 k +1 − 1 2 + 3 k +1 by inductive hypothesis = 3 k +1 − 1 2 + 2 · 3 k +1 2 by creating a common denominator = 3 · 3 k +1 − 1 2 by adding the fractions and combining like terms = 3 k +2 − 1 2 by a law of exponents, which equals the right-hand side of P ( k + 1). Thus the left-hand and right-hand sides of P ( k + 1) are equal [as was to be shown] . 12. Proof (by mathematical induction): Let the property P ( n ) be the equation 4 + 8 + 12 + · · · + 4 n = 2 n 2 + 2 n. ← P ( n ) Note that 4 + 8 + 12 + · · · + 4 n = n ∑ i =1 4 i. 4

  20. Page 20
    Read page 20 as text

    Show that P (1) is true : P (1) is true because the left-hand side is 1 ∑ i =1 4 i = 4 · 1 = 4 and the right-hand side is 2 · 1 2 + 2 · 1 = 4 also. Show that for all integers k ≥ 1 , if P ( k ) is true then P ( k + 1) is true : Let k be any integer with k ≥ 1, and suppose that 4 + 8 + 12 + · · · + 4 k = 2 k 2 + 2 k. ← 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 + · · · + 4 k + 4( k + 1) by making the next-to-last term explicit = (2 k 2 + 2 k ) + 4( k + 1) by inductive hypothesis = 2 k 2 + 6 k + 4 by multiplying out and combining like terms. And the right-hand side of P ( k + 1) is 2( k + 1) 2 + 2( k + 1) = 2( k 2 + 2 k + 1) + 2 k + 2 = 2 k 2 + 4 k + 2 + 2 k + 2 = 2 k 2 + 6 k + 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

  21. Page 21
    Read page 21 as text

    3 + 4 + 5 + · · · + ( k + 1) = 3 + 4 + 5 + · · · + k + ( k + 1) by making the next-to-last term explicit = ( k − 2)( k + 3) 2 + ( k + 1) by inductive hypothesis = ( k − 2)( k + 3) 2 + 2 · ( k + 1) 2 by creating a common denominator = k 2 + k − 6 2 + 2 k + 2 2 by multiplying out = k 2 + 3 k − 4 2 by adding fractions and combining like terms. And the right-hand side of P ( k + 1) is [( k + 1) − 2][( k + 1) + 3] 2 = ( k − 1)( k + 4) 2 = k 2 + 3 k − 4 2 . Thus the left-hand and right-hand sides of P ( k + 1) are equal [as was to be shown] . 14. Proof (by mathematical induction): Let the property P ( n ) be the equation 2 · 3 + 3 · 4 + · · · + ( n − 1) · n = ( n − 2)( n 2 + 2 n + 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)(3 2 + 2 · 3 + 3) 3 = 1 · (9 + 6 + 3) 3 = 6 also. Show that for all integers k ≥ 3 , if P ( k ) is true then P ( k + 1) is true : Let k be any integer with k ≥ 1, and suppose that 2 · 3+3 · 4+ · · · +( k − 1) · k = ( k − 2)( k 2 + 2 k + 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

  22. Page 22
    Read page 22 as text

    Now the left-hand side of P ( k + 1) is 2 · 3 + 3 · 4 + · · · + (( k + 1) − 1) · ( k + 1) = 2 · 3 + 3 · 4 + · · · + ( k − 1) · k + k · ( k + 1) by simplifying the last term and making the next-to-last term explicit = ( k − 2)( k 2 + 2 k + 3) 3 + k · ( k + 1) by inductive hypothesis = k 3 + 2 k 2 + 3 k − 2 k 2 − 4 k − 6 3 + k 2 + k by combining like terms = k 3 − k − 6 3 + 3 · ( k 2 + k ) 3 by creating a common denominator = k 3 − k − 6 3 + 3 k 2 + 3 k 3 by multiplying out = k 3 + 3 k 2 + 2 k − 6 3 by adding fractions and combining like terms. And the right-hand side of P ( k + 1) is (( k + 1) − 2)(( k + 1) 2 + 2( k + 1) + 3) 3 = ( k − 1)( k 2 + 2 k + 1 + 2 k + 2 + 3) 3 = ( k − 1)( k 2 + 4 k + 6) 3 = ( k − 1)( k 2 + 4 k + 6) 3 = k 3 + 4 k 2 + 6 k − k 2 − 4 k − 6 3 = k 3 + 3 k 2 + 2 k − 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 + 3 2 + · · · + 3 n = 3 n +1 − 1 2 . . ← P ( n ) Note that 1 + 3 + 3 2 + · · · + 3 n = n ∑ i =0 3 i . Show that P (0) is true : P (0) is true because the left-hand side is 0 ∑ i =0 3 i = 3 0 = 1 , and the right-hand side is 3 0+1 − 1 2 = 3 − 1 2 = 1 also. Show that for all integers k ≥ 0 , if P ( k ) is true then P ( k + 1) is true : Let k be any integer with k ≥ 0, and suppose that 1 + 3 + 3 2 + · · · + 3 k = 3 k +1 − 1 2 . ← P ( k ) inductive hypothesis We must show that 1 + 3 + 3 2 + · · · + 3 k +1 = 3 ( k +1)+1 − 1 2 . Or, equivalently, that 1 + 3 + 3 2 + · · · + 3 k +1 = 3 k +2 − 1 2 ← P ( k + 1) . 7

  23. Page 23
    Read page 23 as text

    (a) Now the left-hand side of P ( k + 1) is 1 + 3 + 3 2 + · · · + 3 k +1 = 1 + 3 + 3 2 + · · · + 3 k + 3 k +1 by making the next-to-last term explicit = 3 k +1 − 1 2 + 3 k +1 by inductive hypothesis = 3 k +1 − 1 2 + 2 · 3 k +1 2 by creating a common denominator = 3 · 3 k +1 − 1 2 by adding the fractions and combining like terms = 3 k +2 − 1 2 by a law of exponents, which equals the right-hand side of P ( k + 1). Thus the left-hand and right-hand sides of P ( k + 1) are equal [as was to be shown] . 16. Proof (by mathematical induction): Let the property P ( n ) be the sentence 8 n − 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 8 0 − 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 8 k − 1 is divisible by 7. ← P ( k ) inductive hypothesis We must show that 8 k +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 8 k − 1 = 7 r. Then 8 k +1 − 1 = 8 · 8 k − 1 = (7 + 1)8 k − 1 = 7 · 8 k + (8 k − 1) by algebra = 7 · 8 k + 7 r by inductive hypothesis = 7(8 k + r ) by algebra. Now 8 k + r is an integer because products and sums of integers are integers.Thus, by definition of divisibility, 8 k +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 + 4 n < 2 n . ← P ( n ) We will prove that P ( n ) is true for all integers n ≥ 5 . 8

  24. Page 24
    Read page 24 as text

    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 2 5 = 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 + 4 k < 2 k . ← P ( k ) inductive hypothesis We must show that 1 + 4( k + 1) < 2 k +1 . ← P ( k + 1) By algebra and the inductive hypothesis we have that 1 + 4( k + 1) = 1 + 4 k + 4 < 2 k + 4 . So 1 + 4( k + 1) < 2 k + 4 . (*) Now, since k ≥ 5 , 4 < 2 k = 2 k (2 − 1) = 2 k +1 − 2 k , and thus, 2 k + 4 < 2 k +1 . (**) Using the transitive property of order to combine inequalities (*) and (**) gives that 1 + 4( k + 1) < 2 k +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 2 k + 4 < 2 k +1 . Now 2 k + 4 < 2 k +1 ⇔ 4 < 2 k +1 − 2 k = 2 · 2 k − 2 k = 2 k (2 − 1) = 2 k . But when k ≥ 5 , 4 < 2 k , so the desired inequality is true.] 18. Proof (by mathematical induction): Let the property P ( n ) be the sentence If a 1 , a 2 , . . . , a n and b 1 , b 2 , . . . , b n are any real numbers, then ∑ n k =1 (2 a k − 3 b k ) = 2 ∑ n k =1 a k − 3 ∑ n k =1 b k . . ← P ( n ) Show that P (1) is true : Let a 1 and b 1 be any real numbers. By the recursive definition of summation, 1 ∑ k =1 (2 a k − 3 b k ) = 2 a 1 − 3 b 1 , 2 1 ∑ k =1 a k = 2 a 1 , 3 1 ∑ k =1 b k = 3 b 1 , and so 1 ∑ k =1 (2 a k − 3 b k ) = 2 1 ∑ k =1 a k − 3 1 ∑ k =1 b k . 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 a 1 , a 2 , . . . , a m and b 1 , b 2 , . . . , b m are any real numbers, then ∑ m k =1 (2 a k − 3 b k ) = 2 ∑ m k =1 a k − 3 ∑ m k =1 b k . ← P ( m ) inductive hypothesis 9

  25. Page 25
    Read page 25 as text

    We must show that If a 1 , a 2 , . . . , a m +1 and b 1 , b 2 , . . . , b m +1 are any real numbers, then ∑ m +1 k =1 (2 a k − 3 b k ) = 2 ∑ m +1 k =1 a k − 3 ∑ m +1 k =1 b k . . ← P ( m + 1) So suppose a 1 , a 2 , . . . , a m +1 and b 1 , b 2 , . . . , b m +1 are any real numbers. Then ∑ m +1 k =1 (2 a k − 3 b k ) = ∑ m k =1 (2 a k − 3 b k ) + (2 a m +1 − 3 b m +1 ) by the recursive definition of summation = (2 ∑ m k =1 a k − 3 ∑ m k =1 b k ) + (2 a m +1 − 3 b m +1 ) by substitution from the inductive hypothesis = (2 ∑ m k =1 a k + 2 a m +1 ) − (3 ∑ m k =1 b k + 3 b m +1 ) by the associative and commutative laws of algebra = 2 ∑ m +1 k =1 a k − 3 ∑ m +1 k =1 b k 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 a 0 , a 1 , a 2 , . . . is defined recursively as follows: a 0 = 2 , a 1 = 9 a k = 5 a k − 1 − 6 a k − 2 for all integers k ≥ 2 . Let the property P ( n ) be the equation a n = 5 · 3 n − 3 · 2 n . ← 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 a 0 , a 1 , a 2 , . . . , we have that a 0 = 2 and a 1 = 9 . Since 5 · 3 0 − 3 · 2 0 = 5 − 3 = 2 and 5 · 3 1 − 3 · 2 1 = 15 − 6 = 9 , P (0) and P (1) are both true. 10

  26. Page 26
    Read page 26 as text

    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 a i = 5 · 3 i − 3 · 2 i for all integers i with 0 ≤ i ≤ k. ← inductive hypothesis We must show that a k +1 = 5 · 3 k +1 − 3 · 2 k +1 . But a k +1 = 5 a k − 6 a k − 1 by definition of a 0 , a 1 , a 2 , . . . = 5(5 · 3 k − 3 · 2 k ) − 6(5 · 3 k − 1 − 3 · 2 k − 1 ) by inductive hypothesis = 5(5 · 3 · 3 k − 1 − 3 · 2 · 2 k − 1 ) − 6(5 · 3 k − 1 − 3 · 2 k − 1 ) because 3 k = 3 · 3 k − 1 and 2 k = 2 · 2 k − 1 = (75 · 3 k − 1 − 30 · 2 k − 1 ) − (30 · 3 k − 1 − 18 · 2 k − 1 ) = (75 − 30) · 3 k − 1 − (30 − 18) · 2 k − 1 = 45 · 3 k − 1 + 12 · 2 k − 1 = 5 · 3 2 · 3 k − 1 + 3 · 2 2 · 2 k − 1 = 5 · 3 k +1 + 3 · 2 k +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 s 1 , s 2 , s 3 , ... is defined recursively as fol- lows: s k = 5 s k − 1 + ( s k − 2 ) 2 for all integers k ≥ 3 s 1 = 4 s 2 = 8 Let the property P ( n ) be the sentence s n 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 s 1 , s 2 , s 3 , ... , we have that s 1 = 4 and s 2 = 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 s k is divisible by 4 for all integers i with 0 ≤ i ≤ k. ← inductive hypothesis We must show that s k +1 is divisible by 4 . Now, by definition of s 1 , s 2 , s 3 , .., s k +1 = 5 s k + ( s k − 1 ) 2 . By inductive hypothesis,both s k and s k − 1 are divisible by 4. Hence, there exist integers a and b so that s k = 4 a and s k − 1 = 4 b. Then s k +1 = 5 s k + ( s k − 1 ) 2 = 5(4 a ) + (4 b ) 2 by substitution = 4(5 a ) + 4(4 b 2 ) because 3 k = 3 · 3 k − 1 and 2 k = 2 · 2 k − 1 = 4(5 a + 4 b 2 ) by algebra. 11

  27. Page 27
    Read page 27 as text

    Now 5 a + 4 b 2 is an integer because products and sums of integers are integers, and thus s k +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, i old = k + 1. So after execution of statement 1, i new = i old + 1 = ( k + 1) + 1 = k + 2 . Also before statement 2 is executed, product old = A [1] · A [2] · · · A [ k + 1] Statement 2 states that product new := product old · A [ i new ] , Since A [ i new ] = A [ k + 2] , after statement 2 is executed we have that product new = product old · 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. s 1 = 4 (two move to transfer the two disks to pole B and two more moves to transfer them to pole C ) s 2 = 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

  28. Page 28
    Read page 28 as text

    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. s k = s k − 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 ) + s k − 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 ) + s k − 1 (moves to transfer the top 2( k − 1) disks from pole A to pole C ) . So s k = 3 s k − 1 + 4 for all integers k ≥ 2 . 24. a. t 1 = 3 , t 2 = 3 + 3 + 3 = 9 b. For all integers k ≥ 2, t k = t k − 1 (moves to transfer the top 3 k − 3 disks from pole A to pole B ) +3 (moves to transfer the bottom two disks from pole A to pole C ) + t k − 1 (moves to transfer the top 3 k − 3 disks from pole B to pole C ) = 2 t k − 1 + 3. Note that transferring the stack of 3 k 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 3 t k − 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. s 0 = 1 because there is one rabbit pair at the beginning of the first month (i.e., at the end of month 0), and s 1 = 1 and s 2 = 1 because rabbits are not fertile during their first two months of life. Thereafter, s k = s k − 1 + 4 s k − 3 for all integers k ≥ 3 . The reason is that for k ≥ 3 , s k = [ 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 ] = s k − 1 + 4 s k − 3 . 26. a. When 4% interest is compounded quarterly, the interest rate per quarter is 0 . 04 4 = 0 . 01. If S k is the amount on deposit at the end of the k th quarter, then S k = S k − 1 + (0 . 01) S k − 1 = (1 + 0 . 01) S k − 1 = (1 . 01) S k − 1 for each integer k ≥ 1 . b. Because 3 years is 12 quarters, we need to compute S 12 . Now S 0 = $5000 , and so S 12 = (1 . 01) S 11 = (1 . 01) [(1 . 01) S 10 ] = (1 . 01) 2 S 10 = (1 . 01) 2 [(1 . 01) S 9 ] = (1 . 01) 3 S 9 = (1 . 01) 3 [(1 . 01) S 8 ] = (1 . 01) 4 S 8 = (1 . 01) 4 [(1 . 01) S 7 ] = (1 . 01) 5 S 7 = (1 . 01) 5 [(1 . 01) S 6 ] = (1 . 01) 6 S 6 = (1 . 01) 6 [(1 . 01) S 5 ] = (1 . 01) 7 S 5 = (1 . 01) 7 [(1 . 01) S 4 ] = (1 . 01) 8 S 4 = (1 . 01) 8 [(1 . 01) S 3 ] = (1 . 01) 9 S 3 = (1 . 01) 9 [(1 . 01) S 2 ] = (1 . 01) 10 S 2 = (1 . 01) 10 [(1 . 01) S 1 ] = (1 . 01) 11 S 1 = (1 . 01) 11 [(1 . 01) S 0 ] = (1 . 01) 12 S 0 = (1 . 01) 12 · 5000 ∼ = 5634 . 13 dollars. 13

  29. Page 29
    Read page 29 as text

    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 S 4 − S 0 S 0 . Now, by a similar computation as above, S 4 = (1 . 01) 4 S 0 , and so APR = S 4 − S 0 S 0 ∼ = (1 . 01) 4 S 0 − S 0 S 0 = (1 . 01) 4 − 1 ∼ = 4 . 06% . 27. a. a 1 = 3 , a 2 = 4 a 1 + 2 = 4 · 3 + 2 = 14 , and a 3 = 4 a 2 + 2 = 4 · 14 + 2 = 58 b. a 6 = 4 a 5 + 2 = 4(4 4 · 3 + 4 3 · 2 + 4 2 · 2 + 4 · 2 + 2) + 2 = 4 · 4 4 · 3 + 4 · 4 3 · 2 + 4 · 4 2 · 2 + 4 · 2 + 4 · 2 + 2 = 4 5 · 3 + 4 4 · 2 + 4 3 · 2 + 4 2 · 2 + 4 · 2 + 2 c. Guess: a n = 4 n − 1 · 3 + 4 n − 2 · 2 + 4 n − 3 · 2 + · · · + 4 2 · 2 + 4 · 2 + 2 = 4 n − 1 · 3 + 2 ( 4 n − 2 + 4 n − 3 + · · · + 4 2 + 4 + 1 ) = 4 n − 1 · 3 + 2 ( 4 ( n − 2)+1 − 1 4 − 1 ) = 4 n − 1 · 3 + 2 ( 4 n − 1 − 1 3 ) = 3 · 4 n − 1 + 2 3 · 4 n − 1 − 2 3 = 9 3 · 4 n − 1 + 2 3 · 4 n − 1 − 2 3 = 11 3 · 4 n − 1 − 2 3 28. a. c 0 = 1 , and so c 1 = 7 c 0 + 2 = 7 · 1 + 2 = 9 and c 2 = 7 c 1 + 2 = 7 · 9 + 2 = 65 b. 7 n + 2 · 7 n − 1 + · · · + 2 · 7 2 + 2 · 7 + 2 = 7 n + 2(7 n − 1 + · · · + 7 2 + 7 + 1) = 7 n + 2 ( 7 ( n − 1)+1 − 1 7 − 1 ) = 7 n + 2 ( 7 n − 1 6 ) = 3 · 7 n 3 + 7 n − 1 3 = 4 · 7 n − 1 3 14

  30. Page 30
    Read page 30 as text

    c. c 0 = 1 c 1 = 7 c 0 + 2 = 7 · 1 + 2 = 7 + 2 c 2 = 7 c 1 + 2 = 7(7 + 2) + 2 = 7 2 + 7 · 2 + 2 c 3 = 7 c 2 + 2 = 7(7 2 + 7 · 2 + 2) + 2 = 7 3 + 7 2 · 2 + 7 · 2 + 2 c 4 = 7 c 3 + 2 = 7(7 3 + 7 2 · 2 + 7 · 2 + 2) + 2 = 7 4 + 7 3 · 2 + 7 2 · 2 + 7 · 2 + 2 . . . Guess: c n = 7 n + 7 n − 1 · 2 + 7 n − 2 · 2 + · · · + 7 2 · 2 + 7 · 2 + 2 = 4 · 7 n − 1 3 by part (b). 29. b 0 = 1 b 1 = 2 b 0 + 3 = 2 · 1 + 3 = 2 + 3 b 2 = 2 b 1 + 3 = 2 · (2 + 3) + 3 = 2 2 + 2 · 3 + 3 b 3 = 2 b 2 + 3 = 2 · (2 2 + 2 · 3 + 3) + 3 = 2 3 + 2 2 · 3 + 2 · 3 + 3 b 4 = 2 b 3 + 3 = 2 · (2 3 + 2 2 · 3 + 2 · 3 + 3) + 3 = 2 4 + 2 3 · 3 + 2 2 · 3 + 2 · 3 + 3 . . . Guess: b n = 2 n + 2 n − 1 · 3 + · · · + 2 2 · 3 + 2 · 3 + 3 = 2 n + 3(2 n − 1 + · · · + 2 2 + 2 + 1) = 2 n + 3 ( 2 n − 1 2 − 1 ) = 2 n + 3 · 2 n − 3 = 4 · 2 n − 3 = 2 n +2 − 3 . 30. Proof (by mathematical induction): : Let a 0 , a 1 , a 2 , . . . . be a sequence that satisfies the recurrence relation a k = 4 a k − 1 + 1 for all k ≥ 1, with initial condition a 0 = 2, and let the property P ( n ) be the equation a n = 7 · 4 n − 1 3 . ← P ( n ) Show that P (0) is true : P (0) is the equation a 0 = 7 · 4 0 − 1 3 . The right-hand side of P (0) is 7 · 4 0 − 1 3 = 7 − 1 3 = 2. This equals a 0 , 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 a k = 7 · 4 k − 1 3 . ← P ( k ) inductive hypothesis We must show that a k +1 = 7 · 4 k +1 − 1 3 . ← P ( k + 1) 15

67 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.