Okay, so we have shown that if a sequence satisfies a linear recurrence relation of order k, it's generating function is rational with a denominator of degree equal to k. In fact, the converse is also true. And this is left for you as an exercise. Prove the converse. If A(q) Is rational. Being the ratio of two polynomials. Then, it's coefficient satisfy a linear recurrence relation of order equal to the degree of the denominator. Then an's satisfy, A linear recurrence relation Of order equal to the degree of q. So now we know that the sequence is satisfying linear recurrence relations, are exactly those which have rational generating functions. And we want to find explicit solutions for linear recurrence relations. And to do this, we need the the following theorem for presentations of rational functions. I won't give the proof of this theorem now, but this is a standard fact which is used in say in calculus for integrating rational functions or maybe you've seen it elsewhere. So theorem Let A of q Which is equal to P of q over Q of q be A rational function. With the degree of numerator less than the degree of the denominator. And for simplicity, I suppose that the polynomial Q, Has constant term equal to 1. And Q, so the value of the polynomial Q in 0 is equal to 1. Then I claim that A of q can be uniquely presented. As the linear combination of fractions of the following form. As the linear combination. Of fractions, Of the form. 1 over 1 minus lambda iq to the power ki, So, we have already seen these fractions in the binomial theorem with negative exponents Where 1 over lambda i's are exactly the complex roots of the polynomial in the denominator. Are the complex, Roots of, q and where ki does not, see the multiplicity of the corresponding root. ki is less than or equal to the multiplicity, Of the root 1 over lambda i. So this theorem allows us to take the generating function of a linear recurrence relation and present it in such a way. And for these fractions, we already know their generating functions. These are given by the binomial theorem. And so we can find an explicit solution of, an explicit presentation of the terms of the sequence ak as the sum of terms appearing in the binomial theorem. Well, a very important particular case is when this polynomial in the denominator does not have any multiple roots. And this is essentially the case we're dealing with, Most of the time. So a corollary is as follows. If Q(q) does not have any multiple roots. So all the ki's are non-zero. Then So Q of q is equal to 1 minus lambda 1q times etc times 1 minus lambda kq. And then the Corresponding function is. Equal to the sum of fractions 1 over 1 minus lambda 1 q times certain coefficient C1 plus etc plus capital Ck over one minus lambda Kq. And in this case the corresponding sequence defined by the layer recurrence relation is the sum of geometric progressions with common ratios lambda1, lambda2, etc., lambda k. This is what we have seen in the example with Fibonacci numbers. So in this lecture we're dealing with linear recurence relations and we have seen how to write down their generating functions. We have shown that their generating functions are rational. And we have seen how to present them in certain simple forms and which sometimes allows us to find explicit presentations for terms of these sequences. In the next lecture we will be dealing with non-linear recurrence relations. And in particular we'll see how does the generating function for Catalan numbers look like.