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.