The Binet formula

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]

Let's consider a couple of examples.

So example one.

Suppose we have a recurrence relation,

A(n) = 5A(n-

1)- 6A(n- 2).

And suppose that we want to find a sequence satisfying certain initial

conditions.

Find a solution,

Satisfying, The following initial conditions.

A0 = 3, and a1 = 7.

Okay, how to solve this?

Let's write down the characteristic equation of this.

Recurrence relation.

So we know that it should have

form t squared = 5t- 6.

Or alternatively, it can be written down as t squared- 5t + 6 = 0.

So the solutions are 2 and 3.

So lambda = 2, mu = 3.

These are roots of this quadratic equation.

So this means that, since we know the roots of the characteristic equation,

we know that general solution of this relation.

It is,

an = C times 2 to the power n.

(lambda's to the power n) + D times 3 to the power n.

Okay, and what we want to do now is we want to find

such C and D that this solution satisfies this, these initial conditions.

To find such C and D, we can use either the general formulas or

we can solve this system again for these concrete values.

Well, maybe the second option is simpler, so let's do this.

So we know that [COUGH],

a0 = 3, and

this is just C + D.

And a1 = 7, it is 2C,

+ 3D.

So we solve this system of equations and

we get C = 2 and D = 1.

So 2 + 1 = 3 and (2 times 2) + 3 = 7.

Okay, so the solution we're looking for

is an = 1 times (2 to the power n).

This makes (2 to the power n + 1)

+ D = 1 + (3 to the power of n).

Okay, so this was our first example.

And our second example, a much more interesting one is the Fibonacci sequence,

the first recurrence relation we started with.

So example two,

The Fibonacci sequence.

In this case, we know that

F(n) = F(n- 1) + F(n- 2).

The initial conditions for the Fibonacci

sequence are f0 = 0, and f1 = 1.

So in the first month,

you had one pair of rabbits, and before that you had no rabbits at all.

So well, We start our Fibonacci sequence from 0.

Okay, so what about the solution

of this recurrence satisfying these initial conditions?

Again, we can do the same and write down the characteristic equation,

t squared = t + 1.

So this means that t squared- t- 1 = 0.

The coefficients, the roots of this equation, are not

that nice as the roots of this equation anymore, they're not rational.

Let us note them by phi and psi.

Phi = 1 + (square root of 5) divided by 2,

and psi = 1- (square root of 5) divided by 2.

So here they are.

So our general solution of this sequence,

satisfying this particular relation,

has the form fn = C times (phi to the power n)

+ D times (phi to the power of n).

Okay, and we are looking for these initial conditions.

So we know that phi 0 = 0, so, f0 = 0.

So 0 = C + D.

What happens if n = 0?

So this is just C, and this is just D.

And if you take n = 1,

you get (C times phi) +

(D times psi) = 1.

Okay, so from the first equation,

we see that D = -C, and

1 = C times (phi- psi).

So C = 1 over (phi- psi) and

D = 1 over (psi- phi).

The same thing but with the negative sign.

Okay, and if we take these values again we see that,

C = 1 over the square root of 5, and

D = minus 1 over square root of 5.

So what we get is the explicit formula for the nth Fibonacci number.

So we have found those C and D.

And we see that Fn,

Can be computed as follows.

This is (phi to the nth- psi to

the nth) divided by (phi- psi).

And this is nothing but 1 over the square

root of 5 times the following thing.

Phi to the nth = ((1 + the square

root of 5) over 2) to the power n.

And -psi to the power n, which is ((1- the square root

of 5) divided by 2)), also the power n.

This formula allows us to find explicitly the nth Fibonacci number,

without computing all the previous ones.

So fn can be can be obtained

as the sum of two geometric

progressions, this way.

This is called the Binet Formula.

And well, I think this is something really amazing.

Because when you're looking at this multiplier with radicals and

with the power n, well of course, you think this must be irrational.

But it turns out that it is not only rational, it is always an integer for

an arbitrary n and moreover it gives the nth for the Fibonacci number

[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