szukanie zaawansowane
 [ Posty: 9 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 28 sty 2017, o 22:34 
Użytkownik

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

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

\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 ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 28 sty 2017, o 23:38 
Administrator

Posty: 22282
Lokalizacja: Wrocław
Olka97 napisał(a):
\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
Góra
Kobieta Offline
PostNapisane: 28 sty 2017, o 23:45 
Użytkownik

Posty: 81
Jan Kraszewski, Prawa strona : zsumowałam wszystkie składniki aż do przedostatniego (czyli do p) , a potem dodałam ostatni składnik
Góra
Mężczyzna Offline
PostNapisane: 28 sty 2017, o 23:51 
Administrator

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

JK
Góra
Kobieta Offline
PostNapisane: 28 sty 2017, o 23:59 
Użytkownik

Posty: 81
A czy taki zapis byłby poprawny :
\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}
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 00:12 
Administrator

Posty: 22282
Lokalizacja: Wrocław
Tak.

JK
Góra
Kobieta Offline
PostNapisane: 29 sty 2017, o 21:50 
Użytkownik

Posty: 81
Niestety nie wiem jak dalej poradzić sobie z zadaniem. Ktoś pomoże?
Góra
Mężczyzna Offline
PostNapisane: 29 sty 2017, o 22:40 
Użytkownik
Avatar użytkownika

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

\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 {n-p-1 \choose m}={p \choose 0}{n-p-1 \choose m-0} oraz przesunąłem indeksy w tej drugiej sumie. Aha, {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:
\sum_{k=0}^{p}{p \choose k}{(n-1)-p \choose m-k}={n-1 \choose m}
oraz
\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:
{n-1 \choose m}+{n-1 \choose m-1}={n \choose m}, c.n.d.
Góra
Kobieta Offline
PostNapisane: 30 sty 2017, o 10:14 
Użytkownik

Posty: 81
Premislav, Bardzo serdecznie Ci dziękuję! Wszystko przejrzyście wytłumaczone. Uratowałeś mi życie :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 9 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Dowód indukcyjny - zadanie 45  Macck  5
 Dowód indukcyjny - zadanie 26  Sirkami  8
 dowód indukcyjny - zadanie 8  niekumatyuczen  1
 Dowód indukcyjny - zadanie 41  Alpha_PL  3
 dowód indukcyjny - zadanie 17  Geniusz  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl