# Fibonacci Number as Sum of Binomial Coefficients

## Theorem

Let $F_n$ denote the $n$th Fibonacci number.

Then:

 $\, \displaystyle \forall n \in \Z_{>0}: \,$ $\displaystyle F_n$ $=$ $\displaystyle \sum_{k \mathop = 0}^{\floor {\frac {n - 1} 2} } \dbinom {n - k - 1} k$ $\displaystyle$ $=$ $\displaystyle \binom {n - 1} 0 + \binom {n - 2} 1 + \binom {n - 3} 2 + \dotsb + \binom {n - j} {j - 1} + \binom {n - j - 1} j$ where $j = \floor {\frac {n - 1} 2}$

where:

$\dbinom a b$ denotes a binomial coefficient
$\floor x$ denotes the floor function, which is the greatest integer less than or equal to $x$.

## Proof

By definition of Fibonacci numbers:

$F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, \ldots$

The proof proceeds by induction.

For all $n \in \Z_{>0}$, let $P(n)$ be the proposition:

$\displaystyle F_n = \sum_{k \mathop = 0}^{\floor {\frac {n - 1} 2} } \dbinom {n - k - 1} k$

### Basis for the Induction

$\map P 1$ is the case:

 $\displaystyle F_1$ $=$ $\displaystyle 1$ $\displaystyle$ $=$ $\displaystyle \dbinom 0 0$ Zero Choose Zero $\displaystyle$ $=$ $\displaystyle \dbinom {1 - 0 - 1} 0$ $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop = 0}^{\floor {\frac {1 - 1} 2} } \dbinom {1 - k - 1} k$

So $\map P 1$ is seen to hold.

$\map P 2$ is the case:

 $\displaystyle F_2$ $=$ $\displaystyle 1 + 0$ $\displaystyle$ $=$ $\displaystyle \dbinom 1 0$ Binomial Coefficient with Zero $\displaystyle$ $=$ $\displaystyle \dbinom {2 - 0 - 1} 0$ $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop = 0}^{\floor {\frac {2 - 1} 2} } \dbinom {2 - k - 1} k$

So $\map P 2$ is also seen to hold.

This is our basis for the induction.

### Induction Hypothesis

Now we need to show that, if $\map P {k - 1}$ and $\map P k$ are true, where $k > 2$ is an even integer, then it logically follows that $\map P {k + 1}$ and $\map P {k + 2}$ are both true.

So this is our induction hypothesis:

$\displaystyle F_{k - 1} = \sum_{i \mathop = 0}^{\frac k 2 - 1} \dbinom {k - i - 2} i$
$\displaystyle F_k = \sum_{i \mathop = 0}^{\frac k 2 - 1} \dbinom {k - i - 1} i$

Then we need to show:

$\displaystyle F_{k + 1} = \sum_{i \mathop = 0}^{\frac k 2} \dbinom {k - i} i$
$\displaystyle F_{k + 2} = \sum_{i \mathop = 0}^{\frac k 2} \dbinom {k - i + 1} i$

### Induction Step

This is our induction step:

For the first part:

 $\displaystyle \sum_{i \mathop = 0}^{\frac k 2} \dbinom {k - i} i$ $=$ $\displaystyle \dbinom k 0 + \sum_{i \mathop = 1}^{\frac k 2 - 1} \dbinom {k - i} i + \dbinom {k - \frac k 2} {\frac k 2}$ $\displaystyle$ $=$ $\displaystyle 1 + \sum_{i \mathop = 1}^{\frac k 2 - 1} \dbinom {k - i} i + \dbinom {\frac k 2} {\frac k 2}$ Binomial Coefficient with Zero $\displaystyle$ $=$ $\displaystyle 1 + \sum_{i \mathop = 1}^{\frac k 2 - 1} \dbinom {k - i} i + 1$ Binomial Coefficient with Self $\displaystyle$ $=$ $\displaystyle 1 + \sum_{i \mathop = 1}^{\frac k 2 - 1} \left({ \dbinom {k - i - 1} i + \dbinom {k - i - 1} {i - 1} }\right) + 1$ Pascal's Rule $\displaystyle$ $=$ $\displaystyle 1 + \sum_{i \mathop = 1}^{\frac k 2 - 1} \dbinom {k - i - 1} i + \sum_{i \mathop = 1}^{\frac k 2 - 1} \dbinom {k - i - 1} {i - 1} + 1$ Summation is Linear $\displaystyle$ $=$ $\displaystyle 1 + \sum_{i \mathop = 1}^{\frac k 2 - 1} \dbinom {k - i - 1} i + \sum_{i \mathop = 0}^{\frac k 2 - 2} \dbinom {k - i - 2} i + 1$ $\displaystyle$ $=$ $\displaystyle \dbinom {k - 2} 0 + \sum_{i \mathop = 1}^{\frac k 2 - 1} \dbinom {k - i - 1} i + \sum_{i \mathop = 0}^{\frac k 2 - 2} \dbinom {k - i - 2} i + 1$ Binomial Coefficient with Zero $\displaystyle$ $=$ $\displaystyle \dbinom {k - 2} 0 + \sum_{i \mathop = 1}^{\frac k 2 - 1} \dbinom {k - i - 1} i + \sum_{i \mathop = 0}^{\frac k 2 - 2} \dbinom {k - i - 2} i + \dbinom {k - \paren {\frac k 2 - 1} - 2} {\frac k 2 - 1}$ Binomial Coefficient with Self $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = 0}^{\frac k 2 - 1} \dbinom {k - i - 1} i + \sum_{i \mathop = 0}^{\frac k 2 - 1} \dbinom {k - i - 2} i$ $\displaystyle$ $=$ $\displaystyle F_k + F_{k - 1}$ Induction hypothesis $\displaystyle$ $=$ $\displaystyle F_{k + 1}$ Definition of Fibonacci Number

For the second part:

 $\displaystyle \sum_{i \mathop = 0}^{\frac k 2} \dbinom {k - i + 1} i$ $=$ $\displaystyle \dbinom k 0 + \sum_{i \mathop = 1}^{\frac k 2} \dbinom {k - i + 1} i$ $\displaystyle$ $=$ $\displaystyle 1 + \sum_{i \mathop = 1}^{\frac k 2} \dbinom {k - i + 1} i$ Binomial Coefficient with Zero $\displaystyle$ $=$ $\displaystyle 1 + \sum_{i \mathop = 1}^{\frac k 2} \paren {\dbinom {k - i} i + \dbinom {k - i} {i - 1} }$ Pascal's Rule $\displaystyle$ $=$ $\displaystyle 1 + \sum_{i \mathop = 1}^{\frac k 2} \dbinom {k - i} i + \sum_{i \mathop = 1}^{\frac k 2} \dbinom {k - i} {i - 1}$ Summation is Linear $\displaystyle$ $=$ $\displaystyle 1 + \sum_{i \mathop = 1}^{\frac k 2} \dbinom {k - i} i + \sum_{i \mathop = 0}^{\frac k 2 - 1} \dbinom {k - i - 1} i$ $\displaystyle$ $=$ $\displaystyle \dbinom {k - 2} 0 + \sum_{i \mathop = 1}^{\frac k 2} \dbinom {k - i} i + \sum_{i \mathop = 0}^{\frac k 2 - 1} \dbinom {k - i - 1} i$ Binomial Coefficient with Zero $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = 0}^{\frac k 2} \dbinom {k - i} i + \sum_{i \mathop = 0}^{\frac k 2 - 1} \dbinom {k - i - 1} i$ $\displaystyle$ $=$ $\displaystyle F_{k + 1} + F_k$ Induction hypothesis $\displaystyle$ $=$ $\displaystyle F_{k + 2}$ Definition of Fibonacci Number

So $\map P {k - 1} \land \map P k \implies \map P {k + 1} \land \map P {k + 2}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

$\displaystyle \forall n \in \Z_{>0}: F_n = \sum_{k \mathop = 0}^{\floor {\frac {n - 1} 2} } \dbinom {n - k - 1} k$

$\blacksquare$

## Examples

### Fibonacci Number $F_{12}$

 $\displaystyle F_{12}$ $=$ $\displaystyle \binom {11} 0 + \binom {10} 1 + \binom 9 2 + \binom 8 3 + \binom 7 4 + \binom 6 5$ $\displaystyle$ $=$ $\displaystyle 1 + 10 + 36 + 56 + 35 + 6$ $\displaystyle$ $=$ $\displaystyle 144$

## Historical Note

This result was discovered by Édouard Lucas.

## Sources

but note the misprint in the statement of the result.