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 5 of 6: Count distinct values of

x=2\cos\theta

[0,\pi]

Previous step Next step

In plain words

Counting solutions to a trigonometric equation always requires fixing a fundamental domain first; choosing $[0,\pi]$ here matches exactly how $\cos$ behaves as a bijection, which is what makes an exact count possible.

2^{n-1} + \big(2^{n-1}+1\big) - 1 = 2^n

Detailed analysis

Since $\cos\theta$ takes each value exactly once for $\theta\in[0,\pi]$ , restrict to this range to avoid double-counting: this gives $0\le k\le 2^{n-1}-\tfrac12$ , i.e. $2^{n-1}$ integer values of $k$ , and $0\le l\le 2^{n-1}+\tfrac12$ , i.e. $2^{n-1}+1$ integer values of $l$ . The two families overlap only at $\theta=0$ (from $k=0$ and $l=0$ ), so the total number of distinct angles $\theta\in[0,\pi]$ , and hence distinct values $x=2\cos\theta$ , is $2^{n-1}+(2^{n-1}+1)-1=2^n$ .