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 inrow 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 inrow 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 sumfor 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 −