Nie daje mi spokoju zadanie z publikacji "Kombinatoryka i R.P." (Gerstenkorn, Śródka). Mój egzemplarz to wyd. 2, PWN, W-wa, 1973. Konkretnie, chodzi mi o zadanie 1.7.g) ze str. 24:
"Wykazać, że \(\displaystyle{ \sum_{k=0}^{n} {n+1-k \choose 2} = {n+2 \choose 3}}\) "
Korzystając z wyrażenia na sumę wyrazów ciągu arytmetycznego łatwo mogę wykazać, że
\(\displaystyle{ \sum_{k=0}^{n} {n+1-k \choose 1} = {n+2 \choose 2}}\)
Czy ktoś mógłby mnie naprowadzić na rozwiązanie tego zadania w oryginalnym brzemieniu? Z góry dziękuję.
Symbol Newtona (pewna tożsamość)
-
maciek_r10
- Użytkownik
- Posty: 7
- Rejestracja: 5 wrz 2010, o 15:44
- Płeć: Mężczyzna
- Podziękował: 1 raz
-
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: Symbol Newtona (pewna tożsamość)
Odwracając kolejność sumowania i opuszczając wyraz równy zero, masz do pokazania
\(\displaystyle{ \sum_{k=1}^{n} {k+1 \choose 2} = {n+2 \choose 3}}\)
Dwa sposoby:
1) indukcja po \(\displaystyle{ n}\), baza indukcji dla \(\displaystyle{ n=1}\) jest trywialna, w kroku indukcyjnym
\(\displaystyle{ {n+2\choose 2}+{n+2\choose 3}={n+3\choose 3}}\)
W sposób analogiczny (indukcja po \(\displaystyle{ n\ge k}\) przy ustalonym \(\displaystyle{ k}\)) można udowodnić ogólniejszą prawidłowość
\(\displaystyle{ \sum_{i=k}^{n}{i\choose k}={n+1\choose k+1}}\)
dla \(\displaystyle{ k,n \in \NN, \ n\ge k}\)
2) interpretacja kombinatoryczna (napiszę od razu ogólniejszą):
bądź proboszczem, level 2137; chcesz wybrać \(\displaystyle{ k+1}\) spośród \(\displaystyle{ n+1}\) ministrantów, których będziesz molestować (\(\displaystyle{ k\le n}\) jest ustalone). Z jednej strony oczywiście możesz to uczynić na \(\displaystyle{ {n+1\choose k+1}}\) sposobów. Z drugiej strony można na to spojrzeć tak: ustawiasz ministrantów w szeregu. Rozważmy ostatniego ministranta w tym szeregu, który padnie Twym łupem. Będzie on stał w miejscu o numerze \(\displaystyle{ i+1}\), gdzie możesz wybrać \(\displaystyle{ i\in\left\{ k, k+1\ldots n\right\}}\), ponieważ wybierzesz też \(\displaystyle{ k}\) ministrantów o mniejszych numerach, by łącznie było ich \(\displaystyle{ k+1}\). Zatem spośród ministrantów nr \(\displaystyle{ 1,\ldots i}\) wybierasz dokładnie \(\displaystyle{ k}\) efebów na \(\displaystyle{ {i\choose k}}\) sposobów.
\(\displaystyle{ \sum_{k=1}^{n} {k+1 \choose 2} = {n+2 \choose 3}}\)
Dwa sposoby:
1) indukcja po \(\displaystyle{ n}\), baza indukcji dla \(\displaystyle{ n=1}\) jest trywialna, w kroku indukcyjnym
\(\displaystyle{ {n+2\choose 2}+{n+2\choose 3}={n+3\choose 3}}\)
W sposób analogiczny (indukcja po \(\displaystyle{ n\ge k}\) przy ustalonym \(\displaystyle{ k}\)) można udowodnić ogólniejszą prawidłowość
\(\displaystyle{ \sum_{i=k}^{n}{i\choose k}={n+1\choose k+1}}\)
dla \(\displaystyle{ k,n \in \NN, \ n\ge k}\)
2) interpretacja kombinatoryczna (napiszę od razu ogólniejszą):
bądź proboszczem, level 2137; chcesz wybrać \(\displaystyle{ k+1}\) spośród \(\displaystyle{ n+1}\) ministrantów, których będziesz molestować (\(\displaystyle{ k\le n}\) jest ustalone). Z jednej strony oczywiście możesz to uczynić na \(\displaystyle{ {n+1\choose k+1}}\) sposobów. Z drugiej strony można na to spojrzeć tak: ustawiasz ministrantów w szeregu. Rozważmy ostatniego ministranta w tym szeregu, który padnie Twym łupem. Będzie on stał w miejscu o numerze \(\displaystyle{ i+1}\), gdzie możesz wybrać \(\displaystyle{ i\in\left\{ k, k+1\ldots n\right\}}\), ponieważ wybierzesz też \(\displaystyle{ k}\) ministrantów o mniejszych numerach, by łącznie było ich \(\displaystyle{ k+1}\). Zatem spośród ministrantów nr \(\displaystyle{ 1,\ldots i}\) wybierasz dokładnie \(\displaystyle{ k}\) efebów na \(\displaystyle{ {i\choose k}}\) sposobów.
-
maciek_r10
- Użytkownik
- Posty: 7
- Rejestracja: 5 wrz 2010, o 15:44
- Płeć: Mężczyzna
- Podziękował: 1 raz
Re: Symbol Newtona (pewna tożsamość)
Dziękuję za szybką odpowiedź! Tak, rzeczywiście, pierwotne sumowanie przebiega od tyłu tylko nie pokusiłem się o przearanżowanie lewej strony. Gapa ze mnie!
Książka wystała mi się na półce przez wiele lat, aż wreszcie postanowiłem sobie z niej przyswoić, zwietrzały już doszczętnie, R.P. Tak więc jestem dopiero na początku reedukacji i do właściwej kombinatoryki jeszcze nie doszedłem. Na obecnym etapie sposób 2. raczej pominę, ale do niego wrócę kiedy przyswoję sobie kombinatoryczną interpretację symbolu Newtona (i może kiedy będę potrafił sobie siebie wyobrazić w sutannie).
Podoba mi się, że poszedłeś w kierunku uogólnienia tej prawidłowości, od tej strony sam to chciałem początkowo "ugryźć".
EDIT:
Udowodniłem (sobie samemu) prawdziwość tożsamości z Twojego punktu 1). Oczywiście korzystałem z niej wcześniej ale bez dowodu. Rozpisywałem drugą wartość rekurencyjnie aż do uzyskania sumy po lewej stronie zadania.
Książka wystała mi się na półce przez wiele lat, aż wreszcie postanowiłem sobie z niej przyswoić, zwietrzały już doszczętnie, R.P. Tak więc jestem dopiero na początku reedukacji i do właściwej kombinatoryki jeszcze nie doszedłem. Na obecnym etapie sposób 2. raczej pominę, ale do niego wrócę kiedy przyswoję sobie kombinatoryczną interpretację symbolu Newtona (i może kiedy będę potrafił sobie siebie wyobrazić w sutannie).
Podoba mi się, że poszedłeś w kierunku uogólnienia tej prawidłowości, od tej strony sam to chciałem początkowo "ugryźć".
EDIT:
Udowodniłem (sobie samemu) prawdziwość tożsamości z Twojego punktu 1). Oczywiście korzystałem z niej wcześniej ale bez dowodu. Rozpisywałem drugą wartość rekurencyjnie aż do uzyskania sumy po lewej stronie zadania.