[MUSIC] Let's consider a couple of examples. So example one. Suppose we have a recurrence relation, A(n) = 5A(n- 1)- 6A(n- 2). And suppose that we want to find a sequence satisfying certain initial conditions. Find a solution, Satisfying, The following initial conditions. A0 = 3, and a1 = 7. Okay, how to solve this? Let's write down the characteristic equation of this. Recurrence relation. So we know that it should have form t squared = 5t- 6. Or alternatively, it can be written down as t squared- 5t + 6 = 0. So the solutions are 2 and 3. So lambda = 2, mu = 3. These are roots of this quadratic equation. So this means that, since we know the roots of the characteristic equation, we know that general solution of this relation. It is, an = C times 2 to the power n. (lambda's to the power n) + D times 3 to the power n. Okay, and what we want to do now is we want to find such C and D that this solution satisfies this, these initial conditions. To find such C and D, we can use either the general formulas or we can solve this system again for these concrete values. Well, maybe the second option is simpler, so let's do this. So we know that [COUGH], a0 = 3, and this is just C + D. And a1 = 7, it is 2C, + 3D. So we solve this system of equations and we get C = 2 and D = 1. So 2 + 1 = 3 and (2 times 2) + 3 = 7. Okay, so the solution we're looking for is an = 1 times (2 to the power n). This makes (2 to the power n + 1) + D = 1 + (3 to the power of n). Okay, so this was our first example. And our second example, a much more interesting one is the Fibonacci sequence, the first recurrence relation we started with. So example two, The Fibonacci sequence. In this case, we know that F(n) = F(n- 1) + F(n- 2). The initial conditions for the Fibonacci sequence are f0 = 0, and f1 = 1. So in the first month, you had one pair of rabbits, and before that you had no rabbits at all. So well, We start our Fibonacci sequence from 0. Okay, so what about the solution of this recurrence satisfying these initial conditions? Again, we can do the same and write down the characteristic equation, t squared = t + 1. So this means that t squared- t- 1 = 0. The coefficients, the roots of this equation, are not that nice as the roots of this equation anymore, they're not rational. Let us note them by phi and psi. Phi = 1 + (square root of 5) divided by 2, and psi = 1- (square root of 5) divided by 2. So here they are. So our general solution of this sequence, satisfying this particular relation, has the form fn = C times (phi to the power n) + D times (phi to the power of n). Okay, and we are looking for these initial conditions. So we know that phi 0 = 0, so, f0 = 0. So 0 = C + D. What happens if n = 0? So this is just C, and this is just D. And if you take n = 1, you get (C times phi) + (D times psi) = 1. Okay, so from the first equation, we see that D = -C, and 1 = C times (phi- psi). So C = 1 over (phi- psi) and D = 1 over (psi- phi). The same thing but with the negative sign. Okay, and if we take these values again we see that, C = 1 over the square root of 5, and D = minus 1 over square root of 5. So what we get is the explicit formula for the nth Fibonacci number. So we have found those C and D. And we see that Fn, Can be computed as follows. This is (phi to the nth- psi to the nth) divided by (phi- psi). And this is nothing but 1 over the square root of 5 times the following thing. Phi to the nth = ((1 + the square root of 5) over 2) to the power n. And -psi to the power n, which is ((1- the square root of 5) divided by 2)), also the power n. This formula allows us to find explicitly the nth Fibonacci number, without computing all the previous ones. So fn can be can be obtained as the sum of two geometric progressions, this way. This is called the Binet Formula. And well, I think this is something really amazing. Because when you're looking at this multiplier with radicals and with the power n, well of course, you think this must be irrational. But it turns out that it is not only rational, it is always an integer for an arbitrary n and moreover it gives the nth for the Fibonacci number [MUSIC]
