## DSP Filter to generate Fibonacci numbers

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: $1,1,2,3,5, 8, \ldots$

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

Solution: Let $y(n)$ be the nth term of the Fibonacci sequence. Clearly, $y(n)$ satisfies the difference equation: $y(n) = y(n-1) + y(n-2)$…..Equation A

with initial conditions $y(0)=y(-1)+y(-2)=1$…..B $y(1)=y(0)+y(-1)=1$….C

From the above, $y(-1)=0$ and $y(-2)=1$. Thus, we have to determine $y(n)$ for $n \geq 0$, which satisfies equation A with initial conditions $y(-1)=0$ and $y(-2)=1$.

By taking the one-sided z-transform of the equation A and using the shifting property, we obtain: $Y^{+}(z) = (z^{-1}Y^{+}(z)+y(-1))+(z^{-1}Y^{+}(z)+y(-2)+y(-1)z^{-1})$

or $Y^{+}(z) = \frac{1}{1-z^{-1}-z^{2}} = \frac{z^{2}}{z^{2}-z-1}$….equation D

where we have used the fact that $y(-1)=0$ and $y(-2)=1$.

We can invert $Y^{+}(z)$ by the partial fraction expansion method. The poles of $Y^{+}(z)$ are: $p_{1} = \frac{1+\sqrt{5}}{2}$, and $p_{2} = \frac{1-\sqrt{5}}{2}$

and the corresponding coefficients are $A_{1} = \frac{p_{1}}{\sqrt{5}}$ and $A_{2}=\frac{-p_{1}}{\sqrt{5}}$. Therefore, $y(n) = (\frac{1+\sqrt{5}}{2\sqrt{5}})(\frac{1+\sqrt{5}}{2})^{n}u(n) - \frac{1-\sqrt{5}}{2\sqrt{5}}(\frac{1-\sqrt{5}}{2})^{n}u(n)$

or, equivalently, $y(n) = \frac{1}{\sqrt{5}}(\frac{1}{2})^{n+1}((1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1})u(n)$.

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.