Algorithmic Problem Solving

Induction is a very important problem-solving technique based on repeatedly breaking a problem down into subproblems.

Central to the use of induction is the idea of generalising a given problem to a class of problems. Specific problems within the class are called instances and each has a certain size. The “size” is said to be a parameter of the problem. For example, the problem might involve a pile of matchsticks, where the number of matches is a parameter; an instance of the problem is then a particular pile of matches, and its size is the number of matches in the pile.

Having decided on a suitable generalisation, the solution process has two steps. First, we consider problems of size 0. This is called the basis of the induction. Almost invariably, such problems are very easy to solve. (They are often dismissed as “trivial”.) Second, we show how to solve, for an arbitrary natural number n, a problem of size n+1 given a solution to problems of size n. This is called the induction step.

By this process, we can solve problems of size 0. We can also solve problems of size 1; we apply the induction step to construct a solution to problems of size 1 from the known solution to problems of size 0. Then, we can solve problems of size 2; we apply the induction step again to construct a solution to problems of size 2 from the known solution to problems of size 1. And so it goes on. We can ...