OEIS/Generating Functions and Recurrences

Linear Recurrences

• There is a one-to-one relation between a linear recurrence and an ordinary, rational generating functions ("g.f.", with a fraction of two univariate polynomials).
• The linear recurrence is computed from the g.f. 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    <---- denominator * (-1)
------------    <---- add
 0 + x +  x^2  
    -x +  x^2 + x^3
    --------------
     0 + 2x^2 + x^3
        -2x^2 + 2x^3 + 2x^4
       -------------------
          0   + 3x^2 + 2x^4
               -3x^3 + 3x^4 + 3x^5
               -------------------
                 0   + 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[{terms}]

Generating Functions

• Corresponding Mathematica functions:

 CoefficientList[Series[numerator_polynomial / denominator_polynomial, {x, 0, number of terms}], x]
 CoefficientList[Series[-(x/(-1 + x + x^2)), {x, 0, 20}], x]
 FindGeneratingFunction[{terms}]