0:44

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.

Â 1:49

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.

Â 2:15

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?

Â 2:55

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.

Â 3:32

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.

Â 4:14

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.

Â 4:44

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

Â 5:07

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.

Â 5:30

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.

Â 8:34

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.

Â