Soma dos números pares na sequência Fibonacci

Os números de Fibonacci (Wikipedia, Wikipedia) são uma sequência definida como $F_n = F_{n-2} + F_{n-1}$. Os primeiros números são 0 e 1, e a partir deles, a sequência segue: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …. Dada a definição da sequência Fibonacci, como se calcula a soma dos números pares até $F_n < C$?

A solução simples é fazer um script conforme

C = 100
F_n2 = 0
F_n1 = 1
soma = 0
while True:
    F_n = F_n2 + F_n1
    if F_n >= C:
        break
    elif F_n % 2 == 0:
        soma += F_n
    F_n2 = F_n1
    F_n1 = F_n
print(soma)

Mas é possível fazer melhor? Sim, e isso requer pensar em como um número na sequência Fibonacci é calculado.

Inicialmente é necessário notar que um número par aparece a cada três posições:

$F_0$	$F_1$	$F_2$	$F_3$	$F_4$	$F_5$	$F_6$	$F_7$	$F_8$	$F_9$
0	1	1	2	3	5	8	13	21	34

Como os intervalos são regulares, a próxima questão é saber se as diferenças também são regulares. Portanto, existe alguma regularidade entre $F_{n+3} - F_n$?

Reescreve a diferença (substitui $F_n$ e $F_{n+3}$ pelas definições)

$F_{n+3} - F_n = (F_{n+1} + F_{n+2}) - (F_{n-1} + F_{n-2})$

Reescreve a diferença (substitui $F_{n+2}$ e $F_{n+1}$ pelas definições)

$F_{n+3} - F_n = ((F_{n} + F_{n-1}) + (F_{n} + F_{n+1})) - (F_{n-1} + F_{n-2})$

Reescreve a diferença (substitui $F_{n+1}$ pela definição)

$F_{n+3} - F_n = ((F_{n} + F_{n-1}) + (F_{n} + (F_{n} + F_{n-1}))) - (F_{n-1} + F_{n-2})$

Organiza

$F_{n+3} - F_n = F_{n} + F_{n} + F_{n} + F_{n-1} + F_{n-1} - F_{n-1} - F_{n-2}$

Cancela $F_{n-1} - F_{n-1}$ e junta $F_{n} + F_{n} + F_{n}$

$F_{n+3} - F_n = 3F_{n} + F_{n-1} - F_{n-2}$

Reescreve $F_{n-1}$

$F_{n+3} - F_n = 3F_{n} + F_{n-3} + F_{n-2} - F_{n-2}$

Cancela $F_{n-2} - F_{n-2}$

$F_{n+3} - F_n = 3F_{n} + F_{n-3}$

Resolve $F_{n+3}$

$F_{n+3} = 3F_{n} + F_{n-3} + F_n$

$F_{n+3} = 4F_{n} + F_{n-3}$

Portanto, o próximo número par da sequência Fibonacci ($F_{n+3}$) é dado por $F_{n+3} = 4F_{n} + F_{n-3}$, sendo $F_n$ o número par atual e $F_{n-3}$ o número par anterior.

Um script para resolver

C = 100
F_n6 = 0
F_n3 = 2
soma = F_n3 + F_n6
while True:
    F_n = 4 * F_n3 + F_n6
    if F_n >= C:
        break
    soma += F_n
    F_n6 = F_n3
    F_n3 = F_n
print(soma)

Pronto, dessa forma é possível calcular a soma de números Fibonacci pares evitando calcular os números ímpares e o módulo/resto (%) da divisão.