Matematyka.pl

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?

Ustal `k` i rób indukcję po `n`

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.

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}}\)

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.

Pomyśl jak powinien wyglądać pierwszy krok

\(\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ę?)

\(\displaystyle{ {0 \choose k} = \frac{0!}{k!(k-0)!}}\)

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:

Bran pisze: 20 kwie 2020, o 11:16 \(\displaystyle{ k}\) jest liczbą naturalną nie większą od \(\displaystyle{ n}\)

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?

Nie każda indukcja musi sure zaczynać od zera. Tutaj akurat musisz wystartowac od `n=k`

\(\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.

\(\displaystyle{ \sum_{m=0}^{0} {m \choose k} = {0 \choose 0} = 1}\)

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=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)?

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)?

Bo \(\displaystyle{ \sum_{m=k}^{k} {m \choose k} = {k \choose k} = 1 = {k+1 \choose k+1} }\)?

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.

Bran pisze: 20 kwie 2020, o 13:07 \(\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.

A \(\displaystyle{ \sum_{m=0}^{0} {m \choose k} = {0 \choose k} }\) i dla `k>0` ma mało sensu