Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Created page with "The Chebyshev polynomials of the first kind are defined recursively by <cmath>T_0(x) = 1,</cmath> <cmath>T_1(x) = x,</cmath> <cmath>T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x),</cmath>...")
 
(→‎First proof)
Line 16: Line 16:
  
 
===First proof===
 
===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)===
 
===Second proof (Induction)===

Revision as of 18:03, 28 February 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)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Chebyshev_polynomials_of_the_first_kind&oldid=172218"