If your initial conditions are $a_0$ and $a_1$, $p(x)=c(x)=(a_1-a_0)x+a_0$. Look at it this way. You have $$a_n=a_{n-1}+a_{n-2}\tag{1}$$ for $n\ge 2$. Assume that $a_n=0$ for $n<0$. Then $(1)$ is valid for all integers $n$ except possibly $0$ and $1$. To make it valid for all integers, add a couple of terms using the Iverson bracket to get $$a_n=a_{n-1}+a_{n-2}+(a_1-a_0)[n=1]+a_0[n=0]\;.\tag{2}$$
Note that while $a_0$ is straightforward, you have to be careful for $n>0$, since the earlier initial values are automatically built into the basic recurrence.
Now multiply $(2)$ through by $x^n$ and sum:
$$\begin{align*}
\sum_na_nx^n&=\sum_na_{n-1}x^n+\sum_na_{n-2}x^n+(a_1-a_0)\sum_n[n=1]x^n+a_0\sum_n[n=0]x^n\\
&=x\sum_na_nx^n+x^2\sum_na_nx^n+(a_1-a_0)x+a_0\;.
\end{align*}$$
Thus, if your generating function is $A(x)=\displaystyle\sum_na_nx^n$, you have $$A(x)=xA(x)+x^2A(x)+(a_1-a_0)x+a_0\;,$$ and hence $$A(x)=\frac{(a_1-a_0)x+a_0}{1-x-x^2}\;.$$
This obviously generalizes to higher-order recurrences and other starting points for the initial values. For example, a third-order recurrence with initial values $a_0,a_1,a_2$ would have
$$\begin{align*}
p(x)=c(x)&=a_0+(a_1-a_0)x+\left(a_2-\big(a_0+(a_1-a_0)\big)\right)x^2\\
&=a_0+(a_1-a_0)x+(a_2-a_1)x^2\;.
\end{align*}$$
In general with initial values $a_0,\dots,a_m$ you’ll get Iverson terms
$$a_0[n=0]+(a_1-a_0)[n=1]+(a_2-a_1)[n=2]+\cdots+(a_m-a_{m-1})[n=m]$$
in the recurrence and
$$c(x)=p(x)=a_0+(a_1-a_0)x+\cdots+(a_m-a_{m-1})x^m\;.$$
You have builе a Fibonacci (?) field $Q[x]/(x^2-x-1)$. Every element of this field can be written as binomial, so it has representation in 2x2 matrices:
$$
ax+b\qquad\Leftrightarrow\quad \begin{pmatrix}a+b & a\\ a & b\end{pmatrix} = aF+bI
$$
You can check that $F^2=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}^2=F+I $
You $O(\log n)$ algorithm is a well known the Doubling Method, which is essentially fast multiplication algorithm for matrix $F$.
To generalize, you should just select right first element. So in ordinary fibonacci, you start with (1,0), which is $X_1=1x+0$, next element is $X_2=x X_1$, then $X_3=x^2 X_1$ and so on. If you want to start with (-1, 2), then $Y_1=-1x+2$, $Y_2=x Y_1$, $y_3=x^2 Y_1$ and so on. You can use the same algorithm of fast multiplication to find $Y_n$.
Edit. As an example, I want to show how to build a tribonacci field $Q[x]/(x^3-x^2-x-1)$.
If we have $y=\alpha x^2+\beta x+\gamma$, then $$xy = \alpha x^3+\beta x^2+\gamma x = (\beta+\alpha)x^2 + (\gamma+\alpha)x+\alpha$$
So element $x$ is equivalent to matrix:
$$
T = \begin{pmatrix}1 & 1& 1\\ 1 & 0&0\\0&1&0\end{pmatrix}.
$$
So our field can be represented with $Q[I, T]$
Best Answer
The Fibonacci recurrence relation:
$$F_{n+1} = F_n + F_{n-1}$$
is linear. By that I mean it gives the next term as a linear combination of previous terms. Other recurrences having this feature are:
$$A_{n+1} = 3A_n + A_{n-1}$$ $$B_{n+1} = -4B_n$$ $$C_{n+1} = C_n + C_{n-1} + C_{n-2}$$
so any of those could be represented by matrices. Here they are!
$$ \begin{aligned} M_A &= \begin{bmatrix}3 & 1\\1& 0\end{bmatrix}\\ M_B &= \begin{bmatrix}-4\end{bmatrix} \end{aligned} $$
And the last one is a challenge to the reader.
The Fibonacci matrix
$$\begin{bmatrix}1&1\\0&1\end{bmatrix}$$
maps a vector
$$\begin{bmatrix}F_n\\F_{n-1}\end{bmatrix} \rightarrow \begin{bmatrix}F_{n+1}\\F_n\end{bmatrix}$$
and these work analogously.
But the factorial recurrence relation:
$$n! = n(n-1!)$$
is not a linear combination (with constant coefficients) of previous arguments, so we can't represent it as a matrix. That is, we can't represent it by the same matrix, no matter what $n$ we're trying to compute. When the coefficents are constant, we can, which lets us do exponentiation by squaring, etc.
Matrices are a convenient shorthand for representing linear functions on vectors. (They're not only a shorthand, but often I find it useful to think of them this way).