## 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 [].