Teaching Induction to Prove the Correctness of Algorithms

This is a subject that I have had a lot of trouble clarifying for students. I can explain the components well enough, but I have trouble getting kids to connect the big picture of the proof to the smaller parts. Finding a good loop invariant almost seems more art than science, and while I can find them myself, I am at a loss with how to break that step down into coherent procedural steps.

So, the question is this: how do you go about teaching Induction so that it is both intuitive and masterable?

• I am a student, can you give me an example? – Quazi Irfan May 23 '17 at 15:05

I think induction should be taught first, and then loop invariants, since you usually need induction to prove that the loop invariant is really an invariant, and also because you need induction for other purposes than just proving that a loop invariant is really an invariant. In fact, in most curricula for Computer Science at university will have some math class that covers induction before a Algorithm Correctness course.

If this isn't the case, you might want to teach induction with some other examples first.

For example, proving that $1+2+\cdots+n = \frac{n(n+1)}{2}$ and a few other, relatively simple induction statements (e.g. sums, divisions, inequalities). If you need to teach recurrence relations as well, then you might introduce them now as well since you sometimes need induction to solve them. I think it is also helpful for the intuition to explain the domino-effect: $P(1)$ implies $P(2)$, $P(2)$ implies $P(3)$, $P(3)$ implies $P(4)$, etc. (also with a concrete example). This also shows the importance of the base case in the induction.

Then, loop invariants.

I would again (as always, actually) start with some easy examples, for example:

x=0
while (x < 2)
x = x+1


with the invariant being $x \leq 2$. How to find this? Well, just go through the loop. In this case this is doable: $x=0$ becomes $x=1$ becomes $x=2$. Now show them you don't really need to do the whole loop if you have while (x<100), for example. Now it is time to mention induction again: Since you don't want to write all hundred steps, you can use induction to prove this loop invariant.

Students now might think they just need to replace the lesser than with lesser than or equals. Show them this isn't true with an example like this (or use lesser than or equals in the statement):

x=0
while (x < 9)
x = x+2


Now, it is probably time for some complexer examples.

• This looks so much nicer now that math notation is enabled :) – Ben I. May 26 '17 at 19:45
• @Choirbean Yeah. I expected that the math notation would be enabled soon enough, so I already used it when writing the answer. This answer is also a good one to show it is needed here, I think. – wythagoras May 26 '17 at 20:12

I have been teaching theoretical CS to math teachers (don't ask why...). I assumed that they were comfortable with numerical induction and therefore the transition to structural induction (on a computation as in proving invariants) wouldn't be difficult. I was wrong on both counts. It seemed to me that this is partly because they encountered induction in a very narrow context. This year I showed them that - even in mathematics - induction is so much more than n to n+1. For example, to prove unique factorization of integers, four inductive proofs are needed (even if some of them are implicit). The transition to structural induction seemed easier this year.

I have prepared a document "The Many Guises of Induction" which may help others dealing with this subject. It can be downloaded from http://www.weizmann.ac.il/sci-tea/benari/mathematics.

• Welcome to Computer Science Educators. Generally it is better to include the basic information in the answer than to link to something externally. The link may not last, and then the answer will not help anyone. Would you please edit your answer to show how you have solved the problem of teaching induction in an intuitive and masterable fashion. – Gypsy Spellweaver Jun 7 '17 at 6:17
• The document in question is 50 pages of mathematics. Do you really want me to include it inline?! – Moti Jun 8 '17 at 7:02

One big struggle is getting CS students to care about induction. Proving correctness doesn't really count as motivation, when "passing the tests" seems so much approachable and the extra benefits from proving correctness just don't seem worth the extra effort. On the other hand, if induction could be practically useful in designing algorithms in the first place, that seems to provide more motivation.

That's essentially the approach used in Udi Manber's fantastic 1988 CACM article: "Using induction to design algorithms". (He later expanded this into a full textbook called "Introduction to Algorithms: A Creative Approach".) One caution for both the article and the book is you can't just throw these at students and assume that they already know induction, but instead probably need to review/teach induction at the same time.