Let P1(x) = x2 - 2, and Pi+1 = P1(Pi(x)) for i = 1, 2, 3, ... . Show that the roots of Pn(x) = x are real and distinct for all n.
Solution
We show that the graph of Pn can be divided into 2n lines each joining the top and bottom edges of the square side 4 centered on the origin (vertices (2,2), (-2,2), (-2,-2), (-2,2) ). We are then home because the upward sloping diagonal of the square, which represents the graph of y = x, must cut each of these lines and hence give 2n distinct real roots of Pn(x) = x in the range [-2,2]. But Pn is a polynomial of degree 2n, so it has exactly 2n roots. Hence all its roots are real and distinct.
We prove the result about the graph by induction. It is true for n = 1: the first line is the graph from x = -2 to 0, and the second line is the graph from 0 to 2. So suppose it is true for n. Then P1 turns each of the 2n lines for Pn into two lines for Pn+1, so the result is true for n+1.
Alternative solution from Arthur Engel, Problem-Solving Strategies, Springer 1998 [Problem books in mathematics series], ISBN 0387982191. A rather good training book.
Put x = 2 cos t (so we are restricting attention to -2 ≤ x ≤ 2). Then we find Pn(x) = 2 cos 2nt, so the equation Pn(x) = x becomes cos 2nt = cos t. By inspection, has the 2n solutions t = 2kπ/(2n - 1) and t = 2kπ/(2n + 1), giving 2n distinct solutions in x.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
10 Oct 1998