Relating Fibonacci Numbers to Pascal Triangle

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:

Relationship of Fibonacci Numbers 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

$$\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,

$$\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.

The Progeny of a Single Pair of Rabbits

The mathematician Leonardo Fibonacci (1170 A.D. - 1250 A.D.), also called Leonardo Pisano or Leonard of Pisa,  was born in the commercial city of Pisa, Italy into the Bonacci family.  He is commonly known as Fibonacci  which is a shortened form of Filius Bonaccio (son of Bonaccio).  His father was a customs inspector in the city of Bugia (presently Bougie in Algeria).  As a result, Fibonacci received his early education from a Muslim schoolmaster, who introduced him to the Indo-Arabic numeration system and computational techniques.  Around 1200 A.D., at the age of about 30, Fibonacci returned to Pisa.  He was convinced of the elegance and practical superiority of the Indo-Arabic system over the Roman numeration system, and published his pioneering work, Liber Abaci (The Book of the Abacus) in 1202 A.D..    Liber Abaci was devoted to arithmetic and elementary algebra, and it introduced the Indo-Arabic numeration system and arithmetic methods to Europe.

In this book, he proposed the following problem which gave birth to Fibonacci Numbers (or Fibonacci Sequence).

Suppose there are two newborn rabbits, one male and the other female. Find the number of rabbits produced in a year if

• Each pair takes one month to become mature;

• Each pair produces a mixed pair every month, from the second month; and

• All rabbits are immortal.

Let $A_n$ be the number of adult rabbit pairs and $B_n$ be the number of baby rabbit pairs in the month $n$.  Let $F_n$ be the total number of rabbit pairs in month $n$.  Then, we see that 

1. In any month, say month $n+1$, the number of pairs of baby rabbits will be equal to the number of adult rabbit pairs in the previous month.  That is, \[\begin{equation}B_{n+1} = A_n\end{equation}\].
2. The number of adult rabbit pairs in a particular month (say month $n+1$), $A_{n+1}$ is given by the number of adult rabbit pairs in the previous month, $A_n$, plus the number of baby pairs from the previous month which grow to be adults, $B_n$.  Thus, we see that \[\begin{equation}A_{n+1} = A_n + B_n\end{equation}\]

From the above two equations, we can see that \[A_{n+2} = A_{n+1}+B_{n+1} = A_{n+1}+A_n.\] We see that the total number of pairs in a particular month (say month $n+2$) is given by \[\begin{eqnarray} F_{n+2} &=& A_{n+2} + B_{n+2} \nonumber \\ &=& A_{n+2}+A_{n+1} \nonumber \\ &=& \left[A_{n+1}+A_{n}\right]+\left[A_{n}+A_{n-1}\right] \nonumber \\ &=& \left[A_{n+1}+B_{n+1}\right]+\left[A_n+B_n\right] \nonumber \\ &=& F_{n+1} + F_n. \nonumber \end{eqnarray}\]On the basis of the above facts, we can form the following table:

Fibonacci Numbers

No. of pairs	$n=1$	$n=2$	$n=3$	$n=4$	$n=5$	$n=6$	$n=7$	$n=8$	$n=9$
Adults $A_n$	$0$	$1$	$1$	$2$	$3$	$5$	$8$	$13$	$21$
Babies $B_n$	$1$	$0$	$1$	$1$	$2$	$3$	$5$	$8$	$13$
Total $F_n$	$1$	$1$	$2$	$3$	$5$	$8$	$13$	$21$	$34$

Here, we see that \[F_1 = 1, \; F_2 = 1, \; F_3 = 2, \; F_4 = 3,\; F_5=5,\; F_6 =8, \; F_7 = 13, \; \ldots\] These numbers are called Fibonacci Numbers.

From the above table, we can observe that \[ \begin{eqnarray}  &F_3 &=& 2 = 1+1 = F_1 +F_2 \nonumber \\ &F_4 &=& 3 = 1+2 = F_2 + F_3 \nonumber \\ &F_5 &=& 5 = 2+3 = F_3 + F_4  \nonumber \\ &F_6 &=& 8 = 3+5 = F_4 + F_5 \nonumber \\ &\ldots && \ldots \quad \ldots \quad \ldots \quad \ldots \nonumber\end{eqnarray} \]That is, any Fibonacci number, except the first two, is the sum of the two immediately preceding Fibonacci numbers. This yields the following recursive definition of $n^{th}$ Fibonacci number $F_n$:\[\begin{eqnarray} &F_1 = F_2 = 1 \quad &\leftarrow \text{Initial Conditions} \nonumber \\ &F_n = F_{n-1}+F_{n-2}, \quad n \ge 3 \quad &\leftarrow \text{Recurrence Relation} \nonumber \end{eqnarray}\]It is not known whether Fibonacci knew of this recurrence relation.  In fact, the first written confirmation of the recurrence relation appeared four centuries later when Johannes Kepler (1571A.D.-1630 A.D.) wrote that Fibonacci must have noted this relationship.  But, according to some evidences it was noted that Fibonacci numbers and the recursive formulation were known in India several centuries before Fibonacci posed the rabbit problem.  They were given by Virahanka (between 600 A.D. and 800 A.D.), Gopala (prior to 1135 A. D.), and Hemachandra (about 1150 A.D.).  In fact, these numbers also occur as a special case of a formula established by Narayana Pandita (1356 A.D.).

Interestingly enough, Fibonacci numbers appeaer in quite unexpected places, like nature, music, geography, and geometry.  They can also be found in the spiral arrangements of seeds in sunflowers, the scale patterns of pine cones, the number of petals in flowers, and arrangement of leaves on trees.  

We will discuss some important facts and properties of Fibonacci numbers in the upcoming posts.