1)Proof of Euler's formula, V-E+F=2, with induction on F (number of faces). Induction proof of the same formula using number edges as induction variable has a much simpler base case.
2)Backward induction proof of generalized AM-GM inequality.
3)Proof of Heine-Borel theorem using Transfinite Topological induction.
ADDED LATER: The Maximum Sum Contiguous Subsequence Problem is another interesting one. The problem of determining such a sequence becomes very cumbersome with naive inductionon the length of the sequence. But, strengthening the induction hypothesis with suffix sequence makes the problem almost trivial to solve.
