Name printed Student ID Section or TA s name and time CMSC 250 Quiz 9 Wednesday Mar 31 2004 Write all answers legibly in the space provided The number of points possible for each question is indicated in square brackets the total number of points on the quiz is 30 and you will have exactly 20 minutes to complete this quiz You may not use calculators textbooks or any other aids during this quiz 1 15 pnts Use regular induction to prove the following inequality n Z where n 6 4n n2 7 Base Case n 6 4 6 24 62 7 36 7 29 24 29 Inductive Hypothesis n x 4x x2 7 Inductive Step n x 1 Show 4 x 1 x 1 2 7 Proof By the I H 4x x2 7 Adding 4 to both sides 4x 4 x2 7 4 Doing Algebra 4 x 1 x2 3 Since we know that 0 2x 3 x Z 2 We can add the 0 to the left and the 2x 3 to the right and get 4 x 1 x2 3 2x 3 Doing Algebra 4 x 1 x2 2x 1 7 after further algrbra 4 x 1 x 1 2 7 QED 2 15 pnts Use strong induction to prove the following statement Assume a1 3 a2 5 a3 1 an 2an 1 3an 2 4an 3 Prove that n Z where n 1 an Z odd Base Case n 1 2 3 a1 3 3 Z odd a2 5 5 Z odd a3 1 1 Z odd Inductive Hypothesis n i i Z4 i k ai Z odd where ai 2ai 1 3ai 2 4ai 3 Inductive Step n k 1 Show ak 1 Z odd where ak 1 2ak 3ak 1 4ak 2 Proof By the I H Since ak Z odd m Z ak 2m 1 Since ak 1 Z odd p Z ak 1 2p 1 Since ak 2 Z odd q Z ak 2 2q 1 By Substitution ak 1 2 2m 1 3 2p 1 4 2q 1 4m 2 6p 3 8q 4 4m 6p 8q 9 2 2m 3p 4q 4 1 Since 2m 3p 4q 4 Z ak 1 Z odd by the definition of odd QED
View Full Document
Unlocking...