Moving from a rational generating function to recurrence relation

Question

I am trying to understand the following segment of my notes:

.

I will try to explain what I think I understand and point out the parts I don't understand.

First, there is a result in my notes (not shown here) proving that a rational generating function defines a homogeneous recurrence relation. Then, I consult the following section of my notes:

.

This is a procedure for turning a homogeneous recurrence relation into a generating function (in its rational form). Given the rational form $f(x) = \frac{1 + 7x}{1 + x - 6x^2}$, we see that the coefficients that define the homogeneous recurrence relation (i.e. the $b_1, \dots, b_k$) are located in the denominator, so we conclude that $a_n = 6 a_{n - 2} - a_{n - 1}$.

I don't understand how the initial conditions $a_0 = 1$ and $a_1 = 6$ are determined through long division. I am only vaguely familiar with polynomial division so I may be missing something obvious, but isn't $\frac{1 + 7x}{1 + x - 6x^2}$ simply equal to $1 + 7x$, because the degree of the numerator is less than the degree of the denominator? How does this help me determine the initial conditions?

According to my notes (not shown here), the "term formula" as I call it for the $i$th coefficient $a_i$ of the generating function can be found by factoring the denominator of $\frac{1 + 7x}{1 + x - 6x^2}$ into a suitable form, applying the method of partial fractions and using a result regarding the term formula for $\frac{1}{(1 - cx)^k}$ for $c \in \mathbb C$. Eventually I get that $a_i = \frac{9}{5} \cdot 2^i - \frac{4}{5} (-3)^i$, which is the same result as the one in my notes, and from this we can determine the initial conditions $a_0$ and $a_1$.

I appreciate any help.

Answer 1

$\frac{1+7x}{1+x-6x^2}$ is certainly not equal to $1+7x$, since $1+x-6x^2$ is not identically equal to $1$. The fact that the degree of the numerator is less than that of the denominator is not a bar to doing long division. If you divide $1+7x$ by $1+x-6x^2$ using ordinary polynomial long division, but starting at the low order end, for the first four terms you get:

$$\begin{array}{ccc} &&&&&&1&+&6x&&&+&36x^3\\ &&&&&&-&-&-&-&-&-&-\\ 1&+&x&-&6x^2&)&1&+&7x\\ &&&&&&1&+&x&-&6x^2\\ &&&&&&-&-&-&-&-\\ &&&&&&&&6x&+&6x^2\\ &&&&&&&&6x&+&6x^2&-&36x^3\\ &&&&&&&&-&-&-&-&-\\ &&&&&&&&&&&&36x^3 \end{array}$$

If you keep going, you can get as much of the power series as you want. You know that the power series is $\sum_{n\ge 0}a_nx^n$, so this already shows that $a_0=1$, $a_1=6$, $a_2=0$, and $a_3=36$.

You are correct, however, in thinking that you can also determine $a_0$ and $a_1$ from the closed form that you get from power series expansions of the partial fractions.

Answer 2

How polynomial long division shows that $a_0=\color{blue}1$ and $a_1= \color{green}6$:

$$ \require{enclose} \begin{array}{r} &\color{blue}1+\color{green}6x\dots \\[-3pt] 1+x-6x^2 &\enclose{longdiv}{1+7x} \\[-3pt] &\underline{\color{blue}{1+x-6x^2}}\phantom{2} \\[-3pt] &6x+6x^2 \\[-3pt] &\underline{\color{green}{6x+6x^2-36x^3}} \end{array} $$

[Editing for better alignment is welcomed.]