Dowód indukcyjny

[Olka97]

Korzystając z metody indukcji matematycznej, udowodnić:
\(\displaystyle{ \sum_{k=0}^{p} {p \choose k}{n-p\choose m-k}= {n \choose m}}\) , gdzie \(\displaystyle{ n, m}\) - liczby naturalne

Przedstawię, gdzie pojawia się problem:
1. Sprawdzam dla \(\displaystyle{ p=0}\) - tożsamość prawdziwa
Na wszelki wypadek sprawdziłam też dla \(\displaystyle{ p=1}\)
2. Sprawdzam dla \(\displaystyle{ p+1}\)

\(\displaystyle{ \sum_{k=0}^{p+1} {p+1 \choose k}{n-p-1\choose m-k}=\sum_{k=0}^{p} {p \choose k}{n-p\choose m-k}+ {p+1\choose p+1}{n-p-1\choose m-p-1}= {n \choose m}+{n-p-1 \choose m-p-1}}\)

I dalej nie wiem, co mam zrobić z tym wyrażeniem. Czy samo moje rozumowanie jest poprawne ?

[Jan Kraszewski]

\(\displaystyle{ \sum_{k=0}^{p+1} {\red p+1\black \choose k}{\red n-p-1\black\choose m-k}=\sum_{k=0}^{p} {\red p\black \choose k}{\red n-p\black \choose m-k}+ {p+1\choose p+1}{n-p-1\choose m-p-1}}\)

A możesz wyjaśnić, skąd wzięłaś powyższą równość?

JK

[Olka97]

Jan Kraszewski, Prawa strona : zsumowałam wszystkie składniki aż do przedostatniego (czyli do p) , a potem dodałam ostatni składnik

[Jan Kraszewski]

Co to znaczy "zsumowałam"? Przecież w lewej sumie i w prawej są inne składniki (poza tym ostatnim). Rozpisz swoje sumy dla \(\displaystyle{ p=1}\) i sprawdź, czy się zgadza...

JK

[Olka97]

A czy taki zapis byłby poprawny :
\(\displaystyle{ \sum_{k=0}^{p+1} {p+1 \choose k}{ n-p-1\choose m-k}=\sum_{k=0}^{p+1} \left( {p \choose k}+{p \choose k-1}\right) { n-p-1 \choose m-k}}\)

[Jan Kraszewski]

Tak.

JK

[Olka97]

Niestety nie wiem jak dalej poradzić sobie z zadaniem. Ktoś pomoże?

[Premislav]

A co to jest \(\displaystyle{ {p \choose k-1}}\) dla \(\displaystyle{ k=0}\)? [może i jakoś się to uogólniało \(\displaystyle{ {n choose k}}\) na \(\displaystyle{ k}\) rzeczywiste] Ogólnie pomysł z wykorzystaniem tej własności jest dobry, ale nie tak bym to zapisał.

\(\displaystyle{ \sum_{k=0}^{p+1} {p+1 \choose k}{ n-p-1\choose m-k}={n-p-1 \choose m}+ \sum_{k=1}^{p+1}{p+1 \choose k}{n-p-1 \choose m-k}=\\ \\={n-p-1 \choose m}+ \sum_{k=1}^{p+1}\left({p \choose k}+{p\choose k-1} \right){n-p-1 \choose m-k}=\\ \\={n-p-1 \choose m}+ \sum_{k=1}^{p+1}{p \choose k}{n-p-1 \choose m-k} + \sum_{k=1}^{p+1}{p \choose k-1}{n-p-1 \choose m-k}=\\ \\= \sum_{k=0}^{p}{p \choose k}{(n-1)-p \choose m-k}+ \sum_{k=0}^{p}{p \choose k}{(n-1)-p \choose (m-1)-k}}\)
Uwagi: w ostatniej równości włączyłem do pierwszej sumy to \(\displaystyle{ {n-p-1 \choose m}={p \choose 0}{n-p-1 \choose m-0}}\) oraz przesunąłem indeksy w tej drugiej sumie. Aha, \(\displaystyle{ {p \choose p+1}=0}\), więc także skróciłem tę pierwszą sumę o jeden wyraz, który i tak był zerem.

Teraz możesz dwa razy skorzystać z założenia indukcyjnego, a dostaniesz:
\(\displaystyle{ \sum_{k=0}^{p}{p \choose k}{(n-1)-p \choose m-k}={n-1 \choose m}}\)
oraz
\(\displaystyle{ \sum_{k=0}^{p}{p \choose k}{(n-1)-p \choose (m-1)-k}={n-1 \choose m-1}}\)
Więc suma tych dwóch:
\(\displaystyle{ {n-1 \choose m}+{n-1 \choose m-1}={n \choose m}}\), c.n.d.

[Olka97]

Premislav, Bardzo serdecznie Ci dziękuję! Wszystko przejrzyście wytłumaczone. Uratowałeś mi życie