Computing the Generating Function of a C-finite sequence Dr. Z.

Input: A C-finite sequence a(n) that is a solution of a (homogeneous) linear recurrence equation with constnt coefficient

a(n) = R_{1}a(n − 1) + … + R_{d}a(n − d) ,

subject to the initial conditions

a(0) = a_{0}, …, a(d − 1) = a_{d−1} .

Note: this ‘infinite’ sequence is a finite object, and we represent it in class as a pair of lists

[INI,REC] where

INI = [a_{0}, …, a_{d−1}] , REC = [R_{1}, …, R_{d}] .

The (ordinary) generating function of a sequence a(n), 0 ≤ n < ∞ is, by definition

f(x) = ∑_{n=0}^{∞} a(n)x^{n} .

How to go from the C-finite description to the generating function For n ≥ d we have

a(n) = R_{1}a(n − 1) + … + R_{d}a(n − d) ,

Hence

f(x) = ∑_{n=0}^{∞} a(n)x^{n} = ∑_{n=0}^{d−1} a(n)x^{n} + ∑_{n=d}^{∞} a(n)x^{n}

= ∑_{n=0}^{d−1} a(n)x^{n} + ∑_{n=d}^{∞} (R_{1}a(n − 1) + R_{2}a(n − 2) + … + R_{d}a(n − d)) x^{n} .

Distributing, we have

f(x) = ∑_{n=0}^{d−1} a(n)x^{n}

+ ∑_{n=d}^{∞} R_{1}a(n − 1)x^{n} + ∑_{n=d}^{∞} R_{2}a(n − 2)x^{n} + … + ∑_{n=d}^{∞} R_{d}a(n − d)x^{n} .

Rewritng: we get

f(x) = ∑_{n=0}^{d−1} a(n)x^{n}

+ R_{1}x ∑_{n=d}^{∞} a(n − 1)x^{n−1} + R_{2}x^{2} ∑_{n=d}^{∞} a(n − 2)x^{n−2} + … + R_{d}x^{d} ∑_{n=d}^{∞} a(n − d)x^{n−d} .

Changing the index of summation we get

f(x) = ∑_{n=0}^{d−1} a(n)x^{n}

+ R_{1}x ∑_{n=d−1}^{∞} a(n)x^{n} + R_{2}x^{2} ∑_{n=d−2}^{∞} a(n)x^{n} + … + R_{d}x^{d} ∑_{n=0}^{∞} a(n)x^{n} .

It follows that

f(x) = P OLY NOMIAL_{d−1}(x) + (R_{1}x + dots + R_{d}x^{d})f(x)

where P OLY NOMIAL_{d−1}(x) is some polynomial of degree d − 1. Hence

f(x)(1 − (R_{1}x + dots + R_{d}x^{d})) = P OLY NOMIAL_{d−1}(x) ,

and hence

f(x) = \frac{P OLY NOMIAL_{d−1}(x)}{)(1 − (R_{1}x + dots + R_{d}x^{d}))} .

This explains why f(x) is always a rational function, why its denominator is what it is. As for the numerator, the best way is to find it empirically as we did in class.

Dr. Z. Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad at gmail dot com .