[MUSIC] Welcome back. In this lecture, I want to derive another identity, which is the sum of the Fibonacci numbers squared. Okay, so we're going to look for a formula for F1 squared + F2 squared, all the way to Fn squared, which we write in this notation, the sum from i = 1 through n of Fi squared. Okay, so we're going to look for the formula. And then after we conjuncture what the formula is, and as a mathematician, I will show you how to prove the relationship. So let's go again to a table. Here, I write down the first seven Fibonacci numbers, n = 1 through 7, and then the sum of the squares. So the first entry is just F1 squared, which is just 1 squared is 1, okay? The second entry, we add 1 squared to 1 squared, so we get 2. Then next entry, we have to square 2 here to get 4. And we add that to 2, which is the sum of the squares of the first two. So we get 6. And 6 actually factors, so what is the factor of 6? 6 is 2x3, okay. That kind of looks promising, because we have two Fibonacci numbers as factors of 6. For the next entry, n = 4, we have to add 3 squared to 6, so we add 9 to 6, that gives us 15. And 15 also has a unique factor, 3x5. And look again, 3x5 are also Fibonacci numbers, okay? The next one, we have to add 5 squared, which is 25, so 25 + 15 is 40. Before we do that, actually, we already have an idea, 2x3, 3x5, and we can look at the previous two that we did. So we have 2 is 1x2, so that also works. And 1 is 1x1, that also works. This one, we add 25 to 15, so we get 40, that's 5x8, also works. And the next one, we add 8 squared is 64, + 40 is 104, also factors to 8x13. So we're seeing that the sum over the first six Fibonacci numbers, say, is equal to the sixth Fibonacci number times the seventh, okay? So the sum over the first n Fibonacci numbers, excuse me, is equal to the nth Fibonacci number times the n+1 Fibonacci number, okay? That's our conjecture, the sum from i=1 to n, Fi squared = Fn times Fn + 1, okay? So let's prove this, let's try and prove this. How do we do that? Well, kind of theoretically or mentally, you would say, well, we're trying to find the left-hand side, so we should start with the left-hand side. But we have our conjuncture. So there's nothing wrong with starting with the right-hand side and then deriving the left-hand side. It turns out to be a little bit easier to do it that way. So we're going to start with the right-hand side and try to derive the left. We start with the right-hand side, so we can write down Fn times Fn + 1, and you can see how that will be easier by this first step. We have this is = Fn, and the only thing we know is the recursion relation. So we can replace Fn + 1 by Fn + Fn- 1, so that's the recursion relation. And immediately, when you do the distribution, you see that you get an Fn squared, right, which is the last term in this summation, right, the Fn squared term. And what remains, if we write it in the same way as the smaller index times the larger index, we change the order here. We have Fn- 1 times Fn, okay? And we can continue. We can do this over and over again. We replace Fn by Fn- 1 + Fn- 2. So then, we'll have an Fn squared + Fn- 1 squared plus the leftover, right, and we can keep going. So we're just repeating the same step over and over again until we get to the last bit, which will be Fn squared + Fn- 1 squared +, right? And we're going all the way down to the bottom. We're going to have an F2 squared, and what will be the last term, right? The last term is going to be the leftover, which is going to be down to 1, F1, And F1 larger than 1, F2, okay? So if we go all the way down, replacing the largest index F in this term by the recursion relation, and we bring it all the way down to n = 2, right? So then we end up with a F1 and an F2 at the end. So this isn't exactly the sum, except for the fact that F2 is equal to F1, so the fact that F1 equals 1 and F2 equals 1 rescues us, so we end up with the summation from i = 1 to n of Fi squared. So we proved the identity, okay? This particular identity, we will see again. It has a very nice geometrical interpretation, which will lead us to draw what is considered the iconic diagram for the Fibonacci numbers. So I'll see you in the next lecture.