Difference between revisions of "Chebyshev polynomials of the first kind"

Revision as of 00:28, 1 March 2022

The Chebyshev polynomials of the first kind are defined recursively by $T_0(x) = 1,$ $T_1(x) = x,$ $T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x),$ or equivalently by $T_n(x) = \cos (n \arccos x).$

Proof of equivalence of the two definitions

In the proof below, $T_n(x)$ will refer to the recursive definition.

For the $n = 0$ base case, $\cos(0 \arccos x) = \cos 0 = 1 = T_0(x);$ for the $n = 1$ base case, $\cos(1 \arccos (x)) = \cos(\arccos (x)) = x = T_1(x).$

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

From the cosine sum and difference identities we have $\cos ((n+1)y) = \cos (ny+y) = \cos ny \cos y - \sin ny \sin y$ and $\cos ((n-1)y )= \cos (ny-y) = \cos ny \cos y + \sin ny \sin y.$ The sum of these equations is $\cos ((n+1)y) + \cos ((n-1)y) = 2 \cos ny \cos y;$ rearranging, $\cos ((n+1)y) = 2 \cos y \cos ny - \cos ((n-1)y).$ Substituting our assumptions yields $\cos ((n+1)y) = 2xT_n(x) - T_{n-1}(x) = T_{n+1}(x),$ as desired.

Composition identity

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

First proof

By the trigonometric definition, $T_m(T_n(x)) = \cos(m(\arccos(\cos(n(\arccos(x))))))$ .

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

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

Second proof (Induction)

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

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

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

To prove the claim, we now fix $n$ and induct on $m$ .

For all $n$ , we have $T_0(T_n(x)) = 1 = T_0(x)$ and $T_1(T_n(x)) = T_n(x),$ proving the claim for $m = 0$ and $m = 1$ respectively.

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

@@ Line 23: / Line 23: @@
 ===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) - (T_{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.

Page

Toolbox

Search