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.

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

Problem

Solution

See also