One of the concepts that most students seem to struggle with the most in the first year maths course is that of mathematical induction. It feels abstract, yet when you have to prove a concrete statement, it feels like all the assumptions, and cases you look at shouldn’t have any real impact on the thing that you’re trying to prove. I will now try and prove that this is not true (though not by mathematical induction!).
I’m going to start with a ladder brought from a magical ladder supplier. Steps on the ladder are labeled S(1), S(2), S(3) etc. The question is, are there infinitely many steps on the ladder? Well, with the information that I’ve given you so far, you just don’t know, but the manufacturer has given a little leaflet with the it. In the leaflet it says:
“As long as your ladder has a step S(n), we hereby guarantee that it will have a step S(n+1), for any integers n”.
That sound promising, but what if our ladder had no steps at all? They wouldn’t have lied in the statement, though they would have sold us a terrible ladder!
We go and check the ladder for a first step, and on inspection we see that indeed there is an S(1). Now, they told us that if there was an S(n) for any integer n, then there will be an S(n+1). Well, that’s great, because we can use that information to see that there must be an S(2), because there was an S(1). We can also use their guarantee to know that there must be an S(3) because there was S(2). In fact we can see that we can use their statement to prove that the ladder must have an infinite number of steps on it. Looks like we got a pretty good deal on our ladder.
So, this is all very silly, but this is precisely the process of mathematical induction. We want to prove that a statement holds true for a certain set of integers (for instance, we want a statement S(n) to be true for all integers ). All we need to do is to show that it’s true for a base case (ie. the first integer in our set of cases for which we want to show that it’s true), and we need to show that as long as S(n) is true for some n, it will always be true for S(n+1).
Let’s try a really simple example. I’m actually going to go through one of the tutorial questions, but I think that a lot can be learnt from going through it in really good detail.
The statement that we want to prove is:
The sum of odd numbers:
Well, let’s think about the naive way of doing it (this is NOT mathematical induction). Let’s check it for each integer…
For n=1: , yup, that sounds about right
For n=2: , yup, we’re still happy.
For n=3: , intriguing – might not have guessed it, but it looks good…
For n=4: , ok, still good.
So the question is, do we have to keep going, or are we happy now that this is true for all ? Well, we are being mathematicians now, and so this is definitely not a proof. It could be that for n=5 this fails, and even if we checked n=5, we couldn’t be sure that for n=17, or 325, or 82750284952 it didn’t suddenly stop working. It seems unlikely, but we don’t want to be pretty sure of something, we want to be completely sure of it.
So, we now turn to mathematical induction. Indeed we have already seen that the base case, which is n=1 works.
Let’s go back to the ladder situation. The company told us that so long as the step is there, they can guarantee that the will be there too. Can we make such a statement about the mathematical formulation above? Let’s see if we can somehow prove that if the case for some n holds, then it must also hold for n+1. We’re going to do a bit of a strange thing now.
Let’s assume that it holds for some n. Therefore, we are going to assume that for some integer n, the statement
is true. Note that we haven’t assumed that this is true for all . That’s what we are trying to prove. We just assume that it is true for some (unspecified) n. This is the most abstract thing to understand in mathematical induction. The idea of assuming that it holds for some, unspecified n. Now, can we prove the statement for n+1, using the above assumption? The thing that we are trying to prove is now:
Make sure that you understand why this is the statement for n+1. Let’s look at the left hand side:
Note that we assumed just a moment ago that . So let’s use this. We can see that the first terms of the expression above are exactly this so we can replace them:
Now let’s reshuffle this:
But hang on a minute, this, on the right is just . So we have now shown that indeed
That was what we were trying to prove. We have therefore proved that if the statement holds for some n, then it will also hold for n+1.
But is this enough? Well, just with the above line, we have only proved that IF it holds for some n, then it also holds for n+1. However, we earlier proved that it does hold for n=1. Therefore, by the above reasoning, it must hold for n=2. And if it holds for n=2 it must hold for n=3. If it holds for n=3, by the above reasoning it must hold for n=4. Now we can see that as long as the base case holds (and we did indeed proved that it does), then it will hold for all subsequent integers.
Thus, by the principle of mathematical induction we have proved that the statement holds true for all integers .
The steps of mathematical induction are always the same.
- Prove that the statement holds true for the base case (ie. the lowest integer about which the statement is being asserted).
- Assume that the statement holds true for some n (the some here is very important – it does not mean all n, and it does not mean a specific n – it just means some arbitrary, unspecified n. I think that this is the most abstract part of proof by induction, but the most important).
- Use the assumption made in part 2. to show that if that holds true, the statement will also be true for the statement n+1. This is the inductive step.
- You are done. As long as the statement about n being true leads to the statement about n+1 being true, and the statement for the base case holds true, then you have proved it for all integers where b was the base case.
Now go back to the tutorial questions and see if you can prove them all.