IMO 1976 · Problem 2

Let \(P_1(x)=x^2-2\) and \(P_j(x)=P_1(P_{j-1}(x))\) for \(j=2,3,\cdots\). Show that, for any positive integer \(n\), the roots of the equation \(P_n(x)=x\) are real and distinct.

Official text of the problem. Official problem paper (PDF)

Solution

The double-angle identity gives \[ P_1(2\cos\theta)=4\cos^2\theta-2=2\cos(2\theta). \] Consequently, induction using the defining recurrence yields \[ P_n(2\cos\theta)=2\cos(2^n\theta). \]

Fix a positive integer \(n\), and put \(m=2^n\) and \[ Q(x)=P_n(x)-x. \] Each iteration doubles the degree, so \(P_n\), and hence \(Q\), has degree \(m\).

Consider the \(m+1\) real numbers \[ x_k=2\cos\frac{k\pi}{m},\qquad k=0,1,\ldots,m. \] Since cosine is strictly decreasing on \([0,\pi]\), \[ 2=x_0>x_1>\cdots>x_m=-2. \] The identity above gives \[ Q(x_k)=2\cos(k\pi)-x_k=2(-1)^k-x_k. \] Thus \(Q(x_0)=0\). For \(1\le k\le m-1\), we have \(-2<x_k<2\), so \[ Q(x_k) \begin{cases} >0,&k\text{ even},\\ <0,&k\text{ odd}. \end{cases} \] Also, \(m\) is even, and therefore \(Q(x_m)=2-(-2)=4>0\).

It follows that \(Q(x_k)\) and \(Q(x_{k+1})\) have opposite signs for every \(k=1,\ldots,m-1\). By the intermediate value theorem, \(Q\) has a root in each of the \(m-1\) disjoint intervals \[ (x_{k+1},x_k),\qquad k=1,\ldots,m-1. \] Together with the root \(x_0=2\), these give \(m\) distinct real roots.

Since \(Q\) has degree \(m\), the factor theorem shows that these account for all its roots, each with multiplicity one. Hence the roots of \(P_n(x)=x\) are all real and distinct.

The solution was checked against John Scholes' IMO solution archive (Kalva).