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

From ProofWiki
Jump to navigation Jump to search

Theorem

$\ds \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: \ds \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:

$\ds \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:

\(\ds \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}\) \(=\) \(\ds F_{t - 1} F_m + F_t F_{m + 1}\)
\(\ds \) \(=\) \(\ds F_{m + t}\) Honsberger's Identity

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: \ds \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: \ds \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:

\(\ds F_{m + t \paren {q + 1} }\) \(=\) \(\ds F_{m + t q} F_{t - 1} + F_{m + t q + 1} F_t\) Honsberger's Identity
\(\ds \) \(=\) \(\ds \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
\(\ds \) \(=\) \(\ds \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}\)
\(\ds \) \(=\) \(\ds \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
\(\ds \) \(=\) \(\ds \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$
\(\ds \) \(=\) \(\ds \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}\)
\(\ds \) \(=\) \(\ds \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: \ds \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:


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_over_k_of_n_Choose_k_by_Fibonacci_t_to_the_k_by_Fibonacci_t-1_to_the_n-k_by_Fibonacci_m%2Bk&oldid=568625"