# Find $3a+b+3c+4d$ if $\left(\begin{smallmatrix}-4&-15\\2&7\end{smallmatrix}\right)^{100}=\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)$.

Let $\begin{pmatrix} -4 & -15 \\ 2 & 7 \end{pmatrix}^{100} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$.
Find $3a + b + 3c + 4d$.
I've gotten this answer for the matrix to the 100th power(via calculator) , but it's HUGE. I need a simpler method to find it. Can I get some tips please?

Let $A=\begin{pmatrix}-4&-15\\2&7\end{pmatrix}$. By Cayley-Hamilton theorem, we get $A^2-3A+2I=O$. Thus $A^n$ can be represented as the sum of $A$ and $I$; that is, there are $a_n$ and $b_n$ such that $A^n = a_n A + b_n I$. Then \begin{align} A^{n+1}&=a_n A^2+b_n A\\ &=a_n(3A-2I)+b_n A\\ &=(3a_n +b_n)A-2a_n I. \end{align} We get $$\begin{cases} a_{n+1}=3a_n+b_n\\ b_{n+1} = -2a_n. \end{cases}$$ Now we can construct the linear recurrence relation of second order for $a_n$: $$a_{n+2}=3a_{n+1}-2a_n.$$ Thus, $a_n = c_1 2^n + c_2$ for some $c_1,c_2$. Since $a_1=1$ and $a_2=3$, $a_n = 2^n -1$, and $b_n = -2^n+2$. Also, \begin{align} A^{100}&= a_{100}A+b_{100}I\\ &=\begin{pmatrix} -4a_{100}+b_{100} & -15a_{100}\\ 2a_{100} & 7a_{100} + b_{100} \end{pmatrix}. \end{align} Therefore, \begin{align} 3a+b+3c+4d&=3(-4a_{100}+b_{100})-15a_{100}+3\cdot 2a_{100} +4(7a_{100}+b_{100})\\ &=7a_{100}+7b_{100}\\ &=7(2^{100}-1)+7(-2^{100}+2)\\ &=7. \end{align}
Hint: If $A$ is that matrix, then $A^2=3A-2I$ and so $A^n = (2^n-1)A-(2^n-2)I$.
Then you can compute $3a + b + 3c + 4d$ directly for $A^n$.
Or you can set $$\varphi\begin{pmatrix} a & b \\ c & d \end{pmatrix}=3a + b + 3c + 4d$$ and notice that $\varphi(A)=\varphi(I)=7$ and so $\varphi(A^n) = (2^n-1)\varphi(A)-(2^n-2)\varphi(I)=7$.