I just finished teaching a class on using proof assistants (in this case, Agda) to write provably correct programs. Reflecting on how it went, the biggest difficulty I noticed the students having was that they had a lot of trouble working out how to generalize the induction hypothesis. They were generally able to work out how to prove theorems by induction (even with numerous quantifiers in the statement), as long as they didn't have to generalize the hypothesis.

This is obviously one of the key skills underpinning "mathematical maturity", but it's also not a skill I feel I have good handle on how to teach. My current idea is to come up with a list of exercises where they have to work out a generalization, but I'd really also like to be able to explain some of the strategies they should use, and I'm having trouble putting that into words.

So my question is twofold:

  1. Suggest some of your favorite small examples where the proof requires a generalization. (It doesn't have to be a nontrivial generalization -- it just needs to be a generalization! Also, I want to do this in a proof assistant, so sticking with basic properties of basic algebraic structures is helpful.)

  2. How do you explain how to recognize when to generalize, and how do you explain how you should generalize the induction hypothesis?

  • 2
    $\begingroup$ Community Wiki ? $\endgroup$ – Hachino Apr 24 '15 at 9:38
  • 5
    $\begingroup$ This would be better at matheducators.stackexchange.com $\endgroup$ – Neil Strickland Apr 24 '15 at 10:00
  • $\begingroup$ Since you write "provably correct programs", is someone teaching "provably correct CPU"? Last time I checked the CPU errata of the major CPU vendors there were a lot of "issues". $\endgroup$ – joro Apr 24 '15 at 11:46
  • 1
    $\begingroup$ 1) When you write, "generalization", do you mean, "strengthening"? 2) Since you have noticed students have trouble doing it, you must know some examples, yourself. Why not start us off with the ones you know --- that will both clarify your meaning, and save all of us the effort of telling you things you already know. $\endgroup$ – Gerry Myerson Apr 24 '15 at 12:50
  • 2
    $\begingroup$ I asked the following related question mathoverflow.net/questions/31699/… $\endgroup$ – Tony Huynh Apr 24 '15 at 21:53

The following observation about your question 2 might be too obvious, but one simple way to recognize when you need to strengthen the induction hypothesis is to notice that when you try to prove your theorem by induction, you can't quite seem to derive the $n$th case by assuming the $(n-1)$st case; it seems that you need something a bit stronger than the $(n-1)$st case, that you don't know how to prove. So, articulate exactly what that stronger statement is, and see if you can prove that by induction instead.


Not the answer you're looking for? Browse other questions tagged or ask your own question.