The first time I worked through Cauchy's proof of the AM-GM inequality I had to stop myself from shouting out loud: THIS IS OUTRAGEOUS! Less time consuming I don't know, but easier (in the sense of more intuitive) for me, yes.
I first came across the problem in Spivak's excellent book Calculus (Chapter 2, Problem 22.)
Theorem
Let $a_{1},\ldots,a_{n}$ be a set of real numbers such that $a_{i}\geq 0$ for each $i.$
Define
$$ \begin{align*}
A_{n} & = \frac{a_{1} + \ldots + a_{n}}{n} \\
G_{n} & = \left[a_{1}\ldots a_{n}\right]^{\frac{1}{n}}
\end{align*} $$
Then $A_{n} \geq G_{n}.$
Proof
We use induction on the set of integers $2^{k}$ for $k \in \mathbb{N}.$
For the case $k=1,$ we need to show $\frac{a_{1}+a_{2}}{2} \geq \sqrt{a_{1}a_{2}},$ which is done by considering the fact that $(\sqrt{a_{1}}-\sqrt{a_{2}})^{2} \geq 0.$
Assume the proposition holds for $2^{k}.$ For $2^{k+1}$ we have
$$ \begin{align*}
A_{2^{k+1}} & = \frac{a_{1} + \ldots + a_{2^{k}} + a_{2^{k}+1} + \ldots + a_{2^{k+1}}}{2^{k+1}} \\
& = \frac{1}{2} \left[ \frac{a_{1} + \ldots + a_{2^{k}} } {2^{k}} + \frac{ a_{2^{k}+1} + \ldots + a_{2^{k+1}}}{2^{k}} \right] \\
& = \frac{1}{2}\left[ A + B \right] \\
& \geq \sqrt{AB} \\
& \geq [(a_{1}\ldots a_{2^{k}})^{\frac{1}{2^{k}}}( a_{2^{k}+1}\ldots a_{2^{k+1}})^{\frac{1}{2^{k}}}]^{\frac{1}{2}} & \text{(by inductive hypothesis)}\\
& = G_{2^{k+1}}
\end{align*}$$
(Note we have even used the base step here!)
Now we go back and think about general $n.$ Let $m$ be defined so that $2^{m} > n$ and let $a_{n+1}=\ldots=a_{2^{m}} = A_{n}.$ Then $$
A_{2^{m}} = \frac{a_{1} + \ldots + a_{n} + (2^{m}-n)A_{n}}{2^{m}} = A_{n}
$$
so that
$$
(A_{n})^{2^{m}} \geq a_{1}\ldots a_{n}(A_{n})^{2^{m}-n}
$$
and rearranging easily proves the theorem.
There are certainly a few details missing here which you would have to fill out, and perhaps this article is a bit clearer (a less slick proof), but the proof can definitely be broken down so that undergraduates can work through it as an exercise in several steps.
Edit: The reason I find this proof so appealing is that the step $P(2^{k}) \Rightarrow P(2^{k+1})$ is really reduced to basic algebra, whereas $P(n) \Rightarrow P(n+1)$ requires more lemmas. My conceptual focus when reading this proof is on the idea of using a different induction step and how this simplifies the argument so much. In this sense, I find Cauchy's proof easier and more understandable even if it is not faster than others.
