PUMaC 2021 · 代数（A 组） · 第 8 题

PUMaC 2021 — Algebra (Division A) — Problem 8

Consider the sequence of Fibonacci numbers F , F , F , . . . , given by F = F = 1 and F = 0 1 2 0 1 n +1 2 2 F + F for n ≥ 1. Define the sequence x , x , x , . . . by x = 1 and x = x + F for k n n − 1 0 1 2 0 k +1 k 2 2 k ≥ 0. Define the sequence y , y , y , . . . by y = 1 and y = 2 x y − y for k ≥ 0. If 0 1 2 0 k +1 k k k √ ∞ X 1 a − b = y c k k =0 for positive integers a, b, c with gcd( a, c ) = 1, find a + b + c . 1

解析

Consider the sequence of Fibonacci numbers F , F , F , . . . , given by F = F = 1 and F = 0 1 2 0 1 n +1 2 2 F + F for n ≥ 1. Define the sequence x , x , x , . . . by x = 1 and x = x + F for n n − 1 0 1 2 0 k +1 k k 2 2 k ≥ 0. Define the sequence y , y , y , . . . by y = 1 and y = 2 x y − y for k ≥ 0. If 0 1 2 0 k +1 k k k √ ∞ X 1 a − b = y c k k =0 for positive integers a, b, c with gcd( a, c ) = 1, find a + b + c . Proposed by: Sunay Joshi Answer: 14 k k Let f ( n ) = F . We claim that for all k ≥ 0, we have x = f (2 + 1) and y = f (2 ). To see n k k this, we proceed by induction on k . The base case is clear. Assume the result holds k . Then 3 k 2 k 2 k +1 2 2 2 x = f (2 + 1) + f (2 ) = f (2 + 1) , using the identity f (2 i + 1) = f ( i ) + f ( i + 1) . k +1 k k k k +1 Thus, y = y (2 x − y ) = f (2 )( f (2 − 1) + f (2 + 1)) = f (2 ), using the identity k +1 k k k f (2 i ) = f ( i )( f ( i − 1) + f ( i + 1)). The induction is complete. From the above, we must compute ∞ X 1 . F k 2 k =0 √ 7 − 5 However, this is simply the Millin series, with value . Thus our answer is 7 + 5 + 2 = 14. 2 4