MathLabs

第2問

nn と rr を 1≤r≤n1 \le r \le n を満たす整数とし、集合 {1,2,…,n}\{1,2,\dots,n\} の rr 個の要素からなるすべての部分集合、すなわち (nr)\binom{n}{r} 個の部分集合を考える。それぞれの部分集合には最小の要素がある。これらの最小要素の相加平均を F(n,r)F(n,r) とする。F(n,r)=n+1r+1.F(n,r) = \frac{n+1}{r+1}. を証明せよ。
ステップ 4/6: 各行にホッケースティック恒等式を適用する
(n−ir−1)+(n−i−1r−1)+⋯+(r−1r−1)=(n−i+1r)\binom{n-i}{r-1}+\binom{n-i-1}{r-1}+\cdots+\binom{r-1}{r-1} = \binom{n-i+1}{r}
詳しい解説

ホッケースティック恒等式 ∑k=r−1m(kr−1)=(m+1r)\sum_{k=r-1}^{m}\binom{k}{r-1}=\binom{m+1}{r} により、各内側の並びは単一の二項係数 (n−i+1r)\binom{n-i+1}{r} に簡約される。