# Solving a recurrence of polynomials

I am wondering how to solve a recurrence of this type

$$p_1(x) = x$$ $$p_2(x) = 1-x^2$$

and

$$p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x).$$

I am wondering, how could one solve such a recurrence. One way would be to pretend $x$ is fixed and solve it using the well known method for linear recurrences. My problem with this is that it gets rather messy and besides when solving for the initial terms one gets a fraction that is not well defined for all $x$.

I would therefore like to ask if there is an easier way to solve it or perhaps whats the proper way to apply the theory of linear recurrences.

Edit. The recurrence is indeed of second order.

-
Because the order of the recurrence equation is 4, you need two more initial conditions for the problem to be well posed. –  Sasha Aug 16 '12 at 19:07
Are you sure the recurrence form is not: $$p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x)$$ –  S4M Aug 16 '12 at 19:56
You have a forth order recurrence relation with constant coefficients which can be solved in a closed form. If you feed this to Maple you will get the answer. –  Mhenni Benghorbal Aug 16 '12 at 20:00
@S4M You are right, the recurrence is indeed of this form! –  Jernej Aug 16 '12 at 20:49

related problem: (I), (II), (III). Here is the solution of the corrected recurrence relation computed by maple

$$\left( -3\,x-\sqrt {{x}^{2}+4} \right)\left( -2\, \left( -x-\sqrt{{x}^{2}+4} \right)^{-1} \right) ^{n}{\frac {1}{\sqrt {{x}^{2}+4}}}\left( -x-\sqrt {{x}^{2}+4} \right)^{-1}$$ $$+ \left( 3\,x-\sqrt {{x}^{2}+4} \right)\left( -2\,\left( -x+\sqrt {{x}^{2}+4} \right)^{1} \right) ^{n}{\frac {1}{\sqrt {{x}^{2}+4}}} \left( -x+\sqrt {{x}^{2}+4}\right)^{-1}$$

If you are interested in how you can solve it. Assume your solution $p_n = r^n\,,$ for some $r$ to be determined and substitute in your recurrence relation which gives

$$r^{n+2} + x r^{n+1} - r^n = 0 \Rightarrow r^n(r^2+xr-1)=0 \Rightarrow (r^2+xr-1)=0$$ $$r_1 = -\frac{1}{2}\,x+\frac{1}{2}\sqrt {{x}^{2}+4}\,, \,\,\, \, r_2 = -\frac{1}{2}\,x - \frac{1}{2}\,\sqrt {{x}^{2}+4}$$ Now, you construct the general solution as $$p_n(x) = c_1 {r_{1}}^n + c_2 {r_{2}}^n = c_1 {\left( -\frac{1}{2}\,x+\frac{1}{2}\sqrt {{x}^{2}+4} \right)}^n + {\left( -\frac{1}{2}\,x - \frac{1}{2}\,\sqrt {{x}^{2}+4} \right)}^n$$ To determine the constants $c_1$ and $c_2$, you just need to exploit the initial conditions $p_0(x)$ and $p_1(x)$ and solve for $c_1$ and $c_2$.

-

Notice that the recurrence equation is constant coefficients, with respect to $n$. It can be solved using the generating function approach. Multiply both sides of the equation with $t^n$ and sum over $n\geqslant 2$: $$\sum_{n=2}^\infty t^n p_{n+2} = -x \sum_{n=2}^\infty t^n p_{n+1} + \sum_{n=2}^\infty t^n p_{n-2}$$ Defining $g(t,x) = \sum_{n=0}^\infty t^n p_n(x)$ this translates into: $$\frac{1}{t^2} \left( g(t,x) - p_0(x) -t p_1(x) -t^2 p_2(x) - t^3 p_3(x) \right) = -\frac{x}{t} \left(g(t,x)-p_0(x) - t p_1(x) - t^2 p_2(x) \right) + t^2 g(t,x)$$ giving: $$g(t,x) = \frac{1+t x}{1+t x-t^4} \left( p_0(x) + t p_1(x) + t^2 p_2(x) \right) + \frac{t^3}{1+t x-t^4} p_3(x)$$ The general solution $p_n(x)$ is obtained by extracting series coefficient: $$p_n(x) = [t]^n g(t,x)$$

Here is verification in Mathematica:

-

Alternatively, compare your recurrence to known recurrences.
In this case, the Chebyshev polynomials ... result:

$$p_n(x) = i^{n} \Biggl(4 T_n \biggl(\frac{ix}{2}\biggr) - 3 U_n \biggl(\frac{ix}{2}\biggr)\Biggr)$$

-

I tried another generating function approach for $p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x)$ and did not realize until I got an obviously wrong answer why the method was wrong.

You lucky readers might enjoy finding out why the method was wrong.

Let $F(x) =\sum_{n=1}^{\infty} x^n p_n(x)$. Since $0 = p_{n+2}(x) +xp_{n+1}(x)-p_{n}(x)$, I will try to get $0 = \sum_{n=1}^{\infty} x^n(p_{n+2}(x) +xp_{n+1}(x)-p_{n}(x))$ in terms of $F(x)$ so as to get a formula for $F(x)$.

\begin{align} \sum_{n=1}^{\infty} x^n p_{n+2}(x) &=x^{-2}\sum_{n=1}^{\infty} x^{n+2} p_{n+2}(x)\\ &=x^{-2}\sum_{n=3}^{\infty} x^{n} p_{n}(x)\\ &=x^{-2}(-xp_1(x)-x^2p_2(x)+\sum_{n=1}^{\infty} x^{n} p_{n}(x))\\ &=x^{-2}(-xp_1(x)-x^2p_2(x)+F(x))\\ \end{align}

\begin{align} \sum_{n=1}^{\infty} x^n (xp_{n+1}(x)) &=\sum_{n=1}^{\infty} x^{n+1} p_{n+1}(x)\\ &=\sum_{n=2}^{\infty} x^{n} p_{n}(x)\\ &=-xp_1(x)+\sum_{n=1}^{\infty} x^{n} p_{n}(x)\\ &=-xp_1(x)+F(x)\\ \end{align}

Therefore

\begin{align} 0 &=\sum_{n=1}^{\infty} x^n(p_{n+2}(x) +xp_{n+1}(x)-p_{n}(x))\\ &=\sum_{n=1}^{\infty} x^np_{n+2}(x) +\sum_{n=1}^{\infty} x^n(xp_{n+1}(x))-\sum_{n=1}^{\infty}x^n p_{n}(x)\\ &=x^{-2}(-xp_1(x)-x^2p_2(x)+F(x))+(-xp_1(x)+F(x))-F(x)\\ &=x^{-2}(-xp_1(x)-x^2p_2(x)+F(x))-xp_1(x)\\ &=x^{-2}(-xp_1(x)-x^3p_1(x)-x^2p_2(x)+F(x))\\ &=x^{-2}(-(x+x^3)p_1(x)-x^2p_2(x)+F(x))\\ \end{align}

so

\begin{align} F(x) &=(x+x^3)p_1(x)+x^2p_2(x)\\ &=(x+x^3)x+x^2(1-x^2)\\ &=x^2+x^4+x^2-x^4\\ &=2x^2\\ \end{align}

But this is obviously wrong!!!

Why?

And, can this method be salvaged?

-