[MUSIC] Let's come back to combinatorics and let us discuss how to apply generating functions to solving linear recurrences, the object we were dealing with in our third lecture. And as usual, our first and favorite example is Fibonacci numbers. So recall that the Fibonacci sequence is defined by the relation fn+2 = fn+1 + fn. So this is a linear recurrence relation of order two with initial conditions f naught = 0, f1 = 1. Okay, and let us perform the generating function for the Fibonacci sequence. It will be as follows. Denoted by phi(q) and it is equal to q + q2 + 2q3 + 3q4 + 5q5 + 8q6 + etc. Okay, and what we want to do now is we want to get some presentation of this power series. We want to present it as a rational function, as a ratio of two polynomials. And to do this, let us first multiply phi(q) by q and look at this power series. q phi(q) is, The same power series, but shifted by 1. q2 + q3 + 2q4 + 3q5 + 5q6 + etc. Okay, and what are we going to get if we multiply the same power of series by q squared? This means we will shift it by two and we will get something started with q3, and we proceed as, q4 + 2q5 + 3q6 + etc. Okay, now let us look at these three rows. We see that the sum of the two last rows, the white ones, is almost the same as phi( q) over here. The only difference is that phi(q) starts with q and in the sum of these two rows q does not appear at all. So we see that, If we take the sum of the second and third row, add q, we get exactly the power series for phi(q). So let us state this as follows. Phi(q) = q + q phi(q) + q2 phi(q). So this is the equation for the generating function of the Fibonacci sequence. So sometimes it is called a functional equation. For the Fibonacci generating function. Okay, now if we look at this equation and, well, we can write it as follows, phi(q)( 1-q- q2) = q. So, the product of this power series and this polynomial, 1- q- q2 is equal to q. And you probably recall that this polynomial is nothing but the characteristic polynomial of the initial recurrence relation. And of course, this is not a coincidence. So, phi(q) is nothing but q divided by 1- q- q2. And so if you want to compute Fibonacci numbers, you just can take the inverse of this polynomial, you already know how to compute inverses over arbitrary power series. And if you multiply by q, you will get exactly the generating function for Fibonacci numbers. But there's a better way. This is a polynomial of degree two and this polynomial has two distinct roots. Let us write this in the following way, 1- q- q2 = (1- phi q)( 1- psi q) where phi and psi are the inverses to the roots of this polynomial. Phi and psi are the inverses, To the roots, Of 1- q- q2. So, of course, you can find these roots. And these are phi = 1 + square root of 5 over 2. And psi is equal to 1- square root of 5 over 2. So my next claim is as follows. Proposition, There is this such number C and D that, there exists C and D such that, Phi(q) can be presented as the sum of the following two fractions, C divided 1- phi q + D divided by 1- psi q. Now let us find the C and D. [MUSIC]