1
$\begingroup$

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
    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.2011-10-21
  • 0
    @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 here2011-10-21
  • 1
    Why do you think you can't ask the second one in a separate question?2011-10-21
  • 7
    "i don't want to wait for five minute to ask" - Sorry to be blunt, but that sounds like a poor excuse to me.2011-10-22
  • 1
    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](http://myweb.cwpost.liu.edu/aburns/orbits/quadrati.htm)?) And +1 to @Srivatsan's last comment.2011-10-22
  • 0
    Please ask that other question as a separate question.2011-10-23

1 Answers 1

4

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.

  • 0
    -thank you very much, now i understand2011-10-23