The Fibonacci Sequence

One interesting relationship arises between Pascal's Triangle and the Fibonacci sequence which we define below.

Definition: The Fibonacci Sequence is the infinite sequence $\{ f_n \}$ defined recursively as $f_1 = 1$, $f_2 = 1$, and $f_k = a_{k-1} + a_{k-2}$ for $k \geq 3$.

The first few terms of the Fibonacci sequence are:

(1)

\begin{align} \quad \{f_n \} = \{ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... \} \end{align}

What's neat is that the Fibonnaci sequence appears as the left-to-right diagonal sums of the entries on Pascal's triangle.

Notice that for each $n \in \{ 0, 1, 2, ... \}$ and for each $k = 0, 1, 2, ..., n$ we have that the left-to-right diagonal sum is given by the formula

(2)

\begin{align} \quad \sum_{k=0}^{n} \binom{n-k}{k} = \binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2} + ... + \binom{1}{n-1} + \binom{0}{n} \end{align}

Recall that if $n < k$ then $\binom{n}{k} = 0$ though, and so some of the terms of this finite series are $0$. In fact, for $n \in \{ 0, 1, 2, ... \}$ it's not hard to see that only the first $\left \lfloor \frac{n}{2} \right \rfloor$ terms of the series above are nonzero. Therefore the series above can be written cleaner as:

(3)

\begin{align} \quad \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \binom{n-k}{k} = \binom{n}{0} + \binom{n-1}{1} + ... + \binom{n-\left \lfloor \frac{n}{2} \right \rfloor}{\left \lfloor \frac{n}{2} \right \rfloor} \end{align}

Therefore a general formula for the Fibonacci sequence for $n = 0, 1, 2, ...$ is given by:

(4)

\begin{align} \quad \{ f_n \} = \left \{ \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \binom{n-k}{k} \right \} = \left \{ \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \frac{(n-k)!}{k!(n - 2k)!} \right \} \end{align}

Let $f : \{0, 1, 2, ... \} \to \mathbb{Z}$ be the function defined by the formula $f(n) = \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \frac{(n-k)!}{k!(n - 2k)!}$. Then $f(n)$ gives us the $(n+1)^{\mathrm{st}}$ number in the Fibonacci sequence.

For example, suppose that we wanted to find the $14^{\mathrm{th}}$ number in the Fibonacci sequence. Then we need to compute $f(13)$ which is:

(5)

\begin{align} \quad f(19) = \sum_{k=0}^{\left \lfloor \frac{13}{2} \right \rfloor} \frac{(19-k)!}{k!(19 - 2k)!} \\ \quad = \sum_{k=0}^{6} \frac{(13-k)!}{k!(13-2k)!} \\ \quad = \frac{13!}{0! \cdot 13!} + \frac{12!}{1! \cdot 11!} + \frac{11!}{2! \cdot 9!} + \frac{10!}{3! \cdot 7!} + \frac{9!}{4! \cdot 5!} + \frac{8!}{5! \cdot 3!} + \frac{7!}{6! \cdot 1!} \\ \quad = 1 + 12 + 55 + 120 + 126 + 56 + 7 \quad = 377 \end{align}