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