<s>[INST] Computing a closed formula for a recurrent sequence using eigen -values and -vectors How would you use eigenvalues and eigenvectors to compute a closed formula for the following sequence: $$\{x_0=1, x_1=2, x_n=5x_{n-1} + 14x_{n-2}, n \ge 0 \}$$
I have come up with the following formula: $$ \begin{bmatrix}
0 & 1 \\
14 & 5
\end{bmatrix}
*
\begin{bmatrix}
x_{n-2}\\
x_{n-1}\\
\end{bmatrix}
=
\begin{bmatrix}
x_{n}\\
x_{n+1}\\
\end{bmatrix}$$
So to compute x_n I want to take the n'th power of the matrix A: $A=\begin{bmatrix}
0 & 1 \\
14 & 5
\end{bmatrix}$ and multiply it with the "starting state" vector: $\begin{bmatrix}
1\\
2\\
\end{bmatrix}$.
Therefore I used the theory that $A^n=PD^nP^{-1}$, where $D$ is the diagonal matrix holding eigenvalues for $A$ along its diagonal and $P$ is the matrix holding the corresponding eigenvectors for the eigenvalues in $A$.
I computed the eigenvalues and vectors for $A$ and got that $\begin{bmatrix}
1\\
\frac{-1}{7}
\end{bmatrix}$ is an eigenvector with eigenvalue $\lambda_1 = 7$. And $\begin{bmatrix}
1\\
\frac{1}{2}
\end{bmatrix}$ is an eigenvector with eigenvalue $\lambda_2 = -2$.
So filling out the formula $A^n=PD^nP^{-1}$:
$$
\begin{bmatrix}
0 & 1 \\
14 & 5
\end{bmatrix}^n=\begin{bmatrix}
1 & 1 \\
\frac{-1}{7} & \frac{1}{2}
\end{bmatrix} * \begin{bmatrix}
7^n & 0 \\
0 & -2^n
\end{bmatrix} * \frac{9}{14} \begin{bmatrix}
\frac{1}{2} & -1 \\
\frac{1}{7} & 1
\end{bmatrix}
$$
Which when multiplied gives: $$
\begin{bmatrix}
0 & 1 \\
14 & 5
\end{bmatrix}^n=\frac{9}{14} * \begin{bmatrix}
7^n*\frac{1}{2}+(-2)^n
*\frac{1}{7} & -9^n \\
-\frac{1}{7}*7^n*\frac{1}{2}+\frac{1}{2}*\frac{1}{7}*-2^n & \frac{1}{7}*-7^n+\frac{1}{2}*-2^n
\end{bmatrix}
$$
The problem is now that when I multiply the result onto the "starting vector" $\begin{bmatrix}
1\\
2\\
\end{bmatrix}$ I get the this formula for $x_n$: $\frac{9}{14}((7^n+\frac{1}{2}+(-2)^n*\frac{1}{7})+(2*(-9)^n))$
Which doesn't give the correct answer when checking for $n=2$ for example: $\frac{9}{14}((7^2+\frac{1}{2}+(-2)^2*\frac{1}{7})+(2*(-9)^2)) = \frac{26721}{196}$.
For $n=2$ I would expect $x_2=5*2 + 14*1=24$.
Can anyone help me figure out where I am doing it wrong?
 [/INST] Do you really need to use eigenvalues/eigenvectors? This is a linear difference equation for which you can easily identify a basis for the solution space. Looking at the roots of the characteristic polynomial $p(\lambda) = \lambda^2 -5 \lambda -14$, any solution is of the form
$$
x_n = c_1 \cdot (-2)^n + c_2 \cdot 7^n
$$
Now you can just compute $c_1, c_2$ from the initial condition $x_0 = 1$ and $x_1=2$.
</s>