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.

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

Page

Toolbox

Search

1976 IMO Problems/Problem 2

Contents

Problem

Solution

Alternate Solution

See also