Problem: F 1 = 1 , F 2 = 1 F 1 ​ = 1 , F 2 ​ = 1 F n = F n − 1 + F n − 2 F n ​ = F n − 1 ​ + F n − 2 ​ n ≥ 3 n ≥ 3
F 2 F 1 + F 4 F 2 + F 6 F 3 + ⋯ + F 20 F 10 ? F 1 ​ F 2 ​ ​ + F 2 ​ F 4 ​ ​ + F 3 ​ F 6 ​ ​ + ⋯ + F 1 0 ​ F 2 0 ​ ​ ?
Answer Choices:
A. 318 3 1 8 319 3 1 9 320 3 2 0 321 3 2 1 322 3 2 2
Solution:
1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 , 987 , 1597 , 2584 , 4181 , 6765 , … , 1 , 1 , 2 , 3 , 5 , 8 , 1 3 , 2 1 , 3 4 , 5 5 , 8 9 , 1 4 4 , 2 3 3 , 3 7 7 , 6 1 0 , 9 8 7 , 1 5 9 7 , 2 5 8 4 , 4 1 8 1 , 6 7 6 5 , … ,
so the given sum is
1 1 + 3 1 + 8 2 + 21 3 + 55 5 + 144 8 + 377 13 + 987 21 + 2584 34 + 6765 55 1 1 ​ + 1 3 ​ + 2 8 ​ + 3 2 1 ​ + 5 5 5 ​ + 8 1 4 4 ​ + 1 3 3 7 7 ​ + 2 1 9 8 7 ​ + 3 4 2 5 8 4 ​ + 5 5 6 7 6 5 ​
which equals 1 + 3 + 4 + 7 + 11 + 18 + 29 + 47 + 76 + 123 = ( B ) 319 1 + 3 + 4 + 7 + 1 1 + 1 8 + 2 9 + 4 7 + 7 6 + 1 2 3 = ( B ) 3 1 9 ​
OR OR
The Fibonacci sequence starts out 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 1 , 1 , 2 , 3 , 5 , 8 , 1 3 , 2 1 , 3 4 , 5 5
1 1 + 3 1 + 8 2 + 21 3 + 55 5 = 1 + 3 + 4 + 7 + 11 1 1 ​ + 1 3 ​ + 2 8 ​ + 3 2 1 ​ + 5 5 5 ​ = 1 + 3 + 4 + 7 + 1 1
It appears that these summands satisfy the same recurrence relation, namely
F 2 n F n = F 2 ( n − 1 ) F n − 1 + F 2 ( n − 2 ) F n − 2 F n ​ F 2 n ​ ​ = F n − 1 ​ F 2 ( n − 1 ) ​ ​ + F n − 2 ​ F 2 ( n − 2 ) ​ ​
With the initial conditions 1,3 instead of 1 , 1 , the sequence
( L n ) = ( F 2 n F n ) ( L n ​ ) = ( F n ​ F 2 n ​ ​ )
is known as the Lucas sequence. If the recurrence above is correct, then the required sum is
1 + 3 + 4 + 7 + 11 + 18 + 29 + 47 + 76 + 123 = 319 1 + 3 + 4 + 7 + 1 1 + 1 8 + 2 9 + 4 7 + 7 6 + 1 2 3 = 3 1 9
To prove the identity for ( L n ) ( L n ​ ) F n = 1 5 ( ϕ n − ψ n ) F n ​ = 5 ​ 1 ​ ( ϕ n − ψ n ) ϕ = 1 + 5 2 ϕ = 2 1 + 5 ​ ​ ψ = 1 − 5 2 ψ = 2 1 − 5 ​ ​ x 2 − x − 1 x 2 − x − 1
L n = F 2 n F n = ϕ 2 n − ψ 2 n ϕ n − ψ n = ϕ n + ψ n . L n ​ = F n ​ F 2 n ​ ​ = ϕ n − ψ n ϕ 2 n − ψ 2 n ​ = ϕ n + ψ n .
Therefore
L n − 1 + L n − 2 = ϕ n − 1 + ϕ n − 2 + ψ n − 1 + ψ n − 2 = ϕ n − 2 ( ϕ + 1 ) + ψ n − 2 ( ψ + 1 ) = ϕ n − 2 ⋅ ϕ 2 + ψ n − 2 ⋅ ψ 2 = ϕ n + ψ n = L n . L n − 1 ​ + L n − 2 ​ ​ = ϕ n − 1 + ϕ n − 2 + ψ n − 1 + ψ n − 2 = ϕ n − 2 ( ϕ + 1 ) + ψ n − 2 ( ψ + 1 ) = ϕ n − 2 ⋅ ϕ 2 + ψ n − 2 ⋅ ψ 2 = ϕ n + ψ n = L n ​ . ​
The problems on this page are the property of the MAA's American Mathematics Competitions