21127 Lecture Notes - Lecture 15: Computer-Aided Technologies, Kaiaphas, Holda
16 Dec 2015
School
Department
Course
Professor
Document Summary
Recall problem #5 from homework 2: mo" brendans, mo" problems. Claim: with currency notes of denominaton 3 and 7 brendans, we can de nitely make payments of anything over (and including) 12 brendans. Let p (n) be the statement we can pay n with denominations 3 and 7 . Base cases: we can show p (12), p (13), p (14) easily: Induction hypothesis: suppose k n and k 14 and suppose. P (12) p (13) p (14) p (k) (notice that k 14 is an essential assumption here, based on the way we set up our base cases. We can"t use the following argument to deduce p (13), say, so we need to make this restriction. ) Since k 14, k +1 15 so (k +1) 3 12. This tells us (k + 1) 3 = k 2 is achievable. By adding another 3 brendan note to the representation of k 2, we can achieve k + 1.
