I've posted here before my experience last spring co-teaching a discrete math for teachers course (the instructor of record being a mathematician has published a discrete math text and research articles in the field). He decided about four weeks or so into the course to teach mathematical induction (with a few standard examples of the sums of the first n integers, first n squares, etc.). The students appeared almost without exception to be hopelessly confused both as to the method and the concept they were being shown (and though this mathematician generally teaches a lot by what he believes to be a guided discovery approach) in this case he was pretty straightforward with the class, but as I've said, to no apparent avail).
Eventually, I introduced the "Gauss Trick" as a way to help see it from another viewpoint, and to help increase their "belief" in the formula. I was successful with these limited goals, but that was as far as it went: they still found induction a mystery. My colleague became increasingly frustrated, as did the students. Few did at all well on the midterm, and particularly they bombed on induction. This led to some things of interest only to those who care about pedagogy, so I'll save it for my memoirs. But the relevant point here is, rather, a question:
For those who believe that the principal of induction is an important (indeed, vital) mathematical tool (or technique, method, concept, etc.): any thoughts on how to better get folks who aren't mathematicians or future mathematicians to "get" it? (And trust me, we looked at the domino metaphor and my colleague and I probably waltzed around this in a variety of other ways. No dice.)
Any suggestions other than what boils down to "louder and slower" would be appreciated. :)