Usaremos la siguiente identidad:

$$\displaystyle F_{n + k} = F_n\cdot F_{k + 1} + F_{n-1}\cdot F_k$$

Esta se puede demostrar usando inducción sobre ~k~ para ~n~ fijo.

Necesitamos hallar ~S_n = F_1 + F_2 + \dots + F_n~. Lo haremos de manera recursiva.

Consideremos el caso ~n~ siendo par.

$$\displaystyle S_{2n} = (F_1 + F_2 + \dots + F_n) + (F_{n+1} + F_{n+2} + \dots + F_{n + n})$$

$$\displaystyle S_{2n} = \sum_{k = 1}^nF_k + \sum_{k=1}^nF_{n+k}$$

$$\displaystyle S_{2n} = S_n + \sum_{k=1}^nF_{n+k}$$

$$\displaystyle S_{2n} = S_n + \sum_{k=1}^n[F_n\cdot F_{k + 1} + F_{n-1}\cdot F_k]$$

$$\displaystyle S_{2n} = S_n + F_n\sum_{k=1}^nF_{k+1} + F_{n-1}\sum_{k=1}^nF_k$$

$$\displaystyle S_{2n} = S_n + F_n(S_n + F_{n+1} - F_1) + F_{n-1}S_n$$

$$\displaystyle S_{2n} = S_n \cdot (1 + F_{n-1} + F_n) + F_nF_{n+1} - F_n$$

$$\displaystyle S_{2n} = S_n \cdot (1 + F_{n + 1}) + F_nF_{n+1} - F_n$$

Para el caso impar, tenemos:

$$\displaystyle S_{2n+1} = S_{2n} + F_{2n + 1}$$

Notemos que para computar ~S_{2n}~ necesitamos ~S_n, F_n, F_{n + 1}~, y para computar ~S_{2n+1}~ necesitamos ~S_{2n}, F_{2n+1}~

Entonces, hagamos un algoritmo recursivo que dado ~n~, retorne ~S_n, F_n, F_{n + 1}~ La complejidad temporal es ~\mathcal{O}(\log n)~

$$\displaystyle solve (n) \rightarrow [S_n, F_n, F_{n+1}]$$

Para ~n~ par usamos los resultados de ~solve(n/2)~, y para ~n~ impar usamos los resultados de ~solve(n-1)~.