Prove that any integer amount of postage from 18 cents and up can be made using only 4-cent and 7-cent stamp. Assume an infinite supply of stamps My question reads as follows: 
Prove that any integer amount of postage from 18 cents and up can be
made using only 4-cent and 7-cent stamp. Assume an infinite supply of
stamps. Use induction
Firstly, I must construct an equation to allow me to evaluate this problem with induction. The equation I have decided on is $N=4m+7n$ and $N>17$ so the base case must be in this case that N = 18.
Evaluating the base case I achieve that 18 is in fact equal to 18. Great, now I can move onto the induction step.
However, I am unsure as to how to continue this problem. And am in need of assistance. Thanks
 A: There are four standard answers
1) Google the Frobenuis coin problem.
2) Google the (shudder)  "Chicken McNuggets"  problem (ugh).
3) Show that $4*2+ 7*(-1) = 3*7 + 4*(-5) = 1$ so if you have $N= 4m + 7n$ then $N + 1 = 4(m+2) + 7*(n-1) = 4(m-5) + 7(n+3)$ which will work so long as either $n > 0$ or $m > 4$.
4) If you have $N = 4m + 7n$ is possible then $N+4 = 4(m+1) + 7n$ is possible.  Then do ** $4$ ** base cases.  $18,19,20, 21$  If those four base cases work then so do $4k$ plus any of those four base cases.
=======
More detail
3) Base Case:  $18 = 4*1 + 2*7$.
Induction Step:  If $N = 4*m +7*n$ and $N \ge 18$ then if $n \ge 1$ then $4*(m+2) + 7*(n-1) = 4*m + 7*n + 8-7 = N+1$.
If $n = 0$ then $N=4*m \ge 18$ so $m \ge 4.5$ so $m \ge 5$.
Then $4(m-5) + 7*(n+3) = (4m + 7n) + (-20+21) = N+1$.
........
4) Base cases:
$18= 4*1 + 7*1$
$19 = 4*3 + 7*1$
$20 = 4*5 + 7*0$
$21 = 4*0 + 7*3$.
Induction step:
If $N = 4m + 7n$ then $N + 4 = 4(m+1) + 7n$.
As as all $N$ are equivalent to $18,19,20$ or $21\pmod 4$ that covers all cases even though we need a different base case for each equivalence class.
A: Hint:
Think of this as four separate induction problems, whose base cases are 18 cents, 19 cents, 20 cents, and 21 cents, respectively.
A: You can get $18 = 2 \cdot 7 + 1\cdot 4$, $19 = 1 \cdot 7 + 3 \cdot 4$, $20 = 0 \cdot 7 + 5 \cdot 4$, $21 = 3 \cdot 7 + 0 \cdot 4$. From those you get all larger numbers by adding $4$. You need to also show that 17 is impossible (try all posibilities, there aren't that many...).
This is called Frobenius problem, for 2 values of stamps (like here) the largest value that can't be represented is $a_1 a_2 - a_1 - a_2$, here $4 \cdot 7 - 4 - 7 = 17$.
A: Hint: what you have to show is that for each $N \ge 18$, there exist $m$ and $n$, such that $N = 4m + 7n$. This is true for $N = 18$. Now you have to assume it's true for some $N \ge 18$ and show that it is true for $N + 1$, i.e., given $m$ and $n$ such that $N = 4m + 7n$, you have to find $m'$ and $n'$ such that $N + 1 = 4m' + 7n'$, i.e., such that:
$$4m + 7n + 1 = 4m' + 7n'$$
To derive $m'$ and $n'$ from $m$ and $n$, you can use $2\cdot4 = 7 + 1$, if $n > 0$, and you can use $4 \cdot 5 + 1 = 3 \cdot 7$, if $n = 0$, (because in the latter case as $N \ge 18$, $m \ge 5$).
