How would I compute $a_n$ in $O(\log n)$ given they have a linear recurrence, such as $a_i=3b_{i-1}+2b_{i-2}+6^i, b_i=14a_{i-1}-b_{i-2}-6^i$ with matrices?
I know how to deal with recurrences like $a_i=b_0a_{i-1}+b_1a_{i-2}+\cdots+b_ka_{i-k-1}$ in $O(k^3 \log n)$
Dealing with constants isn’t hard; for $a_i=3a_{i-1}+2a_{i-2}+1$, I can let $b_i=a_i-\frac 14$ to clear the constant term.
I don't know how to deal with an exponential term and multiple sequences.
Hint:
Look at new sequences $A_i = \frac{a_i}{6^i}$ and $B_i = \frac{b_i}{6^i}$. By dividing your original recurrences by $6^i$, we see that these must satisfy the following recurrences:
$$ A_i = \frac{3 B_{i-1}}{6} + \frac{2 B_{i-2}}{6^2} + 1 \quad \quad B_i = \frac{14 A_{i-1}}{6} - \frac{B_{i-2}}{6^2} -1 $$
From here, standard matrix theoretic techniques will work. After finding the $A_i$ and $B_i$, you can recover $a_i = 6^i A_i$ and $b_i = 6^i B_i$.
As an aside, though -- $a_n$ will not be $O(\log(n))$. In fact, $a_i$ seems to grow extremely quickly (proof by sage):
Edit:
I realize I misunderstood your question - you don't want to show that $a_n \in O(\log(n))$. Instead you want to compute $a_n$ in $O(\log(n))$ time by using the repeated squaring trick.
While you could still use the trick of $A_i$ and $B_i$ to turn our recurrence into something more manageable, we can also do the whole problem in one step:
We want to work with $a_i$ and $b_i$, and to compute them we need to keep track of $a_{i-1}$, $b_{i-1}$, and $b_{i-2}$.
So we package this data into a vector, and want to find a matrix $M$ so that the following holds:
$$ \begin{pmatrix} a_i\\ b_i\\ a_{i-1}\\ b_{i-1}\\ 6^i \end{pmatrix} = M \begin{pmatrix} a_{i-1}\\ b_{i-1}\\ a_{i-2}\\ b_{i-2}\\ 6^{i-1} \end{pmatrix} $$
Notice we keep a $6^i$ in our vector because we need it in order to compute the future $a_i$.
If we find such a matrix $M$, then notice $a_n$ is just the first entry of $M^n v$ for some vector of initial conditions $v$ (why?). We can then use the repeated squaring trick to compute $M^n$ (and thus $a_n$) efficiently.
Do you see how to construct such a matrix $M$? Hint: The $a_i$ and $b_i$ are given as linear combinations of earlier $a$s and $b$s, as well as a $6^i$, all of which we're keeping track of in the vector!
I hope this helps ^_^