My example is the classical proof that sqrt(2) is irrational.
More generally, many proofs that proceed by showing that there are no minimal counterexamples exemplify your phenomenon. (This The method is, of course, equivalent to no-minimal-counterexamples is exactly the same as strong inductionand to the well-order principle.) Often, with but where one proves the no-minimal-counterexample required implication by contradiction. In many applications of this method, it is often clear that the smallest numbers are not counterexamples, and this would not ordinarily regarded as a separate base "case".
In the classical proof that sqrt(2) is irrationalis essentially like this. Suppose , for example, we suppose sqrt(2) = p/q, where p is minimal. Now, square both sides and proceed with the usual argument, to arrive at a smaller counterexample. Contradiction! This amounts to a proof by strong induction that no rational number squares to 2, and there seems to be no separate base case here.
People often carry out the classical argument by assuming p/q is in lowest terms, but the argument I just described does not need this extra complication. Also, in any case, the proof that every rational number can indeed be put into lowest terms is itself another instance of the phenomenon. Namely, if p/q is a counterexample with p minimal, then if you're not already done, divide by any common factor and apply induction. Does the There seems to be no separate base case when here where it is already in lowest termsconstitute a separate base "case"? To my mind, no, but perhaps you object to thissince we were considering a minimal counterexample. Perhaps someone else objects that there is no induction here at all, since one can just divide by the gcd(p,q). But the usual proof that any two numbers have a gcd is, of course, also inductive. The standard proof using : considering the least linear combination xq+yp amounts to strong inductionagain, again with no separate base case.