Задача
COM-B2-M09-P005 Тождество Вандермонда
#5
★★☆☆☆ Уровень 2 из 5
Докажите с помощью производящих функций, что для неотрицательных целых \(r,s,n\)
\[\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}.\]
Сравните коэффициент при \(x^n\) в \((1+x)^r(1+x)^s\) двумя способами.
С одной стороны, \((1+x)^r(1+x)^s=(1+x)^{r+s}\), поэтому коэффициент при \(x^n\) равен \(\binom{r+s}{n}\). С другой стороны, чтобы получить \(x^n\), можно взять \(x^k\) из первого множителя и \(x^{n-k}\) из второго. Это дает сумму \(\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}\). Коэффициенты одного и того же многочлена равны, значит, тождество доказано.
Стандартное применение: доказать тождество без алгебраического раскрытия сумм.