返回题库

HMMT 二月 2019 · ALGNT 赛 · 第 10 题

HMMT February 2019 — ALGNT Round — Problem 10

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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
解析

英文解析

  1. 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