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:

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: