Indukcja w symbolu Newtona

[kaetae]

Udowodnij, że liczba \(\displaystyle{ k}\)-elementowych podzbiorów zbioru \(\displaystyle{ n}\)-elementowego wynosi \(\displaystyle{ {n\choose k}}\)

Dowód poprowadzę indukcyjnie.

Baza indukcji dla \(\displaystyle{ k = 1}\)
Skoro \(\displaystyle{ k = 1}\) to \(\displaystyle{ {n\choose 1} = n}\) i jest to prawda, ponieważ w zbiorze \(\displaystyle{ n}\) elementowym jest \(\displaystyle{ n}\) singletonów.

Krok indukcyjny dla \(\displaystyle{ k+1}\):

\(\displaystyle{ {n\choose k+1} = \frac{n!}{\left( k+1\right)! \left( n-k-1\right)!}}\)

Jakaś podpowiedź co dalej? Próbowałem skorzystać z tego, że:
\(\displaystyle{ {n\choose k+1} = {n\choose k } \cdot \frac{n-k}{k+1}}\)
ale za dużo mi to nie mówi.

[Premislav]

Wskazówka: spróbuj wykazać (np. poprzez interpretację kombinatoryczną albo algebraiczną zabawę z silniami), że
\(\displaystyle{ {n+1 \choose k+1}={n \choose k}+{n \choose k+1}}\)
i wykorzystaj tę własność w drugim kroku indukcyjnym.

-- 15 paź 2016, o 18:15 --

Wtedy oczywiście drugi krok indukcyjny nie działa dla \(\displaystyle{ k=0}\), ale to akurat trywialne do wyjaśnienia, bo liczba podzbiorów zeroelementowych zbioru \(\displaystyle{ n}\)-elementowego to zawsze \(\displaystyle{ 1}\), bo zbiór pusty jest jeden.

[kaetae]

Nie do końca wiem czemu ma mi pomóc \(\displaystyle{ {n+1 \choose k+1}}\)? Skoro indukcję robie po \(\displaystyle{ k}\), a \(\displaystyle{ n}\) jest liczbą, której teoretycznie nie ruszam?

[a4karo]

Dlatego to zadanie lepiej robi sie indukcją po \(\displaystyle{ n}\). Założenie indukcyjne jest wtedy takie
Każdy zbiór \(\displaystyle{ n}\)-elementowy ma \(\displaystyle{ \binom{n}{k}}\) podzbiorów \(\displaystyle{ k}\)-elementowych dla dowolnego \(\displaystyle{ k=0,1,\dots,n}\).

[Premislav]

A to źle spojrzałem, przepraszam, nie widziałem, że robisz indukcję po \(\displaystyle{ k}\), miałem inny pomysł, właśnie taki, jak napisał Pan a4karo.

Szczerze powiedziawszy, nie umiem tutaj przeprowadzić indukcji po samym \(\displaystyle{ k}\).

Najprościej to zrobić bez indukcji, tylko zliczając:
mamy dowolny zbiór n-elementowy. Wybieramy \(\displaystyle{ k}\) liczb z tego zbioru na
\(\displaystyle{ n(n-1)\dots (n-k+1)}\) sposobów, zaś \(\displaystyle{ n(n-1)\dots (n-k+1)= \frac{n!}{(n-k)!}}\)
Zauważmy jednak, że w ten sposób braliśmy pod uwagę kolejność, a każde dwa zbiory o równych elementach są równe (i są one równe tylko wtedy, gdy mają takie same elementy).
Liczba permutacji zbioru k-elementowego to \(\displaystyle{ k!}\) (i niezależnie od kolejności dostajemy ten sam podzbiór), więc wybierając jak wyżej, każdy zbiór policzyliśmy \(\displaystyle{ k!}\) razy.
Stąd otrzymujemy
\(\displaystyle{ \frac{n!}{(n-k)! k!}}\) podzbiorów k-elementowych zbioru n-elementowego, zaś
z definicji \(\displaystyle{ {n \choose k}=\frac{n!}{ k!(n-k)!} =\frac{n!}{(n-k)! k!}}\)

[kaetae]

Muszę zrobić to indukcyjnie. Wracając, tym razem do indukcji po \(\displaystyle{ n}\).

Baza indukcji
\(\displaystyle{ n=0}\) oraz \(\displaystyle{ k \le n}\) czyli \(\displaystyle{ k = 0}\)
Wtedy \(\displaystyle{ \binom{0}{0} = 1}\) czyli mamy 1 zbiór 0 elementowy - jest to \(\displaystyle{ \emptyset}\).

Krok indukcyjny dla \(\displaystyle{ n+1}\)
I tutaj mam jedną wątpliwość w \(\displaystyle{ \binom{n+1}{k+1}}\) czemu zwiększamy \(\displaystyle{ k}\)?

[Jan Kraszewski]

Ja to bym robił indukcję po samym \(\displaystyle{ n}\), a \(\displaystyle{ k}\) zostawił w spokoju:

Dlatego to zadanie lepiej robi sie indukcją po \(\displaystyle{ n}\). Założenie indukcyjne jest wtedy takie
Każdy zbiór \(\displaystyle{ n}\)-elementowy ma \(\displaystyle{ \binom{n}{k}}\) podzbiorów \(\displaystyle{ k}\)-elementowych dla dowolnego \(\displaystyle{ k=0,1,\dots,n}\).

JK

[kaetae]

Wiemy, że \(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k} = 2^{n}}\)

Krok indukcyjny.

Załóżmy, że działa to dla dowolnego \(\displaystyle{ n \in \NN}\) i sprawdźmy dla \(\displaystyle{ n+1.}\)
Wiemy, że
\(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k} = 2^{n}}\)

\(\displaystyle{ \sum_{k=0}^{n+1} \binom{n+1}{k} = 2^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} = 2^{n} \cdot 2 =
\sum_{k=0}^{n} \binom{n+1}{k} + \binom{n+1}{n+1}}\)

Co daje ostatecznie
\(\displaystyle{ \sum_{k=0}^{n} \binom{n+1}{k}+1}\)

Coś mi się tutaj nie zgadza.. Mamy wtedy \(\displaystyle{ 2^{n} +1}\) zbiorów czyli coś mało. Z resztą - czy to w ogóle dobry pomysł? Próbuje łapać się różnych własności Symbolu Newtona ale wydaje mi się czasami, że chcę za bardzo to przekombinować.

[Premislav]

Załóżmy, że działa to dla dowolnego \(\displaystyle{ n \in \NN}\) i sprawdźmy dla \(\displaystyle{ n+1}\).

Ale co tu jeszcze sprawdzać, skoro działa dla dowolnego, starczy wziąć \(\displaystyle{ n:=n+1}\). [oczywiście to ironia]
Redakcja rozwiązania jest nie najlepsza, bo wygląda to tak, jakbyś zakładała tezę.

Poza tym skoro piszesz, że
\(\displaystyle{ \sum_{k=0}^{n+1} \binom{n+1}{k} = 2^{n+1}}\), to już de facto założyłaś tezę indukcyjną, co jest błędem krytycznym. Myślę, że z korzyścią dla Ciebie będzie, jeśli napiszę, jak to dokładnie zrobić.

Drugi krok indukcyjny: pokażemy, że jeśli dla pewnego \(\displaystyle{ n \in \NN}\) zachodzi
\(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}=2^n}\), to także
\(\displaystyle{ \sum_{k=0}^{n+1} \binom{n+1}{k}=2^{n+1}}\)
Otóż \(\displaystyle{ \sum_{k=0}^{n+1} \binom{n+1}{k}=1+ \sum_{k=1}^{n+1}\binom{n+1}{k}}\).
Następnie zastosujmy następujący lemat:
\(\displaystyle{ {n \choose k}+{n \choose k+1}={n+1 \choose k+1}}\)
-dowód pozostawiam jako ćwiczenie (możesz poszukać interpretacji kombinatorycznej lub rozpisać na wzory z silniami). A mianowicie:
\(\displaystyle{ \sum_{k=0}^{n+1} \binom{n+1}{k}=1+ \sum_{k=1}^{n+1}\binom{n+1}{k-1+1}=1+ \sum_{k=1}^{n+1}{n \choose k-1}+ \sum_{k=1}^{n+1}{n \choose k}=\\= 1+\sum_{k=0}^{n}{n \choose k}+ \sum_{k=1}^{n}{n \choose k}}\),
gdyż \(\displaystyle{ {n \choose n+1}=0}\)
i ostatecznie \(\displaystyle{ 1+\sum_{k=0}^{n}{n \choose k}+ \sum_{k=1}^{n}{n \choose k} =2 \sum_{k=0}^{n}{n \choose k}=2 \cdot 2^n=2^{n+1}}\).
W przedostatniej równości skorzystaliśmy z założenia indukcyjnego.

[kaetae]

Dzięki!

[Jan Kraszewski]

Udowodnij, że liczba \(\displaystyle{ k}\)-elementowych podzbiorów zbioru \(\displaystyle{ n}\)-elementowego wynosi \(\displaystyle{ {n\choose k}}\)

Dla \(\displaystyle{ n=0}\) masz pokazać, że zbiór zeroelementowy ma \(\displaystyle{ \binom{0}{0}}\) podzbiorów i to się zgadza.

Zakładasz teraz, że dla ustalonego \(\displaystyle{ n}\) prawdą jest, iż każdy zbiór \(\displaystyle{ n}\)-elementowy ma \(\displaystyle{ \binom{n}{k}}\) podzbiorów \(\displaystyle{ k}\)-elementowych dla dowolnego \(\displaystyle{ k=0,1,\dots,n}\). Chcesz pokazać, że

Każdy zbiór \(\displaystyle{ n+1}\)-elementowy ma \(\displaystyle{ \binom{n+1}{k}}\) podzbiorów \(\displaystyle{ k}\)-elementowych dla dowolnego \(\displaystyle{ k=0,1,\dots,n, n+1}\).

Zaczynasz od ustalenia dowolnego zbioru \(\displaystyle{ n+1}\)-elementowego \(\displaystyle{ A}\). Następnie ustalasz \(\displaystyle{ k}\) takie, że \(\displaystyle{ 0\le k\le n+1}\). Jeśli \(\displaystyle{ k=0}\), to koniec, bo zeroelementowy podzbiór zbioru \(\displaystyle{ A}\) jest jeden, czyli jest ich \(\displaystyle{ \binom{n+1}{0}}\) (to niegramatycznie napisane, ale trudno). Jeśli \(\displaystyle{ k\ge 1}\), to ze zbioru \(\displaystyle{ A}\) wyrzucasz jeden element \(\displaystyle{ a\in A}\). Dostajesz zbiór \(\displaystyle{ A_1=A\setminus\{a\}}\), który ma \(\displaystyle{ n}\) elementów. Teraz zauważasz, \(\displaystyle{ k}\)-elementowe podzbiory zbioru \(\displaystyle{ A}\) dzielą się na te, do których \(\displaystyle{ a}\) należy i na te, do których \(\displaystyle{ a}\) nie należy. Tych pierwszych jest tyle samo, co \(\displaystyle{ k-1}\)-elementowych podzbiorów \(\displaystyle{ A_1}\) (dlaczego?), a tych na mocy założenia indukcyjnego jest [uzupełnij], zaś tych drugich jest tyle samo, co \(\displaystyle{ k}\)-elementowych podzbiorów \(\displaystyle{ A_1}\) (dlaczego?), a tych na mocy założenia indukcyjnego jest [uzupełnij]. Teraz wystarczy skorzystać ze wskazówki Premislava (po odpowiednim podstawieniu):

Wskazówka: spróbuj wykazać (np. poprzez interpretację kombinatoryczną albo algebraiczną zabawę z silniami), że
\(\displaystyle{ {n+1 \choose k+1}={n \choose k}+{n \choose k+1}}\)
i wykorzystaj tę własność w drugim kroku indukcyjnym.

JK

[kaetae]

Dobra, mam przykładowy zbiór \(\displaystyle{ A = \left\{ 1,2,3\right\}}\) oraz \(\displaystyle{ A_{1} = \{ 2,3\}}\)

Teraz podzbioru zbioru \(\displaystyle{ A}\) to:
\(\displaystyle{ \emptyset \\
\left\{ 1\right\}\left\{ 2\right\} \left\{ 3\right\}\\
\left\{ 1,2\right\}\left\{ 1,3\right\} \left\{ 2,3\right\}}\)
\(\displaystyle{ \left\{ 1,2,3\right\}}\) o mocy \(\displaystyle{ n+1}\)

Oraz zbioru \(\displaystyle{ A_{1}}\)
\(\displaystyle{ \emptyset \\
\left\{ 2\right\}\left\{ 3\right\} \\
\left\{ 2, 3\right\}}\)

I widzę, że jak w zbiorze \(\displaystyle{ A_{1}}\) na \(\displaystyle{ k-1}\) pozycji jest (np. w przypadku \(\displaystyle{ k = 2}\)) \(\displaystyle{ 2}\) elementy to w \(\displaystyle{ A}\) na tej pozycji są \(\displaystyle{ 2}\) elementy z cyfrą, którą wykluczyłem. Ale prawdę mówiąc nie wiem czemu?

Tych pierwszych jest tyle samo, co \(\displaystyle{ k-1}\)-elementowych podzbiorów \(\displaystyle{ A_{1}}\) (dlaczego?), a tych na mocy założenia indukcyjnego jest [uzupełnij],

\(\displaystyle{ \binom{n}{k-1}}\)?

zaś tych drugich jest tyle samo, co \(\displaystyle{ k}\)-elementowych podzbiorów \(\displaystyle{ A_1}\) (dlaczego?), a tych na mocy założenia indukcyjnego jest [uzupełnij].

\(\displaystyle{ \binom{n}{k}}\)?

[Jan Kraszewski]

Dobra, mam przykładowy zbiór \(\displaystyle{ A = \left\{ 1,2,3\right\}}\) oraz \(\displaystyle{ A_{1} = \{ 2,3\}}\)

Teraz podzbioru zbioru \(\displaystyle{ A}\) to:
\(\displaystyle{ \emptyset \\
\left\{ 1\right\}\left\{ 2\right\} \left\{ 3\right\}\\
\left\{ 1,2\right\}\left\{ 1,3\right\} \left\{ 2,3\right\}}\)
\(\displaystyle{ \left\{ 1,2,3\right\}}\) o mocy \(\displaystyle{ n+1}\)

Oraz zbioru \(\displaystyle{ A_{1}}\)
\(\displaystyle{ \emptyset \\
\left\{ 2\right\}\left\{ 3\right\} \\
\left\{ 2, 3\right\}}\)

I widzę, że jak w zbiorze \(\displaystyle{ A_{1}}\) na \(\displaystyle{ k-1}\) pozycji jest (np. w przypadku \(\displaystyle{ k = 2}\)) \(\displaystyle{ 2}\) elementy to w \(\displaystyle{ A}\) na tej pozycji są \(\displaystyle{ 2}\) elementy z cyfrą, którą wykluczyłem. Ale prawdę mówiąc nie wiem czemu?

Zauważ, że każdy \(\displaystyle{ k}\)-elementowy podzbiór \(\displaystyle{ A}\) jest albo \(\displaystyle{ k}\)-elementowym podzbiorem \(\displaystyle{ A_1}\), albo bierze się z \(\displaystyle{ k-1}\)-elementowego podzbioru \(\displaystyle{ A_1}\) poprzez dołożenie do niego \(\displaystyle{ 1}\).

Tych pierwszych jest tyle samo, co \(\displaystyle{ k-1}\)-elementowych podzbiorów \(\displaystyle{ A_{1}}\) (dlaczego?), a tych na mocy założenia indukcyjnego jest [uzupełnij],

\(\displaystyle{ \binom{n}{k-1}}\)?

Tak.

zaś tych drugich jest tyle samo, co \(\displaystyle{ k}\)-elementowych podzbiorów \(\displaystyle{ A_1}\) (dlaczego?), a tych na mocy założenia indukcyjnego jest [uzupełnij].

\(\displaystyle{ \binom{n}{k}}\)?

Tak.

JK

[kaetae]

Dobra, czyli mam:

\(\displaystyle{ \binom{n+1}{k} = \binom{n+1}{k+1-1} = \binom{n}{k-1} + \binom{n}{k}}\)

Co kończy dowód?

[Jan Kraszewski]

Wolałbym raczej w druga stronę: wobec tego podzbiorów \(\displaystyle{ k}\)-elementowych jest \(\displaystyle{ \binom{n}{k-1} + \binom{n}{k}=\binom{n+1}{k+1-1} =\binom{n+1}{k},}\) co należało dowieść.

JK