Derivation of the Fibonacci-Formula - Fibonacci Search

Go to content

Main menu

Derivation of the Fibonacci-Formula

Introductory remarks
For the Derivation of formula a tool is used, as is often the case in mathematics. The original function from the original area (time area) is first transformed into the image area, where it is processed with simple tools and then transformed back into the original area. For example, the Laplace transform is a very suitable tool for solving differential equations.
With it a time function f(t) will assigned with the so-called one-sided Laplace transformation by means of the Laplace

a complex function of frequency..
The Laplace transform of derivatives can be determined as follows:

Or generally

Important is the time shifting function to right.

Using Laplace transform  a differentiation in the original area shall be ​​a multiplication in the image area.
For the reverse transformation back to the original area can be used the so-called Residue formula

Here, n is the order of the pole at p=pν.

Is f(t) not a continous function but a sequence [xn], then can be used the discrete Laplace-Transformation (L*) to transform with the relation

If in this formula will set epT=z, then it comes to so-called z-transform, which we will use for our case.
This results in the following transformation and revers transformation rules:

In this case is p the order of the pole at z=zk.

Again, the time shifting is importent for the solution of our problem.
It is

Such as the Laplace transform is suitable for solving differential equations, the z-transform can be used to solve difference

Calculation using z-transformation

As already shown, is the rule for the Fibonacci numbers

with the initial conditions

To use the the right side time shift, which considered the initial conditions, the formula is slightly redesigned, and it is used the variable x .
So, it follows

The application of the z-transformation yields

From the last equation follows

Now the inverse transformation can be done using the Residue formula.
Because  z1 and z2 are simple poles, is for both cases  p=1.

Back to content | Back to main menu