<s>[INST] 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?
 [/INST] 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}
</s>