Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach:
$$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$
$$\begin{bmatrix}f(n+1) \\\\ f(n) \end{bmatrix} = A^n \begin{bmatrix}f(1) \\\\ f(0)\end{bmatrix} $$
We can calculate $A^n$ in O($\log n$) time by calculating $A$, $A^2$, $A^4$, $A^8$…
Now I have another sequence
$$
T(n) = T(n – 1) + T(n – 2) – (4n – 13)
$$
$$
T(1) = 3
$$
$$
T(2) = 8
$$
I want to calculate its nth term for large n in O($\log n$) time.
Best Answer
Let $T(n)=S(n)+an+b$, where $a,b$ will be decided later...
Then
$$S(n)+an+b=S(n-1)+an-a+b +S(n-2)+an-2a+b -(4n-13)$$
Thus
$$S(n)=S(n-1)+S(n-2) +an-3a+b -(4n-13) \,.$$
Now, if we can make
$$an-3a+b=4n-13 \,, (*)$$
we get
$$S(n)=S(n-1)+S(n-2) \,,$$
and hence,as in Fibonnaci,
$$\begin{bmatrix}S(n+1) \\\\ S(n) \end{bmatrix} = A^n \begin{bmatrix}S(1) \\\\ S(0)\end{bmatrix}$$
you can now calculate $S(n)$ within $O(\log n)$ time, and to get $T(n)$ you need to add $an+b$, where $a,b$ are calculated from $(*)$.