HMMT 二月 2006 · 冲刺赛 · 第 23 题

英文解析

23. Let a , a , a , . . . be a sequence of real numbers defined by a = 21 , a = 35, and
    0 1 2 0 1
    a = 4 a − 4 a + n for n ≥ 2. Compute the remainder obtained when a is 2
    n +2 n +1 n 2006
    divided by 100.
    Answer: 0
    Solution: No pattern is evident in the first few terms, so we look for a formula for a . If we write a = An + Bn + C + b and put b = 4 b − 4 b . Rewriting the 2
    n n n n +2 n +1 noriginal recurrence, we find
    An + (4 A + B ) n + (4 A + 2 B + C ) + b 2
    n +2
    ( ) ( )
    2 2 2 = 4 An + (2 A + B ) n + ( A + B + C ) + b − 4 An + Bn + C + b + nn +1 n = n + 8 An + (4 A + 4 B ) + 4 b − 4 b 2
    n +1 n
    Solving, A = 1 , B = 4 , C = 8. With this information, we can solve for b = 1 andb = 6. Since the characteristic equation of the recurrence of the b is x − 4 x + 4 =20
    1 i
    2 n
    ( x − 2) = 0, we have b = ( Dn + E ) · 2 for some constants D and E . Using thenknown values b and b , we compute D = 2 and E = 1, and finally
    0 1
    2 na = n + 4 n + 8 + (2 n + 1) · 2
    2 2006 n
    Now, taking modulo 100, we have a ≡ 6 + 4 · 6 + 8 + 13 · 2 (mod 100). Evidently
    2006
    2006 φ (25) 20 2006
    2 ≡ 0 (mod 4), but by Euler’s theorem 2 ≡ 2 ≡ 1 (mod 25), and so 2 ≡
    6 2006
    2 ≡ 14 (mod 25). Now the Chinese remainder theorem yields 2 ≡ 64 (mod 100),
    and we compute a ≡ 36 + 24 + 8 + 13 · 64 ≡ 0 (mod 100).
    2006