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.
No comments:
Post a Comment