Using the following function we can solve the linear recurrent equations numerically. The equation is given in the form
where . The coefficients are kept in array , the initial values in array . To find we will compute step by step the values , keeping in the previous values of the sequence in the first positions of (i.e. in the positions with indices ).
Recurrence(
)
1FOR
TO
2DO
3FOR
TO
4DO
5 6IF
7THEN
FOR
TO
8DO
9 10RETURN
Lines 2–5 compute the values () (using the previous values), denoted by in the algorithm. In lines 7–9, if is not yet reached, we copy the last values in the first positions of . In line 10 is obtained. It is easy to see that the computation time is , if we disregard the time to compute the values of the function.
Exercises
11.31 How many additions, subtractions, multiplications and divisions are required using the algorithm
Recurrence
, while it computes using the data given in Example 11.4?
PROBLEMS

111
Existence of a solution of a homogeneous equation using generating function
Prove that a linear homogeneous equation cannot be solved using generating functions (because is obtained) if and only if for all .
112
Complex roots in case of Ztransform
What happens if the roots of the denominator are complex when applying the Ztransform method? The solution of the recurrence equation must be real. Does the method ensure this?
CHAPTER NOTES

Recurrence equations are discussed in details by Agarwal [ 1 ], Elaydi [ 69 ], Flajolet and Sedgewick [ 230 ], Greene and Knuth [ 99 ], Mickens [ 180 ], and also in the recent books written by Drmota [ 67 ], further by Flajolet and Sedgewick [ 75 ]. Knuth [ 144 ] and Graham, Knuth and Patashnik [ 98 ] deal with generating functions. In the book of Vilenkin [ 263 ] there are a lot of simple and interesting problems about recurrences and generating functions.
In [ 167 ] Lovász also presents problems on generating functions. Counting the binary trees is from Knuth [ 144 ], counting the leaves in the set of all binary trees and counting the binary trees with vertices and leaves are from Zoltán Kása [ 141 ].