Linear recurrence relations of order 2

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]

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]

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

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

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

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

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

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