Analysis, Maths, Proofs

Proof of Inequalities by Mathematical Induction

Leave a comment

Still reading though my book in Analysis, I've come across a section on proving inequalities. I'm glad to say that all of this made sense... until I reached a sub-section on proving an inequality by mathematical induction.

As  I've written previously, I find that proofs are notoriously unintuitive. In the past however, I have been particularly puzzled by the logical steps involved in proving an inequality by mathematical induction.

To explain my difficulties, let's have a look at the example provided in the book:

 

Prove that 2^n \geq n^2, for n \geq 4.

If we're proving this by mathematical induction, we generally follow these steps:

  1. Let P(n) be the statement 2^n \geq n^2.
  2. Show that P(4) is true.
  3. Assume that P(k) is also true for k \geq 4.
  4. Show that P(k) \Rightarrow P(k+1). Or rather, show that if P(k) is true, then P(k+1) is also true.

Step 4 is the key step here in the proof as it shows that if any number is true, and the next number is also true, then you can apply this rule forever, and your original statement must be true for all numbers!

Anyway, lets jump to step 2. Show that P(4) is true. Well if n=4, then 2^4 = 16 and 4^2 = 16. So P(4) is true! Easy.

Let's look at step 3. Let's ASSUME that P(k) is true for some k \geq 4.

Now, this is the part that caught me by surprise... At this step, the text in the book reads as follows:

"So, we are assuming that 2^k \geq k^2. Multiplying this inequality by 2 we get:

    \[2^{k+1} \geq 2k^2\]

,

so it is therefore sufficient to prove that 2k^2 \geq (k+1)^2."

Wait, what? How is it that all of a sudden, all we need to prove is that 2k^2 \geq (k+1)^2? This isn't explained explicitly in the text so I had to close the book and do a bit more thinking.

First thing I had to realise here is that the "Step 4" I've listed above requires a bit more detail... What you're actually trying to do is show that you can progress naturally from P(k) to P(k+1). ie: We should be able to show that we can progress naturally from:
2^k \geq k^2
to:
2^{k+1} \geq (k+1)^2.

Now, if we multiply 2^k \geq k^2 by 2, as mentioned in the text, we do arrive at:
2^{k+1} \geq 2k^2

This is good, as we've managed to get the 2^{k+1} we were looking for on the left-hand side of the inequality. But the right-hand side looks nothing like the right-hand side of P(k+1) ie: (k+1)^2.

Here's the key though... It doesn't matter they they're not the same. We only need to see how 2k^2 and (k+1)^2 relate to each other. Look back at Step 3. Part of this assumption is that k \geq 4. Just as a test, let's try k=4:

2k^2 = 2 \times 4^2 = 32
and
(k+1)^2 = (4+1)^2 = 25

Well this is interesting. It's looking as if 2k^2 \geq (k+1)^2. This is exactly what was written in the text!

But to really ram it home, what we really have now is the following:

2^{k+1} \geq 2k^2 \geq (k+1)^2

So.... this show us that IF we can prove that last bit (2k^2 \geq (k+1)^2 ) is true for all k \geq 4, and not just k=4 we have managed to prove that we can get from P(k) to P(k+1)!!! This is exactly why the text in the book said "so it is therefore sufficient to prove that 2k^2 \geq (k+1)^2."

I'm sure in future I'll jump on this immediately and say "oh yes, of course that's all we need to do now", but working through the derivation of why it was sufficient was extremely useful. Long-winded... but useful.

Ah, the learning process...

Leave a Reply