Linear recurrence relations of arbitrary order

Loading...

From the course by National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 оценки

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 оценки

Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed. In the first part of our course we will be dealing with elementary combinatorial objects and notions: permutations, combinations, compositions, Fibonacci and Catalan numbers etc. In the second part of the course we introduce the notion of generating functions and use it to study recurrence relations and partition numbers. The course is mostly self-contained. However, some acquaintance with basic linear algebra and analysis (including Taylor series expansion) may be very helpful.

From the lesson

Linear recurrences. The Fibonacci sequence

We start with a well-known "rabbit problem", which dates back to Fibonacci. Using the Fibonacci sequence as our main example, we discuss a general method of solving linear recurrences with constant coefficients.

Fibonacci’s rabbit problem9:36

Fibonacci numbers and the Pascal triangle7:56

Domino tilings8:26

Vending machine problem10:07

Linear recurrence relations: definition7:53

The characteristic equation8:43

Linear recurrence relations of order 211:02

The Binet formula11:21

Sidebar: the golden ratio9:12

Linear recurrence relations of arbitrary order8:44

The case of roots with multiplicities12:10

Meet the Instructors

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[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]

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play