Eigenvalues for solving linear recurrence equations After discovering the way to come up with formulas for such sequences as the Fibonacci sequence using matrices it occurred to me this may not necessarily always possible. What might skew one’s endeavor is a case in which one of the eigenvalues is 1, 0 or -1 for then applying the linear transformation repeatedly does not do much to put it mildly. I was wondering if there is a way around this. Is it possible to solve recurrence relations using compositions of transformations even if the above conditions apply?
 A: Consider the recurrence relation $x_{n+1}=x_{n-1}$ for $n\geq1$, $x_0=a, x_1=b$.  For $n\geq1$ we have:
$$
\left( \begin{array}{cc}0&1\\1&0
\end{array}\right)
\left( \begin{array}{cc}x_n\\x_{n-1}
\end{array}\right)=
\left( \begin{array}{cc}x_{n+1}\\x_{n}
\end{array}\right)
$$
The above matrix has eigenvalues $1,-1$ and the general solution to the recurrence relation is as usual $$x_n=u1^n+v(-1)^n=u+v(-1)^n.$$
Solving for $u,v$: $$u+v=a, \qquad u-v=b,$$
so $$u=\frac{a+b}2, v=\frac{a-b}2.$$
As you can see the fact that the eigenvalues were $1,-1$ did not change anything.
Next consider the recurrence relation $y_{n+1}=y_{n}$, $n\geq1$ with $y_0=a,y_1=b$.
Then for $n\geq1$ we have:
$$
\left( \begin{array}{cc}1&0\\1&0
\end{array}\right)
\left( \begin{array}{cc}y_n\\y_{n-1}
\end{array}\right)=
\left( \begin{array}{cc}y_{n+1}\\y_{n}
\end{array}\right)
$$
Now we have eigenvalues $0,1$ and the general solution has the form: $$u1^n+v0^n=u+v0^n.$$
Solving for $u,v$ (remembering $0^0=1$) we get: $$u+v=a,\qquad u=b,$$
so
$$
u=b,\qquad v=a-b.
$$
Again nothing about the calculation was different.
