Today we will learn about Fibonacci sequence and a tile matching puzzle. We will soon see that the tile matching puzzle seems to be unrelated to the Fibonacci sequence, but it turns out that the solution to the puzzle is, in fact, the Fibonacci sequence!
Let us first introduce the Fibonacci sequence. The Fibonacci sequence $\{F_n\}$ is determined by the following rule: $$F_0 = 0, ~F_1 = 1, ~F_{n+1} = F_n + F_{n-1}.$$
Thus, $$F_0 = 0, ~F_1 = 1, ~F_2 = 1, ~F_3 = 2, ~F_4 = 3, ~F_5 = 5, ~F_6 = 8, ~F_7 = 13, ~F_8 = 21, \dots$$
The Fibonacci sequence is probably the most well known sequence in mathematics. We actually can write an explicit formula for it as follows $$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$
Let us verify this formula for a few values of $n$
$$F_0 = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^0 - \left( \frac{1 - \sqrt{5}}{2} \right)^0 \right] = \frac{1}{\sqrt{5}} (1-1) = 0$$ (recall that $a^0$ is equal to $1$, not $0$!!!)
$$F_1 = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^1 - \left( \frac{1 - \sqrt{5}}{2} \right)^1 \right] = \frac{1}{\sqrt{5}} \left[ \frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2} \right] = 1$$
$$F_2 = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^2 - \left( \frac{1 - \sqrt{5}}{2} \right)^2 \right] = \frac{1}{\sqrt{5}} \left[ \frac{6 + 2 \sqrt{5}}{4} - \frac{6 - 2 \sqrt{5}}{4} \right] = 1$$
$$F_3 = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^3 - \left( \frac{1 - \sqrt{5}}{2} \right)^3 \right] = \frac{1}{\sqrt{5}} \left[ \frac{16 + 8 \sqrt{5}}{8} - \frac{16 - 8 \sqrt{5}}{8} \right] = 2$$
The above formula can be proven by many different ways. For instance, it is straightforward to prove it by mathematical induction. Here we will present a simple direct proof by letting $$A_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$ and showing that the two sequences $\{F_n\}$ and $\{A_n\}$ are equal.
To prove that the two sequences $\{F_n\}$ and $\{A_n\}$ are equal, we show that $A_0 = 0$, $A_1 = 1$ and $A_{n+1} = A_n + A_{n-1}$. Obviously, there is exactly one sequence satisfying these conditions, so $\{F_n\}$ and $\{A_n\}$ must be the same sequence.
We have verified above that $A_0 = 0$, $A_1 = 1$, so we only need to show the last condition that $A_{n+1} = A_n + A_{n-1}$. For shorter notation, let $$\alpha = \frac{1 + \sqrt{5}}{2} , ~~ \beta = \frac{1 - \sqrt{5}}{2},$$ and so by definition, $$A_n = \frac{1}{\sqrt{5}} (\alpha^n - \beta^n).$$
We have $$A_{n-1} + A_n = \frac{1}{\sqrt{5}} (\alpha^{n-1} - \beta^{n-1}) + \frac{1}{\sqrt{5}} (\alpha^n - \beta^n)= \frac{1}{\sqrt{5}} (\alpha^{n-1}(1+\alpha) - \beta^{n-1}(1+\beta)).$$
We can check that $\alpha$ and $\beta$ are the two roots of the quadratic equation $x^2 - x - 1=0$, so $1 + \alpha = \alpha^2$ and $1 + \beta = \beta^2$, thus, $$A_{n-1} + A_n = \frac{1}{\sqrt{5}} (\alpha^{n-1} \alpha^2 - \beta^{n-1} \beta^2) = \frac{1}{\sqrt{5}} (\alpha^{n+1} - \beta^{n+1} ) = A_{n+1}.$$
So now we have proven that the two sequences $\{F_n\}$ and $\{A_n\}$ are the same and we have the following formula $$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right].$$
You may be curious and wonder how such a formula can be derived. Is there a method to determine explicit formula for a general sequence? The answer is "yes". If you follow this blog, in the next few posts, we will cover this topic and we will learn how to derive formulas for sequences such as $a_{n+1} = 2 a_n + 5$, $b_{n+1} = 2 b_n - b_{n-1}$, $c_{n+2} = 2 c_{n+1} + c_{n} + 2 c_{n-1}$, etc...
Let us now turn to a tile matching puzzle. Have you ever played a computer game called "Tetris"? This game is a type of tile matching game. In this game, a sequence of random tiles fall down on the playing field. The tiles have many different shapes, some tiles look like letters I, T, L, etc.... The player has to control these falling tiles to make them fit into as many horizontal lines of blocks as possible.
The tile matching puzzle that we consider here is not that complicated compared to the game Tetris. In this puzzle, we are only allowed to use two types of tiles, one has the size of $1 \times 1$ and the other has the size of $1 \times 2$. The question is how many different ways that we can build a rectangle of size $1 \times n$ using these two types of tiles.
A Tile Matching Puzzle: Using two types of tiles of sizes $1 \times 1$ and $1 \times 2$, how many ways we can build a rectangle of size $1 \times n$?
In a previous post, I share with you one of the lessons that I have learned to solve problems, that is, always investigate a problem in some special cases first before tackling it in its general form. Sometimes, investigating special cases can help us gain a greater understanding of the problem. In this tile matching puzzle, we will try some small values $n=1, 2, 3$ first, and then we will solve for a general $n$.
Let us use $X_n$ to denote the number of ways to construct a rectangle of size $1 \times n$ from two types of tiles of sizes $1 \times 1$ and $1 \times 2$. Let us determine the values of $X_1$, $X_2$, $X_3$, etc...
- For $n=1$. How many ways to construct a rectangle of size $1 \times 1$? Obviously, there is only one way, so $X_1 = 1$.
- For $n=2$. How many ways to construct a rectangle of size $1 \times 2$? There are two ways, either by two tiles sized $1 \times 1$, or by one tile sized $1 \times 2$. Thus, $X_2 = 2$.
- For $n=3$. We have three different ways as in the figure below, so $X_3 = 3$.
- For $n=4$. We have five different ways so $X_4 = 5$.
By now, we know how to solve for the general case. To construct a rectangle of size $1 \times n$, we first look at the first square. We can either use a tile sized $1 \times 1$ to cover this square, or we can use a tile sized $1 \times 2$ to cover it.
If we use a tile sized $1 \times 1$ to cover the first square then we have left with $(n-1)$ squares. How many ways to cover the $(n-1)$ remaining squares? It is exactly $X_{n-1}$.
And if we use a tile sized $1 \times 2$ to cover the first square then we have left with $(n-2)$ squares and there are exactly $X_{n-2}$ different ways to cover them.
So in total, we have $X_{n-1} + X_{n-2}$ different ways. So $X_n = X_{n-1} + X_{n-2}$.
We have found the pattern of $X_n$: $$X_1 = 1, X_2 = 2, X_n = X_{n-1} + X_{n-2}.$$
Thus, $$X_1 = 1, ~X_2 = 2, ~X_3 = 3, ~X_4 = 5, ~X_5 = 8, ~X_6 = 13, ~X_7 = 21, \dots$$
We can easily see that $X_n = F_{n+1}$ - the Fibonacci number!!!
In summary, the answer to the puzzle is,
There are exactly $F_{n+1}$ different ways to construct a rectangle of size $1 \times n$ by using two types of tiles sized $1 \times 1$ and $1 \times 2$.
How interesting it is! A tile matching puzzle - on the outset it looks unrelated to Fibonacci numbers, but the solution at last is the exact Fibonacci!
Even more interesting is that, using the result of this tile matching puzzle, we can derive several identities of Fibonacci numbers. In the homework section, we will list a few of them.
Let us stop here for now, we will continue in the next post. Hope to see you then.
Homework.
Using the result of tile matching puzzle to prove the following identities of Fibonacci numbers
$$F_{2n+2} = F_{n+1}^2 + 2 F_{n+1} F_n,$$
$$F_{2n+2} = F_{n+2}^2 - F_n^2,$$
$$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1},$$
$${2011 \choose 0} + {2010 \choose 1} + {2009 \choose 2} + {2008 \choose 3} + \dots + {1007 \choose 1004} + {1006 \choose 1005} = F_{2012},$$
$${2012 \choose 0} + {2011 \choose 1} + {2010 \choose 2} + {2009 \choose 3} + \dots + {1007 \choose 1005} + {1006 \choose 1006} = F_{2013}.$$