Inductively prove that any natural number $\ge 12$ can be written as the sum of 4s and 5s I can intuitively see why this is true:


*

*Let us assume $n = \alpha \times 4 + \beta \times 5$ with $\alpha,\beta \in \mathbb{N} \cup \{0\}$.

*$\forall n \in \mathbb{N} \cup \{0\}$: $n \div 4$ will yield a remainder $r \in \mathbb{N} \cup \{0\}$, $0 \le r \lt 4$.

*$r$ can be 'split' into 1s, and each of those 1s can be added to one
of the 4s that go into $n$ to turn them into 5s. Therefore, if $n =
    a\times4 + r \Rightarrow n = (a-r)\times4 + r\times5$ with $a \in \mathbb{N}\cup\{0\}$.

*That is the reason why this only works for $n \ge 12=3\times4$: it's readily
obvious by the pigeonhole principle, and if $a \lt 3 \Rightarrow
    \exists \ r \ | \ (a-r) \lt 0 \Rightarrow \alpha \lt 0$ which contradicts the initial assumption.


Could this give me a start for the inductive proof? I don't know if induction would be the most straightforward or elegant way to prove it, but I have to do it as an exercise (my Elementary Number Theory textbook actually suggests proving it individually for $n\in[12,16]$ and then using 16 as $n_0$). I understand how induction works but I can't think of a way to translate this problem into it. I would also like some help with formally expressing step 3 of my proof.
 A: I think your approach could easily be used for induction and is at least as good as the textbook suggestion of multiple base cases (which is also a perfectly adequate proof).
So to build on your ideas, we have:
Base case
$12=4+4+4$
Inductive step
Assume true for $k\ge 12$. Note that we have at least $3$ terms in the decomposition of $k$. We must therefore have either (a) three $5$s or (b) at least one $4$. 
For a $4$-$5$ decomposition of $k+1$: in case (a) substitute four $4$s for the three $5$s in the decomposition of $k$, and in case (b) substitute a $5$ for a $4$.

Note how this links to the ideas in the question: the greatest possible remainder value is $3$ - that's the case that gives three $5$s in the decomposition. The subsequent integer has remainder $0$, giving no $5$s in the decomposition - so the three $5$s will be replaced by four $4$s. The base case is chosen so that there is a valid partition that has (at least) three components. $12$ is the smallest such.

For clarity, the textbook was (I think) expecting that you demonstrate the existence of a valid partitions from $12$ to $15$, and then use induction for $k\ge 16$ with the inductive assumption that there is a solution for $k-4$, and then add another $4$ to that decomposition.
A: $12=4+4+4$
$13=4+4+5$
$14=4+5+5$
$15=5+5+5$
Now, suppose $n>15$; as the inductive hypothesis you can assume that any number $m$ with $12\le m<n$ can be written as sum of fours and fives. Then $n-4>11$ can be written as sum of fours and fives, which implies the thesis also for $n$.

This is indeed a constructive approach: divide $n\ge12$ by $4$, with remainder $r$, that is, $n=4q+r$, with $0\le r<4$. Then $q\ge3$, as $n\ge12$.
If $r=0$ we are done. 
If $r=1$, $n=4(q-1)+5$
If $r=2$, $n=4(q-2)+5+5$
If $r=3$, $n=4(q-3)+5+5+5$
A: Just to see the pattern: $12=4+4+4$. $13=4+4+5$. $14=4+5+5$. $15=5+5+5$. $16=4+4+4+4$.
Base case: $12$. 
Note that $12=4+4+4$.
Inductive case. 
Assume that $n$ can be written as $n=4x+5y$ with $x,y \in \mathbb{N}_0$. 
If $x>0$, then $n=4(x-1)+4+5y$ so $n+1=4(x-1)+5(y+1)$.
If $x=0$, then $n=5y$ so $n+1=5y+1$. Note $y\geq4$ (we handled the case $n=15$). So then $n+1=5(y-3+3)+1=5(y-3)+16=5(y-3)+4+4+4+4$.
A: In general, the Chicken McNugget theorem says that for any coprime integers $p, q$, the largest integer that is not of the form $px + qy$ is $pq - p - q$. So in this case, $11$ is the largest integer which cannot be expressed as so, so every integer $\geq 12$ can.
