By the same type of reasoning, the sin (n+1)θ expansion contains only odd powers of (sin θ) and each term has total degree n+1. So, with a different set of constant C(n+1,2k) and S(n+1,2k+1) you have the same pattern. By induction, all cos nθ and sin nθ have this form.
Now to your problem. Since the of cos nθ all have even powers of sin θ, you can replace each factor of (sin θ)^(2k) = (sin² θ)^k with (1 - cos² θ)^k and multiply out the result to get a polynomial strictly in terms of powers of cos θ. And that's one way to prove it.
It's easier if you can use complex numbers, because De Moivre showed that:
cos nθ + i sin nθ = (cos θ + i sin θ)^n
Equate real and imaginary parts of that, and you have the exact forms (with C(n,k) coefficients from the binomial expansion) for the cos nθ and sin nθ formulas above. Since real (cosine) terms can only have even powers of i, then can only have even powers of sin θ too. No induction needed (or, rather, it's already been done by De Moivre!)