Chebyshev coefficients from a polynomial Is there an efficient algorithm for finding the coefficients in a Chebyshev basis of a polynomial?  That is, given the set of $a_k$ such that:
$p_n(x) = \sum_{k=0}^N a_k x^k $
Find the set of $c_k$ such that:
$ p_n(x) = \sum_{k=0}^N c_k T_k(x)$
Where $T_k(x)$ is the kth Chebyshev polynomial of the first kind
I've found this link but I think there's some typos in the explanation since the bounds on the sums don't make sense.
 A: Natural way to arrive at the formulas would be to use orthogonality:
$$
     c_k = \frac{2 - \delta_{k,0}}{\pi} \int_0^\pi \cos(k x) p_n(\cos(x)) \mathrm{d}x = \frac{2 - \delta_{k,0}}{\pi} \sum_{m=0}^n a_m \int_0^\pi \cos(k x) \cos^m(x) \mathrm{d}x
$$
Now, using
$$ \begin{eqnarray}
\cos^m(x) &=& \Re\left( \left( \frac{1}{2} \left(\mathrm{e}^{i x} + \mathrm{e}^{-i x} \right) \right)^m \right) = \Re\left(\frac{1}{2^m} \sum_{r=0}^m \binom{m}{r} \mathrm{e}^{i (r x - x (m-r) }\right)\\  &=& \frac{1}{2^m} \sum_{r=0}^m \binom{m}{r} \cos((2r-m)x)
\end{eqnarray}$$
we have
$$\begin{eqnarray}
    c_k &=& \frac{2 - \delta_{k,0}}{\pi} \sum_{m=0}^n \frac{a_m}{2^m}  \frac{\pi}{2-\delta_{k,0}} \sum_{r=0}^m \binom{m}{r} \delta_{k, | 2r-m |}  \\ &=& \sum_{m=0}^{n} \frac{a_m}{2^m} \left[ m + k \equiv 0 \mod 2 \right] \frac{1}{1+\delta_{k,0}}\left( \binom{m}{\frac{m+k}{2}} + \binom{m}{\frac{m-k}{2}} \right)
\end{eqnarray}$$
Here is a confirmation in Mathematica:
In[21]:= c[k_Integer] := 
  Sum[1/2^m a[m] 1/(
    1 + KroneckerDelta[k, 0]) (Binomial[m, (k + m)/2] + 
      Binomial[m, (-k + m)/2]), {m, Mod[k, 2], n, 2}];

In[22]:= Table[
  Sum[c[k] ChebyshevT[k, x], {k, 0, n}], {n, 0, 4}] // Expand

Out[22]= {a[0], a[0] + x a[1], a[0] + x a[1] + x^2 a[2], 
 a[0] + x a[1] + x^2 a[2] + x^3 a[3], 
 a[0] + x a[1] + x^2 a[2] + x^3 a[3] + x^4 a[4]}

In[23]:= Table[Sum[a[m] x^m, {m, 0, n}], {n, 0, 4}] == %

Out[23]= True

