HMMT 二月 2007 · 冲刺赛 · 第 22 题

英文解析

22. [ 12 ] The sequence { a } is defined by a = 7 a − a for positive integers n with initial valuesn n ≥ 1 n +2 n +1 na = 1 and a = 8. Another sequence, { b } , is defined by the rule b = 3 b − b for positive
    1 2 n n +2 n +1 nintegers n together with the values b = 1 and b = 2. Find gcd( a , b ) .
    1 2 5000 501
    Answer: 89 . We show by induction that a = F and b = F , where F is the k th Fibonaccin 4 n − 2 n 2 n − 1 knumber. The base cases are clear. As for the inductive steps, note that
    F = F + F = 2 F + F = 3 F − Fk +2 k +1 k k k − 1 k k − 2
    F = 3 F − F = 8 F + 3 F = 7 F − F .andk +4 k +2 k k k − 2 k k − 4
    We wish to compute the greatest common denominator of F and F . The Fibonacci numbers
    19998 1001
    satisfy the property that gcd( F , F ) = F , which can be proven by noting that they are periodicm n gcd( m,n )
    modulo any positive integer. So since gcd(19998 , 1001) = 11, the answer is F = 89.
    611