Problem 2

Let

P_1(x) = x^2 - 2

and

P_j(x) = P_1(P_{j-1}(x))

for

j = 2, 3, \ldots

. Prove that, for any positive integer

n

, the roots of the equation

P_n(x) = x

are all real and distinct.

Step 2 of 6: Induction: the substitution linearizes the whole iteration

Previous step Next step

In plain words

Once one iteration of $P_1$ is seen to just double the angle, iterating $n$ times simply doubles the angle $n$ times over — the nonlinear-looking recursion $x^2-2$ becomes the utterly simple operation $\theta\mapsto 2\theta$ in disguise.

P_n(2\cos\theta) = 2\cos(2^n\theta)

Detailed analysis

By induction on $n$ , using Step 1 for the base case and $P_{n}(2\cos\theta)=P_1\big(P_{n-1}(2\cos\theta)\big)=P_1\big(2\cos(2^{n-1}\theta)\big)=2\cos(2\cdot 2^{n-1}\theta)=2\cos(2^n\theta)$ for the inductive step, one obtains $P_n(2\cos\theta)=2\cos(2^n\theta)$ for every $n\ge1$ .