4

Truncated Fibonacci numbers

14
0
$$\newcommand{ZZ}[0]{\mathbb{Z}} $$

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:

truncated_Fibonacci_number

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, ありがとうぎざいます!

投稿日:2020117

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

私のことは気にしないでください。🙇‍♂️

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中