# 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?

• That article is about linear recurrences, while what you have is a nonlinear recurrence, so what's written there does not apply to your question as it stands. – anon Oct 21 '11 at 23:06
• @anon -As i say, those thing are new to me, but i think i can't ask the second one in a seperate question, so i chose to post it here – Victor Oct 21 '11 at 23:10
• Why do you think you can't ask the second one in a separate question? – Gerry Myerson Oct 21 '11 at 23:25
• "i don't want to wait for five minute to ask" - Sorry to be blunt, but that sounds like a poor excuse to me. – Srivatsan Oct 22 '11 at 0:37
• Maybe you should wait for five minutes to think: these are definitely not the same topic (ever heard of the iteration of some quadratic functions?) And +1 to @Srivatsan's last comment. – Did Oct 22 '11 at 10:22

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.