Proof of a lower bound of the norm of an arbitrary monic polynomial 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?
 A: 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.

