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.