# Eikonal Blog

## 2010.03.12

### Fibonacci numbers – simple generalizations

Filed under: mathematics — Tags: , , , — sandokan65 @ 17:32

Source: 2009.02.04 Wed

The Fibonacci series $\{f_n | n\in {\Bbb N}_0\}$ are defined by the recursive equation

$f_{n} = f_{n-1} + f_{n-2}$

and the “initial conditions” (i.e. known) $f_0$ and $f_1$.

The case $f_0=f_1=1$ is the original Fibonacci’s sequence, and traditionally the members of the sequence are symbolized by capital case F: $\{F_0=1, F_1=1, F_2=2, \cdots\}$.

The exponential-type generating function ${\cal F}(z) :\equiv \sum_{n=0}^\infty \frac{z^n}{n!} f_n$ satisfies the simple IVP (Initial value Problem):

• ${\cal F}''(z) = {\cal F}'(z) + {\cal F}(z)$,
• ${\cal F}(0) = f_0$,
• ${\cal F}'(0) = f_1$,

with the unique solution

${\cal F}(z) = \frac{f_0}{\sqrt{5}} [(\varphi-1) e^{+\varphi z} + \varphi e^{(1-\varphi) z} ] + \frac{f_1}{\sqrt{5}} [e^{+\varphi z} - e^{(1-\varphi) z}]$.

Here $\varphi :\equiv \frac{\sqrt{5}+1}2$ is the Golden Section, a root of the characteristic polynomial $P(\lambda) = \lambda^2 – \lambda-1$ (the other solution being $1-\varphi = \frac{\sqrt{5}-1}2$).

Having the explicit expression for the generating function, one gets the explicit expression for individual sequence members:

$f_n = \varphi^n \frac{(1-\varphi) f_0 + f_1}{\sqrt{5}} + (1-\varphi)^n \frac{\varphi f_0 - f_1}{\sqrt{5}}$.

## First slight generalization

Use the recursive equation $f_{n+2} = m f_{n+1} + k f_n$. It leads to the following ODE for the generating function ${\cal F}''(z) = m {\cal F}'(z) + k {\cal F}(z)$, the characteristic root equation $\lambda^2 = m \lambda + k$ with the solutions $\lambda_\pm = \frac{m\pm \kappa}2$ (where $\kappa :\equiv \sqrt{m^2+4 k}$). The solution for the generating function is

${\cal F}(z) = f_0 \left[\frac{1-m}2 e^{\lambda_+ z} - \frac{1+m}2 e^{\lambda_- z}\right] + f_1 \left[e^{\lambda_+ z} - e^{\lambda_- z}\right]$

and the explicit expression for the sequence members is

$f_n = f_0 \left[\frac{1-m}2 (\lambda_+)^n - \frac{1+m}2 (\lambda_-)^n\right] + f_1 \left[(\lambda_+)^n - (\lambda_-)^n\right]$.

## Second slight generalization

Use the recursive equation $f_{n+3} = f_{n+3} + f_{n+1} + f_n$. Here:

• ${\cal F}'''(z) = {\cal F}''(z) + {\cal F}'(z) + {\cal F}(z)$
• $\lambda^3 = \lambda^2 + \lambda + 1 = \frac{\lambda^4-1}{\lambda-1}$, i.e. $\lambda^4 = 2\lambda^3 - 1$ (with $\lambda\ne 1$), with solutions (thanks to the Wolfram Alpha online calculator http://www.wolframalpha.com/input/?i=x3%3Dx^2%2Bx%2B1):
• $\lambda_0 = \frac13 (1+ \sqrt[3]{19-3 \sqrt{33}}+ \sqrt[3]{19+3 \sqrt{33}}) \simeq 1.83929$
• $\lambda_\pm = \frac16 (2- (1 \mp i \sqrt{3}) \sqrt[3]{19-3 \sqrt{33}} - (1 \pm i \sqrt{3}) \sqrt[3]{19+3 \sqrt{33}})\simeq -0.419643 \mp 0.606291 i$, (note: $|\lambda_\pm|=0.737353...$)
• $\lambda_0 + + \lambda_+ + \lambda_- = - 1$, $\lambda_0 \lambda_+ + \lambda_0 \lambda_- + \lambda_+ \lambda_- = -1$, $\lambda_0 + \lambda_+ \lambda_- = +1$.
• $\lim_{n\rightarrow \infty} \frac{f_{n+2}+f_{n+1}+f_{n}}{f_{n+2}} = \lambda_0$.