HMMT 二月 2011 · TEAM1 赛 · 第 9 题
HMMT February 2011 — TEAM1 Round — Problem 9
题目详情
- [ 15 ] We would now like to examine the behavior of p ( k ) as m becomes arbitrarily large; specifi- m cally, we would like to discern whether lim p (0) exists and, if it does, to determine its value. Let m m →∞ lim p ( k ) = A . m k m →∞ 2 (a) [ 5 ] Prove that p ( k ) ≥ p ( k + 2) for all m and k . m m 3 (b) [ 10 ] Prove that A exists and that A > 0. Feel free to assume the result of analysis that a 0 0 non-increasing sequence of real numbers that is bounded below by a constant c converges to a limit that is greater than or equal to c .
解析
- [ 15 ] We would now like to examine the behavior of p ( k ) as m becomes arbitrarily large; specifi- m cally, we would like to discern whether lim p (0) exists and, if it does, to determine its value. Let m m →∞ lim p ( k ) = A . m k m →∞ 2 (a) [ 5 ] Prove that p ( k ) ≥ p ( k + 2) for all m and k . m m 3 (b) [ 10 ] Prove that A exists and that A > 0. Feel free to assume the result of analysis that a 0 0 non-increasing sequence of real numbers that is bounded below by a constant c converges to a limit that is greater than or equal to c . Solution: (a) We proceed by induction. 2 2 3 1 1 Base Case: When n = 1, we get p (0) = · = > = p (2). And since p (2 k ) = 0 for k ≥ 2, 1 1 1 3 3 4 2 4 2 we get p ( k ) ≥ p ( k + 2) for all k . 1 1 3 2 2 Induction Step: Assume that p ( k ) ≥ p ( k + 2) for all i ≤ n . This clearly implies p ( k ) ≥ i i n +1 3 3 p ( k + 2) for all k ≥ 4 by the formula (c) from the previous problem. n +1 Now, for k = 2, ( ) 2 2 1 3 3 1 p (2) = p (0) + p (2) + p (4) + p (6) n +1 n n n n 3 3 4 8 8 8 1 ≥ p (0) + p (4) n n +1 12 ≥ p (4) n +1 by the formula (b) from the previous problem and our induction hypothesis. For k = 0, we write out formula (a) from the previous problem. ( ) 2 2 3 1 1 p (0) = p (0) + p (2) + p (4) n +1 n n n 3 3 4 2 8 1 3 1 1 ≥ p (0) + p (2) + p (4) + p (6) n n n n 4 8 2 8 Team Round A 1 3 3 1 by our induction hypothesis. But p (2) = p (0) + p (2) + p (4) + p (6), which is clearly n +1 n n n n 4 8 8 8 2 less than the last line above. Thus p (0) ≥ p (2). This completes the induction step. n +1 n +1 3 Remark: This is nowhere near the strongest bound. We intentionally asked for a bound strong enough to be helpful in part b, but not strong enough to help with other problems. The strongest √ √ 2+ 5 bound is p (0) ≥ p (2) and p (2 k ) ≥ (2 + 5) p (2 k + 2) for k ≥ 1. This is intuitive because n n n n 2 √ √ 2+ 5 A = A and for k ≥ 1, A = (2 + 5) A . 0 2 2 k 2 k +2 2 2 k (b) For any n and k , p (2 k ) ≤ ( ) p (0). Now n n 3 ( ) ∞ ∞ k ∑ ∑ 2 1 = p (2 k ) ≤ p (0) = 3 p (0) . n n n 3 k =0 k =0 1 So p (0) ≥ for all n . This means p (0) is a non-increasing sequence that is bounded below by n n 3 1 1 . So A exists and A ≥ > 0. 0 0 3 3