Prove that every number greater than 7 is a sum of a nonnegative integer multipl

Question

Prove that every number greater than 7 is a sum of a nonnegative integer multiple of 3 and a nonnegative integer multiple of 5. Show: Base case, inductive hypothesis, inductive step, and proof.

Explanation / Answer

The statement is true for n=8, because 8= 3*1 + 5*1 Suppose that it is true for n=k k = 3a + 5b (a,b>=0) Now you have to prove it for n=k+1 k= 3a+5b ==> k+1 = 3a+5b+1 = 3(a-1) +3+ 5(b-1) +5+1 = 3(a-1) + 5(b-1) + 9 = 3(a-1) + 5(b-1) + 3*3 = 3(a-1+3) + 5(b-1) = 3(a+2) + 5(b-1) if b>=1, then a+2 and b-1 are both non-negative integers, and the statement is true for n=k+1 as well. if b=0 k= 3a ( and we know that a>=3, because 3a>=9) k+1 = 3a+1 = 3(a-3) +9+1 = 3(a-3) + 5*2

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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