Uzasadnić taką tożsamość: \(\displaystyle{ \sum^{n}_{k=0} {n+k \choose k} = {2n+1 \choose n} \ n \geq 0}\)
Próbowałam rozpisać lewą stronę jednak niewiele to daje w porównaniu do prawej, jakaś wskazówka jak się za to zabrać, z jakiego wzoru skorzystać przy udowadnianiu takich tożsamości z symbolem Newtona?
Tożsamość z symbolem Newtona
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Tożsamość z symbolem Newtona
Zapiszmy lewą i prawą stronę inaczej, korzystając z \(\displaystyle{ {r\choose k}={r\choose r-k}}\) i od razu zrobi się klarowniej:
\(\displaystyle{ \sum_{k=0}^{n}{n+k\choose n}={2n+1\choose n+1}}\)
Teraz interpretacja kombinatoryczna: jesteśmy Przemkiem-mądralą w 2000 roku i nikt nas nie lubi, więc czytamy suplement encyklopedii PWN z lat osiemdziesiątych, zamiast bawić się z rówieśnikami. Chcemy przeczytać \(\displaystyle{ n+1}\) spośród \(\displaystyle{ 2n+1}\) stron suplementu.
Z jednej strony możemy oczywiście wybrać strony do przeczytania na \(\displaystyle{ {2n+1\choose n+1}}\) sposobów. Z drugiej strony możemy sobie na to popatrzeć tak: mamy \(\displaystyle{ 2n+1}\) stron i w naszym wyborze stron do czytania możemy patrzeć na ostatnią stronę, która zostanie wybrana do przeczytania. Skoro mamy przeczytać \(\displaystyle{ n+1}\) spośród \(\displaystyle{ 2n+1}\), to będzie ona stroną (nie wg jakichś oznaczeń, że do numeracji wchodzą strony tytułowe, jakieś przedmowy od redakcji itd.) numer \(\displaystyle{ n+k+1}\) dla pewnego \(\displaystyle{ k\in\left\{ 0,1,\ldots n\right\}}\). Będzie tak, ponieważ jeśli mamy przeczytać \(\displaystyle{ n+1}\) stron, to w szczególności musimy przeczytać \(\displaystyle{ n}\) stron spośród poprzedzających ostatnią, której poświęcimy uwagę.
Wtedy na \(\displaystyle{ {n+k\choose n}}\) sposobów wybieramy \(\displaystyle{ n}\) stron poprzedzających ostatnią do przeczytania (tę o numerze \(\displaystyle{ n+k+1}\)), na które poświęcimy czas, no i \(\displaystyle{ n+1}\). strona to ta, którą przeczytamy jako ostatnią.
Mam nadzieję, że jest to w miarę zrozumiałe. Można też po tych przekształceniach udowodnić to indukcyjnie, korzystając z \(\displaystyle{ {r\choose k}+{r\choose k+1}={r+1\choose k+1}}\).
BTW True story.
\(\displaystyle{ \sum_{k=0}^{n}{n+k\choose n}={2n+1\choose n+1}}\)
Teraz interpretacja kombinatoryczna: jesteśmy Przemkiem-mądralą w 2000 roku i nikt nas nie lubi, więc czytamy suplement encyklopedii PWN z lat osiemdziesiątych, zamiast bawić się z rówieśnikami. Chcemy przeczytać \(\displaystyle{ n+1}\) spośród \(\displaystyle{ 2n+1}\) stron suplementu.
Z jednej strony możemy oczywiście wybrać strony do przeczytania na \(\displaystyle{ {2n+1\choose n+1}}\) sposobów. Z drugiej strony możemy sobie na to popatrzeć tak: mamy \(\displaystyle{ 2n+1}\) stron i w naszym wyborze stron do czytania możemy patrzeć na ostatnią stronę, która zostanie wybrana do przeczytania. Skoro mamy przeczytać \(\displaystyle{ n+1}\) spośród \(\displaystyle{ 2n+1}\), to będzie ona stroną (nie wg jakichś oznaczeń, że do numeracji wchodzą strony tytułowe, jakieś przedmowy od redakcji itd.) numer \(\displaystyle{ n+k+1}\) dla pewnego \(\displaystyle{ k\in\left\{ 0,1,\ldots n\right\}}\). Będzie tak, ponieważ jeśli mamy przeczytać \(\displaystyle{ n+1}\) stron, to w szczególności musimy przeczytać \(\displaystyle{ n}\) stron spośród poprzedzających ostatnią, której poświęcimy uwagę.
Wtedy na \(\displaystyle{ {n+k\choose n}}\) sposobów wybieramy \(\displaystyle{ n}\) stron poprzedzających ostatnią do przeczytania (tę o numerze \(\displaystyle{ n+k+1}\)), na które poświęcimy czas, no i \(\displaystyle{ n+1}\). strona to ta, którą przeczytamy jako ostatnią.
Mam nadzieję, że jest to w miarę zrozumiałe. Można też po tych przekształceniach udowodnić to indukcyjnie, korzystając z \(\displaystyle{ {r\choose k}+{r\choose k+1}={r+1\choose k+1}}\).
BTW True story.