第2問

n

と

r

を

1 \le r \le n

を満たす整数とし、集合

\{1,2,\dots,n\}

の

r

個の要素からなるすべての部分集合、すなわち

\binom{n}{r}

個の部分集合を考える。それぞれの部分集合には最小の要素がある。これらの最小要素の相加平均を

F(n,r)

とする。

F(n,r) = \frac{n+1}{r+1}.

を証明せよ。

ステップ 5/6: もう一度ホッケースティック恒等式を適用する

\sum_{i=1}^{n-r+1}\binom{n-i+1}{r} = \binom{n}{r}+\binom{n-1}{r}+\cdots+\binom{r}{r} = \binom{n+1}{r+1}

詳しい解説

$i=1,\dots,n-r+1$ について簡約された行を足すと、 $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}$ となる。もう一度ホッケースティック恒等式を使えば、これは $\binom{n+1}{r+1}$ に簡約される。