Originally Posted by

**undefined** Since there are so many formal proofs popping up here, I might as well formalise my earlier post.

Define "k is attainable" as: there exist nonnegative integers m and n such that k = 4m + 5n.

Base cases:

12 is attainable, (m, n) = (3, 0).

13 is attainable, (m, n) = (2, 1).

14 is attainable, (m, n) = (1, 2).

15 is attainable, (m, n) = (3, 0).

Induction step:

Let k be an integer such that k-4 is attainable. Then k is attainable.

Proof:

There exist nonnegative integers m and n such that k-4 = 4m + 5n.

Then k = 4(m+1) + 5n.

Therefore, k is attainable.

One approach to tie together the induction step with the base cases is to use strong induction, but why not just partition the set of nonnegative integers by congruence (mod 4)?

S0 = {0, 4, 8, ...}

S1 = {1, 5, 9, ...}

S2 = {2, 6, 10, ...}

S3 = {3, 7, 11, ...}

It can be seen that the intersection of the sets is the empty set, and the union of the sets is the nonnegative integers.

So we treat each subset the same way we would treat the nonnegative integers and apply weak induction four times.

Therefore, all integers greater than or equal to 12 are attainable.

This concludes the proof.