At the end of last term, my colleague Konstantin Ardakov took the final week of lectures in Mathematical Structures so I could go to Lisbon. This week, I am repaying the debt. The module is Introduction to Algebra; many of the students already took Structures but there is a sizeable contingent of second-years who didn’t, so I am going over some of the material again.
This morning I talked about proving implications, and started on induction. Having the two topics in the same lecture, I noticed a small but maybe important pedagogical point.
First, I offered the students three different ways to prove the implication P ⇒ Q:
- Assume P, and prove Q.
- Use contradiction: assume that P is true and Q is false and reach an impossible situation.
- Prove the contrapositive (not Q) ⇒ (not P).
We had seen that the contrapositive of an implication is equivalent to the original.
The scheme for induction is usually stated like this: “To prove a statement P(n): First prove P(1); then assume P(n) and prove P(n+1); it follows by induction that P(n) holds for all natural numbers n.” This leads to some confusion; for example, some students think that you are assuming the statement P(n) that you are trying to prove.
In fact the scheme (as I outlined it to the class) is this:
- First, write down clearly the statement P(n) you are trying to prove.
- Prove that P(1) is true.
- Prove the implication P(n) ⇒ P(n+1).
- Conclude, by induction, that P(n) holds for all natural numbers n.
As well as (hopefully) avoiding the above confusion, this is more flexible; we already talked about proving an implication, and saw three different ways to do it.
I’d be interested to know whether outlining induction in that precision does avoid confusion. I remember in my learning what what you’ve identified as the third step was the one that I most often tripped on (I suppose it’s most often the actually hard part), but my experience is almost always the unusual one.
One source of confusion is this. You write down P(n), your assumption for this step. You then forget that this is for a specific n, and regard it as being a general statement, in which it is legitimate to replace n by n+1. Miraculously, the job is done!