ordinary generating function for linear recursive relations

Let $(a_n)$ be a linear recursive sequence with values in a (commutative) ring $R$, i.e. there exist constants ${\beta }_1,\mathrm{\dots },{\beta }_k\in R$ such that for any $n>k$ we have

$$a_n={\beta }_1\cdot a_{n-1}+\mathrm{\cdots }+{\beta }_i\cdot a_{n-i}+\mathrm{\cdots }+{\beta }_k\cdot a_{n-k}.$$

Now consider the ordinary generating function for this sequence

$$f(t)=\sum _{n⩾0}{a}_n\cdot t^n$$

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

First write down first $k$ elements of this power series:

$$f(t)=\sum _{n=0}^k{a}_n\cdot t^n+\sum _{n>k}{a}_n\cdot t^n$$

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

$$f(t)=\sum _{n=0}^k{a}_n\cdot t^n+\sum _{n>k}({\beta }_1\cdot a_{n-1}+\mathrm{\cdots }+{\beta }_k\cdot a_{n-k})\cdot t^n$$

which gives us

$f(t)={\displaystyle \sum _{n=0}^k}{a}_n\cdot t^n+\left({\beta }_1\cdot t\cdot {\displaystyle \sum _{n>k}}{a}_{n-1}\cdot t^{n-1}\right)+\mathrm{\cdots }+\left({\beta }_k\cdot t^k\cdot {\displaystyle \sum _{n>k}}{a}_{n-k}\cdot t^{n-k}\right).$ (1)

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

$$\sum _{n>k}{a}_{n-j}\cdot t^{n-j}=\left(\sum _{n⩾0}{a}_n\cdot t^n\right)-\left(\sum _{n=0}^{k-j}{a}_n\cdot t^n\right)=f(t)-\left(\sum _{n=0}^{k-j}{a}_n\cdot t^n\right).$$

Inserting this into (1) gives us

$$f(t)=\sum _{n=0}^k{a}_n\cdot t^n+\left({\beta }_1\cdot t\cdot (f(t)-\sum _{n=0}^{k-1}{a}_n\cdot t^n)\right)+\mathrm{\cdots }+\left({\beta }_k\cdot t^k\cdot (f(t)-\sum _{n=0}^0{a}_n\cdot t^n)\right)$$

which can be simplified as follows:

$$f(t)=\sum _{n=0}^k{a}_n\cdot t^n+\sum _{j=1}^k\left({\beta }_j\cdot t^j\cdot (f(t)-\sum _{n=0}^{k-j}{a}_n\cdot t^n)\right).$$

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

$$f(t)-\sum _{j=1}^k{\beta }_j\cdot t^j\cdot f(t)=\sum _{n=0}^k{a}_n\cdot t^n-\sum _{j=1}^k\left({\beta }_j\cdot t^j\cdot \sum _{n=0}^{k-j}{a}_n\cdot t^n\right),$$

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

$$f(t)=\frac{\sum _{n=0}^k{a}_n\cdot t^n-\sum _{j=1}^k\left({\beta }_j\cdot t^j\cdot \sum _{n=0}^{k-j}{a}_n\cdot t^n\right)}{1-\sum _{j=1}^k{\beta }_j\cdot t^j}.$$

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 invertible in $R[[t]]$. Thus we proved the following theorem:

Theorem. If $(a_n)$ is a recursive sequnce given by

$$a_n={\beta }_1\cdot a_{n-1}+\mathrm{\cdots }+{\beta }_k\cdot a_{n-k}$$

for all $n>k$ then the ordinary generating function

$$f(t)=\sum _{n⩾0}{a}_n\cdot t^n$$

has its closed form given by

$$f(t)=\frac{\sum _{n=0}^k{a}_n\cdot t^n-\sum _{j=1}^k\left({\beta }_j\cdot t^j\cdot \sum _{n=0}^{k-j}{a}_n\cdot t^n\right)}{1-\sum _{j=1}^k{\beta }_j\cdot t^j}.$$

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 functions. 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