I am trying to prove this statement, but am having some trouble with it. I think I am in the right direction but would like some feedback. Note: The proof must be completed using induction, and it looks like I need strong induction.
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
So far, I have that n = 4a + 5b for some positive integer a,b. I did 4 base cases and verified that n = 12, 13, 14, 15 are true. I don't quite understand the hint. I tried a different way, and it seems to work but I'm not sure if it's right.
Base Case (n=12,13,14,15): Proven separately and fairly trivial.
Inductive Step: Suppose that the proposition is true for some n >= 12. Assume that for all natural numbers 12 <= f <= n, f = 4c + 5d for some integer c,d.
We want to show that n + 4 = 4a + 5b. Using our inductive hypothesis, we know that n <= n and thus n + 4 = (4c + 5d) + 4 = 4 (c + 1) + 5d. Since c is an integer, we know that c+1 is an integer as well and thus n + 4 = 4a + 5b (letting c+1 = a and d = b).
Since we have shown that P(n) ---> P(n+4), the proposition is true. That is, we have proven the proposition for n = 12, 16, 20,.... and n = 13, 17, 21, 25 and n = 14, 18, 22.... and n = 15, 19, 23, 27...