Matrix exponentiation for given recurrence relation

Question

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?

Answer 1

$$\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}$$

Answer 2

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}$$