<s>[INST] Help solving this recurrence relation I wanted to resolve the determinant of the next (nxn) matrix via recurrence relations:
$$
\begin{vmatrix}
a & 1 & 0 & 0 & 0 & 0 &.... 0 & 0 & 0 & 0 & 0\\ 
1 & a & 1 & 0 & 0 & 0 &.... 0 & 0 & 0 & 0 & 0 \\ 
0 & 1 & a & 1 & 0 & 0 &.... 0 & 0 & 0 & 0 & 0\\ 
0 & 0 & 1 & a & 1 & 0 &.... 0 & 0 & 0 & 0 & 0\\ 
.. & .. & .. & .. & .. & .. &..... & .. & .. & ..\\ 
0 & 0 & 0 & 0 & 0 & 0 & .... 0 & 1 & a & 1 & 0\\ 
0 & 0 & 0 & 0 & 0 & 0 & .... 0 & 0 & 1 & a & 1\\ 
0 & 0 & 0 & 0 & 0 & 0 & .... 0 & 0 & 0 & 1 & a\\ 
\notag
\end{vmatrix}
$$
After analyzing the matrix I found the recurrence relation:
$$
D_{n}-a*D_{n-1}  +D_{n-2}=0
$$
So the polynomial that describes this recurrence is:
$$
P(\lambda) = \lambda^2 - a * \lambda + 1
$$
The roots will be:
$$
\lambda_1 = \frac{a}{2} + \frac{\sqrt{a^2-4}}{2}\\
\lambda_2 = \frac{a}{2} - \frac{\sqrt{a^2-4}}{2}
$$
To resolve the recurrence I need 2 constants (C1 & C2) that satisfy:
$$
D_n = C_1*(\frac{a}{2} + \frac{\sqrt{a^2-4}}{2})^n + C_2*(\frac{a}{2} - \frac{\sqrt{a^2-4}}{2})^n 
$$
With the initial conditions
$$
D_1 = a\\
D_2 = a^2 - 1
$$
The problem is I don't know how to resolve the equation system generated by substituting the initial conditions on the function.
Any type of help is appreciated.
 [/INST] To solve for the constants we just evaluate the expression for $D_n$ at $n=1$ and $n=2$, as well as use the information that $D_1=a$ and $D_2=a^2-1$ to get
$$C_1\left(\frac{a}{2}+\frac{\sqrt{a^2-4}}{2}\right)+C_2\left(\frac{a}{2}-\frac{\sqrt{a^2-4}}{2}\right)=a$$
$$C_1\left(\frac{a}{2}+\frac{\sqrt{a^2-4}}{2}\right)^2+C_2\left(\frac{a}{2}-\frac{\sqrt{a^2-4}}{2}\right)^2=a^2-1$$
Now, since $a$ is just some constant, we can treat this as a linear system and write it as
$$A\vec{c}=\left[\begin{array}{cc}
\left(\frac{a}{2}+\frac{\sqrt{a^2-4}}{2}\right) & \left(\frac{a}{2}-\frac{\sqrt{a^2-4}}{2}\right) \\
\left(\frac{a}{2}+\frac{\sqrt{a^2-4}}{2}\right)^2 & \left(\frac{a}{2}-\frac{\sqrt{a^2-4}}{2}\right)^2
\end{array}\right]
\left[\begin{array}{c}
C_1 \\
C_2
\end{array}\right]=
\left[\begin{array}{c}
a \\
a^2-1
\end{array}\right]$$
Which has solution
$$
\left[\begin{array}{c}
C_1 \\
C_2
\end{array}\right]
=
\frac{\text{adj }A}{\det A}\left[\begin{array}{c}
a \\
a^2-1
\end{array}\right]
$$
Where
$$\det A=\left(\frac{a}{2}+\frac{\sqrt{a^2-4}}{2}\right)\left(\frac{a}{2}-\frac{\sqrt{a^2-4}}{2}\right)^2-\left(\frac{a}{2}-\frac{\sqrt{a^2-4}}{2}\right)\left(\frac{a}{2}+\frac{\sqrt{a^2-4}}{2}\right)^2$$
$$=\frac{2}{a-\sqrt{a^2-4}-2}$$
and
$$\text{adj }A=\left[\begin{array}{cc}
\left(\frac{a}{2}-\frac{\sqrt{a^2-4}}{2}\right)^2 & -\left(\frac{a}{2}-\frac{\sqrt{a^2-4}}{2}\right) \\
-\left(\frac{a}{2}+\frac{\sqrt{a^2-4}}{2}\right)^2 & \left(\frac{a}{2}+\frac{\sqrt{a^2-4}}{2}\right)
\end{array}\right]$$
</s>