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

enter image description here enter image description here

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*}


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.