# Proof: n can be written as the sum of a nonnegative multiple of 4 and a nonnegative multiple of 5.

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...

$$12+4k=(3+k)\times4$$ $$13+4k=(2+k)\times4+1\times5$$ $$14+4k=(1+k)\times4+2\times5$$ $$15+4k=k\times4+3\times5$$ Since every number $$n\ge12$$ can be written one of the above forms where $$k\in\mathbb{N}$$, we can write any number $$n\ge12$$ in the desired form.
Note that proving $$P(n) \implies P(n+4)$$ when $$n \geq 12$$ is the same thing as proving $$P(k-3) \implies P(k+1)$$ when $$k \geq 15.$$ Since you needed to include four statements of the proposition, $$P(n)$$ for $$12 \leq n \leq 15,$$ in your base case, your proof covers all the integers $$n = 12$$ or greater in the same way as the hint does.
The only caution I would have is that we do not usually define the natural numbers four at a time, that is, they are not axiomatically the numbers $$0, 1, 2, 3$$ and $$n + 4$$ for any $$n$$ that is a natural number, or $$1,2,3,4$$ and $$n + 4$$ for any $$n$$ that is a natural number, or anything else where the inductive part of the definition generates $$n+4$$ from $$n.$$ Instead, we get $$n+1$$ from $$n.$$
So I'm not sure exactly how your instructor would prefer to word it, but the hint suggests to me that instead of taking $$P(n)$$ as your proposition, where $$P(n)$$ means $$n=4a+5b$$ for non-negative integers $$a,b,$$ you should instead take $$P'(n) = P(n)\land P(n-1) \land P(n-2) \land P(n-3)$$ as your proposition, with base case $$n=15.$$ Then in order to prove that $$P'(k) \implies P'(k+1),$$ you use the fact that $$P(k - 3) \implies P(k+1)$$ and the fact that each of the other three sub-propositions implies itself.
On the other hand, if a statement $$P(n)$$ is true for some set of $$m$$ consecutive integers $$n_0, n_0 + 1, \ldots, n_0 + m - 1,$$ and if $$P(n) \implies P(n+m),$$ then $$P(n)$$ is true for all integers $$n$$ such that $$n \geq n_0.$$ Given this general fact about inductive proofs, your proof shows what it was desired to show.