Fibonacci’s rabbit problem

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]

Hi, and welcome back to Introduction to Enumerative Combinatorics.

This is lecture three, it is entitled Layer Recurrence Relations.

Let us talk with a fully motivating example which is more than 800 years old.

It is the famous Fibonacci's problem about rabbits.

This problem first appeared in the book of Leonardo Finonacci,

it was called the Book of the Abacus, Liber Abaci.

It was written more than 800 years ago

in 1202 by a Leonardo from Pisa,

Known as Fibonacci.

Okay, the problem is as follows.

Suppose that someone gave you a pair of baby rabbits, a boy and a girl.

So, here they are,

Two nice bunnies and they,

after one month they are fully grown up and,

After one month they start to give birth to other rabbits.

And in the first month you had a pair of baby rabbits,

and in the second month they're fully grown up.

And suppose that's every month a pair of adult

rabbits gives birth to another pair of rabbits.

Again, a boy and a girl, that's pretty unrealistic, but suppose that's true.

Okay, so in the third month you're going to have another,

well, you going to have your,

Initial pair of rabbits and

they will give birth to another two small bunnies.

So you will have two pairs of rabbits.

So, during the first and the second month you had only one pair.

Okay, and what happens next?

Every year, a pair of adult rabbits gives birth to another pair,

so during the fourth month you will

have, This pair again.

You will have the second pair, which is now also fully grown and

you will have another pair of baby rabbits, children of these two.

So, during the fourth month you will have three pairs.

The question is if we proceed and

this way, how many pairs of rabbits

are going to have after a year?

So what will happen on the 12th set?

Okay, you see that this number grows pretty rapidly.

So during the fifth month it will have these fives pairs and

another two pairs of rabbits, which are chilling on these two pairs.

So there will be five pairs of rabbits at the fifth month,

and okay, I'm not going to draw them.

Okay, so, What does this sequence look like?

How does it behave?

Okay, the general rule is pretty simple and it is as follows.

Denote the number of rabbits which you are going

to have during the nth month by F(n).

F stands for Fibonacci.

So, notation.

F(n) is the number of pairs of rabbits.

You'll have here in the nth month.

So how can we express F(n) through

the previous, as of F(n)?

Okay, so let's take the fifth step.

How many rabbits are we going to have at the fifth step?

So you will have these three pairs, which will be now adults.

And we will have two more pairs, which will be children of the adult rabbits,

of the rabbits which were adults in the previous month.

So, and this number is equal to the number of rabbits at the previous step.

So F(n) is equal to the sum of F(n-1).

This is the number of rabbits at the previous step.

And the number of newly born pairs of rabbits and

this number is equal to the number of adult pairs you had on the previous step.

And this is in turn equal to the number of

pairs of rabbits at the step n minus 2,

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

Okay, and we also know that during the first and

the second month you had only one pair.

So F(1)=F(2)=1, and

these are the initial conditions.

Okay, so if we have this rule, now we can compute the sequence.

And this sequence looks as follows.

It is also known as the Fibonacci Sequence.

So it is 1, 1, then the third,

The third number will be the sum of 1 and 1, 2,

then each next number will be the sum of the previous two.

So, it will be 3,

then 3 plus 2, 5,

5 plus 3 is equal to 8,

8 plus 5 is 13,

then 21, 36, 55,

89, and then 144,

and this is F(12).

So this is the answer to Fibonacci's Problem.

So after one year he will have to

have 144 pairs of rabbits and

this is quite a lot.

[SOUND]

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

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

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

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

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

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