Derivation of $n^{th}$ sequence term

Equation 1 is a difference equation. Such equations are well studied in mathematics and many well known solution techniques exist. Here we will use the technique of matrices to express and then solve the system equation given by Eq. 1.

To cast Eq. 1 into the form of a matrix system, first define the vector $v(n)$ as

$$v(n) = \left[ \begin{array}{c} x(n+1) \\ x(n) \end{array}\right] \; . \eqno(3)$$

Then Eq. 1 can be expressed matrix form as

$$v(n+1) = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right] v(n) \;, \eqno(4)$$

as can be seen using the rules of matrix multiplication.

Defining the system matrix $A$ for this problem as

$$A = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right] \eqno(5)$$

then Eq. 4 assumes the simpler form

$$v(n+1) = A \; v(n) \; , \eqno(6)$$

where multiplication means matrix multiplication.

This equation is to be solved subject to the initial condition

$$v(0) = \left[ \begin{array}{c} 3 \\ 1 \end{array}\right] \; . \eqno(7)$$

It is easy to verify by induction that the solution to Eq. 6 for any $A$ is given by

$$v(n) = A^n v(0) \; , \eqno(8)$$

where $A^n$ denotes the matrix $A$ raised to the $n^{th}$ power.

If the matrix $A$ is diagonizable via the similarity transform $S$ matrix, then $A$ can be expressed as

$$A = S \left[ \begin{array}{cc} \lambda_1 & 0 \\ 0 & \lambda_2 \end{array}\right] S^{-1} \; . \eqno(9)$$

Not every matrix $A$ is expressible as given above, but for this analysis the existence of the representation given by Eq. 9 is assumed.

The $n^{th}$ power of such a diagonizable matrix is then easily expressed as

$$A^n = S \left[ \begin{array}{cc} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{array}\right] S^{-1} \; , \eqno(10)$$

which is also easily obtained by induction on $n$.

We have actually solved a general $2 \times 2$ system, assuming diagonizability. An $n \times n$ is solved similarly.

From Eq. 8 the general solution of the system is

$$v(n) = S \left[ \begin{array}{cc} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{array}\right] S^{-1} \; v(0) \; . \eqno(11)$$

This solution is for any $A$ that is diagonizable with arbitrary initial condition vector $v(0)$. It is noted that Eq. 11 holds for a general $n \times n$ system.