[SOUND] [MUSIC] The example with Fibonacci numbers illustrates the general theorem, which we are about to state right now. This theory says that for an arbitrary recurrence solution of order K, its generating function is ratio two polynomials, where the polynomial in the denominator has degree exactly K. So here is the theorem. Let an, be a sequence defined by a linear recurrence of relation of order K. An + k = C1a, n + K- 1, + C2a, n + K- 2, + etc + CKan. Then the generating functions of the sequence, A(q), Is rational. Namely, it can be presented as the ratio of two polynomials, which we do by P(q). Where the degree of q is exactly K, the order of our occurrence relation. And the degree of P is strictly less than K. And let us write down the exact form of q. q is nothing but a characteristic polynomial of this recurrence relation. Moreover, q, Is equal to 1- C1q- C2q squared- etc -, CKq to the power of K. This is the characteristic polynomial of this relation, is the characteristic polynomial The proof of this statement is essentially the same as in the previous example. Namely, We can multiply the expression for A(q) by various powers of q with coefficient C1, C2, etc, Ck. So we multiply A(q) by C1q + C2q squared + etc + CKq to the power of K. And we get something like this. We get C1a naught q + C1a1q squared + C1a2q to the third + etc + C1a, K- 1, q to the power of K + etc + C2a naught, q squared + C2a1q to the third + etc + C2a, K- 2, q to the power of K + etc, and so on, and so on, + CKa naught q to the power of K + etc. So there are exactly K rules. And you see that say, if you sum up these terms, You get nothing but aK from this relation. And if you sum up the next terms here in next column, you get aK + 1. And so starting from q to the power of K, the sum is equal to A(q). So the difference of this sum and A(q) is some polynomial of degree less than K. So this = A(q) + some polynomial degree less than K, which we denote by P(q). Where, The degree of P(q) is less than K. Question for you is, what's the relation between these polynomial and the initial conditions for our recurrent solution? [SOUND] [MUSIC]