[MUSIC] One more combinatorial interpretation of Fibonacci numbers is as follows. Suppose you have a rectangle of size 2 times n. And you want to cover it with domino tiles of size 1 times 2. And these tiles can be arranged horizontally or vertically. Okay, so the question is, in how many ways can you cover this rectangle by domino tiles? Let's say, You can do something like this. [COUGH] Okay, say, if you have a rectangle of size 2 times 3. Well, you can split it into domino tiles in three ways. Well, here they are. And what is the answer for arbitrary n? For n = 3, there are 3 tilings. So what happens for n = 2? There are just two of them. And for n = 1, the problem is trivial. There is just one domino tile. So what happens for an arbitrary n? The answer is as follows. That number of tilings of this rectangle 2 times n, Is equal to the Fibonacci number. Number of tilings of 2 x n rectangle is equal to the Fibonacci number, but not the nth one. You need to shift it by 1, F(n+1) as you see on this example. Okay, why is it so? Here's the explanation. Suppose, That we have a tiling of a rectangle. And let's take the upper left corner. And it is covered by some domino. And there are two possibilities. It can be either, Covered by vertical domino like this. And in this case, the remaining part is a rectangle of size 2x(n-1). Or it can be covered horizontally. This means that just below it, you also need to have a horizontal tile. And the remaining part of the rectangle is a smaller rectangle of size 2x(n-2). So each tiling is either of this type or of that type. So you see that, again, the number of tilings satisfies the same relation. So if you denote the number of tilings by T(n), then T(n) = T(n-1), which corresponds to this case. So you put one domino and you need to cover the remaining part, +T(n-2). First you put these two dominoes horizontally. And then you need to cover the remaining part. And you can do it in this many ways. And the only difference from the Fibonacci sequence are the initial conditions. So we have already seen that T(1) = 1, and T(2) = 2. So T(3) will be 3, T(4) will be 5, etc., etc. So you see that in this case, T(n) will be equal to the Fibonacci number F(n+1). Okay, and alternatively, you can look at this in the following way that, The number F(n+1), Is the number of ways. F(n+1) is the number of presentations of the number n as a sum of 2's and 1's. So is the number of ways, Of presenting, n as a sum of 1's and 2's. Where the order is important, so, Say, 1+2 and 2+1 are different presentations. These are different compositions. Their relation with this description is obvious. So having a tiling, you can construct such a presentation. Say, if you have a vertical tile, you replace it by sum of the 1. And if you have a pair of horizontal tiles, you replace it by 2. So here in this case, we have 1+2+1+1. These two guys are vertical. These are horizontal. So you have 2+1, and this gives you, This gives you such a presentation of the number 8. Okay, this description will be generalized in our next example. [MUSIC]