Recurrence relations with algorithm Let $x \in \mathbb{R}$ and $n \in \mathbb{N}$. $c_0=1,c_1=\cos x$
for $k=1,2,...,n-1$: 
$c_{k+1}=2c_1c_k-c_{k-1}$
How to prove that $c_k=\cos kx$?
I tried to show this equality with induction:
$k=1:c_1=\cos x$
$k \mapsto k+1: 2\cos(x)c_{k+1}-c_k$ 
Here I don't know how to continue. I want to use the trigonometric addition formulas, but it doesn't work from here.

You need strong induction for this problem, where you assume that the $c_n$ formula is true for all $1\le n\le k$:
$$c_{k+1}=2c_1c_k-c_{k-1}=2\cos x\cos kx-\cos(k-1)x$$
We use a product-to-sum identity to get rid of the cosine product:
$$=\cos(kx-x)+\cos(kx+x)-\cos(k-1)x=\cos(k+1)x+\cos(k-1)x-\cos(k-1)x=\cos(k+1)x$$
This completes the inductive step.
