Własność symbolu Newtona. Dowód.

[myszka9]

\(\displaystyle{ \sum_{r=0}^{n} {r \choose k} = {n+1 \choose k+1}}\)

DOWÓD : (a raczej nieudolna próba)

\(\displaystyle{ X = \{1,2,...,n,n+1\}}\)

\(\displaystyle{ L : {0 \choose k} + {1 \choose k} + {2 \choose k} +...+ {n \choose k}+ {n+1 \choose k}}\)
\(\displaystyle{ A \subseteq X , |A|=k , |X|=n+1}\)
\(\displaystyle{ j=min(A)}\)

Podzbiory k-elementowe, takie, że \(\displaystyle{ 1=min(A)}\), to wszystkie podzbiory zawierające el 1.
Liczba takich podzbiorów : \(\displaystyle{ {n+1 \ choose k}}\)

Podzbiory k-elemntowe, takie, że \(\displaystyle{ 2=min(A)}\), to wszystkie podzbiory zawierające el 2 i nie zawierające el 1.
Liczba takich podzbiorów : \(\displaystyle{ {n+2-1 \choose k} = {n+1 \choose k}}\)

Podzbiory k-elemntowe, tak, że \(\displaystyle{ 3=min(A)}\), to wszystkie podzbiory zawierające el.3 i nie zawierające el.2 i 1
Liczba takich podzbiorów : \(\displaystyle{ {n \choose k}}\)

\(\displaystyle{ 4=min(A)}\)
\(\displaystyle{ {n+4-3-2-1 \choose k} = {n-2 \choose k}}\)

\(\displaystyle{ 5=min(A)}\)
\(\displaystyle{ {n+5-4-3-2-1 \choose k} = {n-5 \choose k}}\)

\(\displaystyle{ 6=min(A)}\)
\(\displaystyle{ {n+6-5-4-3-2-1 \choose k} = {n-9 \choose k}}\)

...
\(\displaystyle{ n=min(A)}\)
\(\displaystyle{ {n+n-(n-1)-...-1 \choose k} = {n+n-n+1-...-1 \choose k}}\)

I co dalej? Nie mam pomysłu. Podpowiedź do zadania było użycie funkcji : j=min(A)

[rafalpw]

P: Liczba \(\displaystyle{ \left( k+1\right)}\)-elementowych podzbiorów zbioru \(\displaystyle{ \left( n+1\right)}\)-elementowego.
Spróbuj sprytnie zapisać lewą stronę, żeby była równoliczna z prawą, czyli uzależnij liczbę \(\displaystyle{ \left( k+1\right)}\)-elementowych podzbiorów zbioru \(\displaystyle{ \left( n+1\right)}\)-elementowego z zapisem po lewej stronie.

[myszka9]

czyli dobrze kombinuje?

[rafalpw]

Trochę pokręciłaś. Rozważ takie zbiory:

\(\displaystyle{ X=\left[ n+1\right]}\)

\(\displaystyle{ A_r=\left\{ S \subseteq X:\left| S\right|=k+1 \wedge \max S=r+1 \right\}}\)

Od razu widać, że liczba \(\displaystyle{ \left( k+1\right)}\)-elementowych podzbiorów \(\displaystyle{ X}\) wynosi \(\displaystyle{ {n+1 \choose k+1}}\)

Teraz spróbuj z tym połączyć rodzinę zbiorów \(\displaystyle{ A_r}\)

[myszka9]

Tylko, że mam zrobić ten dowód, że \(\displaystyle{ j=min(A)}\)
Umiałbyś to jakoś wytłumaczyć?

[rafalpw]

Myślę, że wersja z \(\displaystyle{ \max}\) jest prostsza i bardziej intuicyjna.

Wskazówka do połączenia obydwu stron.\(\displaystyle{ L}\): zbiór podzbiorów:
1) \(\displaystyle{ k+1}\) elementowych takich, że \(\displaystyle{ \max A=2}\)
2) \(\displaystyle{ k+1}\) elementowych takich, że \(\displaystyle{ \max A=3}\)
3) \(\displaystyle{ k+1}\) elementowych takich, że \(\displaystyle{ \max A=4}\)
...

[myszka9]

Wskazówka do Twojego sposobu?

[rafalpw]

Tak.

[myszka9]

Hm.. nie rozumiem tego rozpisania wyżej

[rafalpw]

Na ile sposobów można wybrać \(\displaystyle{ \left( k+1\right)}\)-elementowy podzbiór\(\displaystyle{ A}\) zbioru \(\displaystyle{ \left[ n+1\right]}\) tak, aby \(\displaystyle{ \max A=r+1}\) ?

[myszka9]

Dziękuję Rafał za nowy pomysł, ale nie skorzystam.
Jakbyś mógł, to zerknij na to :

\(\displaystyle{ \sum_{r=0}^{n} {r \choose k} = {n+1 \choose k+1}}\)
L:\(\displaystyle{ {0 \choose k} + {1 \choose k} + ... + {n \choose k}}\)

|X|=n+1
\(\displaystyle{ |A|=k+1}\)
\(\displaystyle{ j=min(A)}\)

\(\displaystyle{ j=1=min(A)}\)
Podzbiory k-elemntowe, takie, że \(\displaystyle{ 1=min(A)}\), to wszystkie podzbiory zawierające ten element.
Elemntów w zbiorze X jest \(\displaystyle{ n+1}\), więc posiadając gwarantując sobie w zbiorze el 1, możemy wybrać ich na \(\displaystyle{ {n \choose k}}\) sposobów. Patrząc na naszą lewą stronę nierówności, jest to ostatni elemnt.

\(\displaystyle{ j=2=min(A)}\)
Podzbiorów k-elemntowych, takich, że \(\displaystyle{ 2=min(A)}\), to wszystke podzbiory zawierające 2 i nie zawierające 1. Możemy je wybrać \(\displaystyle{ {n -1 \choose k}}\) sposobów.

....

\(\displaystyle{ j=n-k+1=min(A)}\)
Te podzbiory możemy wybrać na \(\displaystyle{ {k \choose k}}\) sposobów.
To nie jest ostatni elemnt naszej sumy, jednak każdy zbiór zawierający większy element minimalny, będzie miał wartość 0, gdyż nie możemy wybrać więcej elemntów, niż mamy w zbiorze.
Z prawa dodawania wychodzi równość z prawą stroną.

Ogólny wzór na \(\displaystyle{ A_j = {n+1-j \choose k} , j\in\{1,...,n+1\}}\)



Proszę o takie merytoryczne sprawdzenie.

[rafalpw]

To nie jest ostatni elemnt naszej sumy, jednak każdy zbiór zawierający większy element minimalny, będzie miał wartość 0, gdyż nie możemy wybrać więcej elementów, niż mamy w zbiorze.

To się zgadza.

Z prawa dodawania wychodzi równość z prawą stroną.

To wymaga wyjaśnienia. To właśnie próbujesz pokazać. Myślę, że to nie jest takie oczywiste.

Ogólnie rozumowanie dobre. Nie wiem, czemu nie spodobał Ci się mój sposób, biorąc pod uwagę, że jest prawie identyczny.

[myszka9]

Jest to sposób zliczenia wszystkich \(\displaystyle{ k+1}\) elementowych podzbiorów ze zbioru \(\displaystyle{ n+1}\) elementowego, ze względu na parametr \(\displaystyle{ r = n+1-j}\) , gdzie j jest elementem minimalnym pozbioru. Zbiór \(\displaystyle{ n+1}\) został podzielony na podzbiory ze względu właśnie na element minimalny.

?

[rafalpw]

Zbiór \(\displaystyle{ n+1}\) został podzielony na podzbiory ze względu właśnie na element minimalny.

To zdanie było kluczowe. Wszystkie \(\displaystyle{ \left( k+1\right)}\)-elementowe podzbiory można podzielić na:
\(\displaystyle{ \left( k+1\right)}\) -elementowe podzbiory, których elementem najmniejszym jest \(\displaystyle{ 1}\)
\(\displaystyle{ \left( k+1\right)}\) -elementowe podzbiory, których elementem najmniejszym jest \(\displaystyle{ 2}\)
...

Warto jeszcze dopowiedzieć, że te zbiory podzbiorów są rozłączne i dlatego można zastosować regułę dodawania.