A nice simple problem with natural inductive 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.