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


Now consider the ordinary generating function for this sequence


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:


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


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


Inserting this into (1) gives us


which can be simplified as follows:


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


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


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


for all n>k then the ordinary generating function


has its closed form given by


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