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:
Pn+2(x)=xPn+1(x)−Pn(x)
where P0(x)=0 and P1(x)=1. I successively found:
P2(x)
= x
P3(x)
= x2 − 1
P4(x)
= x3 − 2x = x(x2 −2)
P5(x)
= x4 − 3x2 + 1
P6(x)
= x5 − 4x3 + 3x = x(x2 − 1)(x2 − 3)
P7(x)
= x6 − 5x4 + 6x2 − 1
P8(x)
= x7 − 6x5 + 10x3 − 4x = x(x2 − 2)(x4 − 4x2 +2)
P9(x)
= x8 − 7x6 + 15x4 − 10x2 + 1
P10(x)
= x(x4 − 3x2 +1)(x4 − 5x2 + 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 Pn(x), which is positive.

I have also shown, as required in the question, that P4(x) contains as a factor P2(x), P6(x) contains as factor P3(x) (that is every root of P3 is a root of P6), P8(x) contains as factor P4(x) and P10(x) contains as factor P5(x.


 P4(x)
P2(x)
= x2 − 2
 P6(x)
P3(x)
= x(x2− 3)
 P8(x)
P4(x)
= x4 − 4x2 + 2
 P10(x)
P5(x)
= x(x4 − 5x2 + 5).


Using the defining recurrence relation we can express P6 in terms of previous polynomials in the sequence.
P6
= xP5−P4
= (x2−1)P4−xP3
= P3P4 − P2P3
= P3(P4−P2) .
Similarly we can express P8 in terms of previous polynomials in the sequence.
P8
= xP7−P6
= (x2−1)P6−xP5
= (x3−2x)P5−(x2−1)P4
= P4(P5−P3) .
Again we can express P10 in terms of previous polynomials in the sequence.
P10
= xP9−P8
= (x2−1)P8−xP7
= (x3−2x)P7−(x2−1)P6
= (x4 − 3x2 +1)P6 − (x3 − 2x)P5
= P5P6−P4P5
= P5(P6−P4).


Editor's note: This suggests a conjecture that P2k=Pk(Pk+1−Pk−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 nth order polynomial. He found, looking at Fibonacci numbers, that these polynomials are very similar to Fibonacci polynomials, which are given by the recursive relation:
Fn+2(x) = xFn+1(x) + Fn(x)
with F0(x) = 0 and F1(x) = 1. Using these relations, he found the first 10 Fibonacci polynomials, which are, up to the signs found in Pn(x), identical with Fn(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:
Pn(x)= (n−1)/2
∑
j=0 
 (−1)j Cn−j−1jxn−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 P2n(x) is divisible by Pn(x).