show that nth Chebyshev polynomial is an nth order polynomial 
Define the Chebyshev polynomial $T_n(x)=\cos(n\cos^{-1}(x)), n\geq 1, T_0=1)$.
Show that $T_n(x)$ is an nth order polynomial

This is my attempt, however I couldn't reduce it to a polynomial. 
\begin{align}
T_n(x)&=\cos(n\cos^{-1}x)\\
 &= \cos(\cos^{-1}x+\cos^{-1}x+\dots_\text{n times}) \\
&=\cos(\cos^{-1}x)\cos(\cos^{-1}x)\dots_\text{n times}-\sin(\cos^{-1}x)\sin(cos^{-1}x)\dots_\text{n times}\\
&=x^n -(1-x^2)^{n/2}, \quad\text{using}~(\sin\theta = \sqrt{1-x^2})
\end{align}
but this is not a polynomial!
 A: Your expansion of $\cos(\cos^{-1}x + \ldots + \cos^{-1}x)$ is incorrect.  Note that when $n=3$, we have $\cos(3z) = \cos^3z -3\cos z\sin^2z$ instead of $\cos^3z - \sin^3 z$.  This identity is derived as follows:
$$\begin{align*}
\cos3z = \cos(2z+z) & = \cos 2z \cos z - \sin2z\sin z \\ 
& = (\cos^2z - \sin^2z)\cos z - (2\sin z \cos z)\sin z \\
& = \cos^3 z - 3\cos z\sin^2z 
\end{align*}
$$  The important thing you should note in the context of this problem is that all powers of $\sin z$ are even, so if we plug in $z = \cos^{-1}x$ we get $\sin^2 z = 1-\cos^2z = 1 -x^2$.  The way to proceed for this problem might be to show (inductively, perhaps) that when you expand $\cos(nz)$ as a polynomial in $\cos z$ and $\sin z$ using the angle addition formula, the powers of $\sin z$ are all even.  (Along the way, you might need to show that the powers of $\sin z$ in the expression of $\sin(nz)$ are all odd.)
Instead of induction, if you are comfortable with complex numbers you could use the formula $e^{iz} = \cos z + i \sin z$ to derive $\cos(nz) + i \sin(nz) = e^{inz} = (\cos z + i\sin z)^n$, and expand this out using the binomial formula.
A: Your method will work with a little tweak (and after the corrections noted by the other answer). Try expanding $\cos(n\,\arccos x)$ as:
$$\begin{array}{cl}&\cos(n\,\arccos x) \\= &\cos((n-1)\,\arccos x)\,\cos(\arccos x)-\sin((n-1)\,\arccos x)\,\sin(\arccos x)\end{array}\tag{1}$$
but now bring to bear the identity:
$$\sin(u)\,\sin(v) = \frac{1}{2}(\cos(u-v)-\cos(u+v))$$
on the second term of (1). You'll thus derive the recurrence:
$$T_n = T_{n-1}\,T_1 - \frac{1}{2}(T_{n-2}-T_n)$$
for the Tschebyschev polynomial, which you can then use to show  by induction that $T_n$ is a polynomial in $T_1=\cos(\arccos x)=x$.
