0:11

Some of the problems that I ask you to do in this

Â course require proof by Mathematical induction.

Â So I thought, I would make this video to help you to understand how one does that,

Â if you're not familiar with Mathematical induction.

Â So the kind of a classic problem that one proves by Mathematical

Â induction as an example, is the sum of the first n natural numbers.

Â So 1 plus 2 plus 3, all the way up to n.

Â And that's equal to n(n+1) divided by 2.

Â It's relatively easy to prove this directly but what I will show you here,

Â is how do you make a proof of this statement, given the statement,

Â how do you prove it using Mathematical induction?

Â The first step is called the Base case.

Â Typically, when you prove the theorem for

Â the lowest, smallest natural number, n=1,

Â you can have the Base case at any number.

Â So here, would be n=1.

Â So first, you prove the theorem for n=1.

Â So, how do we do that?

Â Well, it's relatively easy.

Â For n=1, the left hand side of the equation is equals 1, right?

Â The sum here.

Â And then for the right hand side

Â is equal to 1 x 2 / 2 = 1.

Â So that, we can conclude then that the equation is true for n = 1.

Â So, that establishes the Base case.

Â Then we go to the Induction step.

Â In the induction step,

Â we suppose that the equation is true for n = k.

Â Then the goal is to prove that it's true for n = k plus one.

Â So we assume it's true when n = k,

Â then we will right down the left hand side when n = k plus one and

Â show that it's equal to the right hand side when n = k plus one.

Â So, what do we do?

Â So here's the left hand side 1+2+3+k+k+1,

Â we're trying to prove the formula for n=k+1.

Â We can then use our induction hypothesis,

Â that we assume that the equation is true for n = k.

Â We can replace the sum of the first k numbers

Â by the theorem, k (k+1) over 2.

Â To that we add the next number, k + 1.

Â We can then do some algebra here, so we can put them under a common denominator.

Â So we have, k (k + 1) + 2 (k + 1) divided by 2.

Â We can then factor out k + 1, so

Â we have (k+1) (k+2) divided by 2.

Â At this point we can see that this is,

Â is in fact the right hand side when n=k+1 and

Â n+1 will be k+1+1 or k+2.

Â So since (k + 2) = (k + 1 + 1),

Â we have shown that this equation then is true for n = k + 1.

Â So, let's now understand what we've done for Mathematical induction.

Â We've proven the base case, the equation.

Â We've proven that the equation is true for n = 1,

Â then under the assumption that the equation is true for n = k,

Â we've proved that it must be true for n = k + 1.

Â So if we start with one,

Â then we have proved that the equation must be true for n = two.

Â And that if it's true for n = two, we've proved that it must be true for n = three.

Â If it's true for n = three, we've proved that it's true for n = four and so on.

Â So, we've gotten all of the natural numbers.

Â All of the natural numbers.

Â So we can always have the concluding statement then,

Â by the principle of induction.

Â The equation is therefore true for all natural numbers and

Â we've proved this identity for all the natural numbers.

Â So the Mathematical induction, then will be useful for

Â proving formulas about the Fibonacci numbers.

Â It's the index of the Fibonacci numbers, the f's of n,

Â the index which form the natural numbers, the index will be one, two, three, etc.

Â So, a statement about the Fibonacci numbers can be proved by Mathematical

Â induction.

Â Sometimes by showing that it's true for the base case.

Â Making the induction hypothesis and then showing it's true for an n = k + 1.

Â There is one little twist sometimes in some of the problems.

Â In order to prove that it's true for n = k + 1,

Â your going to have to assume that it's true for both n = k and n = k minus one.

Â So, you have to make the hypothesis assume that it's true for n = k minus one and

Â n = k, and then you proceed to prove that it's true for n = k+1.

Â In the proof, you will probably use the recursion relation for

Â the Fibonacci numbers.

Â In order for that proof to be legitimate, you have to change the base case slightly.

Â Instead of just proving for n=one,

Â you'll have to prove the base case for n=one and n=two.

Â Then the assumption, that if it's true for n=(k minus one) and

Â n=k, would mean that if it's true for n = one and n = two.

Â Then you've proved that it's true for n = three.

Â That if it's true for n= two and n = three,

Â you've proved that is true for n = four.

Â And in that way, you can get the proof of the theorem for all natural numbers.

Â Good luck.

Â