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 (from youtube.com):

a(n) = 2*a(n-1) + 4*a(n-2); a(0) = 1, a(1) = 3; [1, 3, 10, 32, ...]
a(n) - 2*a(n-1) - 4*a(n-2) = 0

 A       = 1 + 3x + 10x^2 + 32x^3 + ...
-(2x*A   =     2x +  6x^2 + 20x^3 + ...)
-(4x^2*A =           4x^2 + 12x^3 + ...)
----------------------------------------
(1 - 2x - 4x^2)*A = 1+x

A = (1 + x) / (1 - 2x - 4x^2) 

Example (from youtube.com):

a(n) = a(n-1) + 2*a(n-2) + 3; a(0) = 2, a(1) = 2; [2, 2, 9, 16, 37, 72, 149, 296, ...]
a(n) - a(n-1) - 2*a(n-2) = 3

 A       = 2 + 2x + 9x^2 + 16x^3 + 37x^4 + ...
-(x*A    =     2x + 2x^2 +  9x^3 + 16x^4 + ...)
-(2x^2*A =          4x^2 +  4x^3 + 18x^4 + ...)
----------------------------------------
(1 - x - 2x^2)*A = 2 + 3x^2 +3x^3 + 3x^4 + ... = 2 + 3x^2/(1-x) = (2 - 2x + 3x^2)/(1-x)

A = (2 - 2x + 3x^2) / ((1 - x - 2x^2)*(1 - x))

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

Coxeter Groups

The main entry is:

A169452 
Number of reduced words of length n in Coxeter group on 7 generators S_i 
with relations (S_i)^2 = (S_i S_j)^33 = I.
1, 7, 42, 252, 1512, 9072, 54432, 326592, 1959552
signature(5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,-15).
G.f.:(t^33+2*t^32+2*t^31+2*t^30
+2*t^29+2*t^28+2*t^27+2*t^26+2*t^25+2*t^24+2*t^23+2*t^22+2*t^21+2*t^20
+2*t^19+2*t^18+2*t^17+2*t^16+2*t^15+2*t^14+2*t^13+2*t^12+2*t^11+2*t^10
+2*t^9+2*t^8+2*t^7+2*t^6+2*t^5+2*t^4+2*t^3+2*t^2+2*t+1) / 
(15*t^33-5*t^32-5*t^31-5*t^30
-5*t^29-5*t^28-5*t^27-5*t^26-5*t^25-5*t^24-5*t^23-5*t^22-5*t^21-5*t^20
-5*t^19-5*t^18-5*t^17-5*t^16-5*t^15-5*t^14-5*t^13-5*t^12-5*t^11-5*t^10
-5*t^9-5*t^8-5*t^7-5*t^6-5*t^5-5*t^4-5*t^3-5*t^2-5*t+1)

• Harvey P. Dale gave this Mathematica program for the g.f. on Aug 16 2014:

coxG[{pwr_, c1_, c2_, trms_:20}] := Module[{
num=Total[  2t^Range[pwr-1]]+   t^pwr+1, 
den=Total[c2*t^Range[pwr-1]]+c1*t^pwr+1}, 
CoefficientList[Series[num/den, {t, 0, trms}], t]]; 
coxG[{33, 15, -5, 30}] (* for A169452 *)

• with the parameters:

pwr  = largest exponent in the g.f. 
    and of "(S_i S_j)" in the name,
c1   = first coefficient in the denominator of the g.f., 
     = triangular(-c2) = binomial(-c2 + 1, 2) 
c2   = - second coefficient in the denominator of the g.f., 
     = 2 - (numbers of generators in the name);
trms = number of terms desired (with a default number of 20)