# 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)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)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)Therefore a general formula for the Fibonacci sequence for $n = 0, 1, 2, ...$ is given by:

(4)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)