Exercise 1032Logic, sets and proofs › Proof techniques › InductionL1Added 3 Nov 2026

Coins and strong induction

#induction#coins#Frobenius

Statement

Prove that every integer $n\ge12$ can be written as $4a+5b$ with $a,b\ge0$ .

Hint

Strong induction, starting with four consecutive integers $12,13,14,15$ as base cases.

Show solutionHide solution

Solution

Base cases.
- $12=4\cdot3+5\cdot0$
- $13=4\cdot2+5\cdot1$
- $14=4\cdot1+5\cdot2$
- $15=4\cdot0+5\cdot3$

Inductive step. If $n\ge16$ is representable, then $n+4$ is too (add another $4$ ). Starting from the four base cases, this covers all integers $\ge12$ .

Conclusion. Every integer $\ge12$ is representable.

Coins and strong induction

Statement

Solution

More problems in Induction