Frobenius coin problem induction help I need some help with the actual Induction proof of a Frobenius coin problem. This is the exact problem: 
The government of Elbonia has decided to issue currency only in 5 and 9 cent denominations. Prove that there is largest value that Elbonians cannot pay with this denomination
And a later question says to prove that all values over this found value is payable with 5 and 9 cent coins.
First of all, I've found the largest value that can't be paid is 31 cents. I've found this by just writing out the combinations of coins until I got 5 in a row, and then each of those numbers can just have 5 added to them to continue forever, starting at 32. However I'm not sure if that could be considered "proof" and if I need to show this in a more official way.
I've started on the induction proof anyway, but I'm having some trouble as where to go. I know to prove this I need to show that for S(n): where n is the amount payable with 5 or 9 cent pieces, show that 
S(n) -> S(n+5),
S(n+1) -> S(n+6),
S(n+2) -> S(n+7),
S(n+3) -> S(n+8),
S(n+4)-> S(n+9),
So for my base case I've let n=32, and shown that 
32 = 3(9) + 3(5),
33= 2(9) + 3(5),
34 = 1(9) + 5(5),
35 = 7(5),
36 = 4(9)
So I've shown my base cases can be paid with 5 and 9 cent pieces, but now I'm stuck. What exactly do I assume for my inductive assumption? That S(k), s(k+1).. etc is true for some kEZ? Normally when we are given induction questions for the inductive step there is a way to rearrange it to make your assumption show up somewhere to help you prove it, but I can't see how to do that for the inductive step here.
Any help on this would be awesome, sorry for the long question! Thanks!
 A: You are all set. From your base cases (32 to 36) you can add 5 to each to get the next stretch of 5 (37 to 41), and from them the next one (42 to 46), and...
To make it formal:
Bases: As you did show, 32 to 36 are all possible.
Induction: Asuming all between $32$ and $n \ge 32$ are representable,
$n + 1$ is representable. If $n \le 36$, $n + 1$ is part of the base. Otherwise it is just adding a 5 coin to $n + 1 - 5 = n - 4 > 32$, which is representable by induction hypothesis.
A: Let $a$ and $b$ both be greater than or equal to $2$ and coprime.
Let
$\quad S = \{n \in \Bbb N \mid (\forall \, x,y \in \Bbb N)\; n \ne xa + yb \}$
Clearly $S$ is a nonempty set and it is the complement of integers with a Frobenius coin solution.
The OP is seeking a proof that $S$ is a finite set and we'll address that now.
It is easy to see that if Frobenius solutions can be found for an interval segment of integers of length, say $a$, starting at $s$ then
$\quad S \subset \complement \, [s,+\infty)$
and the argument that $S$ is finite would be complete.
Lemma: Let $s = (a-1)\cdot b$. Then Frobenius solutions exist on the interval $[s,s+a-1]$.
Proof Sketch
If $0 \le k \lt a-1$, consider the expression
$\quad k + (z)b   \quad \text{where } z = a - 1$
and, in order to 're-balance the accounting books', set $y = z - u$ so that
$\quad k + (z)b = k + bu + (y)b$
and consider
$\tag 1 k + bu \equiv 0 \pmod{a} \; \text{ iff } \; bu \equiv -k \pmod{a}$
Recall that there is one and only one solution of $\text{(1)}$ for $[u]$.
So it must be possible to write
$\quad s + k = (x)a+ (y)b, \text{ with } x,y \in \Bbb N$
In fact, there is exactly one such representation for $s+k$ (see also this). $\quad \blacksquare$
So the Frobenius number is indeed well-defined and is equal to the largest number in the set $S$.

Applying the above theory to the OP's specific problem we'll find the exact solutions on the interval
$\quad [(5-1)\cdot9,(5-1)\cdot9 + 5-1] = [36, 40]$
Due to the bijective correspondence, it is simplest to 'borrow and fit':
$\quad \text{Borrow } 0: \quad \quad\quad\quad\quad\quad\quad\quad\quad\;\, 36 = (0)5 + (4)9$
$\quad \text{Borrow } 1: \quad 36 = 9 + (3)9 \;\;\;\, \text{ iff } \; 37 = (2)5 + (3)9$
$\quad \text{Borrow } 2: \quad 36 = 18 + (2)9 \; \ \text{ iff } \; 38 = (4)5 + (2)9$
$\quad \text{Borrow } 3: \quad 36 = 27 + (1)9 \;\, \text{ iff } \; 39 = (6)5 + (1)9$
$\quad \text{Borrow } 4: \quad 36 = 36 + (0)9 \;\, \text{ iff } \; 40 = (8)5 + (0)9$
