# 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$.

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).

• Absolutely terrific. Just for clarification, what is meant by "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"? If I try $f_3(x)$, $g_3(x) = x^2-1$ and $h_3(x) = -x^3$. So the ordering of the roots along the axis is a root from g(x), a root from h(x), and a root from g(x), thus the real part of the roots of $f_3(x)$ have the same sign? – Pistol Pete Apr 1 '15 at 0:23
• @PistolPete Yes, that distribution of the roots that you checked for $g_3(x)$ and $h_3(x)$ is what we aim to check to apply the lemma. Now, in the recurrence, suppose $r_1,r_2,...,r_{n-2}$ are the roots of $h_{n-1}(x)$. Then, when you evaluate the first recurrence we get $g_n(r_i)=0+g_{n-2}(r_i)$. Since the roots of $h_{n-1}(x)$ alternate with the roots of $g_{n-2}(x)$ we know that $g_{n-2}(r_i)$ is non-zero. Moreover, it has a sign that is opposite to the sign of $g_{n-2}(r_{i-1})$. Therefore, $g_{n}(x)$ must vanish in between $r_{i-1}$ and $r_{i}$. Thus proving that $g_{n}(x)$ has ... – OR. Apr 1 '15 at 1:00
• @PistolPete ... real roots and that they are between the $r_i$'s, the roots of $h_{n-1}(x)$. – OR. Apr 1 '15 at 1:00
• I may be overlooking it, but how do we know that the roots of $h_{n-1}(x)$ will alternate with the roots of $g_{n-2}(x)$, and that if $g_{n-2}(r_i) > 0$, then $g_{n-2}(r_{i-1}) < 0$? – Pistol Pete Apr 1 '15 at 1:22
• @PistolPete The first thing is by induction. One must check the initial case $h_{3}(x)$ and $g_{2}(x)$. The changes of sign is because the roots are simple, which incidentally one checks along, inductively, as one is checking the alternation of roots. Maybe I should add that to the answer. – OR. Apr 1 '15 at 1:42

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.

• thanks for your response. That and MSGL's answer got the desired result – Pistol Pete Apr 2 '15 at 21:01