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.
 A: 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:

A: 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$. 
A: 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)
$$
A: 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?
