Simplifying a recurrence relation relating to trig.

Question

How would I simplify this following recurrence relation?:
$$D_{n} = (2\cos\theta)D_{n-1} - D_{n-2}, \quad D_1 = \cos \theta$$
I've tried taking differences, etc but to no avail. I can't get a simple expression for $D_n$.

Answer 1

As I said in the comment, you need to define at least one more $D_k$ to uniquely define this sequence.

The general method for finding an explicit formula for $D_n = AD_{n-1}+BD_{n-2}$ is finding the roots $\lambda_1,\lambda_2$ of the characteristic polynomial $x^2-Ax-B$. (Basically using the ansatz $D_n = r^n$ and combining the linearly independent solutions. It is easy to show that this will produce a solution and that the solution is unique.)

Then the terms are given by

$$ D_n = u\lambda_1^n + v\lambda_2^n \quad \text{ if } \lambda_1 \neq \lambda_2$$

or

$$ D_n = u\lambda^n + vn\lambda^n \quad \text{ if } \lambda_1 = \lambda_2 =: \lambda$$

To find the constants $u,v$ just plug in your two anchors and solve the linear system of equations for $u$ and $v$.

In your general case the general case you get $\lambda_{1,2} = \cos(\theta) \pm i \sin(\theta) = e^{\pm i\theta}$

So $$\boxed{D_{n+1} = \frac{1}{2} (e^{in\theta)} + e^{-in\theta}) = \cos(n\theta)}$$

---

A way that is perhaps a little bit easier to memorize is writing your system in matrix form:

$$ \underbrace{\begin{bmatrix} D_n \\ D_{n-1}\end{bmatrix}}_{=:v_n} = \underbrace{\begin{bmatrix} A & B \\1 & 0\end{bmatrix}}_{=:M} \begin{bmatrix} D_{n-1} \\ D_{n-2} \end{bmatrix}$$

then you can try to diagonalize the matrix $M$ as $\Lambda = SMS^{-1}$. Then

$v_n = M^{n-1} v_1 = (S \Lambda S^{-1})^{n-1} v_1 = S\Lambda^{n-1}S^{-1}v_1$.

If you just take the first row, of this equation, you'll get the explicit formula for $D_n$.

Answer 2

The general solution to the recurrence $$D_n=2\cos\theta\, D_{n-1}-D_{n-2}$$ is $$D_n=re^{in\theta}+se^{-in\theta}$$ which can be re-written as $$D_n= u\cos n\theta+v\sin n\theta.$$ One nice particular solution is $D_n=\cos n\theta$ which arises from initial conditions $D_0=1$ and $D_1=\cos\theta$. From this one can deduce a recurrence for the Chebyshev polynomials of the first kind.