Question

For every natural number n which is greater than or equal to 12, n can be written as the sum of a nonnegative multiple of 4 and a nonnegative multiple of 5. Hint: in the inductive step, it is easiest to show that P(k -3) - P(k +1), where P(n) is the given proposition.

Need a detailed proof by strong induction!

Answer 1

Let, p(n) be the statement that n can be written as the sum of a non negative of 4 and a non negative multiple of 5 therefore p(n): n = 4 a + 5 b where a, b are non negative integers step 1: 12 = 4.3 + 5.0, 13 = 4.2 + 5.1, 14 = 4.1 + 5.2, 15 = 4.0 + 5.3, so, the statements p(12), p(13), p(14), p(15) are true step 2: Assume that, for any value j (12 lessthanorequalto j lessthanorequalto k) where k greaterthanorequalto 15 can be expressed as j = 4 a + 5 b with a and b being non negative integers step 3: since, 12 lessthanorequalto k - 3 lessthanorequalto k (because k greaterthanorequalto 15) k - 3 = 4 a + 5b (because p(k - 3) is true) implies k - 3 + 4 = 4 a + 5b + 4 implies k + 1 =