PUMaC 2022 · 代数（A 组） · 第 8 题
PUMaC 2022 — Algebra (Division A) — Problem 8
题目详情
- The function f sends sequences to sequences in the following way: given a sequence { a } of n n =0 P n n ∞ ∞ real numbers, f sends { a } to the sequence { b } , where b = a for all n ≥ 0. n n n k n =0 n =0 k =0 k ∞ Let { F } be the Fibonacci sequence, defined by F = 0, F = 1, and F = F + F n 0 1 n +2 n +1 n n =0 ∞ for all n ≥ 0. Let { c } denote the sequence obtained by applying the function f to the n n =0 ∞ sequence { F } 2022 times. Find c (mod 1000). n 5 n =0 Name: Team: Write answers in table below: 1 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 2
解析
- The function f sends sequences to sequences in the following way: given a sequence { a } of n n =0 P n n ∞ ∞ real numbers, f sends { a } to the sequence { b } , where b = a for all n ≥ 0. n n n k n =0 n =0 k =0 k ∞ Let { F } be the Fibonacci sequence, defined by F = 0, F = 1, and F = F + F n 0 1 n +2 n +1 n n =0 ∞ for all n ≥ 0. Let { c } denote the sequence obtained by applying the function f to the n n =0 ∞ sequence { F } 2022 times. Find c (mod 1000). n 5 n =0 Proposed by Sunay Joshi 3 Answer: 775 Suppose that a satisfies the recurrence a = sa − pa for all n ≥ 0 with a = 0, a = 1. n n +2 n +1 n 0 1 We claim that if f is applied to { a } , the resulting sequence b satisfies the recurrence b = n n n +2 ( s + 2) b − ( s + p + 1) b for all n ≥ 0, with b = 0, b = 1. To see this, suppose that a has n +1 n 0 1 n n n explicit formula a = c α + c β for n ≥ 0, where α + β = s and αβ = p . Then by definition, n 1 2 P P P n n n n n n k k k k b = ( c α + c β ) = c α + c β . By the Binomial Theorem, n 1 2 1 2 k =0 k =0 k =0 k k k n n ′ ′ this may be rewritten as b = c (1+ α ) + c (1+ β ) . Thus the recurrence b = s b − p b n 1 2 n +2 n +1 n ′ ′ satisfies s = (1 + α ) + (1 + β ) = s + 2 and p = (1 + α )(1 + β ) = 1 + ( α + β ) + αβ = s + p + 1, 0 as claimed. The initial conditions b = 0 and b = 1 follow from definition: b = a = 0 0 1 0 0 0 1 1 and b = a + a = 1. 1 0 1 0 1 Since F = 1 F − ( − 1) F , the Fibonacci sequence has ( s, p ) = (1 , − 1). If f is applied n +2 n +1 n k times to { F } ( k ≥ 0), one can show by induction that the resulting pair ( s, p ) is ( s, p ) = n 2 (2 k + 1 , k + k − 1). In particular, for k = 2022, we have ( s, p ) ≡ (45 , 505) (mod 1000), so that c ≡ 45 c − 505 c . We now simply compute the first 6 terms of the sequence { c } : n +2 n +1 n n 2 c = 0, c = 1, c = 45, c = 45 − 505 ≡ − 408, c ≡ 45( − 408) − 45(505) ≡ − 325, and 0 1 2 3 4 c ≡ 45( − 325) − 505( − 408) ≡ 775. Thus our answer is 775. 5 4