In the tutorial sessions it was clear that one question in particular was causing problems. This is an induction proof with an inequality. The one which we will look at is the inequality:

 

2^n>n^3 for n\ge 10

 

I am going to talk you through it in more detail than would be needed for the formal proof but I want to give some intuition along the way.

 

So, we start off, as always with the base case. The base case is always the first integer for which the statement is claimed to be true. In this case it is for n=10. Let’s check for n=10. Is it true that?

 

2^{10}>10^3 ?

 

Well this is:

 

1024>1000

 

and so we should be happy with that. We’ve proved the base case. Note that you do not then need to check for n=11, or n=12. I have seen many students check a base case for n=1, and then also check for n=2 and n=3. The point about induction is that once you have the base case, the inductive hypothesis, and the inductive step, that you are done – you don’t need to check any ‘intermediate’ values.

 

Ok, so what is our inductive hypothesis? It is that:

 

2^n>n^3

 

For SOME n\ge 10. This is so important, and what I am still seeing students confused by. Here we are assuming that it holds for some n. Not all n, and not some specific value of n, but some, abstract n.

 

Now we want to use this to prove that the statement holds true for n+1. Let’s look at what we are trying to show. We want to prove that:

 

2^{n+1}>(n+1)^3

 

We will do this by only using the left hand side, and try and show that this is indeed greater than the right hand side. With such proofs, you should manipulate one side only, to get it equal to the right hand side. If you find yourself doing things to both sides then you may end up getting 0=0 and this, while true, may mean that you’ve done some intermediate step which is not allowed.

 

So, we start with the left hand side and manipulate it. First we see that:

 

2^{n+1}=2\cdot 2^n

 

We then note that 2^n appears in the inductive hypothesis, and because we are assuming that that is true, we can use this here. So we have:

 

2^{n+1}=2\cdot 2^n>2\cdot n^3

 

ok, now we have to do some inspection. We want to get the right hand side somehow to look like (n+1)^3 but at the moment, we just have n^3. In fact one can write

 

(n+1)^3 = n^3\left(1+\frac{1}{n}\right)^3

 

You will often use a trick like this, so play around and make sure that this is clear. Now, why is this useful? Well, in the left hand side of our equation we have 2\cdot n^3 and this isn’t the same as n^3\left(1+\frac{1}{n}\right)^3 clearly. However, we see that in the expression:

 

\left(1+\frac{1}{n}\right)^3

 

as n increases, this number gets closer and closer to 1. For n=1 for instance, this is 2^3=8. For n=2 this is 1.5^3=3.375. How about for n=10? This is 1.1^3=1.331. Even if you don’t know this exactly, you should be able to see that this is less than 2. Indeed then we can say that:

 

2>\left(1+\frac{1}{n}\right)^3 for n\ge 10

 

Why is this useful? Well, we can now write:

 

2^{n+1}=2\cdot 2^n>2\cdot n^3>\left(1+\frac{1}{n}\right)^3n^3

 

Let’s now take everything back inside the brackets and this gives:

 

2^{n+1}=2\cdot 2^n>2\cdot n^3>\left(1+\frac{1}{n}\right)^3n^3=(1+n)^3

 

But this is exactly what we wanted to show:

 

2^{n+1}>(1+n)^3

 

Thus, because we showed the base case, and we proved that as long as the inductive hypothesis is true, then we can show that the next case holds, then we have shown that the original statement is true.

 

This seems like a lot of steps, so let’s write it all down succinctly:

 

Prove that:

 

2^n>n^3 for n\ge 10

 

  • Base case: 2^{10}=1024>10^3=1000 True, therefore the base case holds.

 

  • Inductive hypothesis:

 

2^n>n^3

 

for some n\ge 10.

 

  • Use the inductive hypothesis to prove that:

2^{n+1}>(n+1)^3

 

Take the left hand side:

 

2^{n+1}=2\cdot 2^n

 

Using the inductive hypothesis:

 

2^{n+1}=2\cdot 2^n>2\cdot n^3

 

We know that 2>\left(1+\frac{1}{n}\right)^3 for $n\ge 10$. Thus:

 

2^{n+1}>\left(1+\frac{1}{n}\right)^3\cdot n^3

 

Which can be written as:

 

2^{n+1}>(1+n)^3

 

We have thus proved, by mathematical induction the original statement holds.

How clear is this post?