Prove by induction: For $n\in{\Bbb N}$ and $n\geq{12}$ there are $a,b\in\Bbb{N}$ such that: $n=4a+5b$.

Question

Prove that for any $n\in{\Bbb N}$ and $n\geq{12}$, there are $a,b\in\Bbb{N}$ such that: $n=4a+5b$.

(I'm trying to resolve it without using strong induction and 4 base cases)

My try Proof by induction:

---

Base case: For $n=12$, we will choose $a=3,b=0$ then: $12=4\cdot3+5\cdot 0.$

Inductive step:

Assuming that the statement holds for some $n\geq12, n\in\Bbb{N}$ such there are $a_0,b_0\in{N}$ such that $n=4\cdot{a_0}+5\cdot{b_0},$ we will prove it for $n+1$, $n+1=4\cdot{a}+5\cdot{b}$.

Split cases to $a_0\gt 0$ or $a_0=0$.

If $a_0\gt 0:$ then we will choose $a,b$ this way: $a=a_0-1,b=b_0+1$. Then: $$4\cdot{a}+5\cdot{b}=4(a_0-1)+5(b_0+1)=4\cdot{a_0}-4+5\cdot{b_0}+5=4\cdot{a_0}+5\cdot{b_0}+1=n+1$.$$

If $a_0=0$:

Any idea how could I continue ?

Thanks !

Answer 1

Make the inductive claim be that $\exists a,b \mid a+b \geq 3 \land n = 4a+5b$. If $a>0$, decrease a by one and increase b by one to increase n by one, whilst $a+b$ remains unchanged. If $a=0$, then $b \geq 3$, so decrease b by three and increase a by four, increasing n by one, while $a+b$ does not decrease.

Answer 2

Use strong induction. Start with.
12 = 4×3; 13 = 4×2 + 5; 14 = 4 + 5×2: 15 = 5×3.
For n >= 15, let k = n mod 4 (0 <= k < 4).
By strong induction hypothesis, n - k = 4a + 5b for some a,b >= 0.
Thus n = 4(a + 1) + 5b.