I’m teaching Discrete Mathematics this semester. It is our “intro to proofs” class. One of the proof techniques the students learn is proof by induction. I told the class that usually the base case for induction proofs are easy and that most of the work occurs in the inductive step. Indeed, most of the proofs that they see have base cases that are elementary to check (performing elementary calculations to conclude that 1=1, for instance). I warned them that this was not always the case. Sometimes the base case is the most difficult part of the induction proof.

I spent a while thinking about an example I could show them where this is the case. I found this Math Overflow link on this same question. They gave a few examples. Here’s one of them—the multi-function product rule for derivatives. The base case requires using the definitions of continuity and differentiability and the theorem that every function differentiable at a point is continuous at the point. It is not a simple “1=1” base case. The inductive step is much easier, although it is still not totally trivial because it requires using both the base case and the inductive hypothesis.

Theorem. Let be functions that are differentiable at some point . Then

Proof. This is a proof by induction on Let be the statement that given differentiable functions it follows that

Base case: Let and be differentiable at Recall that because is differentiable at it is continuous at Then

The penultimate equality follows from the continuity of at and the final inequality follows from the differentiability of and   at Thus holds.

Inductive step. Suppose holds for some integer  Let be functions that are differentiable at some point . Then  By the base case, this equals By the inductive assumption, this equals

Thus, holds.

It follows that holds for all #

If you have another example—especially one that would be suitable for into-to-proof students (who don’t have an extensive math background)—post them in the comments.