Inductively prove that any natural number $\ge 12$ can be written as the sum of 4s and 5s

Question

I can intuitively see why this is true:

1. Let us assume $n = \alpha \times 4 + \beta \times 5$ with $\alpha,\beta \in \mathbb{N} \cup \{0\}$.
2. $\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$.
3. $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\}$.
4. 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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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