[MUSIC] Welcome back. In this video, I want to derive Binet's formula. Which is really remarkable formula in that it gives us an expression for all of the Fibonacci numbers. As I said before, the Fibonacci numbers are completely determined by the recursion relation and by the initial values. So that should be all the information we need to derive Binet's formula. So let me show you how we're going to do this. So rather than start with the equation for the Fibonacci numbers, let's just start with a general equation. Xn = Xn-1 + Xn-2. This equation has a special name. This is a second order linear homogeneous difference equation with constant coefficients. If you've had a course on differential equations, you may have studied the linear second order homogenous differential equation with constant coefficients, that's the equation for mass on a spring. The difference here is that it's a difference equation rather than differential equation, but the method of solution is almost identical to that for the differential equation. If you haven't study differential equations then you can follow along with the method. The method is that we make a guess for Xn. So we try to guess what is a solution for Xn. Through this process of guessing we can determine two independent solutions for Xn. Then because this equation is what's called a linear homogenous equation, we can multiply those solutions by constants and add them and still have a solution to the difference equation. With those two free constants, we can then satisfy the two initial conditions and find the formula for Fibonacci's numbers called Binet's formula. So let me show you then how it works. We need to make our guess. So what is the appropriate guess for the solution of this equation? We can try X sub n = something. Because of the nature of this equation, you can try several things, but it turns out that the appropriate guess is a constant race to the nth power. So a power lower, we can see that that's the appropriate guess because if we substitute it into the equation, we end up with lambda to the nth equals lambda to the n-1 power plus lambda to the n-2 power. We can divide this equation by lambda to the n-2 and collect terms. So we got lambda squared minus lambda, from lambda n*1 over lambda n-2, -1 from this third term = 0. So we get a quadratic equation. This is the same quadratic equation that we obtained when we determined what the golden ratio was. So there's actually two solutions here. One is the golden ratio. The other solution was the 1 minus the square root of 5 over 2 solution. That one, the negative of that solution is what we call the golden ratio conjugate. So the other solution here were called lambda 2, is the negative of the golden ratio conjugate. So those are our two solutions for lambda. So how do we use those two solutions, then we found two solutions for x. So we have two solutions for x and then we can multiply them by constants and add them together to get the general solution. So what that leads to then, is we can write down a solution for the nth Fibonacci number, which satisfies the same equation as X, and use those two solutions for X, multiplied for a constant. So we can multiply one of the solutions by C1. That's the solution, the golden ratio to the nth power, and we can multiply the other solution by C2. That's the negative of the golden ratio conjugate raised to the nth power. So we have now the solution for the nth Fibonacci number. We don't yet know the two constants, c1 and c2, and that's where the initial values come in. So we know that F1 = 1, that's n = 1, we know that F2 = 1, that's n = 2. We can use these two initial values to determine C1 and C2, then we have to deal with the golden ratio square n = 2 here. It's actually easier if instead of using F2 = 1, we use the value of F0 that we define a new Fibonacci number which is called F sub 0. We can define this, because we just have to satisfy the recursion relation. The cursion relation is that F0 + F1 = F2. So if 0 + 1 = 1, that 1 has an easy solution, F 0 is 0. So let's use the two initial conditions F0 = 0 and F1 = one. We plug that into this equation, and if we write the right hand side for n = 0. We have c1, the golden ratio to the 0 power is just 1. So we have c1 + c2, the other term is just c2, and that's for n = 0. So that's supposed to be equal to 0, for n = 1, we have c1 times the golden ratio. Then n = 1 gives us minus little phi, so minus c2 times little phi. And that's supposed to be equal to F1, which is 1. So now we have two linear equations, and two unknowns. C1 and C2 are the unknowns. We can eliminate c2, so c2 = -c1 and substitute that into that into the second equation, so we end up with c1 times big phi + little phi = 1. What is big phi + little phi? Big phi is square root of 5 + 1 over 2, little phi is square root of 5- 1 over 2. So when you add them you get square root of 5 over 2 plus square root of 5 over 2, so you get square root of 5. So c1, let me put it up here, c1 is equal to times square root of 5 is equal to 1. So c1 is equal to 1 over square root of 5. C2 then is -c1, so c2 is -1 over root 5. So we can put it together. We can put c1 in here and c2 here. So let me write the formula. So we get, Binet's formula then is Fn, we have our phi to the nth power, and then minus negative little phi to the nth power divided by our constant which is square root of 5. A remarkable formula, very remarkable formula. So the nth of Fibonacci number is given by this expression both big phi and little phi are irrational numbers. Square root of 5 is an irrational number but when we do the subtraction and the division, we got an integer which is a Fibonacci number. You can try it out at home, you can use a calculator, you can try to compute this and convince yourself that indeed you do get Fibonacci numbers. I will see you next time.