Sunday, November 4, 2007

Mathematical Induction

The IB felt that HL Maths wasn't nerd enough. So what is? I know.

Let's create something that only exists if maths itself exists, has no real world application (besides the testing of MATHEMATICAL formulae) and is generally very, very scary sounding.

So Mathematical Induction was born (Yes the IB invented it. We're arrogant enough to know (not think, or presume, know.) that no one taught it before IB existed. Education started in 1968.)

So anyway that gives you the background of it. Mathematical Induction (from now on referred to as MI). The main point of this post is for me to consolidate my knowledge, as acting superior as when you do posts like this, it's a nice summary and refresher. So with that I've decided to minimize the hard sounding words, along with keeping the tune rather upbeat as you may have noticed (if you haven't then click here, and god speed).



Step One - And so it begins...

Why pick MI?

Well, there are many reasons

  1. MI6 and MI5 are named after it
  2. It's pure maths
  3. It let's you prove things
  4. You don't have a damn choice noob

So now you've picked MI, and you're wondering why.

Well you're a noob, and you should of stuck with trig and pi.

(oh god I did not just do that)


With a mathematical formula. Eg. 2n+1 is an odd number. We can test it for n=1. For n=2. For n=3. and so on. But with just that, we cannot be sure that for n = J (Any real integer) that this would hold. So we have a slight problem.

But then along came MI. But then the traditional book explanation here gets all booky and boring and druidlike. So.

Let's go use our typical maths standby, a person flying a kite a bag with white and black balls bacteria analysis a ladder.

Let's say that our formula is a ladder. And to teach people to use our formula, we have to teach them to climb the ladder. Makes sense?

Now let's say we have something like 2 + 4 + 6 + 8 + ...  +2n.

And our ladder formula is n(n+1)

We can prove it for 1. 1(1+1) = 2

Then we can prove it for 2. 2 + 4 = 6 | 2(2+1)=2(3)=6

And hence so on. So they can go up the first step, and the second step.

But if we did it even for a thousand steps, we cannot be sure that the next step would still hold, that it would still work. (well I can, but the last time I tried to use that to justify my answer in an exam I sort of failed it)

However. If we can teach them the first step, that it works for 1.

Then we teach them how to do it for any single step (eg. k)

Then we teach them how to do it for any step after that (eg. k+1), then we've taught them how to climb the ladder!


Step 2 - Why that part of Step 1 works

So why is it that the whole thing is true when we just teach k and k+1?

It's an Axiom.

In a shorthand definition, it just means something that we just assume to be true.

1+1 = 2.

That's an axiom that whenever 1 is added to 1 in maths, it equals 2.

This is for our base 10 system.

1+1=10 not 2.

With a different axiom (binary) we see that it's now different.

Axioms aren't necessarily true, we just assume that they are.

So. After resisting the urge to avoid ToK (or at least a detailed discussion of it). We go into the next step.

Let's say I say today is Monday (Which at this point of time it is not)

Then if today is Monday. The next day would be Tuesday.

It is undisputable that the next day is Tuesday. But that is ONLY true if today is Monday. So Monday would be the k, and Tuesday is the k+1. This means that when k is true, k+1 must also be true.

So if k = monday

And if k is true

then k+1 = tuesday is also true

Makes sense doesn't it?

So this is the part that's often misquoted about Mathematical Induction.

So wait, you're assuming something is true, to prove that it's true?


Step 3 - Further explanation upon Step 2

The point behind it is, is that the k can be any figure. This means that we could prove it (or teach it to them) for the first step. Then the second step, up to the nth (or in this case kth) step, and call that bit k. Then if though maths we can prove it all the way down to k+1 as well, we can prove it for any value.


Quite simply the k+1 value becomes k, and the next value (k+2) becomes k+1.

And since the k and k+1 thing is true.

This just repeats endlessly, until you get to the number you wish to achieve.

So using the ladder example, we teach you how to get to a certain point, and then how to get from that point to the next one. Then you can just repeat the process. And you're fine.


Step 4 - Actual MI now (n(n+1))

Now here is the process in how we prove a MI. It's rather hard to explain without an example, so we shall use our friend n(n+1).

The start is that this series

2+4+6+8+10+...+2n = n(n+1).

The first step is to test it for 1

2(1) = 1(1+1)


So it works.

Next step is to use k.

That is

2+4+6+8+10+...+2k = k(k+1)

Now we use the next step, eg k+1

As you can see, the whole process is getting bigger by 2n each time.

2(1)+2(2)+2(3)... = 2+4+6...

So if the last step was 2(k). The next one would be 2(k+1)

So we then add this onto the previous step

So this means that


So if we look at the right hand side of that, we have




=k^2+3k+2 (1)

Then this is what we got from adding k+1 onto our k value.

It's perfectly sound. Now if this value is EQUAL to the value that we get when we substitute k+1 as n in n(n+1). Then it means that the MI is true, and it holds for any integer (that we specify).

So. n(n+1) where n=k+1




=k^2+3k+2 (2)

When we compare (2) to (1) we see that they are the same.

k^2+3k+2 (1) = k^2+3k+2 (2)


Well that's probably the easiest mathematical induction problem you'll encounter.


Step 4.5 A mini step (most confusing damn part)

This is to clarify on the step that might be the hardest, from where we added 2n.

It is NOT always 2n. It will NOT be the same each time. Each one is different.

1 + 2 + 2^2 + 2^(n-1)

For our k+1 we would add 2^(k+1-1)=2^k onto both sides


This one is easy. We would add n, eg. k+1 to both sides.

Also a quick point on why it works.

In the first equation for (1) it is obtained by

2+4+6+8+10+...+2k then adding 2(k+1) onto both sides.

For (2), it's the next step, and hence 2(k+1) IS the next step, it gets added on.

So that means that both equations should be equal. That's why it's a proof.

Hope this helped.

If it didn't then meh.

Step 5 - A Summary and another question

So the steps are.

  1. Identify that is indeed MI (look for the words 'prove by mathematical induction' or 'using MI prove that' etc.)
  2. Now test the thing for where n = 1 to see if it actually works.
  3. Now sub k in, and assume that this is true.
  4. Now add whatever is done to the next value (see Step 4.5) to the sub'd k value.
  5. Now do some magic to it (hardest damn part)
  6. Now sub k+1 as n into the orignal formula, and see if both equations equal. If they do. Then. SUCCESS!!!

Well I think I started off rather well, but yeah, the last bit might of got a bit confusing. I think it's easier with a diagram but too lazy to draw atm.


Btw your problem is 1+3+5...+(2n-1) = n^2


gee_cee0 said...

1+3+5+...+(2n-1) = n^2

Test when n=1

2(1)-1 = 1^2 true :D

k = n


2(k)-1 + 2(k+1)-1 = k^2 + 2(k+1)-1

RHS: k^2+2(k+1)-1=k^2+2k+1 (1)

sub k+1 for k

(k+1)^2=k^2+2k+1 (2)



Do i get a prize :D

David Jin said...

Technically I've never seen them do the (1) and (2) statement things but like I don't think it's wrong.

Other then that then yeah it's all good.


2(k)-1 + 2(k+1)-1 = k^2 + 2(k+1)-1

The left hand side of both equations are technically wrong, as it's the sum of all the previous terms as well. If you do that you have to do the 1+3+5+...+ thing. Most of the time I just concentrate on the right hand side (eg. the side that actually matters).