Пожалуйста, помогите с тождеством.

[anr45]

`sum_(r=0)^k ((m), (r)) * ((n), (k-r)) = ((n+m) , (k))`
Задание - доказать с помощью` (1 + t)^n * (1+t)^m = (1+t)^(n+m)`
Я воспользовалась `(1+t)^n = sum_(k=0)^n ((n), (k)) * t^k` для обеих частей.
`sum_(a=0)^n ((n) , (a)) * t^a * sum_(b=0)^m ((m) , (b)) * t^b = sum_(k=0)^(n+m) ((n+m) , (k)) * t^k `
`sum_(a=0)^n sum_(b=0)^m ((n) , (a)) * ((m) , (b)) * t^(a+b) = sum_(k=0)^(m+n) ((n+m) , (k)) * t^k`

в указании сказано, что нужно сравнить коэффиценты при `t^k` в правой и левой частях.
Объясните пожалуйста, как? Как нужно дальше двигаться в док-ве? Я просто не понимаю.

И еще вопрос: есть ли другой способ? (например по индукции)
Заранее большое спасибо!
Скриншот задания

@темы: Комбинаторика

Comments

[Trotill]

У меня скрипта нет, сделайте скриншот, удобнее будет вникнуть, понять и попробовать помочь ответить на ваш ответ.

[anr45]

[Robot]

Я сделала

[Trotill]

Отлично!

По существу вопроса: это так называемая свёртка Вандермонда.
В литературе обычно любят ее доказывать, так что при желании можно отыскать ее доказательство.

А лучше не искать - ибо остался маленький шажок.

Нужно положить a+b=k, переобозначить b=r
Тогда a=k-r, b=r и t^k получается при всех r=0..k
Коэффициент справа равен коэф. слева и получается нужное выражение. Вуаля.

[Trotill]

И еще вопрос: есть ли другой способ? (например по индукции)

Мне известен комбинаторный способ. Его суть.
Допустим, нужно выбрать `k` предметов из `n+m` предметов.
Это можно сделать сразу (правая часть), или разделить предметы на две кучки из `n` и `m` предметов. Понятно, что из первой кучки можно выбрать 0,1,...r,...k-1,k предметов и k,k-1,...,r-k,...1,0 предметов из другой. В сумме они будут давать как раз нужное число.

[anr45]

Спасибо за понятное объяснение!