Solving recurrence relation $a_n = a_{n-1} - a_{n-2}$ I am given a sequence of determinants of matrices $M_n$, where the matrix elements $(M_n)_{ij}$ of $M_n$ are $0$ whenever $|i-j|>1$ and $1$ whenever $|i-j| ≤ 1$. Writing out the first five matrices, it becomes apparent that $\det(M_n) = \det(M_{n-1}) - \det(M_{n-2})$. I want a formula for the mapping $n ↦ \det(M_n)$, which I believe to be
$$a_n = \begin{cases} 0, & n ≡ 2 \mod 6 \,\, \vee n ≡ 5 \mod 6, \\ 1, & n ≡ 0 \mod 6 \,\, \vee n ≡ 1 \mod 6, \\ -1, & n ≡ 3 \mod 6 \,\, \vee n ≡ 4 \mod 6. \end{cases}
$$
This can quite readily be seen from the first 15 or so terms. Of course, this doesn't constitute a proof, which most likely will have to be performed by induction. I just fear that I am to embark on a six-piece proof by exhaustion, which I would like to avoid if there is a (much) quicker way to do it!
 A: You are asking for the recurrence, I think, $a_0=a_1=1$, $a_n=a_{n-1}-a_{n-2}$. Let $T:\Bbb R^3\to\Bbb R^3$ be the linear operator with the following matrix (on the standard basis): $$\begin{pmatrix}1&-1&0\\1&0&0\\0&1&0\end{pmatrix}$$And let, $n\ge 0$, the vectors $v_n$ be given by: $$v_n=\begin{pmatrix}a_{n+2}\\a_{n+1}\\a_n\end{pmatrix}$$Then $Tv_n=v_{n+1}$ for all $n$, or equivalently, $v_n=T^nv_0$ for all $n$. If we can find a nice expression for $T^n$ then we are basically done (this is a standard trick!). The diagonal matrix for this operator is: $$\begin{pmatrix}0&0&0\\0&\zeta&0\\0&0&\overline{\zeta}\end{pmatrix}$$Where $\zeta=\frac{1}{2}(1-i\sqrt{3})=e^{-i\pi/3}$, so the diagonal matrix for $T^n$ is just the same with $\zeta^n,\overline{\zeta^n}$ instead, that is, $e^{\pm in\pi/3}$. The computation of the eigenvalues and the change-of-basis matrices is all doable by hand, in not too much time (less than $20$ minutes, much less if you're fast!), but I have skipped these steps as they are tedious.
We are interested only in $a_n$, the bottom row of $T^nv_0$. The computation looks as follows: $$\begin{align}v_n&=\begin{pmatrix}0&\zeta-1&\overline{\zeta}-1\\0&\zeta&\overline{\zeta}\\1&1&1\end{pmatrix}\begin{pmatrix}0&0&0\\0&\zeta^n&0\\0&0&\overline{\zeta^n}\end{pmatrix}\begin{pmatrix}1&-1&1\\-\frac{1}{2}+\frac{i}{6}\sqrt{3}&\frac{1}{2}+\frac{i}{6}\sqrt{3}&0\\-\frac{1}{2}-\frac{i}{6}\sqrt{3}&\frac{1}{2}-\frac{i}{6}\sqrt{3}&0\end{pmatrix}\begin{pmatrix}0\\1\\1\end{pmatrix}\\&=\begin{pmatrix}0&\zeta-1&\overline{\zeta}-1\\0&\zeta&\overline{\zeta}\\1&1&1\end{pmatrix}\begin{pmatrix}0&0&0\\0&\zeta^n&0\\0&0&\overline{\zeta^n}\end{pmatrix}\begin{pmatrix}0\\\frac{1}{2}+\frac{i}{6}\sqrt{3}\\\frac{1}{2}-\frac{i}{6}\sqrt{3}\end{pmatrix}\\&=\begin{pmatrix}0&\zeta-1&\overline{\zeta}-1\\0&\zeta&\overline{\zeta}\\1&1&1\end{pmatrix}\begin{pmatrix}0\\\zeta^n\left(\frac{1}{2}+\frac{i}{6}\sqrt{3}\right)\\\zeta^{-n}\left(\frac{1}{2}-\frac{i}{6}\sqrt{3}\right)\end{pmatrix}\end{align}$$And the bottom row is: $$a_n=\frac{1}{2}(\zeta^n+\zeta^{-n})+\frac{i}{\sqrt{3}}\frac{1}{2}(\zeta^n-\zeta^{-n})=\cos\frac{\pi n}{3}+\frac{1}{\sqrt{3}}\sin\frac{\pi n}{3}$$Since $\cos,\sin$ are periodic functions, you can read off the periodicity relations from here (modulo $6$, say).
Let's check our work: standard trigonometric identities give $a_0=1=a_1$ using the above formula. In general: $$\begin{align}a_{n+1}-a_n&=\left[\color{red}{\cos\frac{\pi n}{3}\cos\frac{\pi}{3}}-\sin\frac{\pi n}{3}\sin\frac{\pi}{3}\right]+\frac{1}{\sqrt{3}}\left[\sin\frac{\pi n}{3}\cos\frac{\pi}{3}+\cos\frac{\pi n}{3}\sin\frac{\pi}{3}\right]\\&-\left[\color{red}{\cos\frac{\pi n}{3}}+\frac{1}{\sqrt{3}}\sin\frac{\pi n}{3}\right]\\&=\color{red}{-\frac{1}{2}\cos\frac{\pi n}{3}}-\frac{\sqrt{3}}{2}\sin\frac{\pi n}{3}+\frac{1}{2\sqrt{3}}\sin\frac{\pi n}{3}+\frac{1}{2}\cos\frac{\pi n}{3}-\frac{1}{\sqrt{3}}\sin\frac{\pi n}{3}\\&=-\frac{2}{\sqrt{3}}\sin\frac{\pi n}{3}\end{align}$$And: $$\begin{align}a_{n+2}&=-\frac{1}{2}\cos\frac{\pi n}{3}-\frac{\sqrt{3}}{2}\sin\frac{\pi n}{3}+\frac{1}{\sqrt{3}}\left[-\frac{1}{2}\sin\frac{\pi n}{3}+\frac{\sqrt{3}}{2}\cos\frac{\pi n}{3}\right]\\&=0-\frac{4\sqrt{3}}{6}\sin\frac{\pi n}{3}\\&=-\frac{2}{\sqrt{3}}\sin\frac{\pi n}{3}\\&=a_{n+1}-a_n\end{align}$$As desired!
A: For $$A_n=A_{n-1}-A_{n-2}.....(1)$$
Take $A_n=t^n$, then we get $t^2-t+1=0 \implies t=-w,-w^2$ where $w=e^{2in\pi/3}, w^2=e^{-2in\pi/3}$ are cube-root of unity. So the solution of  (1)
$$A_n=p(-w)^n+q(-w^2)^n=(-1)^n [pe^{iu_n}+qe^{-iu_n}]$$ $$=(-1)^n[(p+q)\cos u_n+ i(p-q) \sin u_n], u_n=2n\pi/3.$$
$$A_n=(-1)^n[r\cos u_n+is \sin u_n]$$
The arbitrary parameters $r$ and $s$ may be fixed by various given conditions,
