HMMT 十一月 2009 · 冲刺赛 · 第 33 题

HMMT November 2009 — Guts Round — Problem 33

[ 20 ] Compute ∞ ∑ 1 ( ) . n 2009 n =2009 ( ) n n ! Note that is defined as . k k !( n − k )! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . nd 2 ANNUAL HARVARD-MIT NOVEMBER TOURNAMENT, 7 NOVEMBER 2009 — GUTS ROUND

解析

[ 20 ] Compute ∞ ∑ 1 ( ) . n 2009 n =2009 ( ) n n ! Note that is defined as . k k !( n − k )! 2009 Answer: Observe that 2008 ( ) ( ) ( ) n n − 1 − k + 1 1 1 k + 1 k k ( ) ( ) ( )( ) − = n − 1 n n n − 1 k k k k k k ( ) n − 1 k + 1 k − 1 ( )( ) = n n − 1 k k k k + 1 ( n − 1)! k ! k !( n − k − 1)!( n − k )! = k n !( n − 1)!( k − 1)!( n − k )! k + 1 k · k !( n − k − 1)! = k n ! ( k + 1)!( n − k − 1)! = n ! 1 ( ) = n k +1 Now apply this with k = 2008 and sum across all n from 2009 to ∞ . We get ∞ ∞ ∑ ∑ 1 2009 1 1 ( ) ( ) ( ) = − . n n n − 1 2008 2009 2008 2008 n =2009 n =2009 1 All terms from the sum on the right-hand-side cancel, except for the initial , which is equal to 1, 2008 ( ) 2008 ∑ ∞ 1 2009 so we get = . n n =2009 2008 ( ) 2009 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . nd 2 ANNUAL HARVARD-MIT NOVEMBER TOURNAMENT, 7 NOVEMBER 2009 — GUTS ROUND