## 11.3. 11.3 Numerical solution

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(` `)`

```  1
`FOR` `TO` 2
`DO` 3
`FOR` `TO` 4
`DO` 5 6
`IF` 7
`THEN`

`FOR` `TO` 8
`DO` 9 10
`RETURN` ```

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.3-1 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`

`11-1` `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 .

`11-2` `Complex roots in case of Z-transform`

What happens if the roots of the denominator are complex when applying the Z-transform 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 [], Elaydi [], Flajolet and Sedgewick [], Greene and Knuth [], Mickens [], and also in the recent books written by Drmota [], further by Flajolet and Sedgewick []. Knuth [] and Graham, Knuth and Patashnik [] deal with generating functions. In the book of Vilenkin [] there are a lot of simple and interesting problems about recurrences and generating functions.

In [] Lovász also presents problems on generating functions. Counting the binary trees is from Knuth [], 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 [].