Difference between revisions of "Chebyshev polynomials of the first kind"
(→Connection to roots of unity) |
|||
Line 1: | Line 1: | ||
− | The <b> Chebyshev polynomials of the first kind </b> are defined [[Recursion|recursively]] by <cmath>T_0(x) = 1, | + | 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== | ==Proof of equivalence of the two definitions== | ||
Line 49: | Line 49: | ||
==Connection to roots of unity== | ==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 | + | 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> | 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>. | 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, | + | 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>. |
Revision as of 21:45, 2 March 2022
The Chebyshev polynomials of the first kind are defined recursively by or equivalently by
Contents
Proof of equivalence of the two definitions
In the proof below, will refer to the recursive definition.
For the base case,
for the
base case,
Now for the inductive step, let , so that
. We then assume that
and
, and we wish to prove that
.
From the cosine sum and difference identities we have and
The sum of these equations is
rearranging,
Substituting our assumptions yields
as desired.
Composition identity
For nonnegative integers and
, the identity
holds.
First proof
By the trigonometric definition, .
As before, let . We have
for some integer
. Multiplying by
and distributing gives
; taking the cosine gives
.
For now this proof only applies where the trigonometric definition is defined; that is, for . However,
is a degree-
polynomial, and so is
, so the fact that
for some
distinct
is sufficient to guarantee that the two polynomials are equal over all real numbers.
Second proof (Induction)
First we prove a lemma: that for all
. To prove this lemma, we fix
and induct on
.
For all , we have
and for all
,
proving the lemma for
and
respectively.
Suppose the lemma holds for and
; that is,
and
. Then multiplying the first equation by
and subtracting the second equation gives
which simplifies to
using the original recursive definition, as long as
. Thus, the lemma holds for
(as long as
), completing the inductive step.
To prove the claim, we now fix and induct on
.
For all , we have
and
proving the claim for
and
respectively.
Suppose the claim holds for and
; that is,
and
. We may also assume
, since the smaller cases have already been proven, in order to ensure that
. Then by the lemma (with
) and the original recursive definition,
completing the inductive step.
Roots
Since , and the values of
for which
are
for integers
, the roots of
are of the form
These roots are also called Chebyshev nodes.
Connection to roots of unity
Because cosine is only at integer multiples of
, the roots of the polynomial
follow the simpler formula
. The
th roots of unity have arguments of
and magnitude
, so the roots of
are the real parts of the
th roots of unity. This lends intuition to several patterns.
All roots of are also roots of
, since all
th roots of unity are also
th roots of unity. This can also be shown algebraically as follows: Suppose
. Then
using the composition identity and the fact that
for all
.
Particular cases include that , being a root of
, is a root of
for all positive
, and
, being a root of
, is a root of
for all positive even
. All other roots of
correspond to roots of unity which fall into conjugate pairs with the same real part. One might therefore suspect that all remaining roots of
are double roots. In fact,
and
for polynomials
and
satisfying the same recurrence relation as
, but with the different base cases
and
.