View source for Chebyshev polynomials of the first kind

The <b> Chebyshev polynomials of the first kind </b> are defined [[Recursion|recursively]] by <cmath>\begin{align*} T_0(x) &= 1, \\ T_1(x) &= x, \\ T_{n+1}(x) &= 2xT_n(x) - T_{n-1}(x), \end{align*}</cmath> or equivalently by <cmath>T_n(x) = \cos (n \arccos x).</cmath>

==Proof of equivalence of the two definitions==
In the proof below, <math>T_n(x)</math> will refer to the recursive definition.

For the <math>n = 0</math> base case, <cmath>\cos(0 \arccos x) = \cos 0 = 1 = T_0(x);</cmath> for the <math>n = 1</math> base case, <cmath>\cos(1 \arccos (x)) = \cos(\arccos (x)) = x = T_1(x).</cmath>

Now for the inductive step, let <math>y = \arccos x</math>, so that <math>x = \cos y</math>. We then assume that <math>\cos ((n-1)y) = T_{n-1}(x)</math> and <math>\cos ny = T_n(x)</math>, and we wish to prove that <math>\cos ((n+1)y) = T_{n+1}(x)</math>.

From the [[Trigonometric identities#Angle addition identities|cosine sum and difference identities]] we have <cmath> \cos ((n+1)y) = \cos (ny+y) = \cos ny \cos y - \sin ny \sin y</cmath> and <cmath> \cos ((n-1)y )= \cos (ny-y) = \cos ny \cos y + \sin ny \sin y.</cmath> The sum of these equations is <cmath> \cos ((n+1)y) + \cos ((n-1)y) = 2 \cos ny \cos y;</cmath> rearranging, <cmath> \cos ((n+1)y) = 2 \cos y \cos ny  - \cos ((n-1)y).</cmath>
Substituting our assumptions yields <cmath> \cos ((n+1)y) = 2xT_n(x) - T_{n-1}(x) = T_{n+1}(x),</cmath> as desired.

==Composition identity==

For nonnegative integers <math>m</math> and <math>n</math>, the identity <math>T_{mn} = T_m(T_n(x))</math> holds.

===First proof===
By the trigonometric definition, <math>T_m(T_n(x)) = \cos(m(\arccos(\cos(n(\arccos(x))))))</math>.

As before, let <math>\arccos x = y</math>. We have <math>\arccos(\cos(ny)) = 2k\pi \pm ny</math> for some integer <math>k</math>. Multiplying by <math>m</math> and distributing gives <math>2mk\pi \pm mny</math>; taking the cosine gives <math>\cos (2mk\pi \pm mny) = \cos mny = \cos ( mn (\arccos x)) = T_{mn}(x)</math>.

For now this proof only applies where the trigonometric definition is defined; that is, for <math>x \in [-1,1]</math>. However, <math>T_{mn}(x)</math> is a degree-<math>mn</math> polynomial, and so is <math>T_m(T_n(x))</math>, so the fact that <math>T_{mn}(x) = T_m(T_n(x))</math> for some <math>mn + 1</math> distinct <math>x \in [-1,1]</math> is sufficient to guarantee that the two polynomials are equal over all real numbers.

===Second proof (Induction)===

First we prove a lemma: that <math>T_{k+n}(x) = 2T_n(x)T_k(x) - T_{k-n}(x)</math> for all <math>n \leq k</math>. To prove this lemma, we fix <math>k</math> and induct on <math>n</math>.

For all <math>k</math>, we have <cmath>T_{k}(x) = 2T_{k}(x) - T_k(x) = 2T_0(x)T_{k}(x) - T_{k}(x),</cmath> and for all <math>k \geq 1</math>, <cmath>T_{k+1}(x) = 2xT_k(x) - T_{k-1}(x) = 2T_1(x)T_k(x) - T_{k-1}(x),</cmath> proving the lemma for <math>n = 0</math> and <math>n = 1</math> respectively. 

Suppose the lemma holds for <math>n - 1</math> and <math>n</math>; that is, <math>T_{k+n}(x) = 2T_{n}(x)T_k(x) - T_{k-n}(x)</math> and <math>T_{k+n-1}(x) = 2T_{n-1}(x)T_k(x) - T_{k-n+1}(x)</math>. Then multiplying the first equation by <math>2x</math> and subtracting the second equation gives <cmath>2xT_{k+n}(x) - T_{k+n-1}(x) = 2(2xT_{n}(x) - T_{n-1}(x))T_k(x) - (2xT_{k-n}(x) - T_{k-n+1}(x)),</cmath> which simplifies to <cmath>T_{k+n+1}(x) = 2T_{n+1}(x)T_k(x) - T_{k-n-1}(x)</cmath> using the original recursive definition, as long as <math>k-n-1 \geq 0</math>. Thus, the lemma holds for <math>n + 1</math> (as long as <math>n + 1 \leq k</math>), completing the inductive step.

To prove the claim, we now fix <math>n</math> and induct on <math>m</math>.

For all <math>n</math>, we have <cmath>T_0(T_n(x)) = 1 = T_0(x)</cmath> and <cmath>T_1(T_n(x)) = T_n(x),</cmath> proving the claim for <math>m = 0</math> and <math>m = 1</math> respectively. 

Suppose the claim holds for <math>m - 1</math> and <math>m</math>; that is, <math>T_{m-1}(T_n(x)) = T_{(m-1)n}(x)</math> and <math>T_m(T_n(x)) = T_{mn}(x)</math>. We may also assume <math>m \geq 2</math>, since the smaller cases have already been proven, in order to ensure that <math>n \leq mn</math>. Then by the lemma (with <math>k = mn</math>) and the original recursive definition,
<cmath> \begin{align*} 
T_{(m+1)n}(x) &= T_{mn+n}(x) \\
&= 2T_n(x)T_{mn}(x) - T_{mn - n}(x) \\
&= 2T_n(x)T_{mn}(x) - T_{(m-1)n}(x) \\
&= 2T_n(x)T_m(T_n(x)) - T_{m-1}(T_n(x)) \\
&= T_{m+1}(T_n(x)), \\
\end{align*}</cmath> completing the inductive step.

==Roots==
Since <math>T_n(\cos y) = \cos ny</math>, and the values of <math>ny</math> for which <math>\cos ny = 0</math> are <math>\frac{2k+1}{2}\pi</math> for integers <math>k</math>, the roots of <math>T_n(x)</math> are of the form <cmath>\cos \left( \frac{2k+1}{2n}\pi \right).</cmath>

These roots are also called<b> Chebyshev nodes</b>.

==Connection to roots of unity==
Because cosine is <math>1</math> only at integer multiples of <math>2\pi</math>, the roots of the polynomial <math>T_n(x) - 1</math> follow the simpler formula <math>\cos \frac{2k\pi}{n}</math>. The <math>n</math>th roots of unity have arguments of <math>\frac{2k\pi}{n}</math> and magnitude <math>1</math>, so the roots of <math>T_n(x) - 1</math> are the real parts of the <math>n</math>th roots of unity. This lends intuition to several patterns.

All roots of <math>T_n(x) - 1</math> are also roots of <math>T_{mn}(x) - 1</math>, since all <math>n</math>th roots of unity are also <math>mn</math>th roots of unity. This can also be shown algebraically as follows: Suppose <math>T_n(x) - 1 = 0</math>. Then <cmath>T_{mn}(x) - 1 = T_m(T_n(x)) - 1 = T_m(1) - 1 = 1 - 1 = 0,</cmath>
using the composition identity and the fact that <math>T_m(1) = \cos(m \arccos 1) = \cos 0 = 1</math> for all <math>m</math>.

Particular cases include that <math>1</math>, being a root of <math>T_1(x) - 1 = x - 1</math>, is a root of <math>T_n(x) - 1</math> for all positive <math>n</math>, and <math>-1</math>, being a root of <math>T_2(x) - 1 = 2x^2 - 2</math>, is a root of <math>T_n(x) - 1</math> for all positive even <math>n</math>. All other roots of <math>T_n(x) - 1</math> correspond to roots of unity which fall into [[Complex conjugate|conjugate pairs]] with the same real part. One might therefore suspect that all remaining roots of <math>T_n(x) - 1</math> are double roots. In fact, <cmath>T_{2n+1}(x) - 1= (x - 1)(W_n(x))^2</cmath> and <cmath>T_{2n+2}(x) - 1 = 2(x - 1)(x + 1)(U_n(x))^2</cmath> for polynomials <math>W_n(x)</math> and <math>U_n(x)</math> satisfying the same recurrence relation as <math>T_n(x)</math>, but with the different base cases <math>W_1(x) = 2x + 1</math> and <math>U_1(x) = 2x</math>. The polynomials <math>U_n(x)</math> are known as [[Chebyshev polynomials of the second kind]].

===Rational roots===
Other than <math>1</math> and <math>-1</math>, any root of a Chebyshev polynomial of the first kind must be a root of either <math>W_n(x)</math> or <math>U_n(x)</math> for some <math>n</math>.
The polynomials <math>w_n(x) = W_n \left( \frac{x}{2} \right)</math> and <math>u_n(x) = U_n \left( \frac{x}{2} \right)</math> satisfy the recursive formulas <cmath>\begin{align*} w_0(x) &= 1 \\ w_1(x) &= x + 1 \\ w_{n+1}(x) &= xw_n(x) - w_{n-1}(x), \end{align*}</cmath> and <cmath>\begin{align*} u_0(x) &= 1 \\ u_1(x) &= x \\ u_{n+1}(x) &= xu_n(x) - u_{n-1}(x), \end{align*}</cmath> ensuring that they have integer coefficients and are monic for all <math>n</math>. Thus, by the [[Rational Root Theorem]], any rational roots of <math>w_n(x)</math> or <math>u_n(x)</math> must be integers. The only possible integer roots of <math>w_n(x)</math> or <math>u_n(x)</math> are <math>-1</math>, <math>0</math>, and <math>1</math>, so the only possible rational roots of <math>W_n(x)</math> or <math>U_n(x)</math> are <math>-\frac{1}{2}</math>, <math>0</math>, or <math>\frac{1}{2}</math>. Thus, the only rational roots of <math>T_n(x) - 1</math> across all choices of <math>n</math> are <math>-1</math>, <math>-\frac{1}{2}</math>, <math>0</math>, <math>\frac{1}{2}</math>, and <math>1</math>.

Because any value <math>\cos \frac{a\pi}{b}</math> for integers <math>a</math> and <math>b</math> is a root of <math>T_b(x)</math>, these five are the only rational values of the cosine of a rational multiple of <math>\pi</math>. This result is known as <b>Niven's Theorem</b>.