Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 68 / 2

Put $x=\cos \theta$. The trigonometric identitygivesStarting with $T_0=1$ and $T_1=x$, this recurrence proves inductively that each Chebyshev polynomial is a polynomial. For $n\ge 1$, the highest-degree term in $2x{T}_n$ cannot cancel against $T_{n-1}$, so the degree increases by one and its leading coefficient doubles. ThusThe constant polynomial $T_0$ has leading coefficient one.

For $n\ge 1$, the points $x_j=\cos (j\pi /n)$, $j=0,\dots ,n$, give $T_n(x_j)=(-1{)}^j$. They are all the points where $|T_n|=1$, since $|\cos (n\theta )|=1$ exactly when $n\theta$ is an integer multiple of $\pi$. Therefore there are $n+1$ equioscillation points, including the two endpoints. Reversing their order makes an increasing alternating sequence. For $n=0$ the polynomial is constant: every point has unit value, but an alternating sequence has at most one point.

Now take $n\ge 1$ and $c=2^{1-n}$. Since $c{T}_n$ is monic, $p_0(x)=x^n-c{T}_n(x)$ has degree at most $n-1$, and $\Vert x^n-p_0{\Vert }_{\infty }=c$. This proves the upper bound for the best error.

For the lower bound, suppose a polynomial $p$ of degree at most $n-1$ had $\Vert x^n-p{\Vert }_{\infty }<c$. At each of the $n+1$ ordered extrema, $h=p-p_0$ must have the same strictly nonzero sign as $T_n$: if $c{T}_n=c$, then $|c-h|<c$ gives $h>0$, and if $c{T}_n=-c$, then $|-c-h|<c$ gives $h<0$. Between every consecutive pair, the intermediate value theorem gives a zero of $h$. These are $n$ distinct zeros, impossible for a nonzero polynomial of degree at most $n-1$; $h=0$ is incompatible with the strict error improvement. This first-principles sign argument proves the monic Chebyshev extremal polynomial bound without using the alternation theorem:The displayed $p_0$ supplies an actual best approximating polynomial.