Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my course I have come across the following problem:

The Chebyshev polynomial of degree $n$, $T_n(x)$, is defined on $[-1,1]$ by $T_n(x)=\cos n\theta$.

Let $q_{n+1}(x)$ be any monic polynomial of degree $n+1$. Consider $2^n q_{n+1} - T_{n+1}$ to prove that $\|q_{n+1}\|\ge 2^{-n}$.

I have attempted to prove this in the following way:

$0\le \|2^n q_{n+1} -T_{n+1}\| \le \|2^n q_{n+1}\| - \|T_{n+1}\|$

$\implies \|T_{n+1}\|\le |2^n|\|q_{n+1}\|$

And using the fact that $\|T_{n+1}\| = 1 \space(*)$, we have:

$2^{-n}\le\|q_{n+1}\|$

Which was to be shown. However, I am not convinced by the step at $(*)$. I believe this is true for the infinity norm, but is it true for a norm in general? Are there any other steps in the proof that require more thought?

share|improve this question
2  
Some comments: First, the inequality $\|2^nq_{n+1} - T_{n+1}\|\leq \|2^nq_{n+1}\|-\|T_{n+1}\|$ seems highly suspect to me. Second, when you say "I believe this is true for the infinity norm, but is it true for a norm in general?", it makes it not so clear what norm you are using. So you should specify in the problem: what is $\|\cdot\|$? –  froggie Dec 17 '12 at 21:56

1 Answer 1

I'll post the equivalent definitions of $T_n$ from Wikipedia for the benefit of other readers.

Definition. (Trigonometric.) $T_n$ is the unique polynomial so that $T_n(\cos{\theta})=\cos{n\theta}$, from which we can write $T_n(x)=\cos(n \cos^{-1}x).$

Definition. (Recurrence.) Equivalently, we can define $T_n$ through the following recurrence relation. $$\begin{eqnarray*}T_0(x)&=&1\\ T_1(x)&=&x \\ T_{n+1}(x)&=&2xT_n(x)-T_{n-1}(x)\end{eqnarray*}$$

So, I am assuming that you are using the supremum norm on $[1,1]$, $$\| f \|:=\sup_{x\in[1,1]}|f(x)|.$$ From the trigonometric definition, clearly $\| T_{n+1} \|=1$. It should also come as no surprise that $T_{n+1}$ achieves its extreme values at $x_k:=\cos{\frac{k\pi}{n+1}}$ for $k=0,\ldots, {n+1}$, at which the value of $T_{n+1}(x_k)$ alternates between $\pm 1$.

Now we are ready to do the problem. Note that I chose to do this with $q-2^{-n}T_{n+1}$, but the argument with $2^nq-T_{n+1}$ is identical.

Suppose that there exists a monic polynomial of degree $n+1$ so that $\| q \|<2^{-n}$.

From the recurrence relation definition, you can see that $T_{n+1}(x)$ is not monic; in fact, the coefficient of $x^{n+1}$ in $T_{n+1}(x)$ is $2^{n}$. So let's make $T_{n+1}$ monic by considering $2^{-n}T_{n+1}$.

Then $\left(q-2^{-n}T_{n+1}\right)(x)$ is a degree $n$ polynomial. However, since $\|q\|<2^{-n}<1$, we have that $\left(q-2^{-n}T_{n+1}\right)(x)$ still changes signs between each extreme point (the $x_k$ above) and thus must have $n+1$ zeros in $(-1,1)$. This is impossible unless $q-2^{-n}T_{n+1}=0$. But then $\|q\|=\|2^{-n}T_{n+1}\|=2^{-n}\|T_{n+1}\|=2^{-n}$, a contradiction.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.