重複組合せと組合せの関係式

問題です。解答は下部に載せました。

問題： $\displaystyle { n }$ および $\displaystyle { r }$ を $\displaystyle { 1 }$ 以上の任意の整数とする。このとき、

$\displaystyle { \binom{n + r -1}{r} = \sum_{k = 1}^{\min{[n,r]}} \binom{n}{k} \cdot \binom{r - 1}{r - k} }$

となることを示せ。

解答：題意の式の左辺は重複組合せのよく知られた公式である。ところで、 $\displaystyle { n }$ 種類のものから重複を許して $\displaystyle { r }$ 個選ぶ場合、選ばれるものの種類の数を $\displaystyle { k }$ とすれば、明らかに $\displaystyle { 1 \leq k \leq \min{[n,r]} }$ である。そして、 $\displaystyle { n }$ 種類のものから $\displaystyle { k }$ 種類を選ぶときの選び方の総数は $\displaystyle { \binom{n}{k} }$ 通りであり、それぞれの選び方について重複組合せの総数を考えると、 $\displaystyle { k }$ 種類のものが少なくとも一つずつ選ばれていることに気を付ければ、それは