6.3 Proof by induction
The principle of mathematical induction states that if we have a statement which depends on a natural number and
if the statement is true for ( is some natural number, usually or )
and for every natural number if the statement is true for , then the statement must also be true for
then the statement is true for every .
One way of thinking about induction is by considering an analogy to dominoes. If we have a row of dominoes, and we knock one domino over, and knocking any given domino over means that the next one over, then all the dominoes will fall over.
A general formula for solving any induction problem involving property reads something like:
The basis step - show that is true.
The inductive step - show that if is true, then this implies that is also true.
The completion step - write some words stating that as is true and being true implies is true, must be true for all integer with .
It probably helps to include some examples (see the next sections).
Let the function be defined by
Show that for all , is divisible by 7.
The first step is the basis case. By calculation (which is divisible by , as ).
The next step is the inductive step. Here we assume that is divisible by , and then consider .
The key thing here is to apply the inductive hypothesis (aka the fact that we have assumed that is divisible by ). This is pretty much always the first thing to do!
We know that . Currently, this doesn’t help very much as we have no way to apply it to the equation above. What we can do, however, is rearrange it to express either or in terms of and the other term. In this case, we’ll choose to eliminate , but we could do it the other way, and it would be fine.
We can now apply this to , by taking out a factor of from and then substituting.
Now we can factorise the expression, and hopefully find a factor of lurking somewhere!
This means that being divisible by implies that is also divisible by .
Now onto the completion step! This is pretty much the same every time: \say Thus implies and as is true, holds for all where .
6.3.2 From to
Sometimes it can be more practical to work from the case and apply operations to that to form the case , rather than trying to expose within (i.e. write the case in terms of ).