After two days of contemplating, I believe that I've finally realized why strong induction doesn't require a base case as in regular induction. However, there's something I'd like to ask. To make it easier for discussion, let me restate the Principle of Strong Induction below (In my analysis that follows, $k$ and $n$ will be used exactly as they are in this principle):
$\textit{Suppose that $P(n)$ is a statement about n $\in$ S (S $\subseteq$ $\mathbb{N}$):}$
$\textit{If for every n $\in$ S,}$
$$\textit{P(k) holds for all k < n $\implies$ P(n) holds,} \quad(*)$$
$\textit{then P(n) holds for all n $\in$ S.}$
As I revisited some past examples, I realized that despite the theoretical non-necessity of a base case in the proof, we always seem to need to check a few special cases in practice. The proof doesn't require a base case if $(*)$ is true. However, to prove that $P(n)$ holds, we always seem to need to use $P(k)$ in our argument, but $P(k)$ being true cannot be obtained for some $n$ ($k <n$) or some choice of $k$.
$P(k)$ is a statement about an arbitrary element $k$, if any, in $S$, but no such $k$ exists if $n$ is the smallest value in $S$, or the set $\{x \in S: x < n\}$ is non-empty but the choice of $k$ needed in our proof falls outside of $S$ (E.g., $S =\{x \in \mathbb{N}: x \ge 15\}$, $n = 15$, $k = n - 3$).
Consequently in these situations, we could not obtain $P(k)$ being true to prove that $P(n)$ holds. So in practice, it seems we always have to partition $S$ into two subsets, one where we could obtain a choice of $k \in S$ needed to prove $P(n)$, and the rest whose elements we need to check separately.
I was wondering if there exists any statement in which we could prove $(*)$ for all $n \in S$. That is, we don't need to separately check for some cases of $n$ to 'bridge the gap'.
Thank you!
Additional comment: Since there was no answer yet, I'd like to share some of my thoughts after posting: If $P(k)$ is required in the proof for $P(n)$, then the set $A = \{x \in S: x < n\}$ must be non-empty, and $k$ must be an element of $A$ so that $P(k)$ could be obtained via assumption. However, $A \subseteq S \subseteq \mathbb{N}$, so $A$ must contain the smallest element in $S$, which implies that $n$ must be at least the second smallest in $S$ for $A$ to be non-empty. This means that we must always have to check if $P(n)$ holds for the smallest element in $S$ separately at the minimum.
In this way, a statement that allows us to prove $(*)$ without checking separate cases would essentially allow us to prove $P(n)$ without using $P(k)$ (because using $P(k)$ implies checking at least one separate case). However, that would render the use of induction irrelevant as such would be a direct proof.
I wondered if this analysis is any way correct. Please advise!
You need to show: If p(k) holds for all k < n, then it holds for n. Now take n = 0. There is no k < 0 so p(k) holds for all k<n, whatever p is.
So you have to show: if True then p(0). In other words you have to show p(0) without the help that you would get from induction for larger n.