1976 IMO Problems/Problem 2

Problem

Let $P_{1}(x) = x^{2} - 2$ and $P_{j}(x) = P_{1}(P_{j - 1}(x))$ for $j= 2,\ldots$ Prove that for any positive integer n the roots of the equation $P_{n}(x) = x$ are all real and distinct.

Solution

I shall prove by induction that $P_n(x)$ has $2^n$ distinct real solutions, where $2^{n-1}$ are positive and $2^{n-1}$ are negative. Also, for ever root $r$, $|r|<2$.

Clearly, $P_1(x)$ has 2 real solutions, where 1 is positive and 1 is negative. The absolute values of these two solutions are also both less than 2. This proves the base case.

Now assume that for some positive integer $k$, $P_k(x)$ has $2^k$ distinct real solutions with absolute values less than 2, where $2^{k-1}$ are positive and $2^{k-1}$ are negative.

Choose a root $r$ of $P_{k+1}(x)$. Let $P_1(r)=s$, where $s$ is a real root of $P_k(x)$. We have that $-2<s<2$, so $0<r^2<4$, so $r$ is real and $|r|<2$. Therefore all of the roots of $P_{k+1}$ are real and have absolute values less than 2.

Note that the function $P_{k+1}(x)$ is an even function, since $P_1(x)$ is an even function. Therefore half of the roots of $P_{k+1}$ are positive, and half are negative.

Now assume for the sake of contradiction that $P_{k+1}(x)$ has a double root $r$. Let $P_1(r)=s$. Then there exists exactly one real number $r$ such that $r^2-2=s$. The only way that this could happen is when $s+2=0$, or $s=-2$. However, $|s|<2$ from our inductive hypothesis, so this is a contradiction. Therefore $P_{k+1}(x)$ has no double roots. This proves that that the roots of $P_{k+1}(x)$ are distinct.

This completes the inductive step, which completes the inductive proof.

Alternate Solution

Let $x=2\cos\theta$. We then have that $P_1\left(x\right)=2\cos2\theta$, and we can prove using induction that $P_n\left(x\right)=2\cos2^n\theta$. Thus, we just need to solve $2\cos2^n\theta=2\cos\theta$, which happens when $\cos2^n\theta=\theta+2\pi k$ or $\cos2^n\theta=-\theta+2\pi l$. These give that $\theta=\frac{2k}{2^n-1}\cdot\pi$ or $\theta=\frac{2l}{2^n+1}\cdot\pi$. As we can choose the range $0\leq\theta\leq\pi$ to ensure no duplications, we get that, upon rearranging, $0\leq k\leq2^{n-1}-\frac{1}{2}$ and $0\leq l\leq2^{n-1}+\frac{1}{2}$. There are $2^{n-1}$ integers in the first range and $2^{n-1}+1$ in the second. However, exactly one time, they product the same $\theta$: $\theta=0$. Thus, there are $2^{n-1}+2^{n-1}+1-1=2^n$ distinct roots for $\cos\theta=x$. We can also prove using induction that there are $2^n$ roots of $P_n\left(x\right)$. Thus, all roots of $P_n\left(x\right)$ are distinct and real.

Q.E.D.

See also

1976 IMO (Problems) • Resources
Preceded by
Problem 1
1 2 3 4 5 6 Followed by
Problem 3
All IMO Problems and Solutions