# Understanding a proof regarding the relationship between rational generating functions and linear recurrence relations

I'm trying to understand this lemma from my course notes:

It's my understanding that a linear recurrence relation is one of the form $$x_n = p(n, x_{n - 1}, \dots, x_{n - k}) = q(n) + b_1 x_{n - 1} + b_2 x_{n - 2} + \dots + b_k x_{n - k}$$ for $$n \geq k$$. This recurrence relation is homogeneous if $$q = 0$$.

I find the above proof very terse, so below I give my understanding along with comments/questions where I don't understand things.

First part: Rational generating function defines a homogeneous linear recurrence relation

Start with $$f(x) = a_0 + a_1 x + \dots = \frac{g(x)}{h(x)}$$ where $$g(x) = b_l x^l + \dots + b_0$$ and $$h(x) = c_k x^k + \dots + c_0$$. Bring the denominator over to the left so you get $$(c_k x^k + \dots + c_i x_i) (a_0 + a_1 x + \dots ) = b_l x^l + \dots + b_0$$. We want to set up something like $$a_j = \alpha_1 a_{j - 1} + \dots + \alpha_n a_{j - n}$$. Because we are trying to set up a linear homogeneous recurrence relation, we clearly need to set up something that will work for all $$j > \text{[something]}$$, but it's not clear at this stage what that something should be.

Clearly based on the product $$(c_k x^k + \dots + c_i x_i) (a_0 + a_1 x + \dots )$$ we are going to get products of $$a$$ coefficients with $$c$$ coefficients. This suggests that we might have to divide an expression involving $$a_j c_{\text{something}}$$ by $$c_{\text{something}}$$ in order to isolate $$a_j$$. The only two $$c_{\text{something}}$$s that we know are not equal to zero are $$c_i$$ and $$c_k$$ (which may or may not be distinct).

If we try to work with $$c_k$$ then we would be looking at the coefficient for the $$x^{k + j}$$ term, which would be something like $$c_k a_j + c_{k - 1} a_{j + 1} + \dots + c_i a_{j + (k - i + 1)}$$. This doesn't look like the type of expression we're looking for ($$a_j = \alpha_1 a_{j - 1} + \dots + \alpha_n a_{j - n}$$) so we'll try using $$c_i$$.

If we use $$c_i$$ then we are looking at the coefficient for the $$x^{i + j}$$ term, which would be something like $$c_i a_j + c_{i + 1} a_{j - 1} + \dots + c_k a_{j - (k - i)}$$. Comparing both sides of $$(c_k x^k + \dots + c_i x_i) (a_0 + a_1 x + \dots ) = b_l x^l + \dots + b_0$$, we see that $$c_i a_j + c_{i + 1} a_{j - 1} + \dots + c_k a_{j - (k - i)} = b_{i + j}$$. We want $$b_{i + j} = 0$$ so that we can just divide by $$c_i$$ and move terms over and get our desired recurrence relation. This implies a restriction $$i + j > l$$. We also see that we need $$j - (k - i) \geq 0$$, so our restrictions on $$j$$ are that $$j > l - i$$ and $$j \geq k - i$$.

Given this, we can divide both sides of $$c_i a_j + c_{i + 1} a_{j - 1} + \dots + c_k a_{j - (k - i)} = 0$$ by $$c_i$$ and we get that $$a_j = - \frac{1}{c_i} ( c_{i + 1} a_{j - 1} + \dots + c_k a_{j - (k - i)})$$, which is our desired recurrence relation.

Why is my bound for $$j$$ different from that given in the proof ($$j > \max \{ k, l \}$$)?

Second part: linear recurrence relation (having function $$q(n)$$ that has its own rational generating function) has a rational generating function

This part doesn't make much sense to me at all. I see that $$q$$ essentially defines a sequence starting at index $$k$$, as opposed to zero, so I can see that $$q$$ could have an associated generating function. However the generating function $$g(x)$$ given for $$q$$ is not even a polynomial, much less rational. Is the assumption that $$g(x)$$ can be expressed in a rational form?

I guess $$f(x)$$ is supposed to be the generating function for the linear recurrence relation? I suppose a linear recurrence relation defines a sequence so there is guaranteed to be an associated generating function.

We define the function $$h$$ in such a way that all its coefficients beyond $$k - 1$$ are zero. Since $$g(x)$$ is presumed to be rational, we can write $$g(x) = \frac{r(x)}{s(x)}$$ where $$r$$ and $$s$$ are polynomials, therefore to be more thorough we can write $$f(x) = \frac{h(x)s(x) + r(x)}{s(x)(1 - b_1 x - b_2 x^2 - \dots - b_k x^k)}$$.

Does what I'm saying about this second part make sense? I am trying to talk myself through it. What is the intuition behind the definition of $$h(x)$$? I guess we're trying to make some kind of finite polynomial and that is the definition that works?

I appreciate any help.

First part: We have a generating function $$f(x)=a_0+a_1x+a_2x^2+\cdots$$ which is a rational function \begin{align*} f(x)&=\frac{g(x)}{h(x)}\\ a_0+a_1x+a_2x^2+\cdots&=\frac{b_0+b_1x+\cdots+b_lx^l}{c_0+c_1x+\cdots+c_kx^k}\qquad\qquad b_l\ne 0, c_k\ne 0 \end{align*} We consider $$h(x)f(x)=g(x)$$ and obtain \begin{align*} &\left(c_ix^i+c_{i+1}x^{i+1}+\cdots+c_kx^k\right)\left(a_0+a_1x+a_2x^2+\cdots\right)\\ &\qquad=b_0+b_1x+\cdots+b_lx^l\tag{1} \end{align*} with $$c_i\ne 0$$ the coefficient of the smallest power of $$x$$ of $$h(x)$$ not equal to zero.

In the following we use the coefficient of operator $$[x^q]$$ to denote the coefficient of $$x^q$$ of a series. We want to find a recurrence relation in terms of $$a_j,$$. We take $$j>\max\{k,l\}$$ which is convenient, since the coefficient of $$[x^j]g(x)=0$$ and $$[x^j]h(x)f(x)$$ has to respect all coefficients of $$h(x)$$.

We calculate $$[x^{j+i}]h(x)f(x)$$ and obtain from (1) \begin{align*} \color{blue}{[x^{j+i}]h(x)f(x)}&=[x^{j+i}]\left(c_ix^i+c_{i+1}x^{i+1}+\cdots+c_kx^k\right)\\ &\qquad\qquad\qquad\cdot \left(a_0+a_1x+a_2x^2+\cdots\right)\\ &=\left(c_i[x^{j+i}]x^i+c_{i+1}[x^{j+i}]x^{i+1}+\cdots+c_k[x^{j+i}]x^k\right)\tag{2}\\ &\qquad\qquad\qquad\cdot \left(a_0+a_1x+a_2x^2+\cdots\right)\\&=\left(c_i[x^{j}]+c_{i+1}[x^{j-1}]+\cdots+c_k[x^{j+i-k}]\right)\tag{3}\\ &\qquad\qquad\qquad\cdot \left(a_0+a_1x+a_2x^2+\cdots\right)\\ &\,\,\color{blue}{=c_ia_j+c_{i+1}a_{j-1}+\cdots+c_{k}a_{j+i-k}}\tag{4}\\ \end{align*}

Comment:

• In (2) we use the linearity of the coefficient of operator.

• In (3) we apply the rule $$[x^p]x^qA(x)=[x^{p-q}]A(x)$$.

• In (4) we select the coefficient of $$[x^q], j+i-k\leq q \leq j$$.

Since $$j>\max\{k,l\}$$ we obtain from (1) \begin{align*} \color{blue}{[x^{j+i}]g(x)}=[x^{j+i}]\left(b_0+b_1x+\cdots+b_lx^l\right)\color{blue}{=0}\tag{5} \end{align*} and we obtain from (4) and (5) \begin{align*} \color{blue}{a_j=-\frac{c_{i+1}}{c_i}a_{j-1}-\cdots-\frac{c_{k}}{c_i}a_{j+i-k}} \end{align*} in accordance with the proof of the lemma.

Second part: Note the Lemma states:

• ... Furthermore if ... the function $$q(n)$$ has a rational generating function ...

It follows a representation of the generating function $$g(x)=\frac{r(x)}{s(x)}$$, with $$r, s$$ polynomials, wlog relatively prime and $$\deg{r}<\deg{s}$$ is admissible.