2.1 Introduction

A row of dominoes, all standing on their ends, extends beyond the horizon. The dominoes are spaced close enough so that, if one falls over, the next falls down too. (See Fig. 2.1.) Someone knocks the first domino over.

Figure 2.1: The parable of the dominoes: The essence of mathematical induction.

The result: They all fall down.

This parable of the dominoes describes the essence of mathematical induc tion, the most important method of proof in discrete mathematics. Mathematical induction applies when you have an infinite sequence of statements,

and you want to prove they re all true. The statements are the dominoes. To be proved true is to be knocked down. If you can show that the truth of any one statement P(n) would imply the truth of the next statement P( n+1), then each domino is close enough to knock down the next. If you can also show that the initial statement P(1) is true (falls down), then all the statements are true (fall down).

Mathematical induction is intimately related to the inductive and recursive paradigms because it involves the same approach they use: get from one case to the next by finding a relationship between them. So far we have thought of our two paradigms as being methods of discovering relationships, devising algorithms, and solving problems. However, we also want to be certain (prove) that our algorithms and solutions are correct. This is where mathematical induction comes in.