Using induction, show that using only 3c stamps and 5c stamps, any postage amoun

Question

Explanation / Answer

let P(n) : " There exist a, b, such that 3a + 5b = n", and prove P(n) by complete induction on n >= 8. Suppose n >= 8 and that P(8), ..., P(n-1) all are true. To prove P(n) is true, Either n = 8 or n = 9 or n = 10 or n >= 11. Case 1: If n = 8, then n = 8 = 1*3 + 1*5, so P(8). Case 2: If n = 9, then n = 9 = 3*3 + 0*5, so P(9). Case 3: If n = 10, then n = 10 = 0*3 + 2*5, so P(10). Case 4: If n >= 11, then n-3 >= 8 so let a' and b' be such that n-3 = 3 a' + 5 b', by the Induction Hypothesis.. Then, n = 3 + (n - 3) = 3 + 3 a' + 5 b' = 3 (a' + 1) + 5 b' so P(n) is true (by picking a = a'+1, b = b').

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.