Prove that any integer greater than or equal to 9 can be written as 3a + 4b wher

Question

Prove that any integer greater than or equal to 9 can be written as 3a + 4b where a and b are non-negative integers. By weak induction By strong induction

Explanation / Answer

(a) suppose p(n) = "n is an integer greater than or equal to 9" when n =9, we can write p(n) = 3(3) + 4(0) and so, a =3 , b = 0 are the non negative integers satisfy the requirement. ---(1) when n = 10, we get p(n) = 3(2) + 4(1) such that a = 2, b = 1 are the non negative integers satisfy the requirement. suppose the statement is true for n = k> 9. i.e., p(k) = k = 3x + 4y for some non negative integers x and y. ---(2) when n = k+1, p(k+1) = 3x+ 4y + 1 by (2) since x and y are non negative integers, we have x greater than or equal to zero and y greater than or equal to zero. there arise two cases. that is (1) if x = 0, then y greater than or equal to 2 while k +1 > 9 so, 3x+ 4y + 1 = 3x + 4(y-2) + 9 =3(x+3) + 4(y-2) clearly x+3, y-2 are the non negative integers satisfy the non negative integer condition and thus we are through. (2) if x > 3 and y = 0, then 3x+ 4y + 1 = 3(x-1) + 4(y+1) which satisfy x-1, y+1 will be the non negative integers in the required form. thus, in any case, p(k+1) is in the form 3x + 4y ---(3) (1),(2) and(3) satisfy the hypothesis of the weak mathematical induction. ---------------------------------------------------------------------------------------------- (b) suppose the statement is true for all positive integers 9 by the hypothesis. --------------------------------------------------------------------- keeping case (1) in view, m = 3a+ 4b + 1 = 3(a-1) + 4(b+1) clearly a-1 and b+1 are non negative integers which satisfy our requirement. case 2: m= 3a + 4(b-2) + 9 =3(a+3) + 4(b-2) clearly b greater than or equal to 2 leads tob-2 greater than or equal to zero. thus, a+3, b-2 are the non negative integers which satisfy the requirement. thus, the hypothesis of strong mathematical induction is satisfied.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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