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:

for

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?

?

Well this is:

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:

For SOME . 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:

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:

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

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

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 and this isn’t the same as clearly. However, we see that in the expression:

as n increases, this number gets closer and closer to 1. For n=1 for instance, this is . For n=2 this is . How about for n=10? This is . 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:

for

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

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

But this is exactly what we wanted to show:

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:**

for

- Base case: True, therefore the base case holds.

- Inductive hypothesis:

for some .

- Use the inductive hypothesis to prove that:

Take the left hand side:

Using the inductive hypothesis:

We know that for $n\ge 10$. Thus:

Which can be written as:

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

Jean-JacqMarch 9, 2016 at 4:21 pmAnd this, Dr Shock, is why you are a boss =) Thank you!

ShaiMarch 9, 2016 at 4:50 pmThanks for clarifying, Doc Shock!

JoshMarch 9, 2016 at 6:57 pmThank you!

TshepisoMarch 9, 2016 at 10:49 pmThank you very much Dr Shock!

KabeloMarch 10, 2016 at 8:02 amCan we phrase for exam purposes, the inductive hypothesis: as “Suppose for an arbitrary natural number n, that 2^n > n^3…”?

Jonathan ShockMarch 10, 2016 at 4:13 pmIn this case you have to be a bit careful as it is only true for n>=10, so you can say “Suppose for an arbitrary natural number>=10, that…”

GregMarch 11, 2016 at 9:26 am“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(1+1/n)^3”

I really don’t understand this step at all. Please explain why and how you went from (n+1)^3 to (n+1)^3 = n^3(1+1/n)^3

Thank you kindly.

Jonathan ShockMarch 11, 2016 at 9:33 amIf we have (1+a)^b, we can write this is (a(1+1/a))^b, and we know that if we have (pq)^r, this is p^rq^r, so therefore (a(1+1/a))^b=a^b(1+1/a)^b. In this case a is n and b is 3. Does that help?

Umar FaroukApril 30, 2019 at 7:17 pmyes, this does help as i was lost on the same step.

Mufhatutshedzwa NemakhavhaniApril 19, 2017 at 11:38 pmThank you Dr Shock for such a wonderful explanation.

UCT MAM1000W lecture notes subject links – MathemafricaMarch 15, 2018 at 10:29 am[…] Mathematical induction with an inequalityProof by induction winning explanation […]