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