Anders Lundstedt: When must one strengthen one’s induction hypothesis?

Abstract. Sometimes when trying to prove a fact by induction, one gets “stuck” at the induction step. The solution is often to use a “stronger” induction hypothesis. We provide a precise characterization of this phenomenon and show that this characterization applies to a number of natural examples. By reflecting on mathematical practice, we argue that our definition does capture the notion of “proof by strengthened induction hypothesis”. The general problem of when one must, in order to prove a fact X, first prove another fact Y, seems very hard. Interestingly, the special case of proof by strengthened induction hypothesis turns out to be more manageable.

This is joint work with Eric Johannesson (Stockholm university).