Witajcie Mam zadanie ( p.s. nie trzeba robić indukcyjnie).
Udowodnić, że wzór jest prawdziwy:
\(\displaystyle{ 0^{2} {n \choose 0} + 1^{2} {n \choose 1}+ 2^{2} {n \choose 2}+...+n^{2} {n \choose n} =n(n+1) \cdot 2^{n-2}}\)
Proszę o pomoc.
Udowodnić prawdziwość wzoru
-
Malarz44
- Użytkownik
- Posty: 28
- Rejestracja: 24 wrz 2016, o 17:27
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 10 razy
Udowodnić prawdziwość wzoru
Ostatnio zmieniony 1 paź 2016, o 17:04 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa tematu.
Powód: Poprawa tematu.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Udowodnić prawdziwość wzoru
Ja mam zupełnie inną propozycję:
na zgromadzeniu Żydów na cmentarzu w Pradze wybierani są redaktor naczelny Gazety Wyborczej i tajny żydowski gubernator Polski (przy czym te stanowiska mogą być łączone, jak to miało miejsce w przypadku pana Adama Michnika) oraz ewentualnie delegowana jest grupa wspierająca kontrolę Narodu Wybranego nad RP. Na oba stanowiska mamy taką samą grupę \(\displaystyle{ n}\) kandydatów, spośród tej grupy możemy też dobrać (lub już nie dobierać) grupę wspierającą.
Z jednej strony patrzymy na to tak:
dla \(\displaystyle{ k=1,\dots n}\) możemy wybrać \(\displaystyle{ {n \choose k}}\) osób, które dostaną jakąś rolę do odegrania, a spośród tychże na \(\displaystyle{ k^2}\) sposobów wybieramy redaktora naczelnego GW i gubernatora (oczywiście dodanie \(\displaystyle{ 0^2{n \choose 0}=0}\) nic nie zmienia).
Więc łącznie mamy \(\displaystyle{ \sum_{k=1}^{n}{n \choose k}k^2= \sum_{k=0}^{n}{n \choose k}k^2}\)
sposobów wyboru grupy kontrolującej Polskę z ramienia Narodu Wybranego.
Z drugiej strony możemy na to popatrzeć tak: albo uprawnienia redaktora i gubernatora będą skupione w jednym ręku, albo nie. W tym pierwszym przypadku jest
\(\displaystyle{ n2^{n-1}}\) sposobów wyboru grupy - na \(\displaystyle{ {n \choose 1}=n}\) sposobów wybieramy redaktora-gubernatora, a potem dobieramy podzbiór zbioru \(\displaystyle{ n-1}\) pozostałych kandydatów jako ewentualne wsparcie (dla każdego z \(\displaystyle{ n-1}\) pozostałych prawdą jest, że albo będzie on należał do grupy wspierającej, albo nie). No i reguła mnożenia.
W drugim przypadku na \(\displaystyle{ n(n-1)}\) sposobów wybieramy redaktora i gubernatora,
a następnie na \(\displaystyle{ 2^{n-2}}\) sposobów możemy dobrać grupę wsparcia.
Zatem wychodzi na to, że łącznie mamy \(\displaystyle{ n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}}\)
sposobów wyboru grupy kontrolującej Polskę.
Stąd \(\displaystyle{ \sum_{k=0}^{n}{n \choose k}k^2=n(n+1)2^{n-2}}\).
-- 1 paź 2016, o 17:57 --
Czekam na chwilę, w której zostanę zbanowany za "antysemityzm". W międzyczasie jeszcze jedno rozwiązanie zadania:
zwróćmy uwagę na fakt, że
\(\displaystyle{ k{n \choose k}=n{n-1 \choose k-1}}\) dla \(\displaystyle{ k>0}\)
i podobnie \(\displaystyle{ k(k-1){n \choose k}=n(n-1){n-2 \choose k-2}}\) dla \(\displaystyle{ k>1}\)
- wystarczy rozpisać na silnie i poskracać.
Zatem
\(\displaystyle{ \sum_{k=0}^{n}k^2 {n \choose k}= \sum_{k=1}^{n}k^2{n \choose k}= \sum_{k=1}^{n}k{n \choose k}+ \sum_{k=2}^{n}k(k-1){n \choose k}=\\= \sum_{k=1}^{n}n{n-1 \choose k-1}+ \sum_{k=2}^{n}n(n-1){n-2 \choose k-2}=n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}}\), c.k.d.
na zgromadzeniu Żydów na cmentarzu w Pradze wybierani są redaktor naczelny Gazety Wyborczej i tajny żydowski gubernator Polski (przy czym te stanowiska mogą być łączone, jak to miało miejsce w przypadku pana Adama Michnika) oraz ewentualnie delegowana jest grupa wspierająca kontrolę Narodu Wybranego nad RP. Na oba stanowiska mamy taką samą grupę \(\displaystyle{ n}\) kandydatów, spośród tej grupy możemy też dobrać (lub już nie dobierać) grupę wspierającą.
Z jednej strony patrzymy na to tak:
dla \(\displaystyle{ k=1,\dots n}\) możemy wybrać \(\displaystyle{ {n \choose k}}\) osób, które dostaną jakąś rolę do odegrania, a spośród tychże na \(\displaystyle{ k^2}\) sposobów wybieramy redaktora naczelnego GW i gubernatora (oczywiście dodanie \(\displaystyle{ 0^2{n \choose 0}=0}\) nic nie zmienia).
Więc łącznie mamy \(\displaystyle{ \sum_{k=1}^{n}{n \choose k}k^2= \sum_{k=0}^{n}{n \choose k}k^2}\)
sposobów wyboru grupy kontrolującej Polskę z ramienia Narodu Wybranego.
Z drugiej strony możemy na to popatrzeć tak: albo uprawnienia redaktora i gubernatora będą skupione w jednym ręku, albo nie. W tym pierwszym przypadku jest
\(\displaystyle{ n2^{n-1}}\) sposobów wyboru grupy - na \(\displaystyle{ {n \choose 1}=n}\) sposobów wybieramy redaktora-gubernatora, a potem dobieramy podzbiór zbioru \(\displaystyle{ n-1}\) pozostałych kandydatów jako ewentualne wsparcie (dla każdego z \(\displaystyle{ n-1}\) pozostałych prawdą jest, że albo będzie on należał do grupy wspierającej, albo nie). No i reguła mnożenia.
W drugim przypadku na \(\displaystyle{ n(n-1)}\) sposobów wybieramy redaktora i gubernatora,
a następnie na \(\displaystyle{ 2^{n-2}}\) sposobów możemy dobrać grupę wsparcia.
Zatem wychodzi na to, że łącznie mamy \(\displaystyle{ n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}}\)
sposobów wyboru grupy kontrolującej Polskę.
Stąd \(\displaystyle{ \sum_{k=0}^{n}{n \choose k}k^2=n(n+1)2^{n-2}}\).
-- 1 paź 2016, o 17:57 --
Czekam na chwilę, w której zostanę zbanowany za "antysemityzm". W międzyczasie jeszcze jedno rozwiązanie zadania:
zwróćmy uwagę na fakt, że
\(\displaystyle{ k{n \choose k}=n{n-1 \choose k-1}}\) dla \(\displaystyle{ k>0}\)
i podobnie \(\displaystyle{ k(k-1){n \choose k}=n(n-1){n-2 \choose k-2}}\) dla \(\displaystyle{ k>1}\)
- wystarczy rozpisać na silnie i poskracać.
Zatem
\(\displaystyle{ \sum_{k=0}^{n}k^2 {n \choose k}= \sum_{k=1}^{n}k^2{n \choose k}= \sum_{k=1}^{n}k{n \choose k}+ \sum_{k=2}^{n}k(k-1){n \choose k}=\\= \sum_{k=1}^{n}n{n-1 \choose k-1}+ \sum_{k=2}^{n}n(n-1){n-2 \choose k-2}=n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}}\), c.k.d.