Given a polynomial series $\{p_n(x)\}_{n=1}^{\infty}$ in $\mathbb{R}[X]$ with initial value $p_1(x)=x^2-2$. And $p_k(x)=p_1(p_{k-1}(x))=p_{k-1}(x)^2-2,\;k=2,3,\cdots$.
Prove that for each integer $n$, all roots of $p_n(x)-x$ are real and distinct.
This is an problem in my linear algebra textbook. I tried to figure out the relation of the roots between adjacent polynomial, but I couldn't find any useful result. Also I thought if it could be solved by induction, but it seems impracticable.
On
Lemma; Let $n \geq 2$; If $p_{n}(x)$ has a local minima it is $-2$. If $p_{n}(x)$ has a local maxima it is $2$. Local minima with $x>0$ occurs $2^{n-2}$ times, Local minima with $x<0$ occurs $2^{n-2}$ times, Local maxima with $x<0$ occurs $2^{n-2} -1$ times and finally Local maxima with $x>0$ occurs $2^{n-2}-1$ times. Local maxima occurs at $x=0$
Proof; Differentiating $p_{n}$ we find that
$p_{n}'(x) = 2p_{n-1}(x)(p_{n-1}'(x))$
Hence
(1) $p_{n}'(x) = 2p_{n-1}(x)(2p_{n-2}(x))...(2p_{1}(x))(2x)$
To be a local minima or maxima one has $p_{n}'(x) = 0$. By looking at (1) we see that some $p_{n-j}(x)$ is $0$ or $x=0$. If $p_{n-1}(x)$ is 0 then $p_{n}(x)$ is $-2$. If some $p_{n-j}(x)$ for $j\geq 2$ is $0$ (just define $p_{0}(x) = x$) then $p_{n}(x) = 2$. So if (x,p_n(x)) is a turning point p_n(x) is $\pm 2$. Also note that there are no double roots as if $p_h(x) = 0$ then for any $a >0$ $p_{h+a}(x) = 2$ or $-2$
Now note that each $p_n(x)$ has $2^{n}$ distinct roots. So we can label the roots in an increasing order $c_{1} < c_{2} ...< c_{2^n}$. Observe that between any two successive roots $c_{u}$ and $c_{u+1}$ one has a turning point.
We claim that between any successive roots there is exactly one turning point. To see this suppose that there is an interval $[c_u,c_{u+1}]$ that contains atleast two turning points; hence there are at least $2^n$ turning points in $[c_{1},c_{2^n}]$ but there can only be at most $2^n-1$ turning points (as degree of $p_n(x)$ is $2^{n}$). Combining this information and the information in the previous paragraph we have that in an interval $[c_{u}, c_{u+1}]$ ; $p_n(x)$ attains exactly one of the following;
(I) A local minima of -2
(II) A local maxima of 2
Going all the way back and looking at (1) (the equation above) (I) occurs exactly when $p_{n-1}(x) = 0$ which has $2^{n-1}$ distinct roots; half positive and half negative (even function). (II) occurs exactly when some $p_{n-j}(x) =0$ for some $j \geq 2$ which happens at $2^{n-1} - 1$ distinct places with one of them being $0$.
We will use the observation that the roots of $p_n(x)$ satisfy $|x| < 2$ to finish the proof.
Now consider each of the $2^{n-2} -1$ type (II) intervals $[c_{u},c_{u+1}]$ with $c_{u} > 0$ we can split this interval into two intervals $[c_{u},d]$ and $[d,c_{u+1}]$ where $p_n(d) = 2$ applying intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ we find that $g_n(x)$ contains two distinct roots in $[c_{u},c_{u+1}]$. This till now gives us a total of $2(2^{n-2} -1)= 2^{n-1} -2$ distinct real roots.
It is now time to look at the $2^{n-2}$ type (I) intervals $[c_p, c_{p+1}]$ with $c_{p} < 0$; we once again autistically split this interval into $[c_p, e]$ and $[e, c_{p+1}]$ where $e$ is such that $p_n(e) = -2$ (as we are dealing with a type (I) case); we once again apply the intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ to gather that $g_n(x)$ contains two distinct roots in $[c_p, c_{p+1}]$. Total number roots of g_n(x) found in these type of intervals is hence $2(2^{n-2}) = 2^{n-1}$ distinct roots.
The total number of distinct roots we now have is $2^{n-1} -2 + 2^{n-1} = 2^{n-1}-2$. Where the other two roots are is a question you may ask. You will find those other two roots in the interval $[-a,a]$ where $a$ is the smallest positive root of $p_n(x)$ and you can prove yourself that this is so by doing a similar analysis to that done above.
Hint:
Observe that $-2 \le P_1(x) \le 2$ for all $-2\le x\le 2$ and both its roots lie in the same interval. This property becomes obvious by substitution $x=2\cos t$ which maps interval $t\in[0,\pi]$ onto $x\in[-2,2]$.
We have: $$ P_1(2\cos t)=(2\cos t)^2-2=4\frac{1+\cos 2t}{2}-2=2\cos 2t. $$
Similarly by induction: $$ P_n(2\cos t)=2\cos 2^n t. $$
Thus the polynomial $P_n(x)$ has exactly $2^{n}$ roots on the interval $(-2,2)$: $$ \xi_k=2\cos\frac{2k-1}{2^{n+1}}\pi,\quad k=1\dots 2^n. $$ Besides the polynomial has alternating $2^{n-1}+1$ maxima $P(\xi_k^\text{max})=2$ at $$ \xi_k^\text{max}=2\cos\frac{2k}{2^n}\pi,\quad k=0\dots 2^{n-1} $$ and $2^{n-1}$ minima $P(\xi_k^\text{min})=-2$ at $$ \xi_k^\text{min}=2\cos\frac{2k-1}{2^n}\pi,\quad k=1\dots 2^{n-1}. $$ Note that the maxima at $x=-2$ and $x=2$ are not necessary the extreme points of the polynomial $P_n(x)$, they are just its values at the boundaries of the interval $[-2,2]$.
Note also that as the order of the polynomial $P_n(x)$ is $2^n$ we have found all the roots of the polynomial.
What remains is to prove that the function $Q(x)=x$ intersects the curve described above in exactly $2^n$ points. For this observe that on the interval $(-2,2)$ the graph of $P_n(x)$ consists of $2^n$ parts connecting adjacent maxima and minima. (Note that in fact $Q(x)$ can be any polynomial of order less than $2^n$ such that $-2<Q(x)<2$ for any $-2<x<2$.)