Linear recurrence relations: definition

Loading...

來自 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.

從本節課中

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

與講師見面

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

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

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取