Truncated Fibonacci numbers
Truncated Fibonacci numbers
(Originally posted on Twitter )
The Fibonacci numbers can be expressed as a sum of binomial coefficients
$$ F_{n+1} = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} \qquad (n > 0)$$
You can verify this by checking the initial conditions ($F_0 = 0$ and $F_1$ = 1) and the the recursion relation $F_{n+2} = F_{n+1} + F_{n}$.
From this one can obtain the truncated Fibonacci numbers by removing the lower terms ($k \leq s$) of the summation:
For integers $n \geq 0$,
$$\begin{align}
F_{2n+1|s} =& \sum_{k=0}^{s-1} \binom{n+k}{n-k} & \quad \text{(odd case)} \\
F_{2n|s} =& \sum_{k=0}^{s-1} \binom{n+k}{n-1-k} & \quad \text{(even case)}
\end{align}$$
A Truncated Fibonacci identity
The following well known identity relates the golden ratio $\phi = \frac{1 \pm \sqrt{5}}{2}$ with the Fibonacci numbers.
$$ \phi^{n} = F_{n-1} + \phi F_n \qquad (n\in \ZZ) $$
In this document I want to show a similar identity for truncated Fibonacci numbers.
$$ \phi^{2n} = F_{2n-1|s+1} + F_{2n|s}\phi + \sum_{k=1}^{n-s} \binom{n+s-k}{n-s-k}\phi^{2k-1} $$
As consequence of this we obtain formulas for Fibonacci numbers consisting of binomial coefficients and Fibonacci numbers of lower order:
$$\begin{align} F_{2n} = & F_{2n|s} + \sum_{k=1}^{n-s} \binom{n+s-k}{n-s-k}F_{2k-1} \\ F_{2n+1} = & F_{2n+1|s+1} + \sum_{k=1}^{n-s} \binom{n+s-k}{n-s-k}F_{2k} \\ \end{align}$$
For $s = 1$ we get the identities posted by @Numerus_A on Twitter the other day.
$$\begin{align} F_{2n} = & \binom{n}{1} + \sum_{k=1}^{n-1} \binom{n+1-k}{2}F_{2k-1} \\ F_{2n+1} = & 1 + \binom{n+1}{2} + \sum_{k=1}^{n-1} \binom{n+1-k}{2}F_{2k} \\ \end{align}$$
For $s=n$ the equality is just $\phi^{n} = F_{n-1} + F_{n}\phi$.
To prove $s+1 \to s$, we need to show
$$ \begin{align} & \binom{n+s}{n-1-s} + \binom{n+s+1}{n-(s+1)}\phi + \sum_{k=1}^{n-(s+1)} \binom{n+(s+1)-k}{n-(s+1)-k}\phi^{2k} & = \sum_{k=1}^{n-s} \binom{n+s-k}{n-s-k}\phi^{2k} \\ \iff & \binom{n+s}{2s+1} + \binom{n+s+1}{2s+2}\phi + \sum_{k=1}^{n-s-1} \binom{n+s+1-k}{2s+2}\phi^{2k} & = \sum_{k=1}^{n-s} \binom{n+s-k}{2s}\phi^{2k} \\ \end{align}$$
By repeated application of the properties $\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$ and $\phi^2 = \phi^1 + \phi^0$, we compute:
$$\begin{align} & \binom{n+s}{2s+1}\phi^0 + \binom{n+s+1}{2s+2}\phi^1 + \sum_{k=1}^{n-s-1} \binom{n+s+1-k}{2s+2}\phi^{2k} \\ = & \binom{n+s}{2s+1}\phi^0 + \left(\binom{n+s}{2s+1} + \binom{n+s}{2s+2} \right)\phi^1 + \sum_{k=1}^{n-s-1} \binom{n+s+1-k}{2s+2}\phi^{2k} \\ = &\binom{n+s}{2s+1}\phi^2 + \sum_{k=1}^{n-s-1} \binom{n+s-k}{2s+1}\phi^{2k+1} \\ = & \left(\binom{n+s-1}{2s} + \binom{n+s-1}{2s+1}\right)\phi^2 + \sum_{k=1}^{n-s-1} \binom{n+s-k}{2s+1}\phi^{2k+1} \\ = & \binom{n+s-1}{2s}\phi^2 + \sum_{k=1}^{n-s-1} \binom{n+s-1-k}{2s}\phi^{2k+2} \\ = & \sum_{k=1}^{n-s} \binom{n+s-k}{2s}\phi^{2k} \\ \end{align} $$
(I am sure one could make some sort of game out of this)
I am sure someone else must have found these identities before, so if you know a source, feel free to post it in the comments, ありがとうぎざいます！
この記事を高評価した人
この記事に送られたバッジ
投稿者
