Of course my title isn't sufficiently precise (every induction can be started at $n = 0$ by re-indexing), so let me fix that. I'll start with the question, then explain my terminology.
Question: What are some interesting examples of inductions that don't have a degenerate case?
This question was inspired by a recent MO question stated in terms of a parameter $k \ge 1$. My first instinct was that it was really meant to start at $k = 0$, but the identity's not true there! (So I wonder if there is actually a non-obvious degenerate base case ….) However, to avoid inadvertently making this a representation-theory question, I'll work with more familiar examples.
Most books, when introducing induction, shy away from handling the degenerate case, and instead start the induction at the first interesting case. This often results in essentially repeating the argument for the inductive step twice, once to prove the base step from the degenerate case, and once where you'd expect it. I understand why this is done; it's hard enough to get first-time students of induction to handle the "obvious" part of the structure, without also having them worry about vacuities. (If, however, you really like vacuities, you might enjoy an old MO question.) My question isn't about whether or not this is good pedagogical practice. (For that, there's MESE!)
To clarify my terminology, I give the first example that comes to mind. I won't write it out in detail because this isn't a textbook, and I'm trying your patience already.
Theorem: Every $2^n\times2^n$ chessboard with one square removed can be tiled by L-trominoes.
Base case $n = 1$: Removing one square from a $2\times2$ chessboard leaves an L-tromino.
Inductive step: Given a $2^{n + 1}\times2^{n + 1}$ chessboard with one square removed, place an L-tromino so that it covers the central $2\times2$ subboard, except for the quadrant of that subboard that leaves in the same quadrant as the removed square. Each quadrant is now a $2^n\times2^n$ chessboard with one square "removed" (or else covered by our first L-tromino), and so can be tiled.
It's not much work, but we have essentially been forced to make twice the same observation about $2\times2$ boards. If instead we started at the degenerate base case $n = 0$, then we wouldn't be repeating ourselves (and the inductive step would work without change, with the first step serving as the proof of our non-degenerate base case):
Degenerate base case $n = 0$: Removing one square from a $1\times1$ chessboard leaves the empty board, which can vacuously be tiled by L-trominoes.
Again, my question isn't about whether writing the proof this way is better. Rather, it is about interesting examples of inductions that don't have a degenerate base case.
Best Answer
Cool question!
One that comes to mind quickly is proving that the sum of the angles in any polygon with $n$ sides is $180(n-2)$. The base case of triangles isn't necessarily too difficult, but it's different from the inductive step.
While I'm not sure if you would put this in that category, the Chinese remainder theorem also comes to mind. The base case has to be proved on its own, and the inductive step reduces to applying the base case repeatedly.
Also, I've linked a previous question that is similar.
What are some examples of induction where the base case is difficult but the inductive step is trivial?
Hope this helps!