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