There are two competing ideas here, that of induction, and that of asymptotics. Normally, induction requires a base case, but because of the way asymptotics work, the base case will be trivially satisfied, because we can always take $c$ to be large enough to outweigh what happens in the early cases. The fact that they did any base cases at all is purely pedagogical, so as to make things look like induction, but as we shall see the base case is not strictly necessary.
We can phrase what we are trying to prove in terms of induction as follows.
The recurrence $T(n)$ is $O(f(n))$ if there exists constants $c$ and $n_0$ such that $T(n+n_0)<cf(n+n_0)$ for every n>0$.
Here we have phrased things in terms of $n+n_0$ just so that the induction can start at $1$, but there is no harm in replacing $n$ with $n_0$ and starting the induction with $1+n_0$.
Assume $f(n)>0$ for all $n>k$. Since we don't care what $c$ is, if all we are concerned about is making the asymptotic statement true, we can take $n_0$ to be $k$, because we can push all the rest of the slack into our choice of the unspecified constant $c$. It might take many terms before $f$ starts growing as fast as $T$, but $c$ can take care of any finite number of terms before this happens.
For example. if $T(n)=10^{6n}$ for $n<10^6$ and $0$ afterwards, $T(n)$ is $O(1)$. We start with $n_0=1$ and we take $c=10^{10^{10^{10}}}$. Or bigger if we want. We take $c$ to be whatever it needs to be so that the base case is immediately satisfied without any checking. Note that we could take $c=10^6$ if we only cared about the base case, but a larger constant was required to make the statement true despite our poor choice of $n_0$.
Of course, we might still need $n_0$ to be large, because the growth of the sequence might depend on $n$ in such a way that it behaves differently for small $n$, and our choice of $c$ can only take care of the base case. We need $n_0$ to make sure that the induction step still holds. In the above example, if we want induction to hold, we want to take $n_0>10^6$.
Best Answer
Algorithms texts often introduce substitution as a guess and check method. In my opinion, it's just that. As a matter of personal taste, I am not usually all that good about guessing a solution. But I'm much better at using more decisive techniques to reason things out. The two common techniques are the Tree Method and the Unrolling Technique, though these are not the only techniques. For instance, the Master Theorem packages the Tree Method into a black box.
For this example, I'd advise trying the unrolling method. Notice that you have a recurrence of the form $T(n) = T(n-a) + f(n)$. Such recurrences are usually amenable to unrolling and writing down a series.
If the recurrence was of the form $T(n) = aT(n/b) + f(n)$, then you would want to try the tree method, as you have a recurrence tree with $a$ branches at each node and an input of size $n/b$ to each child.
I hope this is helpful.