1

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$.

Twenty-six colours
  • 1,881
  • 1
    You need to define at least two anchors for this recurrence, otherwise it is not unique. other than that, $\cos \theta$ is just a constant. – flawr May 13 '17 at 09:25
  • @flawr what do you mean by anchors? As in base cases? I think $D_0 = 1$ would be a base case (This wasn't given, but I'm assuming from the question, as this related to a determinant of some $n \times n$ matrix.) – Twenty-six colours May 13 '17 at 09:28
  • You already know how to solve recurrence relations don't you? Moreover, I guess you'll need to do a case study on $\theta$ – Oussama Boussif May 13 '17 at 09:29
  • @Oussama Boussif I've never had a class explicitly on solving/analysing recurrence relations. This just came up in an unrelated area, and the only methods that I can think of is manipulating or substituting akin to recurrences in $IBP$. – Twenty-six colours May 13 '17 at 09:32
  • But in linear algebra you learn to do that using characteristic polynomials for relations of any order (as long as the coefficients are constant). So, I suggest you look that up to understand the answers given and I am sure you have already done this ^^ – Oussama Boussif May 13 '17 at 09:34

2 Answers2

4

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$.

flawr
  • 16,533
  • 5
  • 41
  • 66
  • Appreciated. Would it be possible using Mathematical Induction? Also, what would be a name of this method so that I can search it up online? – Twenty-six colours May 13 '17 at 09:33
  • 1
    Sure. It is just the general way for solving homogeneous linear recurrence relation with constant coefficients. – flawr May 13 '17 at 09:34
  • Would you happen to know if this equals a nice answer like $\cos n \theta$? I'm getting answers that have square-roots, which I think might be because of my two anchors. – Twenty-six colours May 13 '17 at 09:41
  • What formula did you get for $D_n$? – flawr May 13 '17 at 09:43
  • $D_n = u \left(\cos \theta + \sqrt{1+\cos ^2 \theta}\right)^{n} + v \left( \cos \theta - \sqrt{1+ \cos ^2 \theta } \right)^{n}$ where $\cos \theta (u+v) + (u-v) \sqrt{1 + \cos ^2 \theta} = \cos \theta$ and $u+v = 1$. So $D_n = \frac{1}{2} \left(\cos \theta + \sqrt{1+\cos ^2 \theta}\right)^{n} + \frac{1}{2} \left( \cos \theta - \sqrt{1+ \cos ^2 \theta } \right)^{n}$ which is greater than $1$ for $n=8, \theta = 83^{\circ}$. – Twenty-six colours May 13 '17 at 09:45
  • Your roots seem to be incorrect, you should get complex roots in this case. – flawr May 13 '17 at 11:01
0

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.

Angina Seng
  • 158,341