Back to Musings and Other Quandaries

# Prove that the diagonals of Pascal's triangle sum to the Fibonacci sequence

#### A neat little proof

April 8, 2023

math

It appears that if you sum along the diagonal’s of Pascal’s triangle, it follow’s the Fibonacci sequence. Pascal’s triangle is often used to find the coefficients of a binomial $(x+y)^{n}$. This can also be expressed with combinatorics, which is written on the side of each bubble in the triangle.

For this post we will assume that $F_{0}=1$, $F_{1}=1$ and the Fibonacci sequence is generated by $F_{n}=F_{n-1}+F_{n-2}$.

To demonstrate this using combinatorics, the 4th (5th if you don’t count from 0) diagonal’s sum looks like $${4 \choose 0} + {3 \choose 1} + {2 \choose 2} =1+3+1 = 5$$ Which is equal to $F_{4}$ .

We can extrapolate and guess that the pattern continues along the lines of $F_{n} =\sum_{k=0}{n -k \choose k }$. The top term, $n-k$, decreases as k increase, while the bottom number $k$ increases with the sum.

However the number of terms in a diagonal depends on the particular Fibonacci number you are evaluating. If you look at the table in the photo, the number of terms in a diagonal follows a floor pattern. The expression is exactly $\lfloor \frac{n}{2}+1 \rfloor$

We will prove with strong induction that the n-th Fibonacci number is equal to $$F_{n}=\sum_{k=0}^{\lfloor \frac{n}{2} +1\rfloor } {n-k \choose k}$$

# Proof

### Base case

When $n=0$, $F_{0}=1$ and $$\sum_{k=0}^{\lfloor 0+1 \rfloor}{0-k \choose k}={0-0 \choose 0}+{0-1 \choose 0}=1+0=1$$ $F_0$ and the sum are equal.

When $n=1$, $F_{1}=1$ and $$\sum_{k=0}^{\lfloor \frac{1}{2}+1 \rfloor}{1-k \choose k }={1-0 \choose 0}+{1-1 \choose 1}=1+0=1$$ $F_1$ and the sum are equal.

Therefore, the base case holds.

### Inductive step

Assume that for $j\in\mathbb{N}$ and $j\geq 1$ we know how to construct the k-th Fibonacci number as long as it is in the interval $0 \leq k \leq j$ (the interval our base cases are in).

Consider the $j+1$ Fibonacci number. We will proceed with a proof by cases, when $j$ is even and when $j$ is odd.

### Case 1: $j$ is even.

Because $j$ is even, it is a multiple of two. So $j=2m$, $m \in \mathbb{Z}$. Then we know that $$F_{j}=\sum_{k=0}^{\lfloor \frac{2m}{2}+1 \rfloor} {j-k \choose k} \text{ and }F_{j-1}=\sum_{k=0}^{\lfloor \frac{2m-1}{2}+1 \rfloor} {j-k \choose k}$$ We can simplify the upper bounds of each sum.

$$\lfloor \frac{j}{2}+1 \rfloor=\lfloor \frac{2m}{2}+1 \rfloor=\lfloor m+1 \rfloor=m+1$$ $$\lfloor \frac{j-1}{2}+1 \rfloor=\lfloor \frac{2m-1}{2}+1 \rfloor=\lfloor m+\frac{1}{2} \rfloor=m$$

Therefore $F_{j}=\sum_{k=0}^{m+1}{2m-k \choose k}$ and $F_{j-1}=\sum_{k=0}^{m}{2m-1-k \choose k}$

Continuing with the proof, we will make use of the fact that ${{n \choose k-1}+{n \choose k}={n+1 \choose k}}$ (See proof)

\begin{aligned} F_{j+1}&=\sum_{k=0}^{m+1}{(2m+1)-k \choose k} = \sum_{k=0}^{m+1}{2m-k \choose k}+\sum_{k=0}^{m+1}{2m-k \choose k-1} \\ &=F_{j}+\sum_{k=0}^{m+1}{2m-k \choose k-1} \\ &=F_{j}+\cancel{2m-0 \choose 0-1}+\sum_{k=1}^{m+1}{2m-k \choose k-1} \end{aligned} We evaluate the first term of the sum. This ends up being 0 because you can’t choose a negative number of elements (0 ways to do so) ${2m-0 \choose 0-1}={2m \choose -1}=0$

Next we re-index the sum. Let $u=k-1$, then \begin{aligned} F_{j+1}&=F_{j}+\sum_{u=0}^{m}{2m-(u+1) \choose u} \\ &=F_{j}+\sum_{u=0}^{m}{2m-1-u \choose u} \\ &=F_{j}+F_{j-1} \end{aligned}

### Case 2: $j$ is odd.

Because $j$ is odd, then it can be written as a multiple of 2 plus one. So ${j=2m+1}$ where $m \in\mathbb{Z}$.

To streamline our work, let us simplify the floor evaluations. \begin{aligned} j:&\lfloor \frac{j}{2}+1 \rfloor=\lfloor \frac{2m+1}{2}+1 \rfloor=\lfloor m+\frac{3}{2} \rfloor=m+1 \\ j+1:&\lfloor \frac{j+1}{2} +1 \rfloor = \lfloor \frac{2m+1+1}{2}+1 \rfloor=\lfloor m+2 \rfloor=m+2 \\ j-1:&\lfloor \frac{j-1}{2}+1 \rfloor = \lfloor \frac{2m+1-1}{2}+1 \rfloor=\lfloor m+1 \rfloor=m+1 \end{aligned}

Then $F_{j}=\sum_{k=0}^{m+1}{(2m+1)-k \choose k}$ and $F_{j-1}=\sum_{k=0}^{m+1}{2m-k \choose k}$.

Continuing with the proof and making use of the same identity as before: \begin{aligned} F_{j+1}&=\sum_{k=0}^{m+2}{(2m+1)+1-k \choose k } = \sum_{k=0}^{m+2}{(2m+1-k)+1 \choose k } \\ &=\sum_{k=0}^{m+2}{2m+1-k \choose k}+\sum_{k=0}^{m+2}{2m+1-k \choose k-1} \end{aligned}

We evaluate the last term of the first sum. Then we evaluate the first term of the second sum. \begin{aligned} F_{j+1}&={2m+1 - (m+2) \choose m+2 } +\sum_{k=0}^{m+1}{2m+1-k \choose k}+{2m+1-0 \choose 0-1}+\sum_{k=1}^{m+2}{2m+1-k \choose k-1} \\ &=\cancel{m-1 \choose m+2 } +F_{j}+ \cancel{2m+1 \choose -1}+\sum_{k=1}^{m+2}{2m+1-k \choose k-1} \end{aligned} Re-index the second sum. Let $u=k-1$. \begin{aligned} F_{j+1}&=F_{j}+\sum_{u=0}^{m+1}{2m+1-(u+1) \choose u} \\ &= F_{j}+\sum_{u=0}^{m+1}{2m-u \choose u}=F_{j}+F_{j-1} \end{aligned}

$\therefore$ Therefore, we have shown using strong induction that the sum along the diagonals of Pascal’s triangle follow’s the Fibonacci sequence.