Express $f_n(x)=\cos{(n\arccos{x})}$ as a polynomial. I had an interesting problem on an exam a few days ago in elementary calculus. It reads:
Show that for $n\geq 2,$ the function $f_n(x)=\cos{(n\arccos{x})}, \ x\in[-1,1]$ is a polynomial of degree $n$ and determine the coefficient for $x^n$.

I was not able to work this problem and after the exam I looked this up online and it seems as if this is related to the Chebyshev polynomials. But we have never covered these kinds of polynomials in this course. Is there other ways to do this? 
What I tried to do in the exam was to compute $f_n(x)$ for $n=1,2...$ and see if I can find a pattern and formulate an induction hypothesis and then prove it. I got that
$$f_1(x)=\cos{(1\cdot \arccos{x})}=x,\\f_2(x)=\cos{(2\cdot \arccos{x})}=1-2\cos^2{(\arccos{x})}=1-2x^2\\
f_3(x)=\cos{(3\cdot \arccos{x})}=4\cos^3{(\arccos{x})}-3\cos{(\arccos{x})}=4x^3-3x$$
As you can see it quickly becomes ugly and there is no pattern to be seen. So, to formulate a hypothesis for even numbers $n=2k$ was not hard, but for odd numbers, $n=2k+1$ i could not do it.
Is this start a good one or is this totally wrong? Would this method work If I was a bit better at math? any other tips/tricks that only uses elementary calculus? We are not allowed to use expansions in this course.
 A: The polynomials can be computed recursively: set $\:T_n(x)=\cos(n\arccos x)$ and start from the trigonometric identity:
$$\cos(a-b)+\cos(a+b)=2\cos a\cos b.$$
It specialises as
$$\cos(n-1)t+\cos(n+1)t=2\cos t\cos nt.$$
Setting $t=\arccos x$,  you can read the above formula as
$$T_{n+1}(x)=2x\,T_n(x)-T_{n-1}(x).$$
A: HINT

$$\cos{n\theta}=\cos^n{\theta}-
\binom {n} {2}\cos^{n-2} \theta \cdot \sin^2 \theta+
\binom {n} {4}\cos^{n-4} \theta \cdot \sin^{4} \theta -\cdots$$

NOTE
The relation is obtained by binomial theorem and Euler's equality:


*

*$\ \cos \theta +i \sin \theta = e^{i \theta}$

*$\ (e^{i\theta})^n = (\cos\theta+i\sin\theta)^n$

*$\ (e^{i\theta})^n = e^{i(n\theta)} = \cos(n\theta)+i\sin(n\theta) =
   (\cos\theta+i\sin\theta)^n $

A: Substituting $t=\arccos(x)$, we have:
$\begin{equation}\int f_n(x)=\end{equation}$
$\begin{equation}=-\int (\sin(t)\cdot \cos(nt))=\end{equation}$
$\begin{equation}=-\frac{1}{2}\int(\sin((n+1)t)+\sin((1-n)t)=\end{equation}$
$\begin{equation}=\frac{1}{2}\left(\frac{\cos((n+1)\arccos(x))}{n+1}-\frac{\cos(\arccos((n-1)x))}{n-1}\right)=\end{equation}$
$\begin{equation}=\frac{1}{2}\left(\frac{f_{n+1}}{n+1}-\frac{f_{n-1}}{n-1}\right)\end{equation}$ 
(passing from the second to the third equation we have used the prosthaphaeresis)
Now, equating the coefficients of $x^{n+1}$ in the LHS and RHS, we get:
$\begin{equation}2 c_n=c_{n+1}\end{equation}$
$\begin{equation}c_1=1\end{equation}$
$\begin{equation}c_{n}=2^n\end{equation}$
(It doesn't match your computation since you switched the signes in f_2)
Just for your knowledge, the pattern you were looking for is, in fact, not so "nice". It is:
$\begin{equation} \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \binom{n}{2k} \left (x^2-1 \right )^k x^{n-2k}\end{equation}$
A: Hint:
With twice differentiating of $f_n(\cos x)=\cos nx$ we get
$$f''_n(\cos x)\sin^2x=(\cos x-n^2)\cos nx$$
then with $\cos x=u$ solve DE $$(1-u^2)y''=(u-n^2)y$$
with series expansion $\displaystyle y=\sum_{n\geq0}a_nu^n$ where $f_n(u)=y$.
A: Let $t=\arccos x.$ Then $\sin t = \sqrt{1-x^2}/x$ and $\sin 2t = 2\sqrt{1-x^2}.$
We can prove by induction that $\sin nt = \mbox{poly}\times \sqrt{1-x^2}$ and $\cos nt =$ poly for each $n$.  The (four) basis steps are above.  Assume both identities are true for $n$.  Then 
$$\sin (n+2)t = \sin nt \cos 2t + \sin 2t \cos nt  $$
$$ = \mbox{(poly)}\sqrt{1-x^2}(2\cos t-1) +\sqrt{x^2-1}\mbox{(poly)} $$
$$= \mbox{(poly)}\sqrt{1-x^2}.$$
And then
$$\cos (n+2)t = \cos nt\cos 2t - \sin nt \sin 2t$$
$$=\mbox{(poly)}(2\cos t-1) - \left(\mbox{(poly)}\sqrt{1-x^2}\right)\sqrt{1-x^2}  $$
$$= \mbox{(poly)}(2x^2-1) - \mbox{(poly)}(1-x^2) = \mbox{(poly)}.$$
A: 
Summary. We prove that $f_n$ is a polynomial of degree $n$ by showing that its $(n+1)$-th derivative vanishes.

We use the change of variable $x=\cos\theta$ and the chain rule 
$$\tag{1}
\frac{d}{dx} = \frac{-1}{\sin \theta}\frac{d}{d\theta}, $$ 
to show that 
$$\tag{2}\frac{d f_n}{dx}=\sum_{k=0}^{n-1} a_k f_k, $$ 
for some coefficients $a_k\in\mathbb R$. Iterating, we have that $\frac{d^n f_n}{dx^n}=af_0$ for some $a\in\mathbb R$. Since $f_0$ is a constant, we conclude that $\frac{d^{n+1}f_n}{dx^{n+1}}=0$.
Proof. Because of (1), 
$$
\frac{d f_n}{dx} = n\frac{\sin n\theta }{\sin \theta}=n\frac{e^{in \theta}-e^{-in\theta} }{e^{i\theta}-e^{-i\theta}}. $$
Using the relation $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b^2+\dots + a^2 b^{n-2} + b^n)$ with $a=e^{i\theta}, b=e^{-i\theta}$, we rewrite the right-hand side as 
$$
n(e^{i(n-1)\theta} +e^{i(n-3)\theta} +\ldots + e^{-i(n-1)\theta})= \begin{cases} \displaystyle n +2n\sum_{j=1}^{(n-1)/2} \cos(2j\theta), & n\text{ odd} \\ \displaystyle 2n\sum_{j=1}^{n/2}\cos((2j-1)\theta), & n\text{ even}.\end{cases}$$
With the substitution $x=\cos\theta$, the terms in the right hand side equal $f_{2j}(x)$ or $f_{2j-1}(x)$, thus (2) is proved. $\square$
A: Once demonstrated that $f_{n}(x)$ has the recursion
formula as cleverly indicated by Bernard, and thus is a polynomial
since $f_{0}(x)=1$ and $f_{1}(x)=x$, then
we can look and find its zeros.
$$
\eqalign{
  & f_n (x) = 0\quad  \Rightarrow \quad n\,\arccos x = {\pi  \over 2} + m\pi \quad  \Rightarrow   \cr 
  &  \Rightarrow \quad \,x = \cos \left( {{{1 + 2m} \over n}{\pi  \over 2}} \right) \cr} 
$$
In the given interval for $x$ then 
$$
x \in \left[ { - 1,1} \right]\quad  \Rightarrow \quad 0 \le {{1 + 2m} \over n}{\pi  \over 2} \le \pi \quad  \Rightarrow \quad 0 \le m \le n - 1 \le {{2n - 1} \over 2}
$$
which gives that the function has in fact $n$ distinct real zeros.
So, since $f_n (1) = 1$, we can express the polynomial as
$$
f_n (x) = {{\prod\limits_{0{\kern 1pt}  \le \,m\, \le \,n - 1} {\left( {x - \cos \left( {{{1 + 2m} \over n}{\pi  \over 2}} \right)} \right)} } \over {\prod\limits_{0{\kern 1pt}  \le \,m\, \le \,n - 1} {\left( {1 - \cos \left( {{{1 + 2m} \over n}{\pi  \over 2}} \right)} \right)} }}
$$
From here, we can recover the coefficients of the power expansion
of $f_n(x)$ by the Vieta's Rules, besides that by the mentioned recursion formula.
