Matrix exponentiation for given recurrence relation How to find the $n$-th term in a sequence with following recurrence relation for a given $n$?
$$F(n)=2b F(n-1)-F(n-2), \ F(0)=a,\ F(1)=b,$$
where $a$ and $b$ are constants.
The value of $n$ is quite large $(1 \leq n\leq 10^{12})$ and so matrix exponentiation is required.
However I am facing difficulties deducing its matrix from the relation which would give the required value.
Could anyone help me with this question and show how to convert as well so I can tackle these kind of problems myself afterward?
 A: $$\begin{bmatrix} F_{n+1}\\F_n\end{bmatrix} = \begin{bmatrix} 2b&-1\\1\end{bmatrix}\begin{bmatrix} F_n\\F_{n-1}\end{bmatrix}$$
$$A = PDP^{-1}\\
A^n = PD^nP^{-1}$$
$$\lambda^2 - 2b +1 = 0\\
\lambda = b\pm\sqrt {b^2 - 1}$$
$$A^n = \frac{1}{\lambda_1 - \lambda_2}\begin{bmatrix} 1&1\\\lambda_2&\lambda_1\end{bmatrix}\begin{bmatrix}\lambda_1^n\\&\lambda_2^n\end{bmatrix}\begin{bmatrix} \lambda_1&-1\\-\lambda_2&1\end{bmatrix}$$
$$A^n = \frac{1}{\lambda_1 - \lambda_2} \begin{bmatrix}\lambda_1^{n+1}-\lambda_2^{n+1}&-(\lambda_1^n-\lambda_2)\\(\lambda_1\lambda_2)(\lambda_1^{n}-\lambda_2^n)&-(\lambda_1\lambda_2)(\lambda_1^{n-1}-\lambda_2^{n-1})\end{bmatrix}$$
But $\lambda_1\lambda_2 = 1$,
$$A^n = \frac{1}{\lambda_1 - \lambda_2} \begin{bmatrix}\lambda_1^{n+1}-\lambda_2^{n+1}&-(\lambda_1^n-\lambda_2)\\(\lambda_1^{n}-\lambda_2^n)&-(\lambda_1^{n-1}-\lambda_2^{n-1})\end{bmatrix}$$
$$F_{n+1} = \frac {(\lambda_1^{n+1}-\lambda_2^{n+1})b-(\lambda_1^{n}-\lambda_2^{n})a}{\lambda_1-\lambda_2}$$
A: You might note that the generating function is $$g(x) = \frac{a + (1-2a)b x}{1 - 2 b x + x^2} = \frac{r(1-2a)b - a}{2(b - r) (x-r)} + \frac{s(1-2a)b - a}{(2(b-s)(x-s)}$$
where $x=r$ and $x=s$ are the roots of $1-2bx+x^2$ (assuming these are distinct), so that
$$F(n) = \frac{(2a-1) b r - a}{2(r-b)} r^{-n-1} +  \frac{(2a-1) b s - a}{2(s-b)} s^{-n-1}$$
