Here's a small example from the book Concrete Mathematics:
p. 78: Let $K_0=1$ and $K_{n+1}=1+\min(2 K_{\lfloor n/2 \rfloor}, 3 K_{\lfloor n/3 \rfloor})$ for $n\ge 0$. ("One of the authors of this book has modestly decided to call these the Knuth numbers.")
p. 97, exercise 3.25: Prove or disprove that the Knuth numbers satisfy $K_n \ge n$ for $n\ge 0$.
Induction fails when trying to prove $K_n \ge n$ directly (as explained in the text on p. 79), but works easily for the stronger statement $K_n > n$.
