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

Question

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$.

Answer 1

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.

Answer 2

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$.