# Cyclic Recursive Sequences

Let $a_{n+1} = a_n+a_{n-1}$. With the initial conditions of $a_0 = 1$ and $a_0 = 4$, we get the following sequence.

$$1, 4, 3, -1, -4, -3, 1, 4, \ldots$$

Notice that this sequence repeats after 6 terms, so it is of order 6. With $a_0 = 1$ and $a_1 = 1$, we get the following.

$$1, 1, 0, -1, -1, 0, 1, 1, \ldots$$

This sequence is also of order 6. We can conjecture that, regardless of the initial values, sequence $a_n$ will always be of order 6. We will use matrices to help prove this. Let $\vec{A}_n =
\begin{bmatrix}
a_n \\ a_{n-1}
\end{bmatrix}$. Notice that we can transform the following system of equations.

$$\begin{align}
a_{n+1} &= a_n - a_{n-1} \\
a_n &= a_n + 0a_{n-1} \\
\\
\begin{bmatrix}
a_{n+1} \\ a_n
\end{bmatrix}
&= \begin{bmatrix} 1 \\ 1 \end{bmatrix} a_n +
\begin{bmatrix} -1 \\ 0 \end{bmatrix} a_{n-1}
\\
\\
\vec{A}_{n+1} &= \begin{bmatrix} 1 & -1 \\ 1 & 0 \end{bmatrix} \vec{A}_n
\end{align}$$

Notice that $\begin{bmatrix} 1 & -1 \\ 1 & 0 \end{bmatrix}^6 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$, so we have

$$\vec{A}_{n+6} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \vec{A}_n.$$

Therefore, the sequence will always have order 6, regardless of initial conditions.