A nice simple problem with natural inductive structure
is the [tower of Hanoi problem.] [1] It is not obvious that any solution exists, and it is hard to come up with one explicitly, until you *assume* that it is possible to move the top $n-1$ disks, after which it is obvious how to move $n$ disks.

There is in fact a "noninductive" solution, but since it takes $2^n-1$ steps, it is preferable not to think about it.

[Added later] Of course, there is really no such thing as a "noninductive" theorem about natural numbers because of the inductive structure of natural numbers themselves. However, the "right" induction in this case exponentially compresses the solution, by suppressing unnecessary details.



[1]:http://en.wikipedia.org/wiki/Tower_of_Hanoi