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.