Anonymous

# How to use Z-transforms to derive formula for Fibonacci seq?

ysub1 = 1

ysub2 = 1

ysub3 = ysub1+ysub2

then you reformulate this in terms of its z-transforms (these are the discrete versions of Laplace transforms).

You then work out the z-transform representation of the nth term of the sequence.

Then you perform an inverse z-tranform to get the generalized ysubn = <some formula with sqrt(5) in it>

I saw this done once. Really really cool. I just cannot seem to get started on it again. Any pointers out there from some 3rd year electrical engineer freshly through a course in digital signal processing?

Thanks for any pointers.

Relevance

Here is a typical example of using a z-transform to find the

expression for the nth term of the Fibonacci series. The method is

reasonably clear if you follow it through.

The difference equation for the Fibonacci series is:

u(n+2) = u(n+1) + u(n) with u(0) = 0, u(1) = 1

So:

u(n+2) - u(n+1) - u(n) = 0

Taking the transforms:

z^2[u(z) - u(0) - u(1)/z] - z[u(z) - u(0)] - u(z) = 0

u(z)[z^2 - z - 1] - z^2*u(0) - z*u(1) + z*u(0) = 0

Putting u(0) = 0 and u(1) = 1 this becomes:

u(z)[z^2 - z - 1] = z

z

u(z) = -------------

z^2 - z - 1

The denominator factorizes to:

[z-1/2 -sqrt(5)/2)][z-1/2 +sqrt(5)/2]

The trick here is to express u(z)/z in partial fractions:

1 1

u(z)/z = 1/sqrt(5)[ ---------------- - ---------------- ]

z-1/2 - sqrt(5)/2 z-1/2 +sqrt(5)/2

and so:

z z

u(z) = 1/sqrt(5)[---------------- - ------------------ ]

z-1/2-sqrt(5)/2) z-1/2+sqrt(5)/2

Then from table of inverse transforms:

z

------- = a^n

z - a

where a is constant. Then:

z z

u(z) = 1/sqrt(5) [-------------------- - --------------------]

z - (1/2+sqrt(5)/2) z - (1/2-sqrt(5)/2)

Now from the table of inverse transforms:

u(n) = 1/sqrt(5)[(1/2+sqrt(5)/2)^n - (1/2-sqrt(5)/2)^n]

-Doctor Anthony, The Math Forum

Check out our web site! http://mathforum.org/dr.math/