ordinary generating function for linear recursive relations


Let (an) be a linear recursive sequence with values in a (commutative) ring R, i.e. there exist constants β1,,βkR such that for any n>k we have

an=β1an-1++βian-i++βkan-k.

Now consider the ordinary generating function for this sequence

f(t)=n0antn

which is a formal power seriesMathworldPlanetmath in the ring of formal power series R[[t]]. We will try to find the closed formMathworldPlanetmath of f(t).

First write down first k elements of this power seriesMathworldPlanetmath:

f(t)=n=0kantn+n>kantn

and note that for n>k we can use our recursive relation:

f(t)=n=0kantn+n>k(β1an-1++βkan-k)tn

which gives us

f(t)=n=0kantn+(β1tn>kan-1tn-1)++(βktkn>kan-ktn-k). (1)

Now focus on those sums on the right. For any j we have

n>kan-jtn-j=(n0antn)-(n=0k-jantn)=f(t)-(n=0k-jantn).

Inserting this into (1) gives us

f(t)=n=0kantn+(β1t(f(t)-n=0k-1antn))++(βktk(f(t)-n=00antn))

which can be simplified as follows:

f(t)=n=0kantn+j=1k(βjtj(f(t)-n=0k-jantn)).

Taking the components with f(t) to the left side gives us

f(t)-j=1kβjtjf(t)=n=0kantn-j=1k(βjtjn=0k-jantn),

which finally gives us the closed formula for f(t) (note that all sums are finite):

f(t)=n=0kantn-j=1k(βjtjn=0k-jantn)1-j=1kβjtj.

Note that in the denominator we have a power series with the constant term 1, thus (by general properties of formal power series) it is invertiblePlanetmathPlanetmath in R[[t]]. Thus we proved the following theorem:

Theorem. If (an) is a recursive sequnce given by

an=β1an-1++βkan-k

for all n>k then the ordinary generating function

f(t)=n0antn

has its closed form given by

f(t)=n=0kantn-j=1k(βjtjn=0k-jantn)1-j=1kβjtj.

Remark. Note that if we replace R with (for example) the reals then the theorem is still valid if we treat those power series as functionsMathworldPlanetmath. Of course such equalites hold only there where those functions are defined.

Title ordinary generating function for linear recursive relations
Canonical name OrdinaryGeneratingFunctionForLinearRecursiveRelations
Date of creation 2013-03-22 19:20:07
Last modified on 2013-03-22 19:20:07
Owner joking (16130)
Last modified by joking (16130)
Numerical id 7
Author joking (16130)
Entry type Theorem
Classification msc 13H05
Classification msc 13B35
Classification msc 13F25
Classification msc 13J05