The title is slight misnomer; but I am presenting below is a closed form expression for the nth term of the Fibonacci sequence.

Reference: Digital Signal Processing by Proakis and Manolakis, Sixth Edition.

The one-sided z-transform is a very efficient tool for the solution of difference equations with nonzero intial conditions. It achieves that by reducing the difference equation relating the two time-domain signals to an equivalent algebraic equation relating their one-sided z-transforms. This equation can be easily solved to obtain the transform of the desired signal. The signal in the time domain is obtained by inverting the resulting z-transform. For instance:

Example: The well-known Fibonacci sequence of integers is obtained by computing each term as the sum of the two-previous ones. The first few terms of the sequence are:

Determine a closed form expression for the nth term of the Fibonacci sequence.

Solution: Let be the nth term of the Fibonacci sequence. Clearly, satisfies the difference equation:

…..Equation A

with initial conditions

…..B

….C

From the above, and . Thus, we have to determine for , which satisfies equation A with initial conditions and .

By taking the one-sided z-transform of the equation A and using the shifting property, we obtain:

or ….equation D

where we have used the fact that and .

We can invert by the partial fraction expansion method. The poles of are:

, and

and the corresponding coefficients are and . Therefore,

or, equivalently,

.

One smallish comment: We can implement a difference equation of a filter as either FIR or IIR. Of course, based on the physical nature of the signal/processing, one or the other might be preferable.

Regards,

Nalin Pithwa.