El segundo problema de Project Euler nos propone determinar la suma de los números pares en la secuencia de Fibonacci menores que cuatro millones ...
Pares
Es conocido que F n | F kn , F 3 = 2 implica que los valores pares de la secuencia lo son de la forma F 3n .
La subsecuencia formada por los pares satisface la expresión general para la secuencia principal, fórmula de Binet , podemos obtener una recurrencia para los valores pares elevando al cubo el número aúreo,
τ = Φ 3 = 2 + √5
Ecuación característica,
( x - τ ) ( x - τ -1 )
x 2 – 4 x – 1
Recurrencia,
P n = 4 P n - 1 + P n - 2
P 1 = 2
P 2 = 8
Suma
Conocida una recurrencia, podemos obtener la recurrencia de su suma,
S n = ( 1 + 4 ) S n - 1 + ( 1 - 4 ) S n - 2 – S n - 3
S n = 5 S n - 1 – 3 S n - 2 – S n - 3
S 1 = 2
S 2 = 10
S 3 = 44
Conocida la ecuación de recurrencia de la suma de pares, resolver el problema propuesto es cuestión de determinar el término de la secuencia hasta el que hemos de sumar, para lo cual podemos hacer uso de las propiedades asintóticas de la sucesión de Fibonacci.
Otra posibilidad es determinar la expresión general de la suma ...
Media
Jakob Emanuel Handmann, Public domain, via Wikimedia Commons