We know that the binomial coefficient {n \choose k} defined by {n \choose k} = \frac{n!}{k! (n-k)!}From this definition, we can derive the Pascal's Identity as shown below:
The Pascal's Identity
For any two positive integers with k \le n, we see that {n \choose k-1} + {n \choose k} = {n+1 \choose k}Proof:
Let us take the Left-hand Side (L.H.S.) expression and derive the Right-hand Side (R.H.S.) expression.\begin{eqnarray} L.H.S &=& \frac{n!}{(k-1)! (n-(k-1))!} + \frac{n!}{k! (n-k)!} \nonumber \\ \quad & =& \frac{n! \times k}{k! (n-k+1)!} +\frac{n! \times (n-k+1)}{k! (n-k+1)!} \nonumber \\ \quad &=&\frac{n!}{k! (n-k+1)!} (k + n-k+1) \nonumber \\ \quad &=& \frac{n! (n+1)}{k! (n+1-k)!} \nonumber \\ \quad &=& \frac{(n+1)!}{k! ((n+1)-k)!} \nonumber \\ \quad &=& {n+1 \choose k} \nonumber \\ \quad &=& R.H.S \nonumber \end{eqnarray}
The following diagram illustrates how the Fibonacci numbers are related to Pascal Triangle:
We know that k^{th} row in Pascal's triangle has k+1 elements and are nothing but the binomial coefficients k \choose 0, k \choose 1, k \choose 2, \ldots, k \choose k-1, and k \choose k.
Let us consider the sum of the elements of Pascal Triangle across the arrows and denote n^{th} sum by P_n. We see that \begin{eqnarray} P_1 &=& {0 \choose 0} = 1 \nonumber \\ P_2 &=& {1 \choose 0} =1 \nonumber \\ P_3 &=& {2 \choose 0} + {1 \choose 1} = 1+ 1 = 2 \nonumber \\ P_4 &=& {3 \choose 0} + {2 \choose 1} =1 + 2= 3 \nonumber \\ P_5 &=& {4 \choose 0} +{3 \choose 1} + {2 \choose 2} = 1 + 3+1 = 5 \nonumber \\ P_6 &=& {5 \choose 0} + {4 \choose 1} + {3 \choose 2}= 1+ 4 + 3= 8 \nonumber \\ P_7 &=& {6 \choose 0} + {5 \choose 1} + {4 \choose 2} + {3 \choose 3} = 1 + 5 + 6+ 1 = 13 \nonumber \\ P_8 &=& {7 \choose 0} + {6 \choose 1} + {5 \choose 2} + {4 \choose 3} = 1 + 6 + 10+1 = 18 \nonumber \\ \end{eqnarray} From the above illustration, we can observe that P_{n+1} = \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} {n-k \choose k}, \forall n \ge 0. By Pascal's Identity, {(n+1)-k \choose k} = {n-k \choose k} + {n-k \choose k-1}Thus, we see that
The Pascal's Identity
For any two positive integers with k \le n, we see that {n \choose k-1} + {n \choose k} = {n+1 \choose k}Proof:
Let us take the Left-hand Side (L.H.S.) expression and derive the Right-hand Side (R.H.S.) expression.\begin{eqnarray} L.H.S &=& \frac{n!}{(k-1)! (n-(k-1))!} + \frac{n!}{k! (n-k)!} \nonumber \\ \quad & =& \frac{n! \times k}{k! (n-k+1)!} +\frac{n! \times (n-k+1)}{k! (n-k+1)!} \nonumber \\ \quad &=&\frac{n!}{k! (n-k+1)!} (k + n-k+1) \nonumber \\ \quad &=& \frac{n! (n+1)}{k! (n+1-k)!} \nonumber \\ \quad &=& \frac{(n+1)!}{k! ((n+1)-k)!} \nonumber \\ \quad &=& {n+1 \choose k} \nonumber \\ \quad &=& R.H.S \nonumber \end{eqnarray}
The following diagram illustrates how the Fibonacci numbers are related to Pascal Triangle:
Relationship of Fibonacci Numbers to Pascal Triangle |
Let us consider the sum of the elements of Pascal Triangle across the arrows and denote n^{th} sum by P_n. We see that \begin{eqnarray} P_1 &=& {0 \choose 0} = 1 \nonumber \\ P_2 &=& {1 \choose 0} =1 \nonumber \\ P_3 &=& {2 \choose 0} + {1 \choose 1} = 1+ 1 = 2 \nonumber \\ P_4 &=& {3 \choose 0} + {2 \choose 1} =1 + 2= 3 \nonumber \\ P_5 &=& {4 \choose 0} +{3 \choose 1} + {2 \choose 2} = 1 + 3+1 = 5 \nonumber \\ P_6 &=& {5 \choose 0} + {4 \choose 1} + {3 \choose 2}= 1+ 4 + 3= 8 \nonumber \\ P_7 &=& {6 \choose 0} + {5 \choose 1} + {4 \choose 2} + {3 \choose 3} = 1 + 5 + 6+ 1 = 13 \nonumber \\ P_8 &=& {7 \choose 0} + {6 \choose 1} + {5 \choose 2} + {4 \choose 3} = 1 + 6 + 10+1 = 18 \nonumber \\ \end{eqnarray} From the above illustration, we can observe that P_{n+1} = \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} {n-k \choose k}, \forall n \ge 0. By Pascal's Identity, {(n+1)-k \choose k} = {n-k \choose k} + {n-k \choose k-1}Thus, we see that
\begin{eqnarray} P_{n+2} &=& \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor} {(n+1)-k \choose k} \nonumber \\ \quad &=& {n+1 \choose 0} + \sum_{k=1}^{\left \lfloor \frac{n+1}{2} \right \rfloor} {(n+1)-k \choose k} \nonumber \\ \quad &=& 1+ \sum_{k=1}^{\left \lfloor \frac{n+1}{2} \right \rfloor} {n-k \choose k} + \sum_{k=1}^{\left \lfloor \frac{n+1}{2} \right \rfloor} {n-k \choose k-1} \nonumber \\ \quad &=& {n-0 \choose 0} + \sum_{k=1}^{\left \lfloor \frac{n+1}{2} \right \rfloor} {n-k \choose k} + \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor -1} {n-(k+1) \choose k} \nonumber \\ \quad &=& \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor}{n-k \choose k} + \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor -1} {(n-1)-k \choose k} \nonumber \end{eqnarray}Now, we consider two possible cases for n.
Case 1: n is even
If n is even, then n+1 is odd, and hence \left \lfloor \frac{n+1}{2} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor = \frac{n}{2}.Also, note that n-1 is odd, and hence \left \lfloor \frac{n+1}{2} \right \rfloor - 1 = \frac{n}{2} -1 = \frac{n-2}{2} = \left \lfloor \frac{n-1}{2} \right \rfloor.Thus,
\begin{eqnarray} P_{n+2} &=& \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor} {n-k \choose k} + \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor -1}{(n-1)-k \choose k} \nonumber \\ \quad &=& \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}{n-k \choose k}+\sum_{k=0}^{\left \lfloor \frac{n-1}{2} \right \rfloor}{(n-1)-k \choose k} \nonumber \\ \quad &=& P_{n+1} + P_{n} \nonumber \\ \end{eqnarray} Case 2: n is odd.
If n is odd, then both n-1 and n+1 are even. Hence, we observe that \left \lfloor \frac{n+1}{2} \right \rfloor - 1= \frac{n+1}{2} -1 = \frac{n-1}{2} = \left \lfloor \frac{n-1}{2} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor .Thus,
Case 1: n is even
If n is even, then n+1 is odd, and hence \left \lfloor \frac{n+1}{2} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor = \frac{n}{2}.Also, note that n-1 is odd, and hence \left \lfloor \frac{n+1}{2} \right \rfloor - 1 = \frac{n}{2} -1 = \frac{n-2}{2} = \left \lfloor \frac{n-1}{2} \right \rfloor.Thus,
\begin{eqnarray} P_{n+2} &=& \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor} {n-k \choose k} + \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor -1}{(n-1)-k \choose k} \nonumber \\ \quad &=& \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}{n-k \choose k}+\sum_{k=0}^{\left \lfloor \frac{n-1}{2} \right \rfloor}{(n-1)-k \choose k} \nonumber \\ \quad &=& P_{n+1} + P_{n} \nonumber \\ \end{eqnarray} Case 2: n is odd.
If n is odd, then both n-1 and n+1 are even. Hence, we observe that \left \lfloor \frac{n+1}{2} \right \rfloor - 1= \frac{n+1}{2} -1 = \frac{n-1}{2} = \left \lfloor \frac{n-1}{2} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor .Thus,
\begin{eqnarray} P_{n+2} &=& \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor} {n-k \choose k} + \sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor -1} {(n-1)-k \choose k} \nonumber \\ \quad &=& \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor + 1} {n-k \choose k} + \sum_{k=0}^{\left \lfloor \frac{n-1}{2} \right \rfloor} {(n-1)-k \choose k} \nonumber \\ \quad &=& \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}{n-k \choose k} + {n-\frac{n+1}{2} \choose \frac{n+1}{2}} + P_k \nonumber \\ \quad &=& P_{n+1} +0+P_{n} \nonumber \\ \quad &=& P_{n+1} + P_{n}. \nonumber \end{eqnarray} From the above discussion, we can see that \begin{eqnarray} P_1 &=&1 \nonumber \\ P_2 &=& 1 \nonumber \\ P_{n+2} &=& P_{n+1} + P_n, \forall n \ge 1 \nonumber \end{eqnarray} This is exactly the same as the recursive definition of the Fibonacci Numbers: \begin{eqnarray} F_1 &=&1 \nonumber \\ F_2 &=&1 \nonumber \\ F_{n+2} &=& F_{n+1} + F_{n}, \forall n \ge 1. \nonumber \end{eqnarray}Thus, we can assert that the Fibonacci Numbers associated with Pascal Triangle as shown in the above diagram.