4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Community Wiki ? $\endgroup$
    – Hachino
    Commented Apr 24, 2015 at 9:38
  • 5
    $\begingroup$ This would be better at matheducators.stackexchange.com $\endgroup$
    – Neil Strickland
    Commented Apr 24, 2015 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
    Commented Apr 24, 2015 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
    Commented Apr 24, 2015 at 12:50
  • 2
    $\begingroup$ I asked the following related question mathoverflow.net/questions/31699/… $\endgroup$
    – Tony Huynh
    Commented Apr 24, 2015 at 21:53

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .