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!

  • 6
    $\begingroup$ 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. $\endgroup$ – anon Oct 21 '11 at 23:06
  • $\begingroup$ @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 $\endgroup$ – Victor Oct 21 '11 at 23:10
  • 1
    $\begingroup$ Why do you think you can't ask the second one in a separate question? $\endgroup$ – Gerry Myerson Oct 21 '11 at 23:25
  • 7
    $\begingroup$ "i don't want to wait for five minute to ask" - Sorry to be blunt, but that sounds like a poor excuse to me. $\endgroup$ – Srivatsan Oct 22 '11 at 0:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Did Oct 22 '11 at 10:22

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.

  • $\begingroup$ -thank you very much, now i understand $\endgroup$ – Victor Oct 23 '11 at 0:30

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.