[SOUND] [MUSIC] Here's the definition. Layer recurrence relation, Of order k, Is a sequence defined by the following rule. A(n), Is expressed through the previous k terms of this sequence, in a layer way with constant real coefficients. So A(n) = C1 times A(n- 1) + C2 times A(n- 2) + etc + CkA(n- k). So each term is expressed recursively through the previous ones, through the previous k terms where C1, etc, Ck are just some real numbers. Okay. For example, the Fibonacci sequence, It was defined by the rule F(n) = F(n- 1) + F(n- 2), has order 2. So to express the F number, you need to know only the two previous ones, has. And the Fibonacci sequence we had in our previous problems A(n), it was defined by A(n- 1) + A(n- 2) + A(n- 5). It has order five, not three, because here, A(n) is expressed through the previous five terms. While some of these coefficients might be zero, and in this case, C3 and C4 are zero, but C5 is one, so it has order of 5. Okay, our next remark is that such a sequence is uniquely defined by its first k terms. So if we have a layer recurrence relation, and we know its first k terms, we know the whole sequence. So sequence, Defined by a linear recurrence relation, Is uniquely determined by its first k terms. A(0), A(1), etc, A(k- 1). And if we know them, well, we kind of express Ak, Through this k terms, then knowing Ak and the previous ones, we can express Ak + 1, etc, etc. Why are they called linear? Suppose, we have two sequences satisfying this relation. Suppose, a naught, a1, a2, etc and a naught ', a1', etc., a2', satisfy this relation. Which we denote by star. Then I claim that the sum component wise, sum of these two sequences. Then a naught + a naught prime, a1 + a1', a2 + a2', etc, also satisfies this relation. And so having two sequences, you can consider their sum. And it will be another solution of the same equation. And what else can you do? You can multiply the whole sequence by a given constant. And it will also give another solution of the relation star. And so, So does the sequence C times a naught, C times a1, C times a2, etc. So this means that the solutions of this relation form a vector space. So, The solutions, Of star form at vector space. And this will be a very important property of layer recurrence relations. [SOUND] [MUSIC]