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
B. 319 3 1 9
C. 320 3 2 0
D. 321 3 2 1
E. 322 3 2 2
Solution:
The Fibonacci sequence starts out
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 = ( B ) 319 1 + 3 + 4 + 7 + 1 1 + 1 8 + 2 9 + 4 7 + 7 6 + 1 2 3 = ( B ) 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