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

HMMT February 2006 — Guts Round — Problem 23

[9] Let a , a , a , . . . be a sequence of real numbers defined by a = 21 , a = 35, and a = 0 1 2 0 1 n +2 2 4 a − 4 a + n for n ≥ 2. Compute the remainder obtained when a is divided by 100. n +1 n 2006

解析

Let a , a , a , . . . be a sequence of real numbers defined by a = 21 , a = 35, and 0 1 2 0 1 2 a = 4 a − 4 a + n for n ≥ 2. Compute the remainder obtained when a is 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 2 a . If we write a = An + Bn + C + b and put b = 4 b − 4 b . Rewriting the n n n n +2 n +1 n original recurrence, we find 2 An + (4 A + B ) n + (4 A + 2 B + C ) + b n +2 ( ) ( ) 2 2 2 = 4 An + (2 A + B ) n + ( A + B + C ) + b − 4 An + Bn + C + b + n n +1 n 2 = n + 8 An + (4 A + 4 B ) + 4 b − 4 b n +1 n Solving, A = 1 , B = 4 , C = 8. With this information, we can solve for b = 1 and 0 2 b = 6. Since the characteristic equation of the recurrence of the b is x − 4 x + 4 = 1 i 2 n ( x − 2) = 0, we have b = ( Dn + E ) · 2 for some constants D and E . Using the n known values b and b , we compute D = 2 and E = 1, and finally 0 1 2 n a = n + 4 n + 8 + (2 n + 1) · 2 n 2 2006 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