Poly Fibs
A sequence of polynomials starts 0, 1 and each poly is given by
combining the two polys in the sequence just before it. Investigate
and prove results about the roots of the polys.
Age
16 to 18
Challenge level
Image
Consider the sequence of polynomials given by $P_{n+2}(x)=xP_{n+1}(x)-P_n(x)$ where $P_0(x)=0$ and $P_1(x)=1$
(i) Show that every root of $P_3$ is a root of $P_6$.
(ii) Show that every root of $P_4$ is a root of $P_8$.
(iii) Show that every root of $P_5$ is a root of $P_{10}$.
You can do this by finding the polynomials and then finding their roots (maybe using a computer), but try to find another way to get this result without finding the roots of the polynomials.
One of the skills of a research mathematician is making conjectures about results that no-one has thought of and that turn out to be provable. In this problem there is a conjecture about a general result which you may be able to make quite easily although the proof is well beyond the scope of school mathematics. Go on learning mathematics and in a few years you will be able to prove it.
Use the defining relation for these polynomials to write $P_6$ in terms of $P_5$ and $P_4$ then in terms of $P_3$ and $P_2$ and the result follows.
The results for $P_8$ and for $P_{10}$ are proved similarly.
Here Andrei Lazanu, age 14, School No. 205, Bucharest, Romania
gives another excellent solution to this problem which he has
extended after doing some research on the web.
First, I calculated the first 10 polynomials that satisfy the recurrence relation given in the problem:
$$P_{n+2}(x)=xP_{n+1}(x)-P_n(x)$$
where $P_0(x)=0$ and $P_1(x)=1.$ I successively found:
$$\eqalign{ P_2(x) &= x \cr P_3(x) &= x^2 - 1 \cr P_4(x) &= x^3 - 2x = x(x^2 - 2)\cr P_5(x) &= x^4 - 3x^2 + 1 \cr P_6(x) &= x^5 - 4x^3 + 3x = x(x^2 - 1)(x^2 - 3) \cr P_7(x) &= x^6 - 5x^4 + 6x^2 - 1 \cr P_8(x) &= x^7 - 6x^5 + 10x^3 - 4x = x(x^2 - 2)(x^4 - 4x^2 +2) \cr P_9(x) &= x^8 - 7x^6 + 15x^4 - 10x^2 + 1 \cr P_{10}(x) &= x(x^4 - 3x^2 + 1)(x^4 - 5x^2 + 5)}.$$
From the examination of the expressions of the polynomials, I drew some conclusions:
(1) Odd order polynomials contain only even powers of $x$, including zero.
(2) Even order polynomials contain only odd powers of $x$.
(3) There are alternate signs of terms in each polynomial, starting with the first, of order $(n-1)$ for $P_n(x)$, which is positive.
I have also shown, as required in the question, that $P_4(x)$ contains as a factor $P_2(x)$, $P_6(x)$ contains as factor $P_3(x)$ (that is every root of $P_3$ is a root of $P_6$), $P_8(x)$ contains as factor $P_4(x)$ and $P_{10}(x)$ contains as factor $P_5(x$.
$$\eqalign{ {P_4(x)\over P_2(x)} &= x^2 - 2 \cr {P_6(x)\over P_3(x)} &= x(x^2 - 3)\cr {P_8(x)\over P_4(x)} &= x^4 - 4x^2 + 2 \cr {P_{10}(x)\over P_5(x)} &= x(x^4 - 5x^2 + 5).}$$
Using the defining recurrence relation we can express $P_6$ in terms of previous polynomials in the sequence.
$$\eqalign{ P_6 &= xP_5-P_4 \cr &= (x^2-1)P_4-xP_3 \cr &= P_3P_4 - P_2P_3 \cr &= P_3(P_4-P_2) .}$$
Similarly we can express $P_8$ in terms of previous polynomials in the sequence.
$$\eqalign{ P_8 &= xP_7-P_6 \cr &= (x^2-1)P_6-xP_5 \cr &= (x^3-2x)P_5-(x^2-1)P_4 \cr &= P_4(P_5-P_3) .}$$
Again we can express $P_{10}$ in terms of previous polynomials in the sequence.
$$\eqalign{ P_{10} &= xP_9-P_8 \cr &= (x^2-1)P_8-xP_7 \cr &= (x^3-2x)P_7-(x^2-1)P_6 \cr &= (x^4 - 3x^2 +1)P_6 - (x^3 - 2x)P_5 \cr &= P_5P_6-P_4P_5 \cr &= P_5(P_6-P_4).}$$
Editor's note: This suggests a conjecture that $P_{2k}=P_k(P_{k+1}-P_{k-1})$ where $k$ is any natural number. This is true but the general proof is beyond the scope of school mathematics. Andrei made further observations about the coefficients in these polynomials in the hope of finding explicit formulae for the $n$th order polynomial. He found, looking at Fibonacci numbers, that these polynomials are very similar to Fibonacci polynomials, which are given by the recursive relation:
F_{n+2}(x) = xF_{n+1}(x) + Fn(x) with $F_0(x) = 0$ and $F_1(x) = 1$. Using these relations, he found the first 10 Fibonacci polynomials, which are, up to the signs found in $P_n(x)$, identical with $F_n(x)$.
Using the explicit formula of Fibonacci polynomials from http://mathworld.wolfram.com, Andrei hoped to write correctly the explicit formula for the polynomials in the problem, as:
$$P_n(x)=\sum_{j=0}^{(n-1)/2}(-1)^j C^{n-j-1}_jx^{n-2j-1}.$$
The formula works well up to $n = 10$. From this formula, all properties could be found easily, although Andrei was not able to demonstrate the general case that $P_{2n}(x)$ is divisible by $P_n(x)$.
First, I calculated the first 10 polynomials that satisfy the recurrence relation given in the problem:
$$P_{n+2}(x)=xP_{n+1}(x)-P_n(x)$$
where $P_0(x)=0$ and $P_1(x)=1.$ I successively found:
$$\eqalign{ P_2(x) &= x \cr P_3(x) &= x^2 - 1 \cr P_4(x) &= x^3 - 2x = x(x^2 - 2)\cr P_5(x) &= x^4 - 3x^2 + 1 \cr P_6(x) &= x^5 - 4x^3 + 3x = x(x^2 - 1)(x^2 - 3) \cr P_7(x) &= x^6 - 5x^4 + 6x^2 - 1 \cr P_8(x) &= x^7 - 6x^5 + 10x^3 - 4x = x(x^2 - 2)(x^4 - 4x^2 +2) \cr P_9(x) &= x^8 - 7x^6 + 15x^4 - 10x^2 + 1 \cr P_{10}(x) &= x(x^4 - 3x^2 + 1)(x^4 - 5x^2 + 5)}.$$
From the examination of the expressions of the polynomials, I drew some conclusions:
(1) Odd order polynomials contain only even powers of $x$, including zero.
(2) Even order polynomials contain only odd powers of $x$.
(3) There are alternate signs of terms in each polynomial, starting with the first, of order $(n-1)$ for $P_n(x)$, which is positive.
I have also shown, as required in the question, that $P_4(x)$ contains as a factor $P_2(x)$, $P_6(x)$ contains as factor $P_3(x)$ (that is every root of $P_3$ is a root of $P_6$), $P_8(x)$ contains as factor $P_4(x)$ and $P_{10}(x)$ contains as factor $P_5(x$.
$$\eqalign{ {P_4(x)\over P_2(x)} &= x^2 - 2 \cr {P_6(x)\over P_3(x)} &= x(x^2 - 3)\cr {P_8(x)\over P_4(x)} &= x^4 - 4x^2 + 2 \cr {P_{10}(x)\over P_5(x)} &= x(x^4 - 5x^2 + 5).}$$
Using the defining recurrence relation we can express $P_6$ in terms of previous polynomials in the sequence.
$$\eqalign{ P_6 &= xP_5-P_4 \cr &= (x^2-1)P_4-xP_3 \cr &= P_3P_4 - P_2P_3 \cr &= P_3(P_4-P_2) .}$$
Similarly we can express $P_8$ in terms of previous polynomials in the sequence.
$$\eqalign{ P_8 &= xP_7-P_6 \cr &= (x^2-1)P_6-xP_5 \cr &= (x^3-2x)P_5-(x^2-1)P_4 \cr &= P_4(P_5-P_3) .}$$
Again we can express $P_{10}$ in terms of previous polynomials in the sequence.
$$\eqalign{ P_{10} &= xP_9-P_8 \cr &= (x^2-1)P_8-xP_7 \cr &= (x^3-2x)P_7-(x^2-1)P_6 \cr &= (x^4 - 3x^2 +1)P_6 - (x^3 - 2x)P_5 \cr &= P_5P_6-P_4P_5 \cr &= P_5(P_6-P_4).}$$
Editor's note: This suggests a conjecture that $P_{2k}=P_k(P_{k+1}-P_{k-1})$ where $k$ is any natural number. This is true but the general proof is beyond the scope of school mathematics. Andrei made further observations about the coefficients in these polynomials in the hope of finding explicit formulae for the $n$th order polynomial. He found, looking at Fibonacci numbers, that these polynomials are very similar to Fibonacci polynomials, which are given by the recursive relation:
F_{n+2}(x) = xF_{n+1}(x) + Fn(x) with $F_0(x) = 0$ and $F_1(x) = 1$. Using these relations, he found the first 10 Fibonacci polynomials, which are, up to the signs found in $P_n(x)$, identical with $F_n(x)$.
Using the explicit formula of Fibonacci polynomials from http://mathworld.wolfram.com, Andrei hoped to write correctly the explicit formula for the polynomials in the problem, as:
$$P_n(x)=\sum_{j=0}^{(n-1)/2}(-1)^j C^{n-j-1}_jx^{n-2j-1}.$$
The formula works well up to $n = 10$. From this formula, all properties could be found easily, although Andrei was not able to demonstrate the general case that $P_{2n}(x)$ is divisible by $P_n(x)$.
This sequence of polynomials has similarities to the sequence of Fibonnaci numbers.
Sometimes, as in this case, results are easy to state but not so easy to prove so we make an exception here in not asking for a proof of the general conjecture. It is no bad thing to cultivate a sense of what is likely to be true and a sense of curiosity about why it should be true but also to see that one needs to go on learning more to be able to do more.