Finding the Chebyshev polynomials $T_n$ by elementary means

Question

Suppose that one person called the Student—virtually, an advanced schoolchild—obtained a tip that the Chebyshev polynomials of the first kind exist and unique for each $n$. By the Chebyshev polynomial $T_n$, where $n = 0, 1, 2, …$, I understand such degree-$n$ polynomial that maps the segment [−1, 1] to itself, $T_n(1) = 1$, and also $T_n^{-1}｛1,-1｝$ (assuming the domain [−1, 1] for the $T_n$ function) consists of exactly $n+1$ points if $n\ge 1$.

Let the Student be well-versed in polynomials (including their derivatives and related calculus), linear and quadratic equations, but suppose that the Student is ignorant about equations of the degree higher than 2, trigonometry, exponentials, matrices etc.

It’s trivial to find $T_0, T_1$, and $T_2$. For $T_4$ one can learn that it’s an even function (hence, a biquadratic polynomial); moreover, $T_4(0) = 1$ and $T_4(1) = 1$ imply a form $T_4(x) = ax^4 - ax^2 + 1$ for certain real $a$. Then

$T_4'(x) = 4ax^3 - 2ax = 2ax(2x^2 - 1)$

and hence $x = \pm\frac{1}{\sqrt 2}$ are (the global) minima of $T_4$. By equating $T_4(\pm\frac{1}{\sqrt 2})$ to −1 we find $a=8$, at last.

But, ironically, an attempt to do the same for $T_3$ leads to a cubic equation, and it’s unclear how to solve the problem (or even to guess the answer) without further tips, such as, that coefficients of all $T_n$ are integer.

The question: what the Student can learn about $T_3, T_5, T_6, …$? Particularly, can the Student obtain any hint to the recurrence relation $T_{n+1}(x) = 2 x T_n(x) - T_{n-1}(x)$?

Answer 1

Another non-answer (since it does not derive the recursion), but interesting nonetheless. (In fact, I didn’t know this simple approach to compute any $T_n$ directly and quickly without even using said recursion.) Let’s start from first principles and make a number of observations. This leads to a linear second order differential equation for $T_n$ that turns out to be very easy to solve. (Do not despair: Since we’re dealing with polynomials, this is nothing else than linear combinations of coefficients.)

So start with a polynomial $p = a_0 + a_1 x + \ldots + a_d x^d$ of degree $d$ such that:

1. $p(-1) = (-1)^d$ and $p(1) = 1$.
2. $p$ has exactly $d$ distinct roots in $(-1,1)$.
3. All $d-1$ local extremal values of $p$ on $(-1,1)$ are either $-1$ or $1$.

Then $q(x) = 1 - p(x)^2$ has some interesting properties:

1. The leading coefficient of $q$ equals $-a_d^2$.
2. $1 - x^2$ divides $q$, since it has roots at $-1$ and $1$.
3. If $p(x_0)$ is a local extremum of $p$ for some $x_0 \in (-1,1)$ then $x_0$ is at least a double root of $q$.

These observations account for all $2 d$ roots of $q$ and given its leading coefficient we conclude: $$d^2 (1-p(x)^2) = (1 - x^2) p’(x)^2.$$

Nice! As an important by-product we can already conclude that if $x_0$ is a zero of $p$ then $$\lvert p’(x_0) \rvert = \frac{d}{\sqrt{1-x_0^2}}$$ which will become useful later.

Still, all these squares in the equation above are a bit worrying. However, taking derivatives on both sides and dividing by the common factor $2 p’(x)$ leads to:

$$- d^2 p(x) = -x p’(x) + (1 - x^2) p’’(x).$$

Here is our second order differential equation! Expressing this in terms of the coefficients $a_k$ of $p$ leads to the relations $$(k^2 - d^2) a_k = (k+1)(k+2) a_{k+2}$$ for all $k \geq 0$ (where we take $a_k = 0$ when $k > d$). Take $k = d - 1$ to conclude that $a_{d-1}=0$. From here, this zero coefficient cascades down in steps of two. In other words: $p$ must be even if $d$ is even and $p$ must be odd if $d$ is odd.

It is fairly easy to see (from the number of oscillations) that $p(0)=(-1)^{d/2}$ if $d$ is even and $p(0)=0$ if $d$ is odd. In the latter case, using the formula for the derivative at a zero above, we find $p’(0) = (-1)^{(d-1)/2} d$.

Now the procedure to compute $p$ is as follows:

1. If $d$ is even then start with $a_0=(-1)^{d/2}, a_1=0$.
2. Otherwise, start with $a_0=0, a_1=(-1)^{(d-1)/2} d.$
3. Then repeatedly compute $a_{k+2}$ from $a_k$ by $$a_{k+2}=\frac{k^2 - d^2}{(k+1)(k+2)} a_k.$$

Let’s try this for $d=6$ and $d=7$. This results in $$p(x) = -1 + 18 x^2 - 48 x^4 + 32 x^6$$ for $d=6$ and $$p(x) = -7 x + 56 x^3 - 112 x^5 + 64 x^7$$ for $d=7$.

Answer 2

Another approach could be to start from $$\frac{x^n+x^{-n}}2 = T_n\left(\frac{x+x^{-1}}2 \right)$$ as a defining property. Then expanding $$\left(\frac{x+x^{-1}}2\right) \left(\frac{x^n+x^{-n}}2 \right)$$ directly leads to a recursion for $T_{n+1}$.

Answer 3

The way how the Student obtained $a=8$ in $T_4$ clearly indicates that $a=2^3=8$ is the true reason behind this value. This immediately prompts an observation that the leading coefficient of $T_n$ is $2^{n-1}$ for $n=1,2,4$. Moreover. By uniqueness, $T_3$ must be odd (that is, has non-zero coefficients before $x^3$ and $x$ only), and a reasonable conjecture that its leading coefficient is 4 leads to the $4x^3 - 3x$ polynomial as the candidate, given $T_3(1) = 1$. The Student can fairly easily check that it is $T_3$.

The leading coefficient formula notably fails for $T_0$, but $2^{-1}$ is obviously not integer, which suggests that all coefficients in $T_n$ should be integer. Moreover, the coefficient before $x$ is 1 in $T_1$ and −3 in $T_3$, suggesting a conjecture—namely, $(-1)^{(n-1)/2}n$—about its values for all odd $n$. Note that positivity of $T_n'(0)$ where $n = 1 (\mod 4)$ and its negativity where $n = 3 (\mod 4)$ are fairly obvious by consideration of monotonicity on intervals. These conjectural expressions for coefficients (the leading one and before $x$ for odd $n$) can prompt the Student to realize that $T_{mn} = T_m \circ T_n$; the thing which is rather obvious from the functional (not algebraic) viewpoint. For example, $T_2(T_2(x)) = 2(2x^2 - 1)^2 - 1 = 2^{1 + 2\times 1}x^{2\times 2} + (2\times 2\times 2)x^2 + 2 - 1 = 8x^4 - 8x^2 + 1 = T_4(x)$ and in general $mn - 1 = (m - 1) + m(n - 1)$. The $T_{mn}$ hack is, anyway, not necessary (and not useful at all for finding $T_5$).

The above information provides enough tips for a quest for $T_5$. Having guesses—16 before $x^5$ and 5 before $x$—the Student arrives at the $T_5(x) = 16x^5 - 20x^3 + 5x$ hypothesis by $T_5(1) = 1$. Indeed, its derivative is $80x^4 - 60x^2 + 5$, or $16x^4 - 12x^2 + 1$ up to a positive constant factor (which, by the way, equals to $n$ in line with previous tests). Now its roots (that is, extrema of the prospective $T_5$) have to be found. Making the $u = 4x^2$ change of variable, the Student gets the $u^2 - 3u + 1 = 0$ equation which can be solved by a well-known formula and yields $u = \frac{3 \pm \sqrt{5}}{2}$. Obviously, both roots are positive.

My experience with Dirichlet integers helps to realize that these roots are full squares (which indeed makes respective values of $2x$ Dirichlet integers too), albeit the Student is not expected to know that. But with the hypothetical $T_5(x) = (16x^4 - 20x^2 + 5)x$ the Student can, firstly, compute the value of $16x^4 - 20x^2 + 5 = u^2 - 5u + 5$ at the supposed extremal points of $T_5$. By $(\frac{3 \pm \sqrt{5}}{2})² = \frac{7 \pm 3\sqrt{5}}{2}$ it will be $1 \mp \sqrt{5}$.

At this point the Student can observe that $\left(\frac{1 \pm \sqrt{5}}{2}\right)^{-1} = \frac{-1 \pm \sqrt{5}}{2}$ (yes, the golden ratio up to sign). Because we are not, in fact, obliged to compute values of $(16x^4 - 20x^2 + 5)x$ but only to check whether are they (at the extremal points) $\pm 1$, we should look at the set of four values of $x$—namely, $x = \pm\left(1 \mp \sqrt{5}\right)^{-1} = \pm\frac{-1 \mp \sqrt{5}}{4}$—and check whether does each of them yield the same value of $u = 4x^2 = (2x)^2$ as we already found. All that remains is to compute the square of $\frac{-1 \mp \sqrt{5}}{2}$, which is indeed $\frac{3 \pm \sqrt{5}}{2}$, exactly the same as $u$.

Now we actually know all $T$ up to $T_5$, or possibly even $T_6$. I don’t think it would be hard to guess the recurrence relation from such table of coefficients, although I have no idea how to prove it from such elementary grounds.