[MUSIC] So, now we know how to write down all the solutions of their recurrence relation provided that all roots of the characteristic polynomial are distinct. But what happens if some of these roots occur with multiplicities? What if, Some roots, Of the characteristic polynomial Occur with multiplicities. Let us first discuss the case of order two. So suppose that A(n) = c1A(n-1) + C2A(n-2). So A(n) = c1A(n-1)+c2A(n-2), and the characteristic equation looks as follows, t squared- c1t- c2 = 0. Suppose that it has a double root. That means that the discriminate of this quadratic equation is zero. Suppose that lambda is a unique, This means double, Root of this equation. So this means that -c2 = lambda squared, and that c1 = 2 lambda. So our equation has the form of (t- lambda) squared = t squared- c1t- c2, okay. So in this case we have one solution of this linear recurrent relation, which is the geometric progression 1, lambda, lambda squared, etc., lamb n, is a solution. But this is a unique geometric progression satisfying this relation, because the root is unique. And we would like to have two linearly independent sequences of which would be solutions of this relation. So we need to have one more and it is not a geometric progression anymore. But it turns out that in this case we need to cook up another sequence, also with lambda, but it will look as follows, 0, Lambda, 2 lambda squared, 3 lambda to the third, etc., n times lambda to the power n. And we claim that this is also a solution. Well indeed, let us take n times lambda to the power n, as A(n). And let us show that this equality is indeed satisfied. So we have n times lambda to the power n is equal to c1. So we need to show this, so that n times lambda to the power n = c1(n- 1) times lambda to the power n-1 + c2(n-2). Times lambda to the power n- 2. Okay, and we already know how to express c1 and c2 through lambda. So, this is the same thing as n times lambda to the power n, is, so this is proof of the claim. So we need to show that n times lambda to the power n = 2 lambda(n-1) times lambda to the power n-1 + (- lambda squared)(n-2) times lambda to the power n-2. Okay, so you see that both sides of this equation are divisible by lambda to the power n. And if we divide by lambda to the power n we get just n = 2(n-1), Minus (n-2). And this is indeed true. So our sequence is indeed a solution of this recurrence relation. And so we have another solution linearly independent from this one. So in this case the general solution. Looks as follows, it is an = c1 x lambda to the power n + c2 x n x lambda to the power n, where, c1 and c2 are arbitrary coefficients. And if you want to find a sequence satisfying some given initial conditions, well you need to solve a similar system of equations, and this is done absolutely as in the previous case. Then well, to conclude let me say a couple of words about the general situation about the equations of order k. So what happens if lambda is a root of the characteristic polynomial with multiplicity r. So for general, Linear recurrence relations, Of higher order. If, lambda is a root of the characteristic equation, Of order, let's say r. That means that the characteristic equation is divisible by the characteristic polynomial. Is divisible, By t- lambda to the power r. In this case, you have r linearily independent solutions, which are, Our geometric progression, lambda to the power n. Then we have 0 Lambda, 2 lambda squared, etc., n x lambda to the power n. And then you need to take the powers of n as coefficients in front of lambda. Then we take 0, lambda, 4 lambda squared, 9 lambda to the 3rd, etc., n squared lambda to the power n and so on. And then we proceed with taking 3rd powers of n, etc., etc., until for each 0, lambda, 2 to the power r-1 lambda squared, etc., n to the power r-1 lambda to the power n. So, these will be our linearily independent sequences, which will form our solutions corresponding to this root, lambda of multiplicity r. And the generic solution is obtained as a linear combination of such solutions for all roots taken with corresponding multiplicities. In our fifth lecture we will study generating functions and we'll apply the method of generating functions to solving linear recurrences. So, we'll obtain another method of finding solutions of the problem we considered today, thank you. [MUSIC]
