[MUSIC] 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.