Mathematical induction is one of the most useful tools which is extremely helpful when proving theorems (but not only). Our aim in this lecture is to show you that modern Computer science cannot be developed without induction, both on the level of defining concepts and algorithms as well as that of proving programs correctness.

Probably everyone of us used to line up domino's game blocks. If we manage to place them close enough then by pushing the first block we knock over the second one which pushes the third one, etc. As a result of this chain reaction all lined up blocks go down. This simple process  well corresponds to an idea of mathematical induction (see Fig. 8.0.1).

Fig. 8.0.1 Induction principle.

We can explain induction using another real-life example. If we are able to climb on the first step of a ladder and being on any step we can move to a higher one, then we are capable of going as high as we wish.

We devote this lecture to the discussion of different definitions of mathematical induction. We show how to define new concepts by induction as well as formulate the general idea of producing recursive definitions. It is important to notice that none of the induction's steps can not be omitted, induction basis is as important as induction step.
In programming, recursion is one of the useful methods of program construction. However, we should keep in mind the aspect of time. It is a well-known fact that even though recursive algorithms are shorter and more code-elegant than the others, they usually take much more time than equivalent iterative algorithms. At the end we introduce the invariant method which is a very useful tool in deriving algorithms correctness and we present its connection to mathematical induction. 

« previous section

next section »