Cauchy's proof by induction of the inequality between the arithmetic and geometric means (written in his 1821 Cours d'Analyse).
Of course, the base of the induction, for $n=2$, immediately comes from $(x_1+x_2)^2\ge0$$(\sqrt x_1-\sqrt x_2)^2\ge0$, but then, although it is actually possible to follow the natural induction steps, making the inequality $M_G\le M_A$ for $n+1$ nonnegative real numbers follow from the inequality for $n$ numbers, it appears that the other implication is much easier: actually, the inequality for $n$ numbers can be easily seen as a particular case of the inequality for $n+1$ numbers. (For $n$ numbers, just addappend to them their arithmetic meansmean as aan (n+1)$(n+1)$-th number, use the inequality for $n+1$ numbers, and simplify). Also, the inequality for $2n$ numbers easily follows from the inequalities resp. for $2$ and for $n$ numbers. As a consequence, we have an induction proof that follows a funny jumping path along natural numbers (if you like to see it this way; that's not exactly Cauchy's description): $(2)\Rightarrow (4)\Rightarrow (3)\Rightarrow (6)\Rightarrow (5)\Rightarrow (10)\Rightarrow (9)\Rightarrow(8) \Rightarrow(7) \Rightarrow (14)\Rightarrow \dots$