Logo
Published on

The Recursive Geometry of Chebyshev Sequences

Authors
  • avatar
    Name
    Vu Hung
    Twitter

Problem Statement

Let a sequence of functions (Tn(x))(T_n(x)) be defined for n≥0n \ge 0 by the recurrence relation

Tn+1(x)=2xTn(x)−Tn−1(x),T_{n+1}(x)=2xT_n(x)-T_{n-1}(x),

with initial terms T0(x)=1T_0(x)=1 and T1(x)=xT_1(x)=x.

  • Calculate the explicit polynomial expressions for T2(x)T_2(x) and T3(x)T_3(x).
  • Using the identity
cos⁡(A+B)+cos⁡(A−B)=2cos⁡Acos⁡B,\cos(A+B)+\cos(A-B)=2\cos A\cos B,

prove by mathematical induction that for all n≥0n \ge 0,

Tn(cos⁡θ)=cos⁡(nθ).T_n(\cos\theta)=\cos(n\theta).
  • Let x0x_0 be a root of Tn(x)T_n(x). Show that ∣x0∣≤1|x_0|\le 1. Hence, determine the exact values of the nn distinct roots of Tn(x)T_n(x) in terms of nn.
  • Consider the sequence of values vn=Tn(1.5)v_n=T_n(1.5). Show that (vn)(v_n) satisfies a linear recurrence relation with constant coefficients. Find a closed-form expression for vnv_n and determine the value of the limit
lim⁡n→∞vn+1vn.\lim_{n\to\infty}\frac{v_{n+1}}{v_n}.

Hints

  • For (i): Substitute the previous two polynomials into the recurrence formula.
  • For (ii): Use the sum-to-product identity with A=kθA=k\theta and B=θB=\theta.
  • For (iii): Solve cos⁡(nθ)=0\cos(n\theta)=0 for θ\theta, then use x=cos⁡θx=\cos\theta.
  • For (iv): Solve the characteristic equation for the recurrence vn+1=3vn−vn−1v_{n+1}=3v_n-v_{n-1}.

Solutions

(i) Directly from the recurrence,

T2(x)=2x2−1,T3(x)=2x(2x2−1)−x=4x3−3x.T_2(x)=2x^2-1,\qquad T_3(x)=2x(2x^2-1)-x=4x^3-3x.

(ii) The cases n=0,1n=0,1 give 1=cos⁡01=\cos0 and T1(cos⁡θ)=cos⁡θT_1(\cos\theta)=\cos\theta. Suppose

Tk(cos⁡θ)=cos⁡(kθ),Tk−1(cos⁡θ)=cos⁡((k−1)θ).T_k(\cos\theta)=\cos(k\theta),\qquad T_{k-1}(\cos\theta)=\cos((k-1)\theta).

Then

Tk+1(cos⁡θ)=2cos⁡θ Tk(cos⁡θ)−Tk−1(cos⁡θ)=2cos⁡θcos⁡(kθ)−cos⁡((k−1)θ)=cos⁡((k+1)θ),\begin{aligned} T_{k+1}(\cos\theta) &=2\cos\theta\,T_k(\cos\theta)-T_{k-1}(\cos\theta)\\ &=2\cos\theta\cos(k\theta)-\cos((k-1)\theta)\\ &=\cos((k+1)\theta), \end{aligned}

using cos⁡((k+1)θ)+cos⁡((k−1)θ)=2cos⁡(kθ)cos⁡θ\cos((k+1)\theta)+\cos((k-1)\theta)=2\cos(k\theta)\cos\theta. Hence Tn(cos⁡θ)=cos⁡(nθ)T_n(\cos\theta)=\cos(n\theta) for all n≥0n\ge0.

(iii) If x>1x>1, write x=cosh⁡ux=\cosh u; then Tn(x)=cosh⁡(nu)>0T_n(x)=\cosh(nu)>0. If x<−1x<-1, write x=−cosh⁡ux=-\cosh u; then Tn(x)=(−1)ncosh⁡(nu)≠0T_n(x)=(-1)^n\cosh(nu)\ne0. Thus every real root satisfies ∣x0∣≤1|x_0|\le1.

Now write x=cos⁡θx=\cos\theta. The roots satisfy

Tn(cos⁡θ)=0  ⟺  cos⁡(nθ)=0  ⟺  nθ=(2k−1)π2.T_n(\cos\theta)=0\iff \cos(n\theta)=0 \iff n\theta=\frac{(2k-1)\pi}{2}.

So the nn distinct roots are

xk=cos⁡((2k−1)π2n),k=1,2,…,n.x_k=\cos\left(\frac{(2k-1)\pi}{2n}\right),\qquad k=1,2,\ldots,n.

(iv) With vn=Tn(1.5)v_n=T_n(1.5),

vn+1=3vn−vn−1,v0=1,v1=32.v_{n+1}=3v_n-v_{n-1},\qquad v_0=1,\quad v_1=\frac32.

The characteristic equation is λ2−3λ+1=0\lambda^2-3\lambda+1=0, with roots

α=3+52,β=3−52.\alpha=\frac{3+\sqrt5}{2},\qquad \beta=\frac{3-\sqrt5}{2}.

Hence vn=Aαn+Bβnv_n=A\alpha^n+B\beta^n. From v0=1v_0=1 and v1=32v_1=\frac32, A=B=12A=B=\frac12, so

vn=12αn+12βn.v_n=\frac12\alpha^n+\frac12\beta^n.

Since ∣β∣<α|\beta|<\alpha, the dominant term is αn\alpha^n, and therefore

lim⁡n→∞vn+1vn=α=3+52.\lim_{n\to\infty}\frac{v_{n+1}}{v_n}=\alpha=\frac{3+\sqrt5}{2}.

Takeaways

  • The recurrence produces the Chebyshev polynomials one term at a time.
  • The identity Tn(cos⁡θ)=cos⁡(nθ)T_n(\cos\theta)=\cos(n\theta) turns polynomial roots into trigonometric roots.
  • Evaluating a polynomial recurrence at a fixed value gives an ordinary numerical recurrence.

Further Readings

Connect with me