Problem: a a a a b b x 2 − x − 1 x 2 − x − 1 a x 17 + b x 16 + 1 a x 1 7 + b x 1 6 + 1
Solution:
Since the roots of x 2 − x − 1 = 0 x 2 − x − 1 = 0 p = 1 2 ( 1 + 5 ) p = 2 1 ​ ( 1 + 5 ​ ) q = 1 2 ( 1 − 5 ) q = 2 1 ​ ( 1 − 5 ​ ) a x 17 + b x 16 + 1 = 0 a x 1 7 + b x 1 6 + 1 = 0
a p 17 + b p 16 = − 1 and a q 17 + b q 16 = − 1 a p 1 7 + b p 1 6 = − 1 and a q 1 7 + b q 1 6 = − 1
Multiplying the first of these equations by q 16 q 1 6 p 16 p 1 6 p q = − 1 p q = − 1
a p + b = − q 16 and a q + b = − p 16 a p + b = − q 1 6 and a q + b = − p 1 6
Thus
a = p 16 − q 16 p − q = ( p 8 + q 8 ) ( p 4 + q 4 ) ( p 2 + q 2 ) ( p + q ) (1) a = p − q p 1 6 − q 1 6 ​ = ( p 8 + q 8 ) ( p 4 + q 4 ) ( p 2 + q 2 ) ( p + q ) ( 1 )
Since
p + q = 1 p 2 + q 2 = ( p + q ) 2 − 2 p q = 1 + 2 = 3 , p 4 + q 4 = ( p 2 + q 2 ) 2 − 2 ( p q ) 2 = 9 − 2 = 7 , p 8 + q 8 = ( p 4 + q 4 ) 2 − 2 ( p q ) 4 = 49 − 2 = 47 , p + q p 2 + q 2 p 4 + q 4 p 8 + q 8 ​ = 1 = ( p + q ) 2 − 2 p q = 1 + 2 = 3 , = ( p 2 + q 2 ) 2 − 2 ( p q ) 2 = 9 − 2 = 7 , = ( p 4 + q 4 ) 2 − 2 ( p q ) 4 = 4 9 − 2 = 4 7 , ​
substitution into ( 1 ) ( 1 )
a = ( 47 ) ( 7 ) ( 3 ) ( 1 ) = 987 . a = ( 4 7 ) ( 7 ) ( 3 ) ( 1 ) = 9 8 7 ​ .
Note. Substituting for p p q q ( 1 ) ( 1 )
a = 1 5 [ ( 1 + 5 2 ) 16 − ( 1 − 5 2 ) 16 ] a = 5 ​ 1 ​ ⎣ ⎢ ⎡ ​ ( 2 1 + 5 ​ ​ ) 1 6 − ( 2 1 − 5 ​ ​ ) 1 6 ⎦ ⎥ ⎤ ​
whose right side may be recognized as (the Binet form of) the 16 1 6
Fibonacci number F 16 F 1 6 ​ F 16 F 1 6 ​ F 1 = F 2 = 1 , F n = F n − 1 + F n − 2 F 1 ​ = F 2 ​ = 1 , F n ​ = F n − 1 ​ + F n − 2 ​ n > 2 n > 2
OR OR
The other factor is of degree 15 1 5
( − 1 − x + x 2 ) ( − c 0 + c 1 x − … + c 15 x 15 ) = 1 + b x 16 + a x 17 ( − 1 − x + x 2 ) ( − c 0 ​ + c 1 ​ x − … + c 1 5 ​ x 1 5 ) = 1 + b x 1 6 + a x 1 7
Comparing coefficients:
x 0 : c 0 = 1 , x 1 : c 0 − c 1 = 0 ⇒ c 1 = 1 x 2 : − c 0 − c 1 + c 2 = 0 ⇒ c 2 = 2 ​ x 0 : c 0 ​ = 1 , x 1 : c 0 ​ − c 1 ​ = 0 ⇒ c 1 ​ = 1 x 2 : − c 0 ​ − c 1 ​ + c 2 ​ = 0 ⇒ c 2 ​ = 2 ​
and for 3 ≤ k ≤ 15 3 ≤ k ≤ 1 5
x k : − c k − 2 − c k − 1 + c k = 0 x k : − c k − 2 ​ − c k − 1 ​ + c k ​ = 0
It follows that for k ≤ 15 , c k = F k + 1 k ≤ 1 5 , c k ​ = F k + 1 ​ ( k + 1 ) ( k + 1 )
Thus a = c 15 = F 16 = 987 a = c 1 5 ​ = F 1 6 ​ = 9 8 7 ​
The problems on this page are the property of the MAA's American Mathematics Competitions