In previous post, we used the result of a tile matching puzzle to prove an identity for Fibonacci sequence. Today, we will continue on and prove another identity. We will show that $${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}.$$
In general, we have the following identity $$\sum_{v+u=n}{v \choose u} = F_{n+1}.$$ Through this identity, we will see an interesting connection between the Fibonacci sequence and the Pascal triangle.
But first of all, 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$$
Now let us introduce the notation $n!$. It reads as "$n$ factorial", and its formula is as follows $$n! = 1 \times 2 \times 3 \times \dots \times n.$$
Note that by convention we have $0!=1$ (please do not mistake to $0!=0$.)
Thus, $$0! = 1, ~~ 1! = 1, ~~ 2! = 2, ~~ 3! = 6, ~~ 4! = 24, ~~ 5! = 120, \dots $$
Next, we have the notation ${n \choose k}$. Its formula is $${n \choose k} = \frac{n!}{k! (n-k)!}.$$
For example, we can verify that $${4 \choose 0} = \frac{4!}{0! 4!} = 1, ~~{4 \choose 1} = \frac{4!}{1! 3!} = 4, ~~{4 \choose 2} = \frac{4!}{2! 2!} = 6, ~~{4 \choose 3} = \frac{4!}{3! 1!} = 4, ~~{4 \choose 4} = \frac{4!}{4! 0!} = 1.$$
The notation ${n \choose k}$ reads as "$n$ choose $k$", this is because ${n \choose k}$ is precisely the number of ways to choose $k$ objects (regardless of the ordering) from $n$ given objects. For example, if we are given $4$ fish then there are exactly ${4 \choose 2} = 6$ ways to choose $2$ fish.
 |
| there are exactly ${4 \choose 2} = 6$ ways to choose $2$ fish from $4$ given fish |
The numbers ${n \choose k}$ are the coefficients in the binomial identity expansion. They make up the famous Pascal's number triangle.
If we use the ordering as in the following figure, starting with row 0, then row 1, row 2, ..., and on each row we have the number index 0, then number index 1, number index 2, ... then the number index $k$ on the row $n$ is ${n \choose k}$.
For example, in the above figure, we can see that on row $4$, we have the numbers $1$, $4$, $6$, $4$, $1$, they are exactly the values of ${4 \choose 0}$, ${4 \choose 1}$, ${4 \choose 2}$, ${4 \choose 3}$, ${4 \choose 4}$.
Today we will prove the following identity of Fibonacci sequence $$F_{n+1} = \sum_{v+u=n}{v \choose u}.$$
Let us verify it for a few values of $n$, $$F_1 = {0 \choose 0}, ~~F_2 = {1 \choose 0}, ~~F_3 = {2 \choose 0} + {1 \choose 1}, ~~F_4 = {3 \choose 0} + {2 \choose 1},$$ $$F_5 = {4 \choose 0} + {3 \choose 1} + {2 \choose 2}, ~~F_6 = {5 \choose 0} + {4 \choose 1} + {3 \choose 2},$$ $$F_7 = {6 \choose 0} + {5 \choose 1} + {4 \choose 2} + {3 \choose 3}$$
These equations give us an interesting relation between the Pascal triangle and the Fibonacci sequence. Look at the following figure, if we add up the numbers on the diagonals of the Pascal's triangle then the sums are the Fibonacci's numbers.
Proof of the identity.
If we use the ordering as in the following figure, starting with row 0, then row 1, row 2, ..., and on each row we have the number index 0, then number index 1, number index 2, ... then the number index $k$ on the row $n$ is ${n \choose k}$.
Today we will prove the following identity of Fibonacci sequence $$F_{n+1} = \sum_{v+u=n}{v \choose u}.$$
Let us verify it for a few values of $n$, $$F_1 = {0 \choose 0}, ~~F_2 = {1 \choose 0}, ~~F_3 = {2 \choose 0} + {1 \choose 1}, ~~F_4 = {3 \choose 0} + {2 \choose 1},$$ $$F_5 = {4 \choose 0} + {3 \choose 1} + {2 \choose 2}, ~~F_6 = {5 \choose 0} + {4 \choose 1} + {3 \choose 2},$$ $$F_7 = {6 \choose 0} + {5 \choose 1} + {4 \choose 2} + {3 \choose 3}$$
These equations give us an interesting relation between the Pascal triangle and the Fibonacci sequence. Look at the following figure, if we add up the numbers on the diagonals of the Pascal's triangle then the sums are the Fibonacci's numbers.
 |
| Sum on the diagonal: $F_7 = {6 \choose 0} + {5 \choose 1} + {4 \choose 2} + {3 \choose 3}=13$ |
Proof of the identity.
We will use the tile matching puzzle to prove the identity. Recall that the Fibonacci sequence has a "combinatorial meaning" depicted by the following combinatorial 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$?
 |
| $X_1=1$, $X_2 = 2$, $X_3=3$, $X_4=5$. |
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 can see that if we want to construct a rectangle of size $1 \times n$, then we first need to decide how we are going to construct the first square. There are two cases. We can use a tile sized $1 \times 1$ to construct the first square, or we can use a tile sized $1 \times 2$.
If we use a tile sized $1 \times 1$ to construct the first square then we are left with $n-1$ squares. How many ways to construct the remaining $n-1$ squares? Well, the answer is, there are $X_{n-1}$ ways.
And if we use a tile sized $1 \times 2$ to construct the first square then we are left with $n-2$ squares. How many ways to construct the remaining $n-2$ squares? The answer is $X_{n-2}$.
So, in total, we have $X_{n-1} + X_{n-2}$ number of ways to construct a rectangle of size $1 \times n$. We obtain the following relation $$X_n = X_{n-1} + X_{n-2}.$$
Thus, $$X_1 = 1, ~~X_2 = 2, ~~X_3 = 3, ~~X_4 = 5, ~~X_5 = 8, \dots$$
This means that $$X_n = F_{n+1}.$$
Using this result, our identity becomes $$X_{n} = \sum_{v+u=n}{v \choose u}.$$
This means that $$X_n = F_{n+1}.$$
Using this result, our identity becomes $$X_{n} = \sum_{v+u=n}{v \choose u}.$$
We observe that, if in the construction of a rectangle of size $1 \times n$, we use $v$ tiles, among them there are $u$ tiles of size $1 \times 2$ and $(v-u)$ tiles of size $1 \times 1$, then, by adding up the lengths of the tiles, we obtain the relation $$n = 2 \times u + 1 \times (v-u).$$
This equation is simplified to $$u + v = n.$$
Let us look at the following figure. Suppose that we have $v$ positions for $v$ tiles. Among these $v$ positions, we need to choose $u$ positions for the tiles of size $1 \times 2$. (In the remaining $(v-u)$ positions, we will use tiles of size $1 \times 1$.) It means that we have $v$ "fish", and we need to choose $u$ "fish". How many ways to choose? The answer is, the are ${v \choose u}$ ways to choose.
So the total number of ways to construct a rectangle of size $1 \times n$ is $$\sum_{v+u=n}{v \choose u}.$$
This gives us the identity $$X_{n} = \sum_{v+u=n}{v \choose u}.$$
We have proved the following identity for Fibonacci sequence by using combinatorial method $$F_{n+1} = \sum_{v+u=n}{v \choose u}.$$
For example, with $n=2011$ and $n=2012$, the identity gives us the following interesting equations $${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}.$$
For example, with $n=2011$ and $n=2012$, the identity gives us the following interesting equations $${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}.$$
Let us stop here for now, we will learn more about sequences in the next post. Do you still remember the formula for the Fibonacci sequence? It is $$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$
If you are curious and wondering how it is possible that we can derive such a strange formula, then the next few posts are particular for you. In the next few posts, we are going to learn how to derive a formula for a general sequence. Hope to see you again there.
Homework.
Use the property of the Pascal triangle to give another proof of the identity $$F_{n+1} = \sum_{v+u=n}{v \choose u}.$$