Udowodnij kombinatorycznie następującą tożsamość:
\(\displaystyle{ \sum_{k=m}^{n} {k \choose m}= {n+1 \choose m+1}}\)
Należy opisać pewną sytuację, zadać pytanie typu "ile czegoś jest" , a następnie odpowiedzieć na nie na dwa sposoby uzyskując w ten sposób lewą i prawą stronę równości.
Proszę o sprawdzenie poniższego rozwiązania:
Prawa strona to ilość sposobów wyboru \(\displaystyle{ m+1}\) osób z grona \(\displaystyle{ n+1}\) osób. Aby uzasadnić lewą stronę numerujemy te osoby od jeden do \(\displaystyle{ n+1}\) i niech osoba o numerze \(\displaystyle{ n+1}\) będzie liderem. Ile jest zbiorów \(\displaystyle{ m+1}\) osobowych z liderem? \(\displaystyle{ {n \choose m}}\). Następnie usuwamy lidera i patrzymy na zbiór \(\displaystyle{ n}\)-elementowy i niech osoba o numerze \(\displaystyle{ n}\) będzie nowym liderem. Ile jest zbiorów \(\displaystyle{ m+1}\) osobowych z nowym liderem,a bez starego lidera? \(\displaystyle{ {n-1 \choose m}}\). Następnie usuwamy nowego lidera, i ze zbioru \(\displaystyle{ n-1}\)-osobowego osoba o numerze \(\displaystyle{ n-1}\) staje się nowym liderem. Na ile sposobów możemy wybrać \(\displaystyle{ m+1}\)-elementową grupę z nowym liderem? \(\displaystyle{ {n-2 \choose m}}\) i tak dalej, usuwając kolejne osoby dojdziemy do ostatniej grupy \(\displaystyle{ m+1}\) elementowej, w której osoba o numerze \(\displaystyle{ m+1}\) będzie liderem i wtedy ze zbioru \(\displaystyle{ m}\)-osobowego wybieramy \(\displaystyle{ m}\) osób, które razem z tym liderem stworzą ostatnią grupę \(\displaystyle{ m+1}\)-osobową. Sumując te sposoby otrzymamy lewą stronę. Tutaj wszystko było liczone dokładnie raz bo najpierw liczyliśmy na ile sposobów można wybrać grupę z liderem nr.\(\displaystyle{ n+1}\), potem bez lidera nr. \(\displaystyle{ n+1}\),a z liderem nr. \(\displaystyle{ n}\),potem bez lidera nr. \(\displaystyle{ n+1}\) i \(\displaystyle{ n}\), a z liderem nr.\(\displaystyle{ n-1}\) i tak dalej.
Czy tak jest dobrze?