# Sum over k of n Choose k by Fibonacci t to the k by Fibonacci t-1 to the n-k by Fibonacci m+k

## Theorem

$\displaystyle \sum_{k \mathop \ge 0} \binom n k {F_t}^k {F_{t - 1} }^{n - k} F_{m + k} = F_{m + t n}$

where:

$\dbinom n k$ denotes a binomial coefficient
$F_n$ denotes the $n$th Fibonacci number.

## Proof

The proof proceeds by induction on $n$.

For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:

$\forall m, t \in \N: \displaystyle \sum_{k \mathop \ge 0} \binom n k {F_t}^k {F_{t - 1} }^{n - k} F_{m + k} = F_{m + t n}$

$\map P 0$ is the case:

$\displaystyle \binom 0 0 {F_t}^0 {F_{t - 1} }^0 F_{m + 0} = F_m$

Thus $\map P 0$ is seen to hold.

### Basis for the Induction

$\map P 1$ is the case:

 $\displaystyle \binom 1 0 {F_t}^0 {F_{t - 1} }^1 F_{m + 0} + \binom 1 1 {F_t}^1 {F_{t - 1} }^0 F_{m + 1}$ $=$ $\displaystyle F_{t - 1} F_m + F_t F_{m + 1}$ $\displaystyle$ $=$ $\displaystyle F_{m + t}$ Fibonacci Number in terms of Smaller Fibonacci Numbers

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

This is the basis for the induction.

### Induction Hypothesis

Now it needs to be shown that, if $\map P q$ is true, where $q \ge 1$, then it logically follows that $\map P {q + 1}$ is true.

So this is the induction hypothesis:

$\forall m, t \in \N: \displaystyle \sum_{k \mathop \ge 0} \binom q k {F_t}^k {F_{t - 1} }^{q - k} F_{m + k} = F_{m + t q}$

from which it is to be shown that:

$\forall m, t \in \N: \displaystyle \sum_{k \mathop \ge 0} \binom {q + 1} k {F_t}^k {F_{t - 1} }^{q + 1 - k} F_{m + k} = F_{m + t \paren {q + 1} }$

### Induction Step

This is the induction step:

 $\displaystyle F_{m + t \paren {q + 1} }$ $=$ $\displaystyle F_{m + t q} F_{t - 1} + F_{m + t q + 1} F_t$ Fibonacci Number in terms of Smaller Fibonacci Numbers $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \ge 0} \binom q k {F_t}^k {F_{t - 1} }^{q - k} F_{m + k} F_{t - 1} + \sum_{k \mathop \ge 0} \binom q k {F_t}^k {F_{t - 1} }^{q - k} F_{m + 1 + k} F_t$ Induction Hypothesis $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \ge 0} \binom q k {F_t}^k {F_{t - 1} }^{q + 1 - k} F_{m + k} + \sum_{k \mathop \ge 0} \binom q k {F_t}^{k + 1} {F_{t - 1} }^{q - k} F_{m + 1 + k}$ $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \ge 0} \binom q k {F_t}^k {F_{t - 1} }^{q + 1 - k} F_{m + k} + \sum_{k \mathop \ge 1} \binom q {k - 1} {F_t}^k {F_{t - 1} }^{q - \paren {k - 1} } F_{m + k}$ Translation of Index Variable of Summation $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \ge 0} \binom q k {F_t}^k {F_{t - 1} }^{q + 1 - k} F_{m + k} + \sum_{k \mathop \ge 0} \binom q {k - 1} {F_t}^k {F_{t - 1} }^{q - k + 1} F_{m + k}$ $\dbinom q {-1} = 0$ $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \ge 0} \paren {\binom q k + \binom q {k - 1} } {F_t}^k {F_{t - 1} }^{q + 1 - k} F_{m + k}$ $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \ge 0} \binom {q + 1} k {F_t}^k {F_{t - 1} }^{q + 1 - k} F_{m + k}$ Pascal's Rule

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

Therefore:

$\forall m, n, t \in \N: \displaystyle \sum_{k \mathop \ge 0} \binom n k {F_t}^k {F_{t - 1} }^{n - k} F_{m + k} = F_{m + t n}$

$\blacksquare$

## Also see

The following are corollaries to this theorem: