HMMT 二月 2019 · ALGNT 赛 · 第 10 题
HMMT February 2019 — ALGNT Round — Problem 10
题目详情
英文原题
- The sequence of integers { a } satisfies a = 3 , a = 4, andi 0 1
i =0
⌈√ ⌉
√
a = a a + a − 1 a − 122
n +2 n +1 nn +1 nfor n ≥ 0. Evaluate the sum
( )
∞
∑
a a a an +3 n +2 n +1 n − + − .
a a a an +2 n n +3 n +1
n =0
解析
英文解析
- The sequence of integers { a } satisfies a = 3 , a = 4, andi 0 1
i =0
⌈√ ⌉
√
a = a a + a − 1 a − 122
n +2 n +1 nn +1 nfor n ≥ 0. Evaluate the sum
( )
∞
∑
a a a an +3 n +2 n +1 n − + − .
a a a an +2 n n +3 n +1
n =0
Proposed by: Ernest Chiu
Answer:14
√69
√
The key idea is to note that a a + a − 1 a − 1 is the larger zero of the quadratic 22
n +1 nn +1 n
2 2 2
f ( x ) = x − (2 a a ) x + a + a − 1 .
n n +1 nn 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
a − 2 a a a − 1 is some small nonnegative integer. For these particular initial conditions 2
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 , andthe other equation has been checked above. Since the quadratic equation f ( x ) = 1 has a solution 3
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 nthe two roots of f ( x ) = 0 must be in strictly between a and 2 a a − a , so we have thatn +1 n n +1 n +2 na ≤ 2 a a − a since a is the ceiling of the larger root. In fact, since a a is muchn +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), meaningn nthat 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 nwe have f (2 a a − a − 1) < 0, which mean that we must have a = 2 a a − a , whichn +1 n +2 n n +3 n +1 n +2 nsimultaneously proves both statements due to Vieta jumping.
To finish, note that the above recurrence givesa a a a a an +3 n +2 n n − 1 n n − 1 − = 2 a − − 2 a + = − + ,
n +1 n +1
a a a a a an +2 n n +2 n n +2 nwhich telescopes with the other two terms. (Convergence can be shown since the ratio of adjacent termsis bounded above by 1/3. In fact it goes to zero rapidly.) The only leftover terms after telescoping area a a a 3 1 14
3 2 0 − 1 − = − + = − + = , giving the answer. (Here, we use the backwards recurrencea 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