The case of roots with multiplicities

Loading...

From the course by National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

55 ratings

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

55 ratings

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 write down all the solutions of their recurrence

relation provided that all roots of the characteristic polynomial are distinct.

But what happens if some of these roots occur with multiplicities?

What if, Some roots,

Of the characteristic polynomial

Occur with multiplicities.

Let us first discuss the case of order two.

So suppose that A(n) = c1A(n-1) + C2A(n-2).

So A(n) = c1A(n-1)+c2A(n-2),

and the characteristic

equation looks as follows,

t squared- c1t- c2 = 0.

Suppose that it has a double root.

That means that the discriminate of this quadratic equation is zero.

Suppose that lambda is a unique,

This means double, Root of this equation.

So this means that -c2

= lambda squared, and

that c1 = 2 lambda.

So our equation has the form

of (t- lambda) squared =

t squared- c1t- c2, okay.

So in this case we have one solution of this linear recurrent relation,

which is the geometric progression 1, lambda,

lambda squared, etc., lamb n, is a solution.

But this is a unique geometric progression satisfying this relation,

because the root is unique.

And we would like to have two linearly independent

sequences of which would be solutions of this relation.

So we need to have one more and

it is not a geometric progression anymore.

But it turns out that in this case we need to cook up another sequence,

also with lambda, but it will look as follows,

0, Lambda,

2 lambda squared, 3 lambda to the third,

etc., n times lambda to the power n.

And we claim that this is also a solution.

Well indeed, let us take n times

lambda to the power n, as A(n).

And let us show that this equality is indeed satisfied.

So we have n times lambda to the power n is equal to c1.

So we need to show this,

so that n times lambda to

the power n = c1(n- 1)

times lambda to the power

n-1 + c2(n-2).

Times lambda to the power n- 2.

Okay, and we already know how to express c1 and c2 through lambda.

So, this is the same thing as n times lambda to the power n,

is, so this is proof of the claim.

So we need to show that n times

lambda to the power n = 2

lambda(n-1) times lambda

to the power n-1 + (- lambda

squared)(n-2) times

lambda to the power n-2.

Okay, so you see that both sides of this equation

are divisible by lambda to the power n.

And if we divide by lambda to the power

n we get just n = 2(n-1),

Minus (n-2).

And this is indeed true.

So our sequence is indeed a solution of this recurrence relation.

And so we have another solution

linearly independent from this one.

So in this case the general solution.

Looks as follows, it is an =

c1 x lambda to the power n +

c2 x n x lambda to the power n,

where, c1 and

c2 are arbitrary coefficients.

And if you want to find a sequence

satisfying some given initial conditions,

well you need to solve a similar system of equations,

and this is done absolutely as in the previous case.

Then well, to conclude let me say a couple of words about

the general situation about the equations of order k.

So what happens if

lambda is a root of the characteristic polynomial with multiplicity r.

So for general,

Linear recurrence relations, Of higher order.

If, lambda is

a root of the characteristic equation,

Of order, let's say r.

That means that the characteristic equation

is divisible by the characteristic polynomial.

Is divisible, By t- lambda to the power r.

In this case, you have r linearily independent solutions, which are,

Our geometric progression, lambda to the power n.

Then we have 0 Lambda, 2 lambda squared,

etc., n x lambda to the power n.

And then you need to take the powers of n as coefficients in front of lambda.

Then we take 0, lambda, 4 lambda squared,

9 lambda to the 3rd, etc.,

n squared lambda to the power n and so on.

And then we proceed with taking 3rd powers of n,

etc., etc., until for each 0, lambda,

2 to the power r-1 lambda squared, etc.,

n to the power r-1 lambda to the power n.

So, these will be our linearily independent sequences,

which will form our solutions corresponding

to this root, lambda of multiplicity r.

And the generic solution is obtained as a linear combination of such solutions for

all roots taken with corresponding multiplicities.

In our fifth lecture we will study generating functions and

we'll apply the method of generating functions to solving linear recurrences.

So, we'll obtain another method of finding solutions

of the problem we considered today, thank you.

[MUSIC]

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play