# Strong mathematical induction to prove $n=4x+5y$

Use the principle of strong mathematical induction to prove that if $n\in\mathbb N, n\geq12$ , then there exist non-negative integers $x$ and $y$ such that $n=4x+5y$.

-
I suggest this should be closed as a duplicate. All you have to do is search for "postage stamp". –  Rick Decker Nov 15 '12 at 15:47

Start with $13 = 4\cdot2+5\cdot1, 14 = 4\cdot1+5\cdot2,15 = 4\cdot0+5\cdot3,16 = 4\cdot6+5\cdot0$ as your base case. For the inductive step, let $n$ be a natural number greater than $16$ and assume that all numbers $13\le k < n$ may be written as $k=4x+5y$ for nonnegative $x, y$. Then by the inductive hypothesis $n-4$ can be written as $4a+5b$ and so $n=4(a+1)+5b$, thus showing that $n$ can be expressed in the desired form. Done.
Let's suppopse $n=4x+5y$, then we have $$n+1=4(x-1)+5(y+1) = 4(x+4)+5(y-3)$$ The only problematic case for these is when both $x<1$ and $y<3$, i.e. for $n\le 10$.
Start: $12=3\cdot 4+0\cdot 5$.