Proving $2\cos(k\theta) = \sum_{r=0}^{\lfloor k/2\rfloor} c(k,r) (2\cos \theta)^{k-2r}$ for $c(k,r)$ as defined 
Let $k$ be a positive integer. Define for $n\ge 1, 0\leq r\leq \lfloor n/2\rfloor$, the integers $c(n,r)$ so that $c(1,0) = 1, c(2,0) = 1, c(2,1) = -2$ and for $n\ge 3$,
$$\begin{cases}
c(n,0)\phantom{/2} = 1,\\
c(n,r)\phantom{/2} = c(n-1, r) - c(n-2, r-1), &1\leq r\leq (n-1)/2,\\
c(n,n/2) = (-1)^{n/2} 2, &\text{ if $n$ is even}\end{cases}$$
Prove that $2\cos(k\theta) = \sum_{r=0}^{\lfloor k/2\rfloor} c(k,r) (2\cos \theta)^{k-2r}$ for any real number $\theta$.

I was thinking of doing a proof by induction, but it seems very complicated to do.
If $k=1, 2$, then
$$2\cos \theta = 2\cos\theta \quad\text{and}\quad 2\cos (2\theta) = (2\cos\theta)^2 + (-2)(2\cos \theta)^{2-2}$$
so the claim holds. So assume the claim holds for all $1\leq n < m$ and $m\ge 3$.
Suppose $m$ is odd. We want to show that
$$2\cos m\theta = \sum_{r=0}^{(m-1)/2} c(m,r) (2\cos \theta)^{m-2r}$$ We know by induction that
$$2\cos(m-1)\theta = \sum_{r=0}^{(m-1)/2} c(m-1, r)(2\cos \theta)^{m-1-2r}$$ and
$$2\cos(m-2)\theta = \sum_{r=0}^{(m-3)/2} c(m-2, r)(2\cos\theta)^{m-2-2r}$$
But then if I use the cosine addition formula on
$$2\cos m\theta = 2\cos ((m-1)\theta + (m-1)\theta - (m-2)\theta)$$ then I get an expression involving sines for which I don't have an explicit formula. Also, if I were to simplify the resulting expression, it would be very complicated.

Edit: Here's my attempt for even m, based on the first answer for odd m. There's likely a shorter approach though (see Mindlack's comment).

If m is even, then $2\cos ((m-1)\theta) = \sum_{r=0}^{(m-2)/2} c(m-1, r) (2\cos \theta)^{m-1-2r}$ and $2\cos ((m-2)\theta) = \sum_{r=0}^{(m-2)/2} c(m-2, r) (2\cos\theta)^{m-2-2r}$. We have
$\begin{align}
2\cos m\theta &= 2\cos \theta \cdot 2\cos ((m-1)\theta) - 2\cos((m-2)\theta)\\
&= \sum_{r=0}^{(m-2)/2} c(m-1, r) (2\cos \theta)^{m-2r} - \sum_{r=0}^{(m-2)/2}c(m-2, r)(2\cos \theta)^{(m-2) - 2r}\\
&= c(m-1, 0)(2\cos \theta)^m +\sum_{r=0}^{(m-4)/2} c(m-1, r + 1)(2\cos \theta)^{m-2 - 2r} -\sum_{r=0}^{(m-2)/2}c(m-2, r)(2\cos \theta)^{m-2-2r}\\
&= (2\cos \theta)^m - c(m-2, \frac{m-2}2) + \sum_{r=0}^{(m-4)/2}c(m, r+1)(2\cos \theta)^{m-2-2r}\\
&= \sum_{r=1}^{(m-2)/2}c(m, r)(2\cos \theta)^{m-2r} + c(m, m/2) +(2\cos \theta)^m\\
&= \sum_{r=0}^{m/2} c(m,r)(2\cos \theta)^{m-2r}\end{align}$

Remarks: The proof for even $m$ is similar. So I omit it.
The proof for odd $m$:
By the inductive hypothesis, we have
$$2\cos (m - 1)\theta = \sum_{r=0}^{(m - 1)/2} c(m - 1,r)(2\cos \theta)^{m - 1 - 2r}$$
and
$$2\cos (m - 2)\theta = \sum_{r=0}^{(m - 3)/2} c(m - 2,r)(2\cos \theta)^{m - 2 - 2r}.$$
Using the identity $\cos m \theta + \cos (m - 2)\theta = 2\cos \theta \cos (m-1)\theta$, we have
\begin{align*}
 2\cos m x &= 2\cos\theta \cdot 2 \cos (m - 1)\theta - 2\cos (m - 2)\theta\\
 &= \sum_{r=0}^{(m - 1)/2} c(m - 1,r)(2\cos \theta)^{m - 2r} - \sum_{r=0}^{(m - 3)/2} c(m - 2,r)(2\cos \theta)^{m - 2 - 2r}\\
 &= c(m - 1, 0)(2\cos \theta)^m + \sum_{r=1}^{(m - 1)/2} c(m - 1,r)(2\cos \theta)^{m - 2r} \\
 &\qquad - \sum_{r=0}^{(m - 3)/2} c(m - 2,r)(2\cos \theta)^{m - 2 - 2r}\\
 &= (2\cos \theta)^m + \sum_{r=0}^{(m - 1)/2 - 1} c(m - 1, 1 + r)(2\cos \theta)^{m - 2 - 2r} \\
 &\qquad - \sum_{r=0}^{(m - 3)/2} c(m - 2,r)(2\cos \theta)^{m - 2 - 2r}\\
 &= (2\cos \theta)^m + \sum_{r=0}^{(m - 3)/2} [c(m - 1, 1 + r) - c(m - 2, r)](2\cos \theta)^{m - 2 - 2r}\\
 &= (2\cos \theta)^m + \sum_{r=0}^{(m - 3)/2} c(m, 1 + r)(2\cos \theta)^{m - 2 - 2r}\\
 &= (2\cos \theta)^m + \sum_{r=1}^{(m - 3)/2 + 1} c(m, r)(2\cos \theta)^{m - 2r}\\
 &= (2\cos \theta)^m - c(m, 0)(2\cos \theta)^m + \sum_{r=0}^{(m - 1)/2} c(m, r)(2\cos \theta)^{m - 2r}\\
 &= \sum_{r=0}^{(m - 1)/2} c(m, r)(2\cos \theta)^{m - 2r}
\end{align*}
where we have used $c(m - 1, 0) = c(m, 0) = 1$.
The desired result follows.
