Recurrence relation involving matrices

Question

I've done part $(i)-(iv) [(i) (C), (ii) (D),(iii) (F), (iv) (E)].$

I would appreciate if someone could show me how to solve this part (v).

Answer 1

The recurrence relation can be solved by $$\mathbf{X}_n = \mathbf{M}^n \mathbf{X}_0$$ So, you have to compute the diagonlization of $\mathbf{M}$ $$\mathbf{M} = \mathbf{P}^{-1} \left( \begin{matrix} 1 & 0 \\ 0 & 3\end{matrix} \right)\mathbf{P} $$ where $$\mathbf{P} = \left( \begin{matrix} 1 & 1 \\ -1 & 1\end{matrix} \right) , \mathbf{P}^{-1} = \frac 12 \left( \begin{matrix} 1 & -1 \\ 1 & 1\end{matrix} \right)$$ So that $$\mathbf{X}_n = \mathbf{P}^{-1} \left( \begin{matrix} 1 & 0 \\ 0 & 3^n\end{matrix} \right)\mathbf{P} \left( \begin{matrix} 2 \\ 0 \end{matrix} \right)$$

Answer 2

If $M = P D P^{-1}$, then $ X_n = M^n X_0 = P D^n P^{-1} X_0 $.

Answer 3

Find $P$ so that $P^{-1}MP$ is a diagonal matrix $D$. Then $D^n=P^{-1}M^nP$, so

$$X_n=M^nX_0=PD^nP^{-1}X_0\;,$$

which is easy to calculate.

Answer 4

By multiplying the matrices, we get the following recurrence relation: $$\tag1x_{n+1}=2x_n+y_n$$ $$\tag2y_{n+1}=x_n+2y_n$$ Multiplying $(2)$ by $2$ and subtracting $(1)$, $$2y_{n+1}-x_{n+1}=3y_n$$ Replacing $n$ by $n-1$ (which means we are now assuming $n\gt1$, $$2y_n-x_n=3y_{n-1}$$ $$\tag3x_n=2y_n-3y_{n-1}$$ Substituting $(3)$ in $(2)$, $$y_{n+1}=2y_n-3y_{n-1}+2y_n$$ $$\tag4y_{n+1}=4y_n-3y_{n-1}$$

For $n=1$, $$x_1=2x_0+y_0=4$$ $$y_1=x_0+2y_0=2$$

Thus, $(4)$ is a linear homogeneous recurrence relation, and knowing $y_0=2,y_1=2$, it can be easily solved using the characteristic equation.

Similarly, multiplying $(1)$ by $2$ and subtracting $(2)$ will lead to a linear homogeneous recurrence relation for $x_n$.