It is proved that every amount \(n\ge12\) can be made with stamps of \(4\) and \(5\), going from \(n-4\) to \(n\). How many base cases must be checked?
The step uses \(n-4\ge12\), i.e. \(n\ge16\). The values \(12,13,14,15\) remain uncovered (\(3\cdot4\), \(2\cdot4+5\), \(4+2\cdot5\), \(3\cdot5\)), and those are the four base cases.
Strong induction proves \(P(n)\) for every \(n\ge n_0\): after checking the base case \(P(n_0)\), one proves \(P(k+1)\) assuming \(P(j)\) for all \(j\) with \(n_0\le j\le k\).