Własności dwumianu newtona
-
- Użytkownik
- Posty: 421
- Rejestracja: 19 lut 2019, o 19:30
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 163 razy
- Pomógł: 16 razy
Własności dwumianu newtona
Niech \(\displaystyle{ n,k \in \NN, \; n \ge k.}\) Sprawdź, że \(\displaystyle{ {k \choose k} + {k+1 \choose k} + \ldots + {n \choose k} = {n+1 \choose k+1} }\)
W jaki sposób należy przeprowadzić indukcję, gdy mamy do czynienia z dwoma zmiennymi?
W jaki sposób należy przeprowadzić indukcję, gdy mamy do czynienia z dwoma zmiennymi?
- Janusz Tracz
- Użytkownik
- Posty: 4065
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1392 razy
Re: Własności dwumianu newtona
Można też zauważyć, że suma liczb na takiej kolorowej dżdżownicy położonej na daje liczbę z jej końca (powiedzmy z głowy czyli tą w kolorowym kółku). Części \(\displaystyle{ {k \choose k} + {k+1 \choose k} + \ldots + {n \choose k} }\) leży na tułowiu kolorowej dżdżownicy a \(\displaystyle{ {n+1 \choose k+1} }\) leży na jej głowie (w kółku). Krok indukcyjny wtedy dobrze widać na przykładzie czerwonej dżdżownicy \(\displaystyle{ 1+1+1=3}\), można na nią patrzeć jak na wydłużoną dżdżownice \(\displaystyle{ 1+1=2}\) itd. sama dobową trójkąta Pascala zapewnia o tym, że postulowana równość zachodzi.
PS musisz patrzeć na rysunek z linku inaczej ten opis będzie dość enigmatyczny.
PS musisz patrzeć na rysunek z linku inaczej ten opis będzie dość enigmatyczny.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Własności dwumianu newtona
Można też napisać interpretację kombinatoryczną. Chcemy wybrać z drużyny \(\displaystyle{ n+1}\) zawodników drużynę \(\displaystyle{ k+1}\) osób. Z jednej strony jasne jest, że można to uczynić na \(\displaystyle{ {n+1\choose k+1}}\) sposobów. Z drugiej strony możemy ustawić zawodników w szeregu i spojrzeć na ostatniego, którego wybierzemy. Będzie on miał w tym szeregu numer \(\displaystyle{ i+1}\) dla pewnego \(\displaystyle{ i\in \left\{k, k+1\ldots n\right\}}\). Wobec tego spośród osób poprzedzających go w szeregu musimy wybrać do drużyny \(\displaystyle{ {i\choose k}}\) osób, gdzie \(\displaystyle{ i=k, k+1\ldots n}\).
Dodano po 1 minucie 35 sekundach:
A jeśli koniecznie chcesz indukcję, to wskazówka do kroku indukcyjnego: \(\displaystyle{ {r\choose k}+{r\choose k+1}={r+1\choose k+1}}\)
Dodano po 1 minucie 35 sekundach:
A jeśli koniecznie chcesz indukcję, to wskazówka do kroku indukcyjnego: \(\displaystyle{ {r\choose k}+{r\choose k+1}={r+1\choose k+1}}\)
-
- Użytkownik
- Posty: 421
- Rejestracja: 19 lut 2019, o 19:30
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 163 razy
- Pomógł: 16 razy
Re: Własności dwumianu newtona
Weźmy ustalone \(\displaystyle{ k \in \NN}\) takie, że \(\displaystyle{ k \le n}\).
Sprawdźmy dla \(\displaystyle{ n = 0}\)
\(\displaystyle{ {0 \choose 0} = 1 = {0+1 \choose 0+1} }\)
Założenia indukcyjne: Ustalmy dowolne \(\displaystyle{ n \in \NN,}\) takie że \(\displaystyle{ {k \choose k} + {k+1 \choose k} + \ldots + {n \choose k} = {n+1 \choose k+1}}\)
Sprawdźmy czy: \(\displaystyle{ {k \choose k} + {k+1 \choose k} + \ldots + {n \choose k} + {n+1 \choose k} = {n+2 \choose k+1}}\)
\(\displaystyle{ {k \choose k} + {k+1 \choose k} + \ldots + {n \choose k} + {n+1 \choose k} = {n+1 \choose k+1} + {n+1 \choose k} = {n+2 \choose k+1}}\)
Pierwsza równość wynika z założenia indukcyjnego, a druga wynika z własności jaką podał Premislav.
Sprawdźmy dla \(\displaystyle{ n = 0}\)
\(\displaystyle{ {0 \choose 0} = 1 = {0+1 \choose 0+1} }\)
Założenia indukcyjne: Ustalmy dowolne \(\displaystyle{ n \in \NN,}\) takie że \(\displaystyle{ {k \choose k} + {k+1 \choose k} + \ldots + {n \choose k} = {n+1 \choose k+1}}\)
Sprawdźmy czy: \(\displaystyle{ {k \choose k} + {k+1 \choose k} + \ldots + {n \choose k} + {n+1 \choose k} = {n+2 \choose k+1}}\)
\(\displaystyle{ {k \choose k} + {k+1 \choose k} + \ldots + {n \choose k} + {n+1 \choose k} = {n+1 \choose k+1} + {n+1 \choose k} = {n+2 \choose k+1}}\)
Pierwsza równość wynika z założenia indukcyjnego, a druga wynika z własności jaką podał Premislav.
-
- Użytkownik
- Posty: 421
- Rejestracja: 19 lut 2019, o 19:30
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 163 razy
- Pomógł: 16 razy
Re: Własności dwumianu newtona
\(\displaystyle{ {0 \choose k} = \frac{0!}{k!(k-0)!}}\)
Tutaj stanąłem, jeżeli nie mogę skorzystać z tego co napisałem. Bo skoro \(\displaystyle{ k}\) jest liczbą naturalną nie większą od \(\displaystyle{ n}\), to moja propozycja z wyżej wyczerpuje chyba wszystkie możliwości (czy się mylę?)
Tutaj stanąłem, jeżeli nie mogę skorzystać z tego co napisałem. Bo skoro \(\displaystyle{ k}\) jest liczbą naturalną nie większą od \(\displaystyle{ n}\), to moja propozycja z wyżej wyczerpuje chyba wszystkie możliwości (czy się mylę?)
- Janusz Tracz
- Użytkownik
- Posty: 4065
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1392 razy
Re: Własności dwumianu newtona
Ten napis ma sens jedynie dla \(\displaystyle{ k=0}\) napisanie go bez jakichkolwiek założeń jest błędem. Poza tym raczej się tu nie przyda. Skup się raczej na:\(\displaystyle{ {0 \choose k} = \frac{0!}{k!(k-0)!}}\)
No właśnie. Dlatego przy ustalonym \(\displaystyle{ k}\) nie wolno Ci podstawiać \(\displaystyle{ n<k}\). Przy ustalonym \(\displaystyle{ k}\) pierwszym \(\displaystyle{ n}\) jaki można podstawić jest \(\displaystyle{ n=k}\). Lepiej to widać jak się ten wzór napiszę tak:
\(\displaystyle{ \sum_{m=k}^{n} {m \choose k}= {n+1 \choose k+1} }\)
indukcję robisz po \(\displaystyle{ n}\) które jest większe lub równe ustalonemu \(\displaystyle{ k}\). Co zatem wstawisz do powyższego wzoru sprawdzając bazę indukcji?
-
- Użytkownik
- Posty: 421
- Rejestracja: 19 lut 2019, o 19:30
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 163 razy
- Pomógł: 16 razy
Re: Własności dwumianu newtona
\(\displaystyle{ \sum_{m=0}^{0} {m \choose k} = {0 \choose 0} = 1}\)
Z drugiej strony \(\displaystyle{ \sum_{m=k}^{1} {m \choose k} = {1 \choose 0} + {1 \choose 1} = 2}\)
Czyli albo ja coś źle zrobiłem albo twierdzenie nie jest zawsze prawdziwe.
Z drugiej strony \(\displaystyle{ \sum_{m=k}^{1} {m \choose k} = {1 \choose 0} + {1 \choose 1} = 2}\)
Czyli albo ja coś źle zrobiłem albo twierdzenie nie jest zawsze prawdziwe.
- Janusz Tracz
- Użytkownik
- Posty: 4065
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1392 razy
Re: Własności dwumianu newtona
Nie o to chodziło. Twierdzenie jest ok. Tak jak proponowałem wcześniej i a4karo tu wstawiasz \(\displaystyle{ n=k}\) a nie \(\displaystyle{ k=0}\). I to podstawienie robisz do wzoru:\(\displaystyle{ \sum_{m=0}^{0} {m \choose k} = {0 \choose 0} = 1}\)
\(\displaystyle{ \sum_{m=k}^{n} {m \choose k}= {n+1 \choose k+1} }\)
pisząc
\(\displaystyle{ \sum_{m=k}^{k} {m \choose k}= {k+1 \choose k+1}}\)
to co napisałem linijkę wyżej to prawda (dlaczego)?
-
- Użytkownik
- Posty: 421
- Rejestracja: 19 lut 2019, o 19:30
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 163 razy
- Pomógł: 16 razy
Re: Własności dwumianu newtona
Bo \(\displaystyle{ \sum_{m=k}^{k} {m \choose k} = {k \choose k} = 1 = {k+1 \choose k+1} }\)?Janusz Tracz pisze: ↑20 kwie 2020, o 13:14 \(\displaystyle{ \sum_{m=k}^{k} {m \choose k}= {k+1 \choose k+1}}\)
to co napisałem linijkę wyżej to prawda (dlaczego)?
- Janusz Tracz
- Użytkownik
- Posty: 4065
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1392 razy
Re: Własności dwumianu newtona
Tak. I to jest baza indukcji w tym zadaniu.
(filozoficzna rozkmina) W pewnym sensie robiąc to zadanie zrobiłeś \(\displaystyle{ \aleph_0}\) dowodów indukcyjnych każdy z nich zaczynał się od trochę większego \(\displaystyle{ k}\). Trochę tak jakby udowodnić po kolei wzory:
\(\displaystyle{ \sum_{m=1}^{n} {m \choose 1}= {n+1 \choose 1+1} }\)
\(\displaystyle{ \sum_{m=2}^{n} {m \choose 2}= {n+1 \choose 2+1}}\)
\(\displaystyle{ \sum_{m=3}^{n} {m \choose 3}= {n+1 \choose 3+1} }\)
...
ale to akurat nie dziwi ze względu na postać tego twierdzenie.
(filozoficzna rozkmina) W pewnym sensie robiąc to zadanie zrobiłeś \(\displaystyle{ \aleph_0}\) dowodów indukcyjnych każdy z nich zaczynał się od trochę większego \(\displaystyle{ k}\). Trochę tak jakby udowodnić po kolei wzory:
\(\displaystyle{ \sum_{m=1}^{n} {m \choose 1}= {n+1 \choose 1+1} }\)
\(\displaystyle{ \sum_{m=2}^{n} {m \choose 2}= {n+1 \choose 2+1}}\)
\(\displaystyle{ \sum_{m=3}^{n} {m \choose 3}= {n+1 \choose 3+1} }\)
...
ale to akurat nie dziwi ze względu na postać tego twierdzenie.
-
- Użytkownik
- Posty: 22206
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3753 razy
Re: Własności dwumianu newtona
A \(\displaystyle{ \sum_{m=0}^{0} {m \choose k} = {0 \choose k} }\) i dla `k>0` ma mało sensu