In the course of answering a question on Stack Overflow, I stumbled on a technique for evaluating certain non-homogeneous linear recurrence relations that's related to, but a bit different than, a technique I'd seen before.
As a motivation, suppose you want to compute $F_n$, then $n$th Fibonacci number. Using the fact that
$$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix} = \begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix}, $$ we can compute $F_{k+1}$ by computing $$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^k \begin{bmatrix} F_{1} \\ F_0 \end{bmatrix} = \begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix} $$
and looking at the first component of the resulting vector. That middle matrix can be raised to the $k$th power in time $O(\log k)$ using repeated squaring, so this gives a fast algorithm for computing Fibonacci numbers.
The observation I had came up for solving a recurrence that's somewhat similar to this one:
$$A_0 = 1$$ $$A_{n+1} = 2A_n + F_n$$
This recurrence relation isn't homogeneous, but we can still set up a matrix equation like this one:
$$\begin{bmatrix} 2 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} A_{k+1} \\ F_{k+1} \\ F_{k} \end{bmatrix} = \begin{bmatrix} 2A_{k+1} + F_{k+1} \\ F_{k+1} + F_{k} \\ F_{k + 1} \end{bmatrix} = \begin{bmatrix} A_{k+2} \\ F_{k+2} \\ F_{k + 1} \end{bmatrix}. $$
This gives us the same sort of "shifting" as before and works by essentially solving two parallel, interrelated recurrences at the same time. As a result, we can compute $A_{k+1}$ efficiently by computing
$$\begin{bmatrix} 2 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}^k \begin{bmatrix} A_{1} \\ F_{1} \\ F_{0} \end{bmatrix} = \begin{bmatrix} A_{k+1} \\ F_{k+1} \\ F_{k} \end{bmatrix} $$
and looking at the first component. This can again be computed in time $O(\log n)$.
More generally, it seems like any linear recurrence relation of the form
$$A_{n+1} = \sum_{i = 0}^k{c_i A_{n-i}} + L_n$$
where $L_n$ is some other term that can also be expressed as a linear recurrence relation can be evaluated at an arbitrary point in $O(\log n)$ matrix multiplications.
I seriously doubt that I'm the first person to come up with this, but I haven't come across this technique before anywhere. Is this a known technique? Does it have a name?
Let $\ Sf_n = f_{n +1}\,$ be the $n$-shift operator.
In operator form your nonhomogeneous recurrence is $\ (S-2) A_n = F_n$
We can make it homogeneous by multiplying it by $\,S^2-S-1,\,$ the annihilator of $\,F_n,\,$yielding
$$\begin{align} 0 \,&=\, (S^2\!-S-1)(S-2) A_n\\ &=\, (S^3-3S^2+S+2) A_n\\ &=\, P(S) A_n\end{align}$$
This is essentially what you have done by constructing that matrix. Indeed, computing its characteristic polynomial yields $\, -P(S).$