HMMT 二月 2019 · ALGNT 赛 · 第 10 题
HMMT February 2019 — ALGNT Round — Problem 10
题目详情
- The sequence of integers { a } satisfies a = 3 , a = 4, and i 0 1 i =0 ⌈√ ⌉ √ 2 2 a = a a + a − 1 a − 1 n +2 n +1 n n +1 n for n ≥ 0. Evaluate the sum ( ) ∞ ∑ a a a a n +3 n +2 n +1 n − + − . a a a a n +2 n n +3 n +1 n =0
解析
- The sequence of integers { a } satisfies a = 3 , a = 4, and i 0 1 i =0 ⌈√ ⌉ √ 2 2 a = a a + a − 1 a − 1 n +2 n +1 n n +1 n for n ≥ 0. Evaluate the sum ( ) ∞ ∑ a a a a n +3 n +2 n +1 n − + − . a a a a n +2 n n +3 n +1 n =0 Proposed by: Ernest Chiu 14 Answer: 69 √ √ 2 2 The key idea is to note that a a + a − 1 a − 1 is the larger zero of the quadratic n +1 n n +1 n 2 2 2 f ( x ) = x − (2 a a ) x + a + a − 1 . n n +1 n n n +1 2 2 Since a is the smallest integer greater than or equal to this root, it follows that a + a + n +2 n n +1 2 a − 2 a a a − 1 is some small nonnegative integer. For these particular initial conditions n n +1 n +2 n +2 √ 2 2 2 ( a = 3 , a = 4 , a = 12+ d 120 e = 23), this integer is (3 +4 )+(23 − 2 · 3 · 4 · 23) − 1 = 25 − 23 − 1 = 1. 0 1 2 We now use induction to prove both 2 2 2 a = 2 a a − a and a + a + a − 2 a a a − 1 = 1 n +3 n +2 n +1 n n n +1 n +2 n n +1 n +2 √ for n ≥ 0. The base case is not difficult to check: a = 4 · 23 + d 7920 e = 181 = 2 · 4 · 23 − 3 , and 3 the other equation has been checked above. Since the quadratic equation f ( x ) = 1 has a solution n +1 a by induction hypothesis. Then, using Vieta’s theorem, 2 a a − a is also a solution. Then, n n +1 n +2 n the two roots of f ( x ) = 0 must be in strictly between a and 2 a a − a , so we have that n +1 n n +1 n +2 n a ≤ 2 a a − a since a is the ceiling of the larger root. In fact, since a a is much n +3 n +1 n +2 n n +3 n +1 n +2 larger than a for n ≥ 1 (it is not difficult to see that a grows faster than exponential), meaning n n that the two roots of f are more than 1 away from the minimum, and f (2 a a − a ) = 1, n +1 n +1 n +2 n we have f (2 a a − a − 1) < 0, which mean that we must have a = 2 a a − a , which n +1 n +2 n n +3 n +1 n +2 n simultaneously proves both statements due to Vieta jumping. To finish, note that the above recurrence gives a a a a a a n +3 n +2 n n − 1 n n − 1 − = 2 a − − 2 a + = − + , n +1 n +1 a a a a a a n +2 n n +2 n n +2 n which telescopes with the other two terms. (Convergence can be shown since the ratio of adjacent terms is bounded above by 1/3. In fact it goes to zero rapidly.) The only leftover terms after telescoping are a a a a 3 1 14 3 2 0 − 1 − = − + = − + = , giving the answer. (Here, we use the backwards recurrence a a a a 23 3 69 2 0 2 0 a = 2 a a − a to find a = 2 · 3 · 4 − 23 = 1.) n − 1 n n +1 n +2 − 1