Base cases in strong induction

In strong induction, the inductive hypothesis assumes that for all k, P(k) is true. A lot of the proofs I've come across just take this as an assumption.

Why then, in some other cases, is it necessary to provide several base cases instead of just assuming that P(k) is true in each of those base cases?

For instance, the claim, every amount of postage that is at least 12 cents can be made from 4-cent and 5-cent stamps. 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 is often used where there is a recurrence relation, i.e. $a_{n} = a_{n-1}-a_{n-2}$. In this situation, since 2 different steps are needed to work with the given formula, you need to have at least 2 base cases to avoid any holes in your proof. Proving it works for $n=1$ doesn't help since if you try to use the relation for $n=2$ you get an undefined $a_{-1}$ term.

For the example given only normal vanilla “weak” induction is needed. Normal induction does not have to start from zero or 1, but can prove a proposition upward from any integer, for example n! > 2^n for n> 3: assume true then (n+1)! = (n+1).n! > 2.n! (for n > 3) > 2.2^n (by assumption) = 2^n+1. So, if the proposition is true for n (>3) then it is true for n+1. The base case here is n=4 and 24 > 16 so the base case is true, induction applies and the proposition is therefore true for all n > 3.

In your example, induction can easily be used to prove that for n > 14 we can express n as a combination of 4’s and 5’s: assume true then if n contains a 4 in its expression we can change it to a 5 to express n+1; otherwise n is expressed only in 5’s and must contain 3 of them at least, so we can change three 5’s to four 4’s to express n+1. The base case here is 15 which is expressed as exactly three 5’s so the base case is true, induction applies and the proposition is therefore true for n > 14. By examination of individual cases, we can extend the range: 14 = 5 + 5 + 4, 13 = 4 + 4 + 5; 12 = 4 + 4 + 4; 11 is not expressible as a combination of 4’s and 5’s.

So, any number from 12 up is expressible as a combination of 4’s and 5’s where we provide specific proofs for 12, 13, 14, and 15 (the base case) and an inductive proof for anything greater. You could use “strong induction” to prove this but it would come to the same thing. Strong induction can also start from numbers other than zero or 1. Here we need to prove that for all numbers n > 11 if all numbers (> 11) up to n n can be expressed as a combination of 4’s and 5’s then so can n+1. The obvious way to do this is to split the proof for n > 14 and separately for n = 12, 13, 14 and proceed as above.

The favourite example for strong induction is that all integers (> 1) can be expressed as a product of primes. This is true for 2 (base case): suppose true for all integers up to n, then either n + 1 is prime or consists of two factors which are < n and in which case n + 1 is the product of two sets of primes and so always n + 1 can be expressed as a product of primes. This proof actually uses the power of strong induction in factoring n + 1 in to ANY two numbers < n, not just relying on the truth of the proposition for n itself.

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.