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