HMMT 二月 2004 · 团队赛 · 第 3 题

HMMT February 2004 — Team Round — Problem 3

[35] Let ( ) ( ) ( ) ( ) n − 1 n − 1 n − 1 n − 1 S ( n, r ) = + + + · · · + r − 1 r r + 1 n − 1 for all n, r > 0, and in particular S ( n, r ) = 0 if r > n > 0. Prove that the number in row n of the table, r columns to the left of the 1 in the top row, is at most S ( n, r ). ( Hint : First prove that S ( n − 1 , r − 1) + S ( n − 1 , r ) = S ( n, r ).) n − 1

解析

Let ( ) ( ) ( ) ( ) n − 1 n − 1 n − 1 n − 1 S ( n, r ) = + + + · · · + r − 1 r r + 1 n − 1 for all n, r > 0, and in particular S ( n, r ) = 0 if r > n > 0. Prove that the number in row n of the table, r columns to the left of the 1 in the top row, is at most S ( n, r ). ( Hint : First prove that S ( n − 1 , r − 1) + S ( n − 1 , r ) = S ( n, r ).) Solution: First, we prove the statement in the hint: adding the i th term of the sum for S ( n − 1 , r − 1) to the i th term for S ( n − 1 , r ), for each i , we get that S ( n − 1 , r −