Udowodnij tożsamości.

[czekoladowy]

Udowodnij tożsamości stosując własności kombinacji.
1. \(\displaystyle{ {n \choose k} = {n \choose n-k }}\)
2. \(\displaystyle{ {n \choose k } + {n \choose k+1}= {n+1 \choose k+1}}\)
3. \(\displaystyle{ \sum_{i=0}^n {n \choose i} =2^n}\)

[theoldwest]

1. Są to dwa możliwe wybory \(\displaystyle{ k}\) elementów z \(\displaystyle{ n}\) elementów - raz przez wskazanie \(\displaystyle{ k}\) z \(\displaystyle{ n}\) elementów, a raz przez odrzucenie pozostałych \(\displaystyle{ n-k}\) elementów

2. Spośród \(\displaystyle{ n+1}\) elementów wyróżnijmy tylko jeden. Jedna strona to wybór \(\displaystyle{ k+1}\) elementów ze wszystkich \(\displaystyle{ n+1}\) elementów, lewa strona to taki sam wybór gdyż - \(\displaystyle{ {n \choose k+1}}\) oznacza wybór \(\displaystyle{ k+1}\) elementów spośród wszystkich \(\displaystyle{ n}\) elementów (odrzucając ten jeden wyróżniony), \(\displaystyle{ {n \choose k }{1 \choose 1 }={n \choose k }}\) to wybór \(\displaystyle{ k+1}\) elementów wśród których dokładnie jeden jest tym wyróżnionym elementem, jasne jest, że te wybory są niezależne i wyczerpują wszystkie możliwe przypadki (albo wśród wybranych \(\displaystyle{ k+1}\) elementów jest ten wyróżniony element albo go nie ma) stąd ta suma

3. Zliczanie podzbiorów zbioru \(\displaystyle{ n}\)-elementowego. Lewa strona to w oczywisty sposób liczba wszystkich podzbiorów zbioru \(\displaystyle{ n}\) - elementowego, istnieją podzbiory \(\displaystyle{ 0,...,n}\) elementowe i tylko takie, poza tym podzbiór \(\displaystyle{ k}\) - elementowy nie jest podzbiorem \(\displaystyle{ j}\) elementowym dla \(\displaystyle{ j \neq k}\) stąd ta suma, prawa też jest liczbą wszystkich podzbiorów, gdyż - jest liczbą ciągów \(\displaystyle{ n}\)- wyrazowych o zbiorze wartości dwuelementowym (bo albo dany element należy do danego podzbioru albo do niego nie należy stąd mamy dwie wartości), jasne jest, że każdy taki ciąg jest w bijekcji z danym podzbiorem (wskazuje elementy, które do niego należą), poza tym każdy element może być/nie być z dowolnym innym elementem w danym podzbiorze stąd nie ma ograniczeń na ich rozlokowanie i stąd ta równość