I did enough math at college that complex data structures and algorithms were not at all scary. Recursion just reminded me of the infinite descending spiral of the ideals in Noetherian rings :) And working through the proofs of the equivalence of a dozen different versions of the axiom of choice helped me learn to reason about my programs. Never used more than a trivial amount of the math content, but the math processes of thought have been invaluable.
Recursion has always been my favorite example of how learning math helps understand programming. If you've ever proven something by induction, you should have no problem understanding recursion.
Honestly, I think most people who "prove" things using induction don't really understand what they're doing. Then again, most people don't really understand recursion either.
This sounds more like a case of people not understanding what proving by induction is (and as a consequence, not doing so) rather than them proving by induction and and not understanding what they are doing.
In my experience, most people who go through math classes at a University, not to mention classes in High School, are mostly "blindly" following a template of how to do induction. They don't really understand the principle behind it, why it's a valid proof technique, etc. Put another way, if I used induction incorrectly, I could probably still trick them into thinking it's a valid proof because it looks like induction.
The same goes for a lot of things in Mathematics. The same also goes for recursion - most people don't really understand recursion (unless it's used at a "simple" level, like in Tree Recursion).
