# Chebyshev Polynomial Recurrence relation

the problem states: "Show that $\cos(n\theta)$ is a polynomial in $\cos(\theta).$" Now, using De Moivre's and Binomial theorems i get that $$\cos(n\theta) = \sum_{k = 0, evens}^{n}\binom{n}{k}\cos^{n-k}(\theta)(\pm(1-\cos^{2}(\theta))^{k/2})$$ Note that the $\pm$ here does not mean both, but it rather means "we don't care which one," and so it is obvious that the RHS is a polynomial in $\cos(\theta).$

So the second part of the problem asks to "use appropriate trig functions" to show that $$T_{n+1}(z) + T_{n-1}(z) = 2zT_{n}(z).$$

Here i am stuck. Since i have never encountered Chebyshev polynomials before, is the RHS i found for $\cos(n\theta)$ the $T_{n}(z)$? And if so, exactly how would i approach the second part of the problem? I tried induction, but either i am too tired right now, or it really does get hairy too fast. Thanks in advance.

It's strange that the problem statement would drop $T_n$ onto you without ever indicating its relation to $\cos n\theta$. You are right: $T_n(\cos\theta)=\cos n\theta$ for all $\theta\in\mathbb R$. So, the identity you are asked to prove is related to $$\cos(n+1)\theta + \cos(n-1)\theta = 2\cos \theta \cos n\theta \tag{1}$$ which follows by expanding the left side using the cosine of sum/difference formulas.
$$T_{n+1}(z) + T_{n-1}(z) = 2zT_{n}(z)\tag{2}$$ for $z\in [-1,1]$, since these values of $z$ can be written as $\cos \theta$. But this is enough to conclude (2) holds for all $z$: if two polynomials agree in a neighborhood of $0$, then for every $k\in\mathbb N\cup\{0\}$ their $k$th derivatives agree at $0$, which means they have the same coefficients.