HMMT 二月 2009 · 冲刺赛 · 第 24 题
HMMT February 2009 — Guts Round — Problem 24
题目详情
- [ 10 ] Compute, in terms of n ,
( )
∑nn − k
2 .kkk =0
( )
Note that whenever s < t , = 0.st
12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUNDth
英文原题
[ 10 ] Compute, in terms of n , n ∑
k =0
( n − k
k
)
2 k .
Note that whenever s < t , ( s
t
) = 0.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 th HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND
解析
英文解析
- [ 10 ] Compute, in terms of n ,
( )
∑nn − k
2 .kkk =0
( )
Note that whenever s < t , = 0.stn n
2 · 2 +( − 1)
Answer:
( )3
∑
n − knk
Solution: Let T = 2 . From Pascal’s recursion for binomial coefficients, we can findnk =0
T = 2 T + T , with T = 1 and T = 1. The characteristic polynomial of this recursion iskn n − 2 n − 1 0 1
2 n nx − x − 2 = 0, which has roots 2 and − 1. Thus T = a · 2 + b · ( − 1) for some a and b . From theinitial conditions we have a + b = 1 and 2 a − b = 1. It follows that a = 2 / 3 and b = 1 / 3, from whichnthe conclusion follows.
th 5
12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND