Name (printed):Student ID #:Section # (or TA’s:name and time)CMSC 250 Quiz #9 Wednesday, Mar. 31, 2004Write all answers legibly in the space provided. The number of points p os sible for each question is indicatedin square brackets – the total number of points on the quiz is 30, and you will have exactly 20 minutes tocomplete 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− 7Base Case:(n = 6)4(6) = 24===================62− 7 = 36 − 7 = 29===================24 < 29Inductive Hypothesis:(n = x)4x < x2− 7Inductive Step:(n = x + 1)Show:4(x + 1) < (x + 1)2− 7Proof:By the I.H., 4x < x2− 7Adding 4 to both sides, 4x + 4 < x2− 7 + 4Doing Algebra, 4(x + 1) < x2− 3Since we know that 0 < 2x − 3 ∀x ∈ Z≥2We can add the 0 to the left and the 2x − 3 to the right and get 4(x + 1) < x2− 3 + 2x − 3Doing Algebra, 4(x + 1) < x2+ 2x + 1 − 7after further algrbra, 4(x + 1) < (x + 1)2− 7 QED2. [15 pnts.] Use strong induction to prove the following statement.Assume:a1= 3 a2= 5 a3= 1 an= 2an−1+ 3an−2+ 4an−3Prove that∀n ∈ Z where n ≥ 1, an∈ ZoddBase Case:(n = 1, 2, 3)a1= 3, 3 ∈ Zodda2= 5, 5 ∈ Zodda3= 1, 1 ∈ ZoddInductive Hypothesis:(n = i∀i ∈ Z4 ≤ i ≤ k)ai∈ Zoddwhere ai= 2ai−1+ 3ai−2+ 4ai − 3Inductive Step:(n = k + 1)Show:ak+1∈ Zoddwhere ak+1= 2ak+ 3ak−1+ 4ak−2Proof:By the I.H.:Since ak∈ Zodd, ∃m ∈ Z ak= 2m + 1Since ak−1∈ Zodd, ∃p ∈ Z ak−1= 2p + 1Since ak−2∈ Zodd, ∃q ∈ Z ak−2= 2q + 1By 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) + 1Since 2m + 3p + 4q + 4 ∈ Z,ak+1∈ Zoddby the definition of o dd.
View Full Document
Unlocking...