<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] You plug your initial conditions in, so you get
$$D_1=a = C_1*(\frac{a}{2} + \frac{\sqrt{a^2-4}}{2}) + C_2*(\frac{a}{2} - \frac{\sqrt{a^2-4}}{2})\\D_2=a^2-1 = C_1*(\frac{a}{2} + \frac{\sqrt{a^2-4}}{2})^2 + C_2*(\frac{a}{2} - \frac{\sqrt{a^2-4}}{2})^2$$
These are two equations in the two unknowns $C_1,C_2$.  The usual substitution technique will work, though it will be messy.  You can use the recurrence to evaluate $D_0=1=C_1+C_2$.  Using that with the first gives $$a=(C_1+C_2)\frac a2+(C_1-C_2)\frac{\sqrt{a^2-4}}{2}\\C_1-C_2=\frac a{\sqrt{a^2-4}}\\C_1=\frac 12(1+\frac a{\sqrt{a^2-4}})\\C_2=\frac 12(1-\frac a{\sqrt{a^2-4}})$$
</s>