# The polynomials $P_n (X)$ are defined by $P_0 (X)=0$, $P_1 (X)=X$, and $P_n (X)=XP_{n-1} (X) + (1-X)P_{n-2} (X)$ for $n>1$

... Find all the real roots of $P_n (X)$, for each $n$.

Help! I'm completely stuck on this question. I started out by finding $P_n (X)$ for various $n$ up to $n=5$, and then I found that the only real solution for each $n$ is $x=0$. Here is a picture of my polynomial work, keeping in mind there is a mistake in the picture for $n=5$, which should be $x^5-3x^4+4x^3-2x^2+x$

I know I can use induction to show that $0$ is a solution for all $n$, but how can I show it is the unique real solution for all $n$, too?

I asked elsewhere and was provided with an equation that can help, only I have no idea how they derived it, and that thread got ignored and eventually lost, on another forum.

-
What do you mean, this is not simply homework anymore? Note my previous answer had a mistake which I have fixed. There is only one real root: $0$. –  julien Mar 14 '13 at 2:15

Here is how you can derive the formula if you don't know it a priori.

Fix $t\neq 2$ and consider the sequence $a_n=P_n(t)$: $$a_0=0\quad a_1=t\quad a_{n+2}=ta_{n+1}+(1-t)a_n \quad\forall n\geq 0.$$ This is homogeneous and linear, so we know how to find a closed form. You can find the general method here.

First consider the characteristic equation $$r^2-tr+(t-1)=0.$$ The discriminant is $(t-2)^2>0$ and the quadratic formula yields two distinct roots $$r_1=1\qquad r_2=t-1.$$ Now we know that there exist two constants $\lambda,\mu$ such that $$a_n=\lambda \;r_1^n+\mu \;r_2^n=\lambda+\mu (t-1)^n.$$ Considering the intial conditions, we can compute $\lambda$ and $\mu$ and we find $$a_n=P_n(t)=\frac{t((t-1)^n-1)}{t-2}.$$

In the case $t=2$, $$a_{n+2}=2a_{n+1}-a_n\quad\Leftrightarrow\quad a_{n+2}-a_{n+1}=a_{n+1}-a_n.$$ so $a_{n+1}-a_n$ is constant equal to $a_1-a_0=2$. Hence, an easy induction and the fact that $a_0=0$ yield $$a_n=P_n(2)=2n.$$

Note: of course, you could directly deduce that $P_n(2)=2n$ by taking the limit as $t$ tends to $2$ in the formula for $P_n(t)$ when $t\neq 2$.

Now the real roots: $$P_n(t)=0\qquad\Leftrightarrow \qquad t((t-1)^n-1)\quad\mbox{and}\quad t\neq 2$$ $$\quad\Leftrightarrow\quad \{t=0\quad\mbox{or}\quad (t-1)^n=1\}\quad\mbox{and}\quad t\neq 2.$$ Now observe that in $\mathbb{R}$, we have $(t-1)^n=1$ implies $t-1=\pm 1$, ie $t=0$ or $2$. Since $P_n(2)=2n$ this does not add any real root to $0$.

So there is only one real root for $P_n$, for all $n\geq 1$: that's $0$.

-
Sorry, what's linear exactly? In your 4th line, that is. –  user65132 Mar 5 '13 at 14:42
Recursive homogeneous linear of order $2$ means there exist constants $u,v$ such that $a_{k+2}=ua_{k+1}+va_k$. See here en.wikipedia.org/wiki/Recurrence_relation for the general theory. –  julien Mar 5 '13 at 14:44
Ah, I get it now. But your characteristic equation isn't like the one from the wiki page, what's up with that? –  user65132 Mar 5 '13 at 15:19
I can't respond to Julien for some reason. Thanks a lot, and I finally get how to solve this recurrence relation after a few days of banging my head at it, but I have one qualm. You say 2 is a real root, but if you substitute $P_2 (X)=X^2$ then the answer you get for that is 4, not 0. So certainly this means that two cannot be a root? –  user65132 Mar 7 '13 at 22:36
@user65132: You have accidentally created two accounts, which is why you were not able to edit your post directly. Here is the process to merge your accounts: From any page footer -> 'contact us' >> 'Merge user profiles' –  Zev Chonoles Mar 7 '13 at 22:43

Suppose $X \in (0, 1)$. Then, an easy inductive argument shows $P_n(X) > 0$ for all $n > 0$.

Suppose $X \in (1, \infty)$. Then

$$P_n(X) = X (P_{n-1}(X) - P_{n-2}(X)) + P_{n-2}(X)$$

Can we show $P_n(X) > P_{n-1}(X)$ for all $n > 0$? If so, we have another easy inductive argument that $P_n(X) > 0$ for all $n > 0$. Simplifying,

$$P_n(X) - P_{n-1}(X) = (X-1) (P_{n-1}(X) - P_{n-2}(X))$$

Oh wait, this immediately suggests a drastic simplification to the problem, since we can easy solve this recurrence for $P_n(X) - P_{n-1}(X)$:

$$P_n(X) - P_{n-1}(X) = (X-1)^{n-1} (P_1 (X) - P_0(X)) = (X-1)^{n-1} X$$ and this one is easy to solve for $P_n(X)$:

$$P_n(X) = P_n(X) - P_0(X) = \sum_{i=0}^{n-1} (X-1)^i X = X \frac{(X-1)^n - 1}{(X-1) - 1}$$

So the roots of $P_n(X)$ are $0$, the roots of $(X-1)^n - 1$, and possibly roots of $(X-1) - 1$.

-
It may seem odd that I switched my solution method in the middle; what I've written is a sketch of my actual train of thought when solving the problem. Rather than post a canned solution, I'm hoping to demonstrate the actual process of exploring a problem, spotting a useful fact, then using it. –  Hurkyl Mar 5 '13 at 14:17
To verify that $P_n(x)=x\left(\left(x-1\right)^{n-1}+\left(x-1\right)^{n-2}+\ldots+\left(x-1\right)+1\right)$ for $n\geq 1$ you could use the recurrence from which $P_n$ is defined.
Let's denote by $Q_n(x)$ the polynomial $x\left(\left(x-1\right)^{n-1}+\left(x-1\right)^{n-2}+\ldots+\left(x-1\right)+1\right)$.
By noting that $Q_1(x)=x=P_1(x)$ and $Q_2(x)=x^2=P_2(x)$, is enough to show that $$Q_n(x)=xQ_{n-1}(x)-(x-1)Q_{n-2}(x), \text{ for all } n\geq 3.$$