Linear Recurrence In Faster Time I am trying to solve this linear recurrence using matrix exponentiation:-
$$f(n) = 2f(n-1) - f(n-2) + c,$$
where $c$ is a constant.
What I have come up with is this -
Let the matrix $M$ be
$$
\begin{bmatrix}
2 & -1 & 1\\ 1 & 0 & 0\\ 0 & 0 & 1
\end{bmatrix}.
$$
Now, we have 
$$M^{n-4}\cdot\begin{bmatrix}f(4)\\f(3)\\c\end{bmatrix} = \begin{bmatrix}f(n)\\f(n-1)\\c\end{bmatrix}. $$
I have used this to solve the recurrence.
However, I was wondering: since there is a constant in the recurrence, is there any way to solve it using a $2\times 2$ matrix $M$ instead of the $3\times 3$ one which I have used?
Any suggestions would be valued, thank you.
 A: Try to make a variable change of type:
$$ g(n) = f(n) + n^{\alpha} a $$. Try $\alpha$ from $0, 1, 2 ..$. 
Here is the case where $\alpha = 0, 1$ does not work. But $\alpha = 2, a = -\frac{c}{2}$ works!
Then $g(n)$ satisfies:
$$
g(n) = 2g(n-1) - g(n-2)
$$ 
A: $f(n)-2f(n-1)+f(n-2)=(f(n)-f(n-1))-(f(n-1)-f(n-2))=\nabla^2[f](n)$ is a backward second difference. We have a second order nonhomogeneous difference equation $\nabla^2[f](n)=c$.
Note that if we had some sequence $g(n)=n^2$ we observe:
$$g(n)-g(n-1)=n^2-(n-1)^2=2n-1$$ so $$(g(n)-g(n-1))-(g(n-1)-g(n-2))=(2n-1)-(2(n-1)-1)=2$$ which means $n^2$ is a particular solution to $\nabla^2[f](n)=2$.
By linearity, our inhomogeneous part $c$ gives us a particular solution $f_p(n)=\frac12cn^2$. If we look at $f$ in our affine solution space to $\nabla^2[f](n)$ and subtract $f_p$ we get solutions to the homogeneous problem $\nabla^2[f](n)=0$.
This is all in analogy with the standard theory of linear differential equations.

Note that you can also compute terms of this sequence even faster in isolation using the fact that the kernel of $\nabla^2[f]$ is spanned by $\{1,n\}$ hence you know our solution is of the form $f(n)=\frac{c}2 n^2+an+b$; note this gives $$b=f(0)\\a=f(1)-f(0)-\frac{c}2$$... so if you're given initial conditions $f(0),f(1)$ you can compute the $n$-th term using $f(n)=\frac{c}2n^2+an+b$ with $a,b$ computed as above.
