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:
with initial conditions
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 the corresponding coefficients are and . Therefore,
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.