# Question about generating function in an article

Could someone explain what $R(x)$ and constant $c_1,c_2,…,c_k$ are in this article about characteristic polynomial in proof 3?

If that someone could rephrase it, because it seems not so clear in the link provided, I would appreciate it. Could you give me a example?

#### Solutions Collecting From Web of "Question about generating function in an article"

I’ll take the following problem as an example of how to use generating functions in recurrences:

Let $p_{n+1}=3p_{n}-p_{n-1}$ with $p_0=5,p_1=7$. What is the general form of $p_n$?

Define the following generating function:
$$P(x)=\sum_{n=0}^\infty p_nx^n= p_0+p_1x+p_2x^2+p_3x^3+\cdots.$$
Notice that
$$3P(x)-xP(x)=3p_0+(3p_1-p_0)x+(3p_2-p_1)x^2+(3p_3-p_2)x^3+\cdots.$$
We can simplify this using the recurrence to the following:
$$(3-x)P(x)=3p_0+\color{Blue}{p_2x+p_3x^2+p_4x^3+\cdots}.$$
Now the blue part looks familiar. In fact, it’s just the usual expansion for $P(x)$, but with the first two terms cut off and then the powers of $x$ reduced one, so this is:
$$(3-x)P(x)=3p_0+\frac{P(x)-(p_0+p_1x)}{x}$$
$$\implies [x(3-x)-1]P(x)=(3p_0-p_1)x-p_0.$$
Remark: It’s unclear to me whether the AoPS article forgot an initial term or wanted us to subsume the initial $3p_0$ into the fraction in order to form the remainder polynomial $R(x)$. The important fact to take away is that we use the recurrence to simplify the right side involving only $P(x)$ and other basic operations with $x$, specifically as something plus $P(x)$ minus a cut-away divided by a power of $x$. Plug in the initial values for $p_0,p_1$ and divide for
$$P(x)=\frac{8x-5}{-x^2+3x-1}.$$
Now we attempt partial fraction decomposition. The quadratic formula tells us that the roots of the denominator polynomial $x^2-3x+1$ are $u=(3+\sqrt{5})/2$ and $v=(3-\sqrt{5})/2$. We then write:
$$-P(x)=\frac{8x-5}{x^2-3x+1}=\frac{A}{x-u}+\frac{B}{x-v}.$$
Combine the fractions on the right side and focus on numerators to get:
$$8x-5=(A+B)x-(vA+uB)$$
$$\implies \begin{pmatrix}1&1\\v&u\end{pmatrix}\begin{pmatrix}A\\B\end{pmatrix}=\begin{pmatrix}8\\5\end{pmatrix}$$
$$\implies\begin{pmatrix}A\\B\end{pmatrix}=\frac{1}{u-v}\begin{pmatrix}u&-1\\-v&1\end{pmatrix}\begin{pmatrix}8\\5\end{pmatrix}$$
$$=\frac{1}{\sqrt{5}}\begin{pmatrix}+7+4\sqrt{5}\\-7+4\sqrt{5}\end{pmatrix}.$$
Finally, we can expand $P(x)$ using the geometric series formula to get:
$$P(x)=-\frac{A}{x-u}-\frac{B}{x-v}$$
$$=\frac{A/u}{1-x/u}+\frac{B/v}{1-x/v}$$
$$=\sum_{n=0}^\infty \left(Au^{-1-n}+Bv^{-1-n}\right)x^n$$
$$=\sum_{n=0}^\infty\left[ (4+7/\sqrt{5})\left(\frac{3-\sqrt{5}}{2}\right)^{n+1}+(4-7/\sqrt{5})\left(\frac{3+\sqrt{5}}{2}\right)^{n+1}\right]x^n.$$
Note that we used $u^{-1}=v$ and $v^{-1}=u$. The expression inside the square brackets is therefore the formula of $p_n$. Also keep in mind this example is a bit more complicated than usual. Finally, remember that this is an example of a linear recurrence derived using the method described on the AoPS article; it does not apply to the original non$\text{}$linear problem you posted.