7.3 SOLVING RECURRENCES 325
also has nice coefficients,
+ . . . + al
P? *
(7.27)
We will show that every rational function R(z) such that R(0) # 00 can be expressed in the form R(z) = S(z) t T(z),
(7.28)
where S(z) has the form (7.26) and T(z) is a polynomial. Therefore there is a closed form for the coefficients [z”] R(z). Finding S(z) and T(z) is equivalent to finding the “partial fraction expansion” of R(z). Notice that S(z) = 00 when z has the values l/p,, . . . , l/pi. Therefore the numbers pk that we need to find, if we’re going to succeed in expressing R(z) in the desired form S(z) + T(z), must be the reciprocals of the numbers &k where Q(ak) = 0. (Recall that R(z) = P(z)/Q(z), where P and Q are polynomials; we have R(z) = 00 only if Q(z) = 0.) Suppose Q(z) has the form Q(z)
= qo+q1z+~~~+q,z”‘,
where qo # 0 and q,,,
# 0.
The “reflected” polynomial QR(z)
= qoP+ q,z"-'
+...f q,,,
has an important relation to Q (2):
QR(4 = qo(z - PI 1. . . (2 - P,) w Q(z) = qo(l -PIZ)...(~
-P~z)
Thus, the roots of QR are the reciprocals of the roots of Q, and vice versa. We can therefore find the numbers pk we seek by factoring the reflected polynomial QR(z). For example, in the Fibonacci case we have Q(z) = 1 -2-z’;
QR(z) = z2-z-l.
The roots of QR ca.n be found by setting (a, b, c) = (1, -1, -1) in the quadratic formula (-b II: da)/2a; we find that they are l+ds
+=2
a n d
1-d
$ = 2
Therefore QR(z) = (z-+)(2-$) and Q(z) = (1 -+z)(l -i$z).
