OEIS/Generating Functions and Recurrences

Linear Recurrence

• The linear recurrence is computed from an ordinary, rational generating function (with a fraction of two univariate polynomials) by polynomial division beginning with of the lowest term:

 1 / (1-x-x^2) = 1 + x + 2x^2 + 3x^3 + 5x^5 ... (Fibonnacci, A000045)
-1 + x + x^2
------------
     x + x^2  
    -x + x^2 + x^3
    --------------
        2x^2 + x^3
       -2x^2 + 2x^3 + 2x^4
       -------------------
               3x^2 + 2x^4
              -3x^3 + 3x^4 + 3x^5
              -------------------
                      5x^4 + 3x^5 

• The denominator's coefficients (without the constant 1) are the signature of the linear recurrence. THe number of elements in the signature is the order of the recurrence.
• This is equivalient to:

 a(0) = 1, a(1) = 1, a(n) = a(n - 1) + a(n - 2) for n > 1. 

• The number of initial terms must be >= the order.

Corresponding Mathematica functions:

 LinearRecurrence[{signature}, {initial terms}, number of terms]
 LinearRecurrence[{1, 1}, {1, 1}, 8] for the Fibonnacci sequence
 FindLinearRecurrence[{initial terms}]