Solution of recursive polynomial functions Is there anything that can be said about the roots of the polynomial $f_n(x)$ if $f_n(x) = xf_{n-1}(x) + f_{n-2}(x)$ where these are polynomials of degree $n, n-1,$ and $n-2$, respectively? My goal is to conclude that all roots of every $f_i(x)$ must have positive real part, but I haven't thought of a method of proof. I'm convinced it's true, since Sage tells me that I'm right up to $n=200$ . In addition, the roots of both $f_{n-1}(x)$ and $f_{n-2}(x)$ are known to be the maximum number of complex conjugate pairs (at most one purely real root), and all roots have positive real part. While this recursive equation has the form of Fibonacci polynomials, I am dealing with $f_1(x) = x-1$ and $f_2(x) = x^2 - x + 1$.
 A: If you look at your polynomials, their coefficients alternate in sign.  In particular, for $f_n$, the coefficient of $x^k$ has sign $(-1)^{n-k}$.  This is preserved under your recurrence relation.
Now, Descartes' rule of signs tells us that the number of negative real roots is zero because $f_n(-x)$ will have no sign variations.
This doesn't completely answer the question because there may be roots with negative real part, but it should get you started.
A: Let $$g_n(x)=\frac{f_n(ix)+f_n(-ix)}{2}\qquad\text{ and }\qquad h_n(x)=i\frac{f_n(ix)-f(-ix)}{2}.$$
Then 
$$g_n(x)=xh_{n-1}(x)+g_{n-2}(x)$$
$$h_n(x)=-xg_{n-1}(x)+h_{n-2}(x)$$
We use now the following lemma applied to $f_n(x)$.

Lemma: A polynomial $f(x)$ has the all real parts of its roots of the same sign if and only if $$g(x)=\frac{f(ix)+f(-ix)}{2}\qquad\text{ and }\qquad h(x)=i\frac{f(ix)+f(-ix)}{2}$$ have only real roots that alternate (one root of $g(x)$, one root of $h(x)$, and so on ...).

Evaluating the recurrences for $g_n$ and $h_n$ in the roots of $h_{n-1}(x)$ we see (since the roots of $g_{n-2}$ are in between them) that $g_n(x)$ doesn't vanish at those points and that it changes signs. This shows that $g_n(x)$ has all real roots alternating with those of $h_{n-1}$, and likewise for $h_n$ when we use the other recurrence. This step is done inductively and one simultaneously checks that the roots of $g$'s and $h$'s alternate and that they are simple roots. 
Therefore, by the lemma, all roots of $f_n(x)$ will have real parts of the same sign. To check that they are positive look at the sign of the coefficient of the term next to the leading one. Since it is negative (Burr's observation) the sum of the real parts of the roots is positive.

Proof of Lemma: D.K. Faddeev, I.S. Sominskii, Problems in higher algebra, Problem 743. (The book includes the solution/proof).

