HMMT 二月 2009 · 冲刺赛 · 第 24 题

HMMT February 2009 — Guts Round — Problem 24

[ 10 ] Compute, in terms of n , ( ) n ∑ n − k k 2 . k k =0 ( ) s Note that whenever s < t , = 0. t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND

解析

[ 10 ] Compute, in terms of n , ( ) n ∑ n − k k 2 . k k =0 ( ) s Note that whenever s < t , = 0. t n n 2 · 2 +( − 1) Answer: 3 ( ) ∑ n n − k k Solution: Let T = 2 . From Pascal’s recursion for binomial coefficients, we can find n k =0 k T = 2 T + T , with T = 1 and T = 1. The characteristic polynomial of this recursion is n n − 2 n − 1 0 1 2 n n x − x − 2 = 0, which has roots 2 and − 1. Thus T = a · 2 + b · ( − 1) for some a and b . From the n initial conditions we have a + b = 1 and 2 a − b = 1. It follows that a = 2 / 3 and b = 1 / 3, from which the conclusion follows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 th 12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND