Why is it necessary to show the base cases up to 16 cents rather than just starting at P(k=16) and saying suppose 12 <= k is all true?
Strong induction doesn't allow you to start from some predefined position like $k=16$. All it says that to prove $\forall n (P(n))$, you have to do: $\forall n (\forall k < n (P(k)) \implies P(n))$.
Now to see why we need to show the base cases, let's try to prove it without base cases:
Let $n >= 12$ be an arbitrary element. Suppose $\forall k( 12 <= k < n)$, there exists $a$ and $b$ such that $k = 4a + 5b$. Since $n - 4 < n$, it follows that
$n - 4 = 4 a + 5 b$ from inductive hypothesis. So, $n = 4(a + 1) + 5b$. Let $a + 1 = a'$, So, $\exists a' \exists b (n = 4a' + b)$. Since $n$ was arbitrary, it follows that $\forall n >= 12 \exists a \exists b. (n = 4a + 5b)$.
Everything looks right, does it ? NO
In the above proof you can observe the line which involves expression $n - 4 < n$. Now note that $n$ can be any arbitrary number $>=12$. So, if $n = 12$, $n-4 = 8$. But the inductive hypothesis doesn't hold when $n=8$. Note that while the inductive hypothesis is vacuously true, you cannot do the substitution of $k = 4a + 5b$ as done in the above proof. So how to solve it ?
You have to change your problem statement to this:
- Prove for n=12,13,14,15
- $\forall n >= 16 \exists a \exists b. (n = 4a + 5b)$
$\forall n >= 16 \exists a \exists b. (n = 4a + 5b)$ can be proved using strong induction.