[MUSIC] The Fibonacci sequence appears in many combinatorial problems. Okay, to begin with, let me describe one relation of the Fibonacci sequence and the Pascal triangle. So in our previous lectures, we were dealing with a Pascal triangle of binomial coefficients. It was as follows, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, and so on. So this is the Pascal triangle. Okay, we already know what happens if you sum up the entries in each line of the Pascal triangle and what happens if you will look at the shallow diagonals. And well, they're as follows. Say you start with some element here. And then, okay, let's move to the next line, downstairs and to 1 and a half steps left. So from this 1, you get 3. And then from this 3, you get 1 downstairs and 1 and a half to the left, you get this 1. Okay, and similarly, you can start with, Say, this 1 here, 6, 5. And there is a missing 1 in this line, and it is also part of this shallow diagonal. And similarly, you can start with, say, this guy here. Proceed to this 4, and then to 1 up here, or you can, Look at, say, these two entries. They will also form a shallow diagonal, or, This 1 and this 1, or just at the single entries here and there. So what happens if now you sum up all the numbers at this diagonal? So here, we've got 1, I'll draw it in pink. This is also 1. This is 1 plus 1, this is 2. The next diagonal gives you 2 plus 1. This is 3. This is 1 plus 3 plus 1, 5. 3 plus 4 plus 1 is 8. The next diagonal gives you 1 plus 6 plus 5 plus 1. This is 13, so you get exactly the same sequence of numbers, the Fibonacci numbers, as the sums of numbers occurring in shallow diagonals of the Pascal triangle. Okay, and why is it so? So let me write down the explicit formula. So the nth Fibonacci number = the sum of (n- k- 1), choose k. And in this formula, k varies from 0 up to (n- 1) over 2. Okay, and why is it so? Well, this fact is pretty easy. It follows from the combinatorial description of the binomial coefficients that, n choose k = (n- 1 choose k) + (n- 1 choose k- 1). So the sum of each two neighboring elements in one line gives the element which is just below them. Okay, so for instance, what happens if you're summing up all entries in this green diagonal and this pink diagonal? So this 3 is obtained as 1 plus 2. These 4 here, well, 1 is from the pink diagonal, and 2 is from the green one. This 4 here is obtained as the sum of this pink entry, equal to 3, and this green 1. What else, this 1 is just equal to 1 from the previous pink diagonal. So we see that every element is obtained as the sum of something from the previous diagonal, and of something from the diagonal above the previous one. So we see that these sums satisfy the same recurrence relation as the Fibonacci numbers. F(n) = F(n- 1) + F(n- 2). And they satisfy the same initial conditions as the number of rabbits you had during the first two months. So in the first two months, you had only one pair of rabbits. So F(1) is equal to F(2), which is equal to just 1. F(1) = F(2) = 1. And this is exactly the same relation which is satisfied by the sums of the diagonals. [MUSIC]
