In previous post, we have learnt about Fibonacci sequence and a tile matching puzzle. Today, we will use the result of the tile matching puzzle to prove the following identity on Fibonacci sequence $$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1}.$$
Like an art painting, a mathematical problem reflects different beauties if we view it at different angles. Take, for example, the Fibonacci identity that we are considering, we can prove this identity by different methods. One method is to use the 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]$$ to calculate the two sides of the identity and make them equal by straightforward algebraic manipulations. Another method is to make use of the tile matching puzzle that we learned in the previous post. I hope that you will find this "combinatorial" method more interesting.
Let us recall that the Fibonacci sequence is the sequence determined by the following rule: $$F_0 = 0, ~F_1 = 1, ~F_{n+1} = F_n + F_{n-1},$$ and 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$$
Let us verify the identity $$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1}$$ for a few values of $n$ and $m$,
- With $n=0$, $m=0$, the identity is $$F_{2} = F_{1} F_{1} + F_{1} F_0 + F_0 F_{1}$$ we can see that both sides are equal to $1$.
- With $n=1$, $m=0$, $$F_{3} = F_{2} F_{1} + F_{2} F_0 + F_1 F_{1} = 2.$$
- With $n=2$, $m=1$, $$F_{5} = F_{3} F_{2} + F_{3} F_1 + F_2 F_{2} = 5.$$
The Fibonacci numbers have a "combinatorial meaning" depicted by the following tile matching puzzle
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$?
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$. We will show that $X_n = F_{n+1}$.
For example, with $n=1,2,3,4$, we have $X_1 = F_2 = 1$, $X_2 = F_3 = 2$, $X_3 = F_4 = 3$, $X_4 = F_5 = 5$ as illustrated by the following figure.
For example, with $n=1,2,3,4$, we have $X_1 = F_2 = 1$, $X_2 = F_3 = 2$, $X_3 = F_4 = 3$, $X_4 = F_5 = 5$ as illustrated by the following figure.
 |
| $n=4$: there are 5 ways to construct a rectangle of size $1 \times 4$ from two types of tiles sized $1 \times 1$ and $1 \times 2$. |
For the general case, in order to construct a rectangle of size $1 \times n$, we first need to decide how we are going to construct the first square. We can either cover the first square by a tile sized $1 \times 1$, 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 are left with $(n-1)$ squares. How many ways can we cover these $(n-1)$ remaining squares? There are exactly $X_{n-1}$ ways.
And if we use a tile sized $1 \times 2$ to cover the first square then we have $X_{n-2}$ ways to cover the remaining $n-2$ squares.
Thus, in total, we have $X_{n-1} + X_{n-2}$ ways to construct a rectangle of size $1 \times n$. It means that $$X_n = X_{n-1} + X_{n-2}.$$
Therefore, $$X_1 = 1, ~X_2 = 2, ~X_3 = 3, ~X_4 = 5, ~X_5 = 8, ~X_6 = 13, ~X_7 = 21, \dots$$
This is $X_n = F_{n+1}$ - the Fibonacci numbers!!!
Now we will present two combinatorial proofs for the following Fibonacci identity $$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1}.$$
In term of the tile matching puzzle, we need to show the following equivalent identity $$X_{n+m+1} = X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}.$$
The first proof.
We consider the question "How many ways can we construct a rectangle of size $1 \times (n+m+1)$ as in the following figure?"
The straight answer is, there are $X_{n+m+1}$ ways to construct a rectangle of size $1 \times (n+m+1)$.
Now, let us derive the answer by another way. Let us focus on the $n+1$-th square and consider three different scenarios.
Now, let us derive the answer by another way. Let us focus on the $n+1$-th square and consider three different scenarios.
In the first scenario, we will cover the $n+1$-th square by a tile of size $1 \times 1$. On the left of this square, we have $X_n$ ways to cover the rectangle of size $1 \times n$, and on the right, we have $X_m$ ways to cover the rectangle of size $1 \times m$. So in this case, we have in total $X_{n} X_{m}$ ways.
In the second scenario, we will cover the $n+1$-th square by a tile of size $1 \times 2$. On the left, we have $X_n$ ways to cover the remaining $n$ squares, and on the right, we have $X_{m-1}$ ways to cover the remaining $(m-1)$ squares. So in this case, in total, we have $X_{n} X_{m-1}$ ways.
Similarly, in the last scenario, we have $X_{n-1} X_{m}$ ways.
So we have in total $X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}$ ways to construct a rectangle of size $1 \times (n+m+1)$. Thus, we have established the required identity $$X_{n+m+1} = X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}.$$
The second proof.
The identity $$X_{n+m+1} = X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}$$ is equivalent to $$X_{n+m+1} = X_{n} X_{m+1} + X_{n-1} X_{m}.$$
We prove this equivalent identity by considering the question "How many ways can we construct a rectangle of size $1 \times (n+m+1)$ as in the following figure?"
Again, the straight answer is $X_{n+m+1}$.
Let us derive the answer by another way. Consider the "ditch" between the first $n$ squares and the last $m+1$ squares. There are two cases. In the first case, this ditch is not covered by any tile. In the second case, this ditch is covered by a tile sized $1 \times 2$.
In the second scenario, we will cover the $n+1$-th square by a tile of size $1 \times 2$. On the left, we have $X_n$ ways to cover the remaining $n$ squares, and on the right, we have $X_{m-1}$ ways to cover the remaining $(m-1)$ squares. So in this case, in total, we have $X_{n} X_{m-1}$ ways.
Similarly, in the last scenario, we have $X_{n-1} X_{m}$ ways.
So we have in total $X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}$ ways to construct a rectangle of size $1 \times (n+m+1)$. Thus, we have established the required identity $$X_{n+m+1} = X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}.$$
The second proof.
The identity $$X_{n+m+1} = X_{n} X_{m} + X_{n} X_{m-1} + X_{n-1} X_{m}$$ is equivalent to $$X_{n+m+1} = X_{n} X_{m+1} + X_{n-1} X_{m}.$$
We prove this equivalent identity by considering the question "How many ways can we construct a rectangle of size $1 \times (n+m+1)$ as in the following figure?"
Again, the straight answer is $X_{n+m+1}$.
Let us derive the answer by another way. Consider the "ditch" between the first $n$ squares and the last $m+1$ squares. There are two cases. In the first case, this ditch is not covered by any tile. In the second case, this ditch is covered by a tile sized $1 \times 2$.
In the first case, we have $X_{n} X_{m+1}$ ways, and in the second case, we have $X_{n-1} X_{m}$ ways. So in total we have $X_{n} X_{m+1} + X_{n-1} X_{m}$ ways. Thus, we obtain the identity $$X_{n+m+1} = X_{n} X_{m+1} + X_{n-1} X_{m}.$$
We have now two combinatorial proofs of the identity $$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1}.$$
Let $m=n$ we obtain the identity $$F_{2n+2} = F_{n+1}^2 + 2 F_{n+1} F_n.$$
From here, we have $$F_{2n+2} = (F_{n+1} + F_n)^2 - F_n^2$$ and thus derive another identity $$F_{2n+2} = F_{n+2}^2 - F_n^2.$$
Let us stop here for now, we will continue with another Fibonacci identity in the next post. Hope to see you again then.
Homework.
1. Use the 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]$$ to prove the following identities
$$F_{n+m+2} = F_{n+1} F_{m+1} + F_{n+1} F_m + F_n F_{m+1},$$
$$F_{2n+2} = F_{n+2}^2 - F_n^2.$$
$$F_{2n+2} = F_{n+2}^2 - F_n^2.$$
2. Use the result of the tile matching puzzle to establish other identities for Fibonacci sequence.
