Test Bank For Discrete Mathematics With Applications, 5th Edition

Preview (30 of 97 Pages)

100%

Purchase to unlock

Loading page image...

DiscreteMathematicswithApplications,5thEditionbySusannaS.EppAnswers for Test Bank Questions: Chapters 1-4Please use caution when using these answers. Small differences in wording, notation, or choice of examplesor counterexamples may be acceptable.Chapter 11. a. a remainder of 1 when it is divided by 4 and a remainder of 3 when it is divided by 7b. an integern;nis divided by 7 the remainder is 32. a. a positive real number; smaller thanrb. positive real numberr; there is a positive real numbersFill 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 sidesb. has three sidesc. has three sidesd. is a triangle; has three sidese.Thas three sides5. a. have additive inversesb. an additive inversec.yis an additive inverse forx6. a. less than or equal to every positive integerb. positive integerm; less than or equal to every positive integerc. less than or equal ton7. (a) The set of all integersnsuch thatnis a factor of 9.Or:The set of all elementsninZsuch thatnis a factor of 9.Or:The set of all elementsnin the set of all integers such thatnis a factor of 9.(b){1,3,9}8. (a) No(b) Yes(c) Yes(d) No9. 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; Yesb.{(3,15),(3,18),(5,15)}c. domain is{3,5,7}; co-domain is{15,16,17,18}.d. Draw an arrow diagram forR.e. No:Rfails both conditions for being a function fromAtoB. (1) Elements 5 and 7 inAare notrelated to any elements inB, and (2) there is an element inA, namely 3, that is related to two differentelements inB, namely 15 and 18.

Loading page image...

11. a. No; Yes; No; Yesb. Draw the graph ofRin the Cartesian plane.c. No:Rfails both conditions for being a function fromRtoR. (1) There are many elements inRthat are not related to any element inR. For instance, none of 0, 1/2, and−1 is related to any elementofR. (2) there are elements inRthat are related to two different elements inR. For instance 2 isrelated to both 1 and−1.12. a.G(2) =cb. Draw an arrow diagram forG.13.F̸=G.Note that for every real numberx,G(x) = (x−2)2−7 =x2−4x+ 4−7 =x2−4x−3,whereasF(x) = (x+ 1)(x−3) =x2−2x−3.Thus, for instance,F(1) = (1 + 1)(1−3) =−4whereasG(1) = (1−2)2−7 =−6.Chapter 21. e2. e3. a. The variableSis not undeclared or the data are not out of order.b. The variableSis 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> xorx≥24. The statement forms are not logically equivalent.Truth table:pq∼pp∨q∼p∧qp∨q→pp∨(∼p∧q)TTFTFTTTFFTFTTFTTTTFTFFTFFTFExplanation: The truth table shows thatp∨q→pandp∨(∼p∧q) have different truth values inrows 3 and 4, i.e, whenpis false. Thereforep∨q→pandp∨(∼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 aresubstituted in a consistent way for their statement variables the resulting statements have the sametruth value.6.Solution 1:The given statements are not logically equivalent.Letpbe “Sam bought it at CrownBooks,” andqbe “Sam didn’t pay full price.” Then the two statements have the following form:p→qandp∨ ∼q.The truth tables for these statement forms arepq∼qp→qp∨ ∼qTTFTTTFTFTFTFTFFFTTT2

Loading page image...

Rows 2 and 3 of the table show thatp→qandp∨ ∼qdo not always have the same truth values, andsop→q̸≡p∨ ∼q.Solution 2:The given statements are not logically equivalent.Letpbe “Sam bought it at CrownBooks,” andqbe “Sam paid full price.” Then the two statements have the following form:p→∼qandp∨q.The truth tables for these statement forms arepq∼qp→∼qp∨qTTFFTTFTTTFTFTTFFTTFRows 1 and 4 of the table show thatp→∼qandp∨qdo not always have the same truth values, andsop→∼q̸≡p∨q.7. The given statements are not logically equivalent. Letpbe “Sam is out of Schlitz,” andqbe “Sam isout of beer.” Then the two statements have the following form:p→qand∼q∨ ∼p.The truth tables for these statement forms arepq∼p∼qp→q∼p∨ ∼qTTFFTFTFFTFTFTTFTTFFTTTTThe table shows thatp→qand∼p∨ ∼qsometimes have opposite truth values (shown in rows 1 and2), and sop→q̸≡ ∼p∨ ∼q.8.Converse: If Jose is Jan’s cousin, then Ann is Jan’s motherInverse: 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 cousinContrapositive: 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 grandfatherContrapositive: 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 problem16 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 itsstatement 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 itsstatement variables, it is impossible for all the premises to be true at the same time that the conclusionis false.Or:For a form of argument to be valid means that no matter what statements are substituted for itsstatement variables, it is impossible for conclusion to be false if all the premises are true.3

Loading page image...

13. The given form of argument is invalid.premisesz}|{conclusionz}|{pq∼p∼qp→∼qq→∼pp∨qTTFFFFTTFFTTTTFTTFTTTFFTTTTFRow 4 of the truth table shows that it is possible for an argument of this form to have true premisesand a false conclusion.14. The given form of argument is invalid.premisesz}|{conclusionz}|{pqr∼qp∧ ∼qp∧ ∼q→rp∨qq→prTTTFFTTTTTTFFFTTTFTFTTTTTTTTFFTTFTTFFTTFFTTFTFTFFFTTFFFFTTFTFTTFFFTFTFTFRow 2 of the truth table shows that it is possible for an argument of this form to have true premisesand a false conclusion.15. Letpbe “Hugo is a physics major,”qbe “Hugo is a math major,” andrbe “Hugo needs to takecalculus.” Then the given argument has the following form:p∨q→rr∨qThereforep∨q.Truth table:premisesz}|{conclusionz}|{pqrp∨qp∨q→rr∨qp∨qTTTFTTTTTFFFTTTFTTTTTTFFTFFTFTTTTTTFTFTFTTFFTFTTFFFFFTFFRow 7 of the truth table shows that it is possible for an argument of this form to have true premisesand a false conclusion. Therefore, the given argument is invalid.16. Letpbe “12 divides 709,438,”qbe “3 divides 709,438,” andrbe “The sum of the digits of 709,438 isdivisible by 9.” Then the given argument has the following form:p→qr→q∼rTherefore∼p.4

Loading page image...

Truth table:premisesz}|{conclusionz}|{pqr∼qp∧ ∼qp→qr→q∼r∼pTTTFFTTFFTTFFFTTTFTFTTTFFFFTFFTTFTTFFTTFFTTFTFTFFFTTTTFFTTFTFFTFFFTFTTTTRow 2 of the truth table shows that it is possible for an argument of this form to have true premisesand a false conclusion. Therefore, the given argument is invalid.17. The argument has the formp→q∼qTherefore∼p,which is valid by modus tollens (and the fact that the negation of “17 is not a divisor of 54,587” is “17is a divisor of 54,587”).18. The argument has the formp→qqThereforep,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 isimpossible for a knave.Hence A is a knight, and at least one of the three is a knave.That impliesthat 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= 1b.∼(P∧Q)∧(Q∧R)21. 1101012= 1·25+ 1·24+ 1·22+ 1·20= 32 + 16 + 4 + 1 = 531022. 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:PANDORQNOTNOTANDR5

Loading page image...

24. One circuit (among many) having the given input/output table is the following:SPRNOTANDORANDQNOT25.101112+10112100010226. 1001102= 1·25+ 0·24+ 0·23+ 1·22+ 1·21+ 0·20= 32 + 4 + 2 = 381027. 4910= (32 + 16 + 1)10= 001100012−→11001110−→11001111.So the two’s complement is 11001111.Check:28−49 = 256−49 = 207 and110011112=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 31.∀valid argumentx, ifxhas true premises, thenxhas a true conclusion.2. a.∀odd integern,n2is odd.b.∀integern, ifnis odd thenn2is odd.c.∃an odd integernsuch thatn2is not odd.Or:∃an integernsuch thatnis odd andn2is not odd.3.∀rational numberr,∃integersuandvsuch thatris the ratio ofutov.Or:∀rational numberr,∃integersuandvsuch thatr=u/v.4.∀even integernthat is greater than 2,∃prime numberspandqsuch thatn=p+q.Or:∀even integern, ifn >2 then∃prime numberspandqsuch thatn=p+q.5. e6. a7. d8. g6

Loading page image...

9. a. There is an integernsuch thatnis prime andnis not odd.b.∃a real numberxsuch thatx <1 and 1x≯1.Or:∃a real numberxsuch thatx <1 and 1x≤1.c. There are integersaandbsuch thata2dividesb2andadoes not divideb.d.∃a real numberxsuch thatx(x−2)>0 andx≯2 andx≮0.Or:∃a real numberxsuch thatx(x−2)>0 and 0≤x≤2.e.∃a real numberxsuch thatx(x−2)>0 and either 0> xorx >2.Or:∃a real numberxsuch thatx(x−2)>0 and either 0xorx2.f. There are real numbersxandywithx < ysuch that for all integersn, eitherx > norn > y.Or:There are real numbersxandywithx < ysuch that for all integersn, eitherxnorny.10. a.∀real numbersx,ifx+ 1>0 then−1< x≤0.b.∀real numbersx,ifx+ 1≤0 then−1≥xorx >0.Or:∀real numbersx,ifx+ 1≯0 then−1≮xorx0.11. If a graph withnvertices is a tree, then it hasn−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 reciprocalis greater than 1” and the second statement is equivalent to “If the reciprocal of a real number isgreater 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,−12 isgreater than 1.However, the second statement is true; if the reciprocal of a real number is greaterthan 1, then the number itself is positive and is between 0 and 1, and it is impossible for one of a pairof 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 twowill 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 41.Some acceptable answers:a. An integernis odd if, and only if,n= 2k+ 1 for some integerk.b. An integernis odd if, and only if,nequals 2 times some integer plus 1.c. An integernis odd if, and only if, there exists an integermsuch thatn= 2m+ 1 .7

Loading page image...

2.Counterexample:Leta= 1,b= 2,c= 1, andd= 2. Thenab+cd= 12 + 12 = 1, whereasa+cb+d= 1 + 12 + 2 = 24 = 12.(This is one counterexample among many.)3. a.∃integersmandnsuch that 2m+nis odd andmandnare not both odd.In other words,∃integersmandnsuch that 2m+nis odd and at least one ofmandnis even.b. Statement A can be shown to be false by giving a counterexample.Counterexample:Letm= 1 andn= 2. Then 2m+n= 2·1 + 2 = 4, which is even, but it is not thecase that bothmandnare odd becausenis even.(This is one counterexample among many.)4. No matter what integers replacemandnin the expression 6m2+ 34n−18, the result will always bean even integer. To see this, observe that6m2+ 34n−18=2(m2+ 17n−9).Since products, sums, and differences of integers are integers,m2+ 17n−9 is an integer.Thus6m2+ 34n−18 can be written as 2 times an integer, and so it is an even integer.5.Counterexample:Leta=b=√2. Thenaandbare irrational, andab=√2· √2 = 2,which is rational.6.Some acceptable answers:a. A real numberris rational if, and only if,r=abfor some integersaandbwithb̸= 0.b. A real numberris rational if, and only if, there exist integersaandbsuch thatr=abandb̸= 0.c. A real numberris rational if, and only if,rcan be written as a ratio of integers with a nonzerodenominator.7. 605.83 is a rational number because 605.83 = 60583100.8. 56.745 a rational number because 56.745 = 567451000.9.Some acceptable answers:a.An integernis divisible by an integerdif, and only if,n=dkfor some integerk.b. An integernis divisible by an integerdif, and only if, there exists an integerkso thatn=dk.c. An integernis divisible by an integerdif, and only if,nis equal todtimes some integer.10. 0 is divisible by 3 because 0 = 3·0.11. 12 divides 72 because 72 = 12·6.12. Proof: Supposerands, are any[particular but arbitarily chosen]rational numbers.We must show thatr−sis rational.13. Proof: Supposerands, are any rational numbers withs̸= 0.[We must show that2r5sis a rationalnumber.]By definition of rational, there exist integersa,b,c, anddwithb̸= 0 andd̸= 0 such thatr=abands=cd .In addition, sincec=s·dand since neithersnordequals 0, thenc̸= 0 by the zero product property.Then2r5s=2·ab5·cd= 2ad5bc .Now both 2adand 5bcare integers because they are products of integers, and 5bc̸= 0 by the zeroproduct property. Hence 2r5sis a ratio of integers with a nonzero denominator, and so 2r5sis a rationalnumber by definition of rational[as was to be shown].8

Loading page image...

14. Proof : Supposea,b, andcare any integers such thata|banda|c.[We must show thata|(5b+ 3c).]By definition of divisibility,b=arandc=asfor some integersrands. Then5b+ 3c=5(ar) + 3(as)by substitution=a(5r+ 3s)by the commutative and associative laws of algebra.Lett= 5r+3s. Thentis 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 factspreviously proved in class or in the text or in the exercises.For all integersa, b,andc,ifa|banda|c,thena|(5b+ 3c).15. Proof(Version 1): Supposeaandbare integers andadividesb. By definition of divisibility,b=a·kfor some integerk.Raising both sides to the third power givesb3=(a·k)3=a3·k3by the commutative and associative laws of algebra.Observe thatk3is an integer because it is a product of integers. Henceb3equalsa3times an integer,and so by definition of divisibility,a3dividesb3.Proof(Version 2): Supposeaandbare integers andadividesb. By definition of divisibility,b=a·kfor some integerk.Raising both sides to the third power givesb3=(a·k)3=a3·k3by the commutative and associative laws of algebra.Lett=k3. Thentis an integer because it is a product of integers. Henceb3=a3·t,wheretis aninteger, and so by definition of divisibility,a3dividesb3.16. Proof: Supposenis any integer. By the parity principle, eithernis even ornis odd, so we considertwo cases.Case 1 (n is even):By definition of even, there is an integerusuch thatn= 2u. Thenn2+n+ 1 = (2u)2+ 2u+ 1 = 4u2+ 2u+ 1 = 2(2u2+u) + 1.Now 2u2+uis an integer because products and sums of integers are integers. Thusn2+n+ 1 equals2 times an integer plus 1, and son2+n+ 1 is odd by definition of odd.Case 2 (n is odd):By definition of odd, there is an integerusuch thatn= 2u+ 1. Thenn2+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. Thusn2+n+ 1equals 2 times an integer plus 1, and son2+n+ 1 is odd by definition of odd.Conclusion:In both possible casesn2+n+ 1 is odd.17. Proof: Supposenis any integer. By the parity principle, eithernis even ornis odd, so we considertwo cases.Case 1 (n is even):By definition of even, there is an integerasuch thatn= 2a.The nextconsecutive integer afternisn+ 1, and son+ (n+ 1) = 2a+ (2a+ 1) = 4a+ 1 = 2(2a) + 1.Now 2ais an integer because products of integers are integers.Thusn+ (n+ 1) equals 2 times aninteger plus 1, and son+ (n+ 1) is odd by definition of odd.9

Loading page image...

Case 2 (n is odd):By definition of odd, there is an integerasuch thatn= 2a+ 1. Thenn+ (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. Thusn+ (n+ 1) equals2 times an integer plus 1, and son+ (n+ 1) is odd by definition of odd.Conclusion:In both possible casesn+ (n+ 1) is odd.Prove the following statement:The sum of any two consecutive integers can be written in the form4n+ 1 for some integern.18. Proof: Supposexis any real number. By definition of floor,⌊x−2⌋=nif,and only if,n≤x−2< n+ 1.Adding 2 to all parts of the inequality givesn+ 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 (namelyn), and so⌊x−2⌋=⌊x⌋ −2.19. Proof (by contradiction): Suppose not. That is, suppose there is a smallest positive rational number;call itr.[We must show that this supposition leads logically to a contradiction.]By definition ofrational, there exist integersuandvwithv̸= 0 such thatr=uv .Thenr2 =uv2=u2v .Now bothuand 2vare integers because products of integers are integers, and 2v̸= 0 by the zeroproduct property. Thusr2 is a raional number.In addition, sinceris positive, 0< r.Hence, by addingrto both sides,r <2r, and dividing both sidesby 2 gives thatr2< r, sor2 is less thanr.Moreover, dividing both sides of 0< rby 2 gives that 0< r2 , sor2 is positive.In summary:r2 is a positive rational number that is less thanr, which contradicts the supposition thatris the smallest positive rational number.[Hence the supposition is false and the given statement istrue.]20. Proof (by contradiction):Suppose not. That is, suppose there are real numbersrandssuch thatrisrational andsis irrational andr+ 2sis rational.[We must show that this supposition leads logicallyto a contradiction.]By definition of rational,r=abandr+ 2s=cdfor some integersa,b,c, anddwithb̸= 0 andd̸= 0.Then, by substitution,ab+ 2s=cd .Solve this equation forsto obtains= 12(cd−ab)= 12(bcbd−adbd)=bc−ad2bd.But bothbc−adand 2bdare integers because products and differences of integers are integers, and2bd̸= 0 by the zero product property.Hencesis a ratio of integers with a nonzero denominator, and sosis rational by definition of rational.This contradicts the supposition thatxis irrational.[Hence the supposition is false and the givenstatement is true.]10

Loading page image...

21.Solution 1:a. Proof (by contradiction): Suppose not. That is, suppose there is an integernsuch thatn3is evenandnis odd.[We must show that this supposition leads logically to a contradiction.]By definition of odd,n= 2a+ 1 for some integera.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.Lett= 4a3+ 6a2+ 3a. Thenn3= 2t+ 1, andtis an integer because it is a sum of products of integers.It follows thatn3is odd by definition of odd, which contradicts the supposition thatn3is even.[Hence the supposition is false and the given statement is true.]b. Outline of proof by contraposition:Starting point:Supposenis any integer such thatnis odd. (Or:Supposenis any odd integer.)Conclusion to be shown:n3is odd.Solution 2:a. Proof (by contraposition): Supposenis any integer such thatnis odd. (Or:Supposenis any oddinteger.)[We must show thatn3is odd.]By definition of odd,n= 2a+ 1 for some integera.Thusn3= (2a+1)3= (2a+1)2(2a+1) = (4a2+4a+1)(2a+1) = 8a3+12a2+6a+1 = 2(4a3+6a2+3a)+1.Lett= 4a3+ 6a2+ 3a. Thenn3= 2t+ 1, andtis an integer because it is a sum of products of integers.It follows thatn3is 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 integernsuch thatn3is even andnis 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 numberrsuch thatr3isirrational andris rational.[We must show that this supposition leads logically to a contradiction.]By definition of rational, there exist integersaandbwithb̸= 0 such thatr=ab.By substitution,r3=(ab)3=a3b3.Now botha3andb3are integers because products of integers are integers, andb3̸= 0 by the zeroproduct property.Thusr3is a ratio of integers with a nonzero denominator, and sor3is rational by definition of rational.This contradicts the supposition thatr3is irrational.[Hence the supposition is false and the givenstatement is true.]b. Outline of proof by contraposition:Starting point:Supposeris any real number such thatris rational. (Or:Supposeris any rationalnumber.)Conclusion to be shown:r3is rational.Solution 2:a. Proof (by contraposition): Supposeris any real number such thatris rational. (Or:Supposerisany rational number.)[We must show thatr3is rational.]11

Loading page image...

By definition of rational, there exist integersaandbwithb̸= 0 such thatr=ab.By substitution,r3=(ab)3=a3b3.Now botha3andb3are integers because products of integers are integers, andb3̸= 0 by the zeroproduct property.Thusr3is a ratio of integers with a nonzero denominator, and sor3is 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 numberrsuch thatr3is irrational andris 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 integernsuch thatn3is oddandnis even.[We must show that this supposition leads logically to a contradiction.]By definition of even, there is an integerasuch thatn= 2a.Thus, by substitution and algebra,n3= (2a)3= 8a3= 2(4a3).Lett= 4a3. Thenn3= 2t, andtis an integer because it is a product of integers.It follows thatn3is even by definition of even, which contradicts the supposition thatn3is odd.[Hence the supposition is false and the given statement is true.]b. Outline of proof by contraposition:Starting point:Supposenis any integer such thatnis even. (Or:Supposenis any even integer.)Conclusion to be shown:n3is even.Solution 2:a.Proof (by contraposition): Supposenis any integer such thatnis even.(Or:Supposenis anyeven integer.)[We must show thatn3is even.]By definition of even, there is an integerasuch thatn= 2a.Thus, by substitution and algebra,n3= (2a)3= 8a3= 2(4a3).Lett= 4a3. Thenn3= 2t, andtis an integer because it is a product of integers.It follows thatn3is 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 integernsuch thatn3is odd andnis even.Conclusion to be shown:We must show that this supposition leads logically to a contradiction.24. The given statement is false.Counterexample:Letr=√2.Thenris irrational, butr2= (√2)2= 2 is rational.25. (i). rational(ii).aandbare integers andb̸= 0(iii).a−7b(iv).a−7b4b(v). botha−7band 4bare integers (since products and differences of integers are integers) and so√2would be a rational number(vi). the supposition is false and the given statement is true.12

Loading page image...

26. Proof: Suppose not. That is, suppose that 4 + 3√2 is rational. By definition of rational, 7 + 4√2 =ab,whereaandbare integers andb̸= 0.Multiplying both sides bybgives4b+ 3b√2 =a,so if we subtract 4bfrom both sides we have3b√2 =a−4b.Dividing both sides by 3bgives√2 =a−4b3b.But then√2 would be a rational number because botha−4band 3bare integers (since productsand differences of integers are integers) and so√2 would be a rational number. This contradicts ourknowledge that√2 is irrational. Hence the supposition is false and the given statement is true.27.1168⌈284So 284 = 168·1 + 116, and hence gcd(284,168) = gcd(168,116)1681161116⌈168So 168 = 116·1 + 52, and hence gcd(168,116) = gcd(116,52)11652252⌈116So 116 = 52·2 + 12, and hence gcd(116,52) = gcd(52,12)10412412⌈52So 52 = 12·4 + 4, and hence gcd(52,12) = gcd(12,4)48434⌈12So 12 = 4·3 + 0, and hence gcd(12,4) = gcd(4,0)120But gcd(4,0) = 4. So gcd(284,168) = 4.13

Loading page image...

28.110673⌈11284So 11284 = 10673·1 + 611, and hence gcd(11284,10673) = gcd(10673,611)1067361117611⌈10673So 10673 = 611·17 + 286, and hence gcd(10673,611) = gcd(611,286)103872862286⌈611So 611 = 52·2 + 12, and hence gcd(611,286) = gcd(286,39)57239739⌈286So 286 = 39·4 + 4, and hence gcd(286,39) = gcd(39,13)27313313⌈39So 39 = 13·3 + 0, and hence gcd(39,13) = gcd(13,0)390But gcd(13,0) = 13. So gcd(11284,10673) = 13.14

Loading page image...

DiscreteMathematicswithApplications,5thEditionbySusannaS.EppAnswers for Test Bank Questions: Chapters 5-8Please use caution when using these answers.Small differences in wording, notation, or choice ofexamples or counterexamples may be acceptable.Chapter 51.3∑k=012k=120+ 121+ 122+ 123(= 1 + 12 + 14 + 18 = 158 )2.4∑k=1k2= 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 thisquestion.)4. 1−12 + 13−14 + 15−16 =5∑i=1(−1)i+11i(This is just one of a number of correct answers to thisquestion.)5. Whenk= 1,j= 1 + 1 = 2. Whenk=n,j=n+ 1. Sincej=k+ 1, thenk=j−1. Sok2n= (j−1)2n.Therefore,n∑k=1k2n=n+1∑j=2(j−1)2n.6. Whenk= 0,i= 0 + 1 = 1. Whenk=n,i=n+ 1. Sincei=k+ 1, thenk=i−1. Sok2k+n=(i−1)2i−1 +n .Therefore,n∑k=0k2k+n=n+1∑i=1(i−1)2i−1 +n .7.22222220136122551103remainder =r[6] = 1remainder =r[5] = 1remainder =r[4] = 0remainder =r[3] = 0remainder =r[2] = 1remainder =r[1] = 1remainder =r[0] = 1Hence 10310= 11001112.

Loading page image...

8. 2 + 22+ 23+· · ·+ 2m= 2(1 + 2 + 22+· · ·+ 2m−1) = 2(2(m−1)+1−12−1)= 2(2m−1).Alternative answer:2 + 22+ 23+· · ·+ 2m=(1 + 2 + 22+· · ·+ 2m)−1 =(2m+1−12−1)−1=2m+1−1−1 = 2m+1−2 [= 2(2m−1)]9. a.P(3) :3∑i=3i= (3−2)(3 + 3)2P(3) is true because the left-hand side equals3∑i=3i=3 and the right-hand side equals(3−2)(3 + 3)2= 1·62= 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)2Or, equivalently,P(k+ 1) is 3 + 4 + 5 +· · ·+ (k+ 1) = (k−1)(k+ 4)2c.Proof that for all integersk≥3,ifP(k)is true thenP(k+ 1)is true:Letkbe any integer that is greater than or equal to 3, and suppose that3 + 4 + 5 +· · ·+k= (k−2)(k+ 3)2←P(k)inductive hypothesisWe must show that3 + 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 ofP(k+ 1) is3 + 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)2by creating a common denominator=k2+k−62+ 2k+ 22by multiplying out=k2+k−6 + 2k+ 22by adding the fractions=k2+ 3k−42by combining like terms.And the right-hand side ofP(k+ 1) is2

Loading page image...

(k−1)(k+ 4)2=k2+ 4k−k−42=k2+ 3k−42.Thus the left-hand and right-hand sides ofP(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)3P(3) is true because the left-hand side equals3∑i=3(i−1)·i= (3−1)·3 = 2·3 = 6, and theright-hand side equals (3−2)(32+ 2·3 + 3)3= 1·(9 + 6 + 3)3= 1·183= 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)3Or, 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)3c.Proof that for all integersk≥3,ifP(k)is true thenP(k+ 1)is true:Letkbe any integer that is greater than or equal to 3, and suppose that2·3 + 3·4 +· · ·+ (k−1)·k= (k−2)(k2+ 2k+ 3)3.←P(k)inductive hypothesisWe must show that2·3 + 3·4 +· · ·+k(k+ 1) = (k−1)(k2+ 4k+ 6)3.←P(k+ 1)Now the left-hand side ofP(k+ 1) is2·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−63+ 3k(k+ 1)3by creating a common denominator and multiplying out=k3−k−63+ 3k2+ 3k3by multiplying out and combining like terms=k3+ 3k2+ 2k−63by adding the fractions and combining like terms.And the right-hand side ofP(k+ 1) is(k−1)(k2+ 4k+ 6)3=k3+ 4k2+ 6k−k2−4k−63=k3+ 3k2+ 2k−63.Thus the left-hand and right-hand sides ofP(k+ 1) are equal[as was to be shown].11. For each integern≥0, letP(n) be the equation1 + 3 + 32+· · ·+ 3n= 3n+1−12.←P(n)3

Loading page image...

(Recall that by definition 1 + 3 + 32+· · ·+ 3n=n∑i=03i.)(a)P(0):0∑i=03i= 30+1−12P(0) is true because the left-hand side equals0∑i=03i= 30= 1, and the right-hand sideequals 30+1−12= 3−12= 1 also.(b)P(k): 1 + 3 + 32+· · ·+ 3k= 3k+1−12P(k+ 1): 1 + 3 + 32+· · ·+ 3k+1= 3(k+1)+1−12,Or, equivalently,P(k+ 1) is 1 + 3 + 32+· · ·+ 3k+1= 3k+2−12.(c)Proof that for all integersk≥0,ifP(k)is true thenP(k+ 1)is true:Letkbe any integer that is greater than or equal to 0, and suppose that1 + 3 + 32+· · ·+ 3k= 3k+1−12.←P(k)inductive hypothesisWe must show that1 + 3 + 32+· · ·+ 3k+1= 3k+2−12.←P(k+ 1)Now the left-hand side ofP(k+ 1) is1 + 3 + 32+· · ·+ 3k+1=1 + 3 + 32+· · ·+ 3k+ 3k+1by making the next-to-last term explicit=3k+1−12+ 3k+1by inductive hypothesis=3k+1−12+ 2·3k+12by creating a common denominator=3·3k+1−12by adding the fractions and combining like terms=3k+2−12by a law of exponents,which equals the right-hand side ofP(k+ 1).Thus the left-hand and right-hand sides ofP(k+ 1) are equal[as was to be shown].12. Proof (by mathematical induction): Let the propertyP(n) be the equation4 + 8 + 12 +· · ·+ 4n= 2n2+ 2n.←P(n)Note that 4 + 8 + 12 +· · ·+ 4n=n∑i=14i.4

Loading page image...

Show that P(1)is true:P(1) is true because the left-hand side is1∑i=14i= 4·1 = 4 and theright-hand side is 2·12+ 2·1 = 4 also.Show that for all integersk≥1, if P(k)is true thenP(k+ 1)is true: Letkbeany integer withk≥1, and suppose that4 + 8 + 12 +· · ·+ 4k= 2k2+ 2k.←P(k)inductive hypothesisWe must show that4 + 8 + 12 +· · ·+ 4(k+ 1) = 2(k+ 1)2+ 2(k+ 1).←P(k+ 1)Now the left-hand side ofP(k+ 1) is4 + 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+ 4by multiplying out and combining like terms.And the right-hand side ofP(k+ 1) is2(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 ofP(k+ 1) are equal[as was to be shown].13. Proof (by mathematical induction): Let the propertyP(n) be the equation3 + 4 + 5 +· · ·+n= (n−2)(n+ 3)2.←P(n)Note that 3 + 4 + 5 +· · ·+n=n∑i=3i.Show that P(3)is true:P(3) is true because the left-hand side is3∑i=3i= 3 and the right-hand side is (3−2)(3 + 3)2= 3 also.Show that for all integersk≥3, if P(k)is true thenP(k+ 1)is true: Letkbeany integer withk≥1, and suppose that3 + 4 + 5 +· · ·+k= (k−2)(k+ 3)2.←P(k)inductive hypothesisWe must show that3 + 4 + 5 +· · ·+ (k+ 1) = [(k+ 1)−2][(k+ 1) + 3]2.←P(k+ 1)Now the left-hand side ofP(k+ 1) is5

Loading page image...

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)2by creating a common denominator=k2+k−62+ 2k+ 22by multiplying out=k2+ 3k−42by adding fractions and combining like terms.And the right-hand side ofP(k+ 1) is[(k+ 1)−2][(k+ 1) + 3]2= (k−1)(k+ 4)2=k2+ 3k−42.Thus the left-hand and right-hand sides ofP(k+ 1) are equal[as was to be shown].14. Proof (by mathematical induction): Let the propertyP(n) be the equation2·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 is3∑i=3(i−1)·i= (3−1)·3 = 6and the right-hand side is (3−2)(32+ 2·3 + 3)3= 1·(9 + 6 + 3)3= 6 also.Show that for all integersk≥3, if P(k)is true thenP(k+ 1)is true: Letkbeany integer withk≥1, and suppose that2·3+3·4+· · ·+(k−1)·k= (k−2)(k2+ 2k+ 3)3.←P(k)inductive hypothesisWe must show that2·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 image...

Now the left-hand side ofP(k+ 1) is2·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−63+k2+kby combining like terms=k3−k−63+ 3·(k2+k)3by creating a common denominator=k3−k−63+ 3k2+ 3k3by multiplying out=k3+ 3k2+ 2k−63by adding fractions and combining like terms.And the right-hand side ofP(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−63=k3+ 3k2+ 2k−63.Thus the left-hand and right-hand sides ofP(k+ 1) are equal[as was to be shown].15. Proof (by mathematical induction): Let the propertyP(n) be the equation1 + 3 + 32+· · ·+ 3n= 3n+1−12..←P(n)Note that 1 + 3 + 32+· · ·+ 3n=n∑i=03i.Show that P(0)is true:P(0) is true because the left-hand side is0∑i=03i= 30= 1,and theright-hand side is 30+1−12= 3−12= 1 also.Show that for all integersk≥0, if P(k)is true thenP(k+ 1)is true: Letkbeany integer withk≥0, and suppose that1 + 3 + 32+· · ·+ 3k= 3k+1−12.←P(k)inductive hypothesisWe must show that1 + 3 + 32+· · ·+ 3k+1= 3(k+1)+1−12.Or, equivalently, that1 + 3 + 32+· · ·+ 3k+1= 3k+2−12←P(k+ 1).7

Loading page image...

(a) Now the left-hand side ofP(k+ 1) is1 + 3 + 32+· · ·+ 3k+1=1 + 3 + 32+· · ·+ 3k+ 3k+1by making the next-to-last term explicit=3k+1−12+ 3k+1by inductive hypothesis=3k+1−12+ 2·3k+12by creating a common denominator=3·3k+1−12by adding the fractions and combining like terms=3k+2−12by a law of exponents,which equals the right-hand side ofP(k+ 1).Thus the left-hand and right-hand sides ofP(k+ 1) are equal[as was to be shown].16. Proof (by mathematical induction): Let the propertyP(n) be the sentence8n−1 is divisible by 7.←P(n)We will prove thatP(n) is true for all integersn≥0.Show that P(0)is true:P(0) is true because because 80−1 = 1−1 = 0 and 0 is divisibleby 7 (since 0 = 0·7).Show that for all integersk≥0, if P(k)is true thenP(k+ 1)is true: Letkbeany integer withk≥0,and suppose8k−1 is divisible by 7.←P(k)inductive hypothesisWe must show that8k+1−1 is divisible by 7.←P(k+ 1)By definition of divisibility, the inductive hypothesis is equivalent to the statement that thereis an integerrwith8k−1 = 7r.Then8k+1−1=8·8k−1=(7 + 1)8k−1=7·8k+ (8k−1)by algebra=7·8k+ 7rby inductive hypothesis=7(8k+r)by algebra.Now 8k+ris an integer because products and sums of integers are integers.Thus, by definitionof divisibility, 8k+1−1 is divisible by 7[as was to be shown].17. Proof (by mathematical induction): Let the propertyP(n) be the inequality1 + 4n <2n.←P(n)We will prove thatP(n) is true for all integersn≥5.8

Loading page image...

Show that P(5)is true:P(5) is true because the left-hand side is 1 + 4·5 = 21 and theright-hand side is 25= 32,and 21<32.Show that for all integersk≥5, if P(k)is true thenP(k+ 1)is true: Letkbeany integer withk≥5,and suppose1 + 4k <2k.←P(k)inductive hypothesisWe must show that1 + 4(k+ 1)<2k+1.←P(k+ 1)By algebra and the inductive hypothesis we have that1 + 4(k+ 1) = 1 + 4k+ 4<2k+ 4.So1 + 4(k+ 1)<2k+ 4.(*)Now, sincek≥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 that1 + 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 that2k+ 4<2k+1.Now2k+ 4<2k+1⇔4<2k+1−2k= 2·2k−2k= 2k(2−1) = 2k.But whenk≥5,4<2k,so the desired inequality is true.]18. Proof (by mathematical induction): Let the propertyP(n) be the sentenceIfa1, a2, . . . , anandb1, b2, . . . , bnare any realnumbers, then∑nk=1(2ak−3bk) = 2∑nk=1ak−3∑nk=1bk..←P(n)Show that P(1)is true: Leta1andb1be any real numbers. By the recursive definition ofsummation,1∑k=1(2ak−3bk) = 2a1−3b1, 21∑k=1ak= 2a1,31∑k=1bk= 3b1,and so1∑k=1(2ak−3bk) = 21∑k=1ak−31∑k=1bk.HenceP(1) is true.Show that for all integersk≥1,if P(k)is true thenP(k+ 1)is true: Letkbeany integer withk≥1, and suppose thatIfa1, a2, . . . , amandb1, b2, . . . , bmare any realnumbers, then∑mk=1(2ak−3bk) = 2∑mk=1ak−3∑mk=1bk.←P(m)inductive hypothesis9

Loading page image...

We must show thatIfa1, a2, . . . , am+1andb1, b2, . . . , bm+1are any realnumbers, then∑m+1k=1(2ak−3bk) = 2∑m+1k=1ak−3∑m+1k=1bk..←P(m+ 1)So supposea1, a2, . . . , am+1andb1, b2, . . . , bm+1are any real numbers. Then∑m+1k=1(2ak−3bk)=∑mk=1(2ak−3bk) + (2am+1−3bm+1)by the recursive definition of summation=(2∑mk=1ak−3∑mk=1bk) + (2am+1−3bm+1)by substitution from the inductivehypothesis=(2∑mk=1ak+ 2am+1)−(3∑mk=1bk+ 3bm+1)by the associative and commutativelaws of algebra=2∑m+1k=1ak−3∑m+1k=1bkby the recursive definition of summation[This is what was to be shown.]19. Proof (by strong mathematical induction): Let the propertyP(n) be the sentencenis either a prime number or a product of prime numbers.We will prove thatP(n) is true for all integersn≥2.Show that P(2)is true: Whenn= 2, the sentence is “2 is either a prime number or aproduct of prime numbers.” This sentence is true because 2 is prime. HenceP(2) is true.Show that ifk≥2and P(i)is true for all integers i from2through k,thenP(k+ 1)is true: Let be any integer withk≥2, and suppose thatFor all integersiwith 2≤i≤k, iis eithera prime number or a product of prime numbers.←inductive hypothesisWe must show thatk+ 1 is either a prime number or a product of prime numbers.In casek+ 1 is prime, the sentence is true. So supposek+ 1 is not prime. Then, by definitionof prime,k+ 1 =rsfor some positive integersrandswithr̸= 1 ands̸= 1. By Theorem4.3.1,r≤kands≤k,and, because neitherrnorsequals 1,r < kands < k.Thus, byinductive hypothesis, each ofrandsis either a prime number or a product of prime numbers.So, becausek+ 1 is the product ofrands,k+ 1 is a product of prime numbers[as was to beshown].20. Proof (by strong mathematical induction): A sequencea0, a1, a2, . . .is defined recursively asfollows:a0= 2,a1= 9ak= 5ak−1−6ak−2for all integersk≥2.Let the propertyP(n) be the equationan= 5·3n−3·2n.←P(n)We will prove thatP(n) is true for all integersn≥0.Show that P(0)and P(1)are true: By definition ofa0, a1, a2, . . ., we have thata0= 2anda1= 9.Since 5·30−3·20= 5−3 = 2and 5·31−3·21= 15−6 = 9, P(0) andP(1) areboth true.10

Loading page image...

Show that ifk≥1and P(i)is true for all integers i from0through k, thenP(k+ 1)is true: Letkbe any integer withk≥1, and supposeai= 5·3i−3·2ifor all integersiwith 0≤i≤k.←inductive hypothesisWe must show thatak+1= 5·3k+1−3·2k+1.Butak+1=5ak−6ak−1by definition ofa0, 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)because3k= 3·3k−1and2k= 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+1by algebra,[as was to be shown].[Since both the basis and the inductive steps have been proved, we conclude thatP(n)is truefor all integersn≥0.]21. Proof (by strong mathematical induction):A sequences1, s2, s3, ...is defined recursively as fol-lows:sk=5sk−1+ (sk−2)2for all integersk≥3s1=4s2=8Let the propertyP(n) be the sentencesnis divisible by 4.←P(n)We will prove thatP(n) is true for all integersn≥1.Show that P(1)and P(2)are true: By definition ofs1, s2, s3, ..., we have thats1= 4 ands2= 8.Since both 4 and 8 are divisible by 4,P(1) andP(2) are both true.Show that ifk≥2and P(i)is true for all integers i from0through k, thenP(k+ 1)is true: Letkbe any integer withk≥2, and supposeskis divisible by 4 for all integersiwith 0≤i≤k.←inductive hypothesisWe must show thatsk+1is divisible by 4.Now, by definition ofs1, s2, s3, ..,sk+1= 5sk+ (sk−1)2.By inductive hypothesis,bothskandsk−1are divisible by 4. Hence, there exist integersaandbso thatsk= 4aandsk−1= 4b.Thensk+1=5sk+ (sk−1)2=5(4a) + (4b)2by substitution=4(5a) + 4(4b2)because3k= 3·3k−1and2k= 2·2k−1=4(5a+ 4b2)by algebra.11

Loading page image...

Now 5a+ 4b2is an integer because products and sums of integers are integers, and thussk+1is 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 thatP(n)is truefor all integersn≥0.]22. Proof:I.Basis Property:I(0) is the statementi= 0 + 1 = 1 andproduct:=A[1].According to the pre-condition this statement is true.II. Inductive Property: The guardGis the conditioni̸=m.Supposekis any nonnegativeinteger such thatG∧I(k) is true before an iteration of the loop. Then when execution comesto the top of the loop,i̸=m,product=A[1]·A[2]· · ·A[k+ 1]andi=k+ 1.Sincei̸=m, the guard is passed and statement 1 is executed.Now before execution ofstatement 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 thatproductnew:=productold·A[inew],SinceA[inew] =A[k+ 2],after statement 2 is executed we have thatproductnew=productold·A[k+ 2] =A[1]·A[2]· · ·A[k+ 1]·A[k+ 2].HenceI(k+ 1) is true.III. Eventual Falsity of Guard: The guardGis the conditioni̸=m.By I and II, it isknown that for all integersn≥1, afterniterations of the loopI(n) is true. Hence afterm−1iterations of the loopI(m) is true, which implies thati=mandGis false.IV. Correctness of the Post-Condition: Suppose thatNis the least number of iterationsafter whichGis false andI(N) is true. Then (sinceGis false)i=mand (sinceI(N) is true)i=N+ 1andproduct=A[1]·A[2]· · ·A[N+ 1]andi=m.Putting these together givesm=N+ 1 and soproduct=A[1]·A[2]· · ·A[m],which is the post-condition.23. a.s1= 4 (two move to transfer the two disks to poleBand two more moves to transfer themto poleC)s2= 16 (by the reasoning above, 4 moves are needed to transfer the top two disks from poleAto poleC,then 2 moves are needed to transfer the two bottom disks from poleAto poleB,another 4 moves to transfer the top two disks back to poleA,then 2 more to transfer the two12

Loading page image...

bottom disks from poleBto poleC,and finally 4 moves to transfer the two top disks frompoleAto poleC)b.sk=sk−1(moves to transfer the top 2(k−1) disks from poleAto poleC)+2 (moves to transfer the two bottom disks from poleAto poleB)+sk−1(moves to transfer the top 2(k−1) disks from poleCto poleA)+2 (move to transfer the two bottom disks from poleBto poleC)+sk−1(moves to transfer the top 2(k−1) disks from poleAto poleC).Sosk= 3sk−1+ 4 for all integersk≥2.24. a.t1= 3, t2= 3 + 3 + 3 = 9b. For all integersk≥2,tk=tk−1(moves to transfer the top 3k−3 disks from poleAto poleB)+3(moves to transfer the bottom two disks from poleAto poleC)+tk−1(moves to transfer the top 3k−3 disks from poleBto poleC)=2tk−1+ 3.Note that transferring the stack of 3kdisks from poleAto poleCrequires at least two transfersof the top 3(k−1) disks: one to transfer them off the bottom two disks to free the bottomdisks so that they can be moved to poleCand another to transfer the top 3(k−1) disksback on top of the bottom two disks.Thus at least 3tk−1moves are needed to effect thesetwo transfers. Three more moves are needed to transfer the bottom three disks from poleAto poleC, and this transfer cannot be effected in fewer than three moves. It follows that thesequence 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 ofmonth 0), ands1= 1 ands2= 1 because rabbits are not fertile during their first two monthsof life. Thereafter,sk=sk−1+ 4sk−3for all integersk≥3.The reason is that fork≥3,sk=[the number of pairs of rabbitsalive at the end of monthk−1]+ 4·[the number of pairs of rabbitsthat are fertile during monthk]=[the number of pairs of rabbitsalive at the end of monthk−1]+ 4·[the number of pairs of rabbitsalive at the end of monthk−3]=sk−1+ 4sk−3.26. a. When 4% interest is compounded quarterly, the interest rate per quarter is0.044= 0.01. IfSkis the amount on deposit at the end of thekth quarter, thenSk=Sk−1+ (0.01)Sk−1= (1 + 0.01)Sk−1= (1.01)Sk−1for each integerk≥1.b. Because 3 years is 12 quarters, we need to computeS12.NowS0= $5000,and soS12= (1.01)S11= (1.01) [(1.01)S10] = (1.01)2S10= (1.01)2[(1.01)S9] = (1.01)3S9= (1.01)3[(1.01)S8] = (1.01)4S8= (1.01)4[(1.01)S7] = (1.01)5S7= (1.01)5[(1.01)S6] = (1.01)6S6= (1.01)6[(1.01)S5] = (1.01)7S5= (1.01)7[(1.01)S4] = (1.01)8S4= (1.01)8[(1.01)S3] = (1.01)9S3= (1.01)9[(1.01)S2] = (1.01)10S2= (1.01)10[(1.01)S1] = (1.01)11S1= (1.01)11[(1.01)S0] = (1.01)12S0= (1.01)12·5000∼= 5634.13 dollars.13

Loading page image...

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 yearis four quarters, we need to calculateS4−S0S0.Now, by a similar computation as above,S4= (1.01)4S0, and soAPR=S4−S0S0∼= (1.01)4S0−S0S0= (1.01)4−1∼= 4.06%.27. a.a1= 3, a2= 4a1+ 2 = 4·3 + 2 = 14,anda3= 4a2+ 2 = 4·14 + 2 = 58b.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 + 2c. 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−14−1)= 4n−1·3 + 2(4n−1−13)= 3·4n−1+ 23·4n−1−23= 93·4n−1+ 23·4n−1−23 = 113·4n−1−2328. a.c0= 1,and soc1= 7c0+ 2 = 7·1 + 2 = 9 andc2= 7c1+ 2 = 7·9 + 2 = 65b. 7n+ 2·7n−1+· · ·+ 2·72+ 2·7 + 2 = 7n+ 2(7n−1+· · ·+ 72+ 7 + 1)= 7n+ 2(7(n−1)+1−17−1)= 7n+ 2(7n−16)= 3·7n3+ 7n−13= 4·7n−1314

Loading page image...

c.c0= 1c1= 7c0+ 2 = 7·1 + 2 = 7 + 2c2= 7c1+ 2 = 7(7 + 2) + 2 = 72+ 7·2 + 2c3= 7c2+ 2 = 7(72+ 7·2 + 2) + 2 = 73+ 72·2 + 7·2 + 2c4= 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−13by part (b).29.b0=1b1=2b0+ 3 = 2·1 + 3 = 2 + 3b2=2b1+ 3 = 2·(2 + 3) + 3 = 22+ 2·3 + 3b3=2b2+ 3 = 2·(22+ 2·3 + 3) + 3 = 23+ 22·3 + 2·3 + 3b4=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−12−1)= 2n+ 3·2n−3 = 4·2n−3 = 2n+2−3.30. Proof (by mathematical induction)::Leta0, a1, a2, . . ..be a sequence that satisfies therecurrence relationak= 4ak−1+ 1for allk≥1, with initial conditiona0= 2, and let thepropertyP(n) be the equationan= 7·4n−13.←P(n)Show that P(0)is true:P(0) is the equationa0= 7·40−13.The right-hand side ofP(0) is 7·40−13= 7−13= 2. This equalsa0, which is the left-handside ofP(0). SoP(0) is true.Show that for all integersk≥0,if P(k)is true thenP(k+ 1)is true: Letkbe anyinteger withk≥0, and suppose thatak= 7·4k−13.←P(k)inductive hypothesisWe must show thatak+1= 7·4k+1−13.←P(k+ 1)15

Preview Mode

This document has 97 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

Solution Manual For Discrete Mathematics With Applications, 5th Edition

AP Calculus AB Scoring Guide Unit 6 Progress Check

Clinical Psychologist

Module 4 Matrices

MATH 1324 Homework 5 Answers

Ap progress 1 5 all 5

The Fundamental Theorem of Calculus and Definite I

AP Calculus AB Scoring Guide

Investigating the Rising Cost of MTA Transit Fare

Module 11 Geometry

Company

Explore

Study Tools