---
tag: T7GJ551SZ8
kind: proof
name: Proof that Fibonacci numbers are sums of binomial coefficients, by Pascal's rule
msc: [11B39]
proves: 0V4VB6MQDC
uses: [092GEF38YD, 0YRG241HQQ, 0GA9K57A39, 0ASJVEFA9J]
sources:
  - url: https://proofwiki.org/wiki/Fibonacci_Number_as_Sum_of_Binomial_Coefficients
---

## Proof

We show that the sums satisfy the Fibonacci recurrence, by [[induction|0ASJVEFA9J]] and [[Pascal's rule|0YRG241HQQ]].

1. First, $\binom{a}{b} = 0$ for natural numbers $b > a$. We prove this by induction on $a$, using the definition of the [[binomial coefficient|092GEF38YD]].
2. For $a = 0$ and $b \ge 1$, the definition gives $\binom{0}{b} = 0$.
3. Assume the claim for $a$, and let $b > a + 1$. Write $b = c + 1$ with $c > a$. Then $\binom{a+1}{c+1} = \binom{a}{c} + \binom{a}{c+1} = 0 + 0 = 0$.
4. For a natural number $n$, let $T_n = \sum_{k=0}^{n} \binom{n-k}{k}$. If $k > \lfloor n/2 \rfloor$, then $2k > n$, so $k > n - k$ and $\binom{n-k}{k} = 0$ by step 1.
5. So $T_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}$, the right side of the statement.
6. We have $T_0 = \binom{0}{0} = 1$ and $T_1 = \binom{1}{0} + \binom{0}{1} = 1 + 0 = 1$.
7. Let $n$ be a natural number. In $T_{n+2}$, the term $k = 0$ is $\binom{n+2}{0} = 1$. Writing $k = j + 1$ for the other terms gives $T_{n+2} = 1 + \sum_{j=0}^{n+1} \binom{n+1-j}{j+1}$.
8. The term $j = n + 1$ is $\binom{0}{n+2} = 0$. For $0 \le j \le n$, $n - j$ is a natural number, and Pascal's rule gives $\binom{n+1-j}{j+1} = \binom{n-j}{j} + \binom{n-j}{j+1}$.
9. Hence $T_{n+2} = \sum_{j=0}^{n} \binom{n-j}{j} + \left(1 + \sum_{j=0}^{n} \binom{n-j}{j+1}\right)$.
10. The first sum is $T_n$. In the bracket, write $i = j + 1$ and $1 = \binom{n+1}{0}$. The bracket becomes $\sum_{i=0}^{n+1} \binom{n+1-i}{i} = T_{n+1}$.
11. So $T_{n+2} = T_{n+1} + T_n$ for every natural number $n$.
12. Let $P(n)$ be the claim that $T_n = F_{n+1}$ and $T_{n+1} = F_{n+2}$, where $F_m$ are the [[Fibonacci numbers|0GA9K57A39]].
13. $P(0)$ holds by step 6, since $F_1 = 1$ and $F_2 = F_1 + F_0 = 1$.
14. If $P(n)$ holds, then $T_{n+2} = T_{n+1} + T_n = F_{n+2} + F_{n+1} = F_{n+3}$ by step 11. So $P(n + 1)$ holds.
15. By induction, $F_{n+1} = T_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}$ for every natural number $n$.

## Idea

Pascal's rule splits each term of the sum for $n + 2$ into one term of the sum for $n + 1$ and one of the sum for $n$. So these diagonal sums of Pascal's triangle satisfy the Fibonacci recurrence. They start with $1, 1$, like $F_1, F_2$.