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}]

Computation of the G.F. from the Lin.Rec.

Example:

 A173652: 0, 0, 0,  1,   4,   8,  33,  68, 245, 549, 1815 ...
                                             x^3  x^4  x^5  x^6  x^7  x^8  x^9  x^10
 LinearRecurrence[{0,    9,     3,    -17,    -8,     6,     7,    -1,    1}, {0, 0, 0, 1, 4, 8, 33, 68, 245}, 31]
 denominator: (1 + 0x^1- 9x^2 - 3x^3 + 17x^4 + 8x^5 - 6x^6 - 7x^7 + x^8 - x^9)
 numerator: x^3