Cauchy induction: are there examples of cases where choosing an integer other than $2$ is a better strategy?

To answer this question somewhat more generally than posed; there is a completely bizarre backwards induction proof for the Fundamental Theorem of Calculus, due to Laplace (see, for example, p. 120 in this book).

The proof shows that $P(\frac{n(n-1)}{2}) \Rightarrow P(n)$, where $P(n)$ is the statement "Any degree $n$ polynomial with real coefficients has a complex root." This requires proving $P(n)$ for all odd $n$ as the base case; fortunately, when $n$ is odd, we know that we can find a real root by the Intermediate Value Theorem.

To show that all $P(n)$ follow from these base cases and the inductive step $P(\frac{n(n-1)}{2}) \Rightarrow P(n)$, observe that, if $n$ is even and $2^k$ is the highest power of $2$ that divides $n$, then $2^{k-1}$ is the highest power of $2$ that divides $\frac{n(n-1)}{2}$.

(The actual proof of the inductive step is a somewhat unenlightening bit of algebra that can be read from the Google Books link, so I'll skip it. The induction is the cool part.)