[MUSIC] Welcome back. In this lecture I want to derive an identity, which is the sum over the first n Fibonacci numbers. So what we want to do is we want to find a formula for F1 + F2, all the way up to Fn. The notation of writing that is the Sigma notation. It says the sum from i = 1 to n of Fi. So what we're going to do is we're going to try and discover the formula. And then, as mathematicians, I will show you a direct proof of the formula once we've discovered what it is. To discover the formula, we write a table. So we have here the n equals 1 through 9. And then we write down the first nine Fibonacci numbers, 1, 1, 2, 3, 5, 8, 13, etc. And then in the third column, we're going to put the sum over the first n Fibonacci numbers. So the sum of the first Fibonacci number is 1, is just F1. The sum of the first two Fibonacci numbers is 1 plus 1. So that would be 2. The sum of the first three is 1 plus 1 plus 2. But actually, all we have to do is add the third Fibonacci number to the previous sum. We need to add 2 to the number 2. We get four. And then we add 3 to the number 4 to get 7. And then we add 5 to the number 7 to get 12, and so on. So we can get the sum of the first n Fibonacci numbers. Then let's look at these numbers. What do we have here? We have 20, 33. We look at the Fibonacci numbers, we have a 21 and a 34. So that looks promising. 34 here, 33. 21 here, 20. 13 here, 12. 8, 7, 5, 4. So this looks like a general rule, that we can take the sum of the first six Fibonacci numbers. Looks to be related to the eighth Fibonacci number minus one. One less. So we can write that as a formula. Our conjecture is that the sum from i = 1 to n of Fi = Fn + 2. We index two more than the last Fibonacci number that we summed, minus one. That's our conjecture. So how do we prove something like that? Let me use black ink, here. How do we make a proof of that? The only thing we know about Fibonacci numbers in this context is the recursion relation. So we can write down a recursion relation. There's an Fn+2 here, so let's write down the recursion relation for Fn+2. So Fn+2 = Fn+1 + Fn. That's the Fibonacci recursion relation, but we can rearrange this formula. We can rearrange this formula. The left-hand side is going to have an Fn, the last term in this sum. The right-hand side has an Fn+2. So we can try to write this as Fn = Fn+2. Then we have subtract Fn+1. And that would be the last term in the sum, the Fn term. But we need to have all the Fs in the sum, so we need to go back one, so we can reduce the index by one. So we can write down n-1, Fn-1. This is two more than n, so this should be Fn+1, two more then n-1 -, this is just one more, so this should be Fn. And so on. Let's do one more just to see. Fn-2 = Fn- Fn-1. And the idea being that we're going to have all the Fs, here, so we can keep going down. And then the last one will be our F1, our first term. And then this one will be two more than that, so this will be F3- F2. So we have now, on the left-hand side, we have all the Fs that we want to sum in the expression. So we can take this, and then we can add them all. So there's a big plus sign here. That's the idea. But look what happens when we do that. Let me change the ink color to red for the moment. We're summing these equations, but look, we have Fn+2. Where am I? We have Fn+2- Fn+1, and then we have Fn+1. So when we add, we get- Fn+1, exactly cancels Fn+1. We have a really nice cancellation there, and it continues,- Fn cancels Fn. And all these terms cancel. This one cancels against one here, etc. Then finally, going all the way down, this one cancels against this one. So we only have two terms left. We have exactly two terms left. Let me write that. Go back to black. So what do we get at the bottom? We get the sum on the left-hand side. We get the sum down here. We get the summation of our Fi, the sum from i = 1 to n. Let me not write that. And then we have two pieces left. We have Fn+2- F2. Only two terms remain. The identity says Fn+2- 1, but we know F2 is equal to 1. F2 is equal to 1. So by making this list, then, we've managed to prove the identity. In the next lecture, I want to kick it up a notch. Instead of looking at the sum over the Fs, let's look at the sum over the F squares. The sum over the F squares. I'll see you next time.