[MUSIC] Now let us restrict ourselves to the case of linear recurrence relations of order two. Let us take such a relation. A(n) = C1 A(n-1) + C2 A(n-2). And we're going to write down its characteristic equation. t squared = C1 t + C2. So this is a quadratic equation and, well you can use the formula you know from high school, to find its root. Suppose that this equation has two distinct roots. That means that its discriminant is not equal to zero. So suppose that lambda and mu are roots of this equation, what we denoted by two stars. While our original recurrence relation was denoted by one star. And we suppose that lambda is not equal to mu. For the moment, you can suppose that lambda and mu are both real. But if the discriminant is negative, well this won't change much, as we will see later. But if you are more comfortable with real numbers, not with complex ones, you can suppose that they are both real. Okay. So as we have seen previously, if lambda and mu are roots of this equation then, we have two geometric progressions, 1, lambda, lambda squared, lambda to the 3rd, etc. And, 1, mu, mu squared, mu to the 3rd, etc. Which are solutions of, this layer of recurrence relation of order two. Of, This means that, we can take linear combinations of these two solutions. We can multiply each of them by a coefficient, and we can sum them up. And what we get will also be a solution. So this means that, an = C lambda to the power n +D Times mu to the power n, is also a solution. So right now, we can write down a two-parametric family of equations. Or a two-parametric family of solutions. For arbitrary capital C and capital D, we have a solution which is a combination of these two, with these coefficients. Okay. The question is, are there any other solutions? We'll show in a moment that the answer is negative. That any solution of this equation, can be represented in such a way for some C and D. No, for any solution (a0, a1, etc.) of the equation (*), there exist C and D such that, an = C lambda to the nth + D lambda to the nth. Okay. Let us show this. By the way this solution, with C and D as parameters, is called general solution. Of this equation, star. How to show this? We already know that, any layer recurrence relation of a given order, in this case of order two, is defined by it's two first terms a0 and a1. So, if we know a0 and a1, we can reconstruct one by one, all other terms of this sequence. So the sequence a1 etc. an, is uniquely determined by a0 and a1. Let's show that for any, a0 and a1, there exists C and D such that, a0 = C times lambda to the nth, that is, just C. Plus D times lambda to the nth. For n equals to zero, this is just D as well. For any a0, a1 there exist C and D, such that this is true. That means that. A0 = C + D and a1 = C times lambda + D times mu. So we have a system of two layer equations, With variable C and D. We want to find C and D. And since lambda is not equal to mu, they are not proportional. So this system of equations has a unique solution. Well let us solve it. So for the first equation, this is equivalent to saying that D can be expressed as a0-C, and we use this value of D to say that, a1 = C times lambda + (a0-C) times mu. And from this equation we can find C. C = a1- a0 times mu divided by lambda minus mu. And D is just a0 minus this value. And we can write it in such a way that, D = a0 lambda- mu divided by lambda- mu. Note that the denominator here is not equal to zero, because lambda, mu are distinct. This is where we use this assumption. So we have seen that for arbitrary a0 and a1, C and D are uniquely determined by these values, a0 and a1, and the roots of the characteristic equation. So knowing this, we can reconstruct the whole solution. It will have the form of an = C lambda to the power n + D times mu to the power n. This should be mu. Sorry. Where C and D, are written as follows. [MUSIC]
