[MUSIC] So our problem is as follows. Given our recurrency relation, Of order k which is A(n) = C1A( n -1) + C2 A( n -2) + etc.+ Ck A( n -k). Find all the sequences A(0), A(1), etc. A(n) up to infinity satisfying this relation. We denote this relation by star. Okay, how to do this? Well, first let us begin with the easiest case, with the recurrence relation of order 1. So in this case, the so called baby case. What if k = 1? Then, our relation is just A(n) = some C times the previous term of the sequence. So A(n) is C.A(n-1). Well, and of course, all the sequences satisfying this relation, these are just geometric progressions. With an arbitrary first term and with a common ratio, c. So, The answer is, a0 is arbitrary. An is cn * a0. And it is obvious that the sequence is uniquely determined by its first term and if you know the common ratio c. So there are no other sequences of this term. Okay, and, well, but this was the case when k was equal to 1. What about an arbitrary k? Here is our guess, if a geometric progression worked fine in the baby case, maybe it will work fine as well in the arbitrary case. So let's try to find the sequences satisfying this relation which are geometric progressions with some common ratio lambda. So idea, Find a geometric progression. (anr, lambda anr, lambda squared, etc.) satisfying, The relation star(*). And so what happens if we have found a geometric progression satisfying this relation? This means that, well, first case is obvious, if lambda is zero then our solution is just a sequence of zeros, and obviously it satisfies this relation. So will suppose that lambda is not equal to zero. Suppose lambda is not 0. Then what happens? If this is true, this means that, a naught.lambda to the power n. Well, lambda is not 0, and let us suppose that a naught is also not 0. a naught lambda to the power n, this is an, = C1a naught lambda to the power n-1 + C2a naught lambda n -2 + etc.+ Ck a naught lambda n-k. And this holds for all n greater than or equal to k. For, Okay, suppose it's true, and we know that lambda is not 0 and a naught is not 0. So we can divide this equation by a naught times lambda to the power n-k, and we obtain the following thing. We obtain lambda to the power k = C1 lambda to the power k-1 + C2 lambda to the power of k -2 + etc.+ Ck. Here we have divided by a naught times lambda to the power of a -k. Okay, so we see that if lambda is the common ratio of such a geometric progression which satisfies this recurrence relation, then lambda must satisfy this polynomial equation. So this means that, then lambda is a root of the following equation. It is called the characteristic equation. The characteristic equation of our linear recurrence relation. And this equation is as follows. Tk = C1t k- 1 + C2t k-2 + etc.+ ck. This is a polynomial equation, and its coefficients are exactly the same as the coefficients in the original recurrence relation. Now, let us see how it works in the non trial case for k=2. [MUSIC]