Question regarding proof by Induction A vending machine cannot return coins as change, but only five-cent and eight-cent stamps.
For a particular k, though, we can prove by induction that the machine can make every number of cents that is k or greater.
What is the smallest value of k for which we can do this?
My answer is 9 but I was told this is not correct. My understanding is that the machine can only make change for numbers greater than 7.
I am looking for a confirmation.
 A: You can quickly check that $9$ can not be correct, because there is no way it could output $11$.
It also can't output $27$. However it can return $\underbrace{28, 29, 30, 31, 32}_{\text{5 consecutive numbers}}$ and thus also $33 = 28 + 5, 34 = 29 + 5, \ldots$.
$$
\begin{array}{c|cccc}
0 & 5 & 10 & 15 & 20 & 25 & \color{red}{30} \\
\hline
8 & 13 & 18 & 23 & \color{red}{28} & 33 & 38 \\
16 & 21 & 26 & \color{red}{31} & 36 & 41 & 46 \\
24 & \color{red}{29} & 34 & 39 & 44 & 49 & 54 \\
\color{red}{32} & 37 & 42 & 47 & 52 & 57 & 62
\end{array}
$$
A: The machine certainly can't make change of 9 cents from 5c and 8c stamps. 
Induction...
Let $k = 5a + 8b$  for any integers $a,b$ including negatives
then $k+1 = 5a + 8b + (16 - 15) = 5(a-3) + 8(b+2) = 5a' + 8b'$
clearly $0 = 5 \cdot 0 + 8 \cdot 0$ and $1 = 5 \cdot -3 + 8 \cdot 2$, so the proof is complete.
Minimal $k$ (and a realistic vending machine) requires both $a$ and $b$ to be non-negative simultaneously. The first time this occurs is when $k=5 \cdot 4 + 8 \cdot 1 = 28$
