1

Question:
Prove that there are $12 + n = 4k_1 + 5k_2, k_1, k_2 \in \mathbb{N}, n \in \mathbb{N}^+$

The question above is taken from the following:
Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps.

My Attempt:
I've already proven this using induction (using first principle induction and second principle also known as strong induction). The book also hinted that this can be solved without using induction which is bugging me for a while now.

JoeyAndres
  • 1,269
  • 2
    Do you mean $12+n = 4k_1+5k_2$? – Théophile Jul 13 '14 at 15:39
  • 3
    Once we have done $12,13,14,15$, any bigger number can be obtained by adding a suitable number of $4$ cent stamps. – André Nicolas Jul 13 '14 at 15:43
  • 1
    $k_1,k_2$ are supposed to be natural numbers, not integers. You can't have a negative number of stamps. – Deathkamp Drone Jul 13 '14 at 16:11
  • Also, by natural numbers I mean $\Bbb{N}_0={0,1,2,...}$, and not $\Bbb{N}^+={1,2,...}$. Otherwise $n=4$ has no solution, for instance. – Deathkamp Drone Jul 13 '14 at 16:15
  • 1
    While it's easy to get the gist of your statement, what you've written doesn't quite translate the problem correctly - you need to be very careful about the logic. What you specifically wrote most accurately translates as 'prove that there exist $n$, $k_1$ and $k_2$ with $12+n=4k_1+5k_2$, but what you want to say is that 'for ALL $n$ (in $\mathbb{N}$), there exist $k_1$ and $k_2$ with $12+n=4k_1+5k_2$'. – Steven Stadnicki Jul 13 '14 at 16:22

1 Answers1

5

One can verify by hand that for each of $n=12,13,14,15$ cents, we can produce postage of $n$ cents.

Now let $n\gt 15$. Keep putting $4$ cent stamps on the envelope until the amount we still owe falls in the interval from $12$ to $15$. Then do the rest as already calculated.

Like the vast majority of results about the integers, this is in principle an induction argument. However, it is so simple that there seems to be no point in making the induction explicit.

Or else note that $12,13,14,15$ are respectively congruent to $0,1,2,3$ modulo $4$. Any $n$ is therefore congruent to one of these modulo $4$. So if $n\gt 15$, there is a unique $a$ in the interval from $12$ to $15$ such that $4$ divides $n-a$. Thus $n=4q+a$ for some positive integer $q$. Since $a$ is achievable with $4$ cent and/or $5$ cent stamps, and $4q$ obviously is, it follows that $4q+a$ is achievable.

André Nicolas
  • 507,029