# 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},\ldots,\beta_{k}\in R$ such that for any $n>k$ we have

 $a_{n}=\beta_{1}\cdot a_{n-1}+\cdots+\beta_{i}\cdot a_{n-i}+\cdots+\beta_{k}% \cdot a_{n-k}.$

Now consider the ordinary generating function for this sequence

 $f(t)=\sum_{n\geqslant 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}+\cdots+% \beta_{k}\cdot a_{n-k})\cdot t^{n}$

which gives us

 $\displaystyle f(t)=\sum_{n=0}^{k}a_{n}\cdot t^{n}+\left(\beta_{1}\cdot t\cdot% \sum_{n>k}a_{n-1}\cdot t^{n-1}\right)+\cdots+\left(\beta_{k}\cdot t^{k}\cdot% \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\geqslant 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)+\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\limits_{n=0}^{k}a_{n}\cdot t^{n}-\sum\limits_{j=1}^{k}\left(% \beta_{j}\cdot t^{j}\cdot\sum\limits_{n=0}^{k-j}a_{n}\cdot t^{n}\right)}{1-% \sum\limits_{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}+\cdots+\beta_{k}\cdot a_{n-k}$

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

 $f(t)=\sum_{n\geqslant 0}a_{n}\cdot t^{n}$

has its closed form given by

 $f(t)=\frac{\sum\limits_{n=0}^{k}a_{n}\cdot t^{n}-\sum\limits_{j=1}^{k}\left(% \beta_{j}\cdot t^{j}\cdot\sum\limits_{n=0}^{k-j}a_{n}\cdot t^{n}\right)}{1-% \sum\limits_{j=1}^{k}\beta_{j}\cdot t^{j}}.$

Remark. Note that if we replace $R$ with (for example) the reals $\mathbb{R}$ 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 OrdinaryGeneratingFunctionForLinearRecursiveRelations 2013-03-22 19:20:07 2013-03-22 19:20:07 joking (16130) joking (16130) 7 joking (16130) Theorem msc 13H05 msc 13B35 msc 13F25 msc 13J05