Help solving this recurrence relation

Question

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.

Answer 1

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}})$$

Answer 2

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