What affects the number of base cases that I need to prove when using strong induction?

Question

Below are two particular problems to illustrate the question in the title.

Problem 1

Given a sequence $\large a_1=1, a_2=2, ..., a_n= a_{n-1}+a_{n-2}$ prove that for all $n\in Z^+$, $a_n\le\bigg(\dfrac 7 4\bigg)^n$.

My solution. With $n=1$ and $n=2$ as base cases and $S(n)$ as the statement in question, assume the truth of $S(n_0),...,S(k)$ for some $k\ge2$. Then for $S(k+1)$: $$\large \begin{align*} a_{k+1}=a_k+a_{k-1} &< \bigg(\dfrac 7 4 \bigg)^k+ \bigg(\dfrac 7 4\bigg)^{k-1}\\ & =\bigg(\dfrac 7 4 +1\bigg) \bigg(\dfrac 7 4\bigg)^{k-1}\\ &=\bigg(\dfrac {11} 4\bigg) \bigg(\dfrac 7 4\bigg)^{k-1}\\ &=\bigg(\dfrac {44} {16}\bigg) \bigg(\dfrac 7 4\bigg)^{k-1}\\&< \bigg(\dfrac {49} {16}\bigg) \bigg(\dfrac 7 4\bigg)^{k-1} \\ &=\bigg(\dfrac 7 4\bigg)^2 \bigg(\dfrac 7 4\bigg)^{k-1}\\ &= \bigg(\dfrac 7 4\bigg)^{k+1} \end{align*}$$ Consequently, the statement is proved for all $n\in Z^+$ by the principle of strong mathematical induction.

Problem 2

Show that for all $n\in Z^+$ if $n\ge24$, then $n$ might be written as the sum of $5$'s and/or $7$'s.

Solution from my book.

$24=7+7+5+5, \\25=5+5+5+5+5, \\26=7+7+7+5, \\27=5+5+5+5+7, \\28=7+7+7+7$.

Assume the truth of $S(24),...S(k)$ for some $k\in Z^+, k\ge28$. When $n=k+1$, then $n\ge29$ and we may write $k+1=k-4+5$.

Consequently, the statement is true for all $n\in Z^+$ if $n\ge24$.

Question

I thought that when using strong induction I had to prove as many base cases, as many statements are needed to show the truth of S(k+1). That is, in problem 1 to show the truth of $S(k+1)$ we use $S(k)$ and $S(k-1)$, so we prove two base cases, and in problem 2 we need $S(k-4)$ to be true, and that's why we must prove 5 base cases. Do I argue correctly?

I've just asked AI bot about this and it answered that in general, we should prove just one or two base cases regardless of the nature of the problem. It also stated that in the second problem, one base case is enough, but before this, it had tried to persuade me that $26$ cannot be written as the sum of $7$'s and/or $5$'s and the statement is incorrect, so I do not trust it much.

Answer 1

Considering your solution to problem 2 at face value, I see you used $S(k-4)$ without mentioning $S(k)$, $S(k-1)$, $S(k-2)$, or $S(k-3)$, so it's unclear what you mean by "as many base cases, as many statements are needed to show the truth of $S(k+1)$."

In fact, in problem $2$ you really are using only one base case each time you prove $S(k+1)$ for any particular $k$. For example, consider $k = 1056$. Then $S(k+1) = S(1057)$, which is true because $S(1052)$, which is true because $S(1047)$, which is true because $S(1042)$, and so forth all the way back to the base case $S(27)$.

In other words, in order to establish $S(n)$ for $n=1057$ and a lot of other numbers, we just need to prove this:

Show that for all $n\in Z^+$ then $5n + 22$ might be written as the sum of $5$'s and/or $7$'s.

The proof only needs only the base case $n=1$, shown by $27 = 5 + 5 + 5 + 7,$ and the case $k+1$ follows from case $k$ by adding $5$ to $5k + 22.$ Then the statement $S(1057)$ is proved by setting $n = 206.$

Note that this particular proof used only weak induction. It does not need strong induction. But it does not prove $S(n)$ for all $n \geq 24$, only for some of those integers.

The reason you need five base cases is that each one covers a different subset of the integers $n \geq 24$: the base case $n=24$ covers $n = 29, 34, 39, 44, \ldots,$ the base case $n=25$ covers $n = 30, 35, 40, 45, \ldots,$ the base case $n=26$ covers $n = 31, 36, 41, 46, \ldots,$ the base case $n=27$ covers $n = 32, 37, 42, 47, \ldots,$ and the base case $n=28$ covers $n = 33, 38, 43, 48, \ldots.$

The reason strong induction is so convenient here is that it handles all the inductive steps at once (you don't require five separate weak inductive proofs), and it also saves some trouble showing that the five different sequences of numbers starting at each base case actually cover all of the integers $n \geq 24$.

So you're correct in the sense that in order to prove $S(k+1)$ all the times you want to prove $S(k+1)$ you need five base-case statements, but in any particular inductive step only one base-case statement was used. This makes the rule tricky to use in practice. If you use just $S(k-4)$, is that one base case or five? If the proof of some other proposition uses $S(k-5)$ and $S(k-2)$ to prove $S(k+1)$, do you need two base cases, or do you need six?

But it gets worse. Consider Example 7 from these course notes:

Every positive integer $n$ can be written as a sum of distinct nonnegative integer powers of $2$.

In those course notes, to prove $S(k+1)$ in the inductive step, the proof uses $S(k + 1 - 2^\ell)$, where $\ell$ is the greatest integer such that $2^\ell \leq k + 1$. Noticing that $2^\ell$ can be arbitrarily large, do we need just one base case, or do we need an arbitrarily large number of base cases?

An arbitrarily large number of base cases would require us to have proved the statement before we even start. Fortunately, only one base case is needed.

---

The way I would decide how many base cases I need is to ask how many values of $n$ there are for which we must prove that $S(n)$ is true but cannot show $S(n)$ in the inductive step; that is, it does not work to assume $k = n-1$ and then use the inductive step to prove $S(k+1)$.

For your Problem 2, because the inductive step requires $S(k - 4)$ to prove $S(k+1)$, if our first base case is $n=24$ then our first inductive step can only prove $S(k+1)$ when $k-4 = 24,$ that is, when $k+1 = 29$. The statements $S(25)$, $S(26)$, $S(27)$, and $S(28)$ cannot be proved by an inductive step, so we must establish them as base cases.

---

I also feel obliged to say that I don't consider the first two problems good examples of strong induction, because they are really easy to prove by weak induction. The trick to use weak induction for those proofs is to prove an apparently stronger statement. For example, for Problem 2, we can prove the following:

For all $n \in Z^+$, if $n\geq24$ then each of the numbers $n$, $n+1$, $n+2$, $n+3$, and $n+4$ can be written as the sum of $5$s and/or $7$s.

Then in the inductive step we have $S(k)$, which says that $k$, $k+1$, $k+2$, $k+3$, and $k+4$ can be written as sums of $5$s and/or $7$s, and we have to prove $S(k+1)$, which says that $k+1$, $k+2$, $k+3$, $k+4$, and $k+5$ can be written as sums of $5$s and/or $7$s. $S(k)$ tells us we can write $k+1$, $k+2$, $k+3$, and $k+4$ as sums of $5$s and/or $7$s, so we just need to show how to write $k+5$, and we do that by writing $k$ as a sum of $5$s and/or $7$s (using that part of $S(k)$) and add $5$.

Note that in this proof we have only one base case, but it has five parts, and those five parts are the five base cases of the strong induction.

Where strong induction really proves its worth, in my opinion, is in the proofs of propositions such as the one about sums of powers of $2$, where we cannot just use a fixed number of facts related to $k$ in order to prove the corresponding facts about $k+1$ in the inductive step. For Problem 1 and Problem 2, strong induction is useful, but it just saves a little inconvenience in keeping track of multiple statements within $S(k)$ and $S(k+1)$ in the inductive step.