[MUSIC] So now we know how to find the solutions of a linear recurrence or relation of order two. What happens for an arbitrary order? So, here is our relation, which is already familiar to us. A(n) = c1 A(n-1) +... + cK A(n-k). And we are first looking for geometric progressions which satisfy this relation. So we are looking at geometric progressions satisfying this relation, and we already know that, The geometric progression 1, lambda, lambda squared etc., lambda n, and so on is a solution, Of this relation, star. If and only if lambda is a root of the characteristic equation of this layer occurence. So our characteristic equation looks as follows, t to the power of k is c1 t to the power of k minus 1 plus etc. plus Ck. So this is a polynomial of degree k which has at most K roots. Suppose that we are lucky and that all these roots are distinct. And these roots are lambda 1 etc., lambda k. Okay, then we know that our linear recurrence relation has a general solution an. Which is the layer combination of geometric operations with common ratios, lambda 1, etc, lambda k, and arbitrary coefficients. So an = c1 * lambda1 to the power n. Plus C2 lambda 2 to the power N plus etc plus CK lambda K to the power N. And this is the general solution. Now suppose that we are looking for the solution with some given, initial conditions. Suppose that we are given a nought, etc., ak minus 1. And we want to find c1, c2, etc., ck, such that from 0 to k minus 1, all these equalities hold. So we are looking for a solution with these initial conditions. So we need to solve a system of linear equations. So, a0 = c1 + c2 +... ck. a1 is C1 lambda 1, plus C2 lambda 2. Plus etc... plus CK, lambda K and so on. Up to a k-1, which is C1 lambda 1 to the power of k minus 1. Plus C2 lambda 2 to the power of k minus 1, plus etc. Plus Ck lambda k to the power of k-1. And all lambdas are distinct. And then we need to use some linear algebra. Which says that a system of equations with k equations and k unknown variables. Has a unique solution if and only if its matrix is nondegenerate. So the determinant or the system of equations must be non-zero. And let us look at this determinant. And matrix 1, 1 etc., [INAUDIBLE] 1 lambda 1. So in the first row we have row 1s. In the second row we have lambdas. And the third row we their squares. Lambda 1 squared, lambda 2 squared, lambda k squared, and etc. Until the last row which is lambda 1 to the power of k -1 etc. to the lambda k to the power k-1. And this is a well known fact from linear algebra. That this determinant, which is called the Vandermonde determinant Is equal to the product of lambda (I- lambda) J, for all i > j between 1 and k. So here we have k times k- 1 over two factors. And so if all lambdas are distinct then this determinant is also nonzero. So the system has a unique solution, and the solution of linear recurrence relations with given initial conditions is unique. [SOUND]