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?

Thanks in advance!

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.