Informática el término enésimo de la secuencia de fibonacci como para n grande

Question

Suma hasta el enésimo término de la secuencia de fibonacci para n muy grande se puede calcular en tiempo O($\log n$) utilizando el siguiente enfoque:

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

Podemos calcular $A^n$ en O($\log n$) tiempo calculando el $A$, $A^2$, $A^4$, $A^8$...

Ahora tengo otra secuencia

$ T(n) = T (n - 1) + T (n - 2) - (4n - 13) T(1) $$ $$ = T(2) $$ $$ 3 = 8 $

Quiero calcular su término n para n grande en tiempo O($\log n$).

Answer 1

Que $T(n)=S(n)+an+b$, donde se decidirá más adelante $a,b$...

Entonces

$$S(n)+an+b=S(n-1)+an-a+b +S(n-2)+an-2a+b -(4n-13)$$

Por lo tanto

$$S(n)=S(n-1)+S(n-2) +an-3a+b -(4n-13) \,.$$

Ahora, si podemos hacer

$$an-3a+b=4n-13 \,, (*)$$

obtenemos

$$S(n)=S(n-1)+S(n-2) \,,$$

y por lo tanto, como en Fibonnaci,

$$\begin{bmatrix}S(n+1) \\\\ S(n) \end{bmatrix} = A^n \begin{bmatrix}S(1) \\\\ S(0)\end{bmatrix}$$

Ahora puede calcular $S(n)$ $O(\log n)$ plazo y $T(n)$ necesita agregar $an+b$, donde se calculan los $a,b$ $(*)$.

Answer 2

Que $S(n) = T(n) - 4n - 25$, entonces \begin{align*} S(n) &= T(n) - 4n - 25 \\&= T(n-1) + T(n-2) - 8n - 13 - 25 \\&= S(n-1) + 4n - 4 + 25 + S(n-2) + 4n - 8 + 25 - 8n - 13 - 25 \\&= S(n-1) + S(n-2) \end{align*} así $S(n)$ satisface la repetición de Fibonacci. Ahora no como el anterior y calcular $T(n) = S(n) + 4n+25$ luego.