Формула с участие на биномиален коефицент

[Gewitter]

Здравейте! Затруднявам се с доказателството на задачата по-долу Трябва да се докаже с използване на математическа индукция. Първите две стъпки са ясни, при n+1 обаче не мога да докажа равенството, вече изпробвах всичко, за което се сетих, групирания и т.н. Как бихте доказали това равенство за n+1?
Благодаря предварително!

[allier]

Докажи следното по индукция:

[tex]\sum_{k=0}^{n } {n\choose k}{m\choose n-k} = {n+m\choose n}[/tex]

[Gewitter]

allier, благодаря ти много за помощта! Разбрах идеята, поразписах я, но някак не ми се получава третия етап от доказателството на твоето равенство Може ли, ако имаш време, да обясниш кратко как доказваме равенството, което предложи в поста си?
Мерси предварително!

[L.e.o]

(n/n-k) = (n/k)
(n/k)^2 = (n/n-k).(n/k) = (n+n/k) = (2n/k)(замести m с n)

[allier]

Накратко, като смениш n с n+1, разписваш първия биномен коефициент чрез формулата:

[tex]{n+1\choose k} = {n\choose k} + {n\choose k-1}[/tex] като внимаваш за първия член на сумата (където множителят е 1). След това отдясно ще се получи точно:
[tex]{n+m\choose n+1} + {n+m\choose n} = {n+m+1\choose n+1}[/tex]

[Gewitter]

Благодаря ви за помощта!

allier, направих както ме посъветва, след това групирах новополучените коефиценти, но пак не излезе нище свястно, т.е не получих равенство между лявата и дясната страна. Явно съм много съм много зле и няма да мога да предам задачата до понеделник.

[allier]

Извинявай, аз съм се объркал - това, което съм написал, пак се доказва трудно по индукция. Лесният начин е да докажеш следното:

[tex]\sum_{k=0}^{s } {n\choose k}{m\choose s-k} = {n+m\choose s}[/tex].

Сега вече можеш да се справиш - само първото събираемо зависи от n.

[Gewitter]

Сега вече се получи! Мерси много, задължена съм ти