Cześć
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2}}\)
przedstawić w zwartej postaci sumy, mam skorzystać z :
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k=n \cdot 2^{n-1}}\)
Niezbyt mam chęć na korzystanie z owej podpowiedzi i chciałbym się zapytać czy wynikiem będzie:
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k}k^{2} = \frac{(n+1)n(2n+1)}{6} \cdot 2^{n}}\)
Zwarta postać sumy
- Premislav
- Użytkownik
- Posty: 15685
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 195 razy
- Pomógł: 5219 razy
Re: Zwarta postać sumy
Interpretacja kombinatoryczna: wybieramy spośród \(\displaystyle{ n}\) osób zarząd (o nieustalonej liczbie członków) Komitetu Wsparcia Jarosława Kaczyńskiego, przy czym spośród wybranych członków dokonujemy wyboru przewodniczącego i skarbnika i przyjmujemy, że funkcje te można łączyć.
Z jednej strony wybieramy \(\displaystyle{ k}\) osób spośród n i na \(\displaystyle{ k^2}\) sposobów przydzielić możemy stanowiska przewodniczącego i skarbnika (\(\displaystyle{ {k \choose 1}{k \choose 1}}\)), z drugiej strony
albo przewodniczącym i skarbnikiem będzie ta sama osoba, albo nie, jeśli będzie ta sama, to na \(\displaystyle{ n}\) sposobów dobieramy przewodniczącego, który zarazem będzie skarbnikiem i możemy mu dobrać grupę z \(\displaystyle{ n-1}\) pozostałych, co odpowiada wyborowi podzbioru zbioru \(\displaystyle{ n-1}\)-elementowego, czyli takich wyborów jest \(\displaystyle{ n2^{n-1}}\). Jeśli natomiast przewodniczącym i skarbnikiem będą dwie różne osoby, to na \(\displaystyle{ n}\) sposobów wybieramy przewodniczącego, z pozostałych na \(\displaystyle{ n-1}\) sposobów wybieramy skarbnika, no i możemy jeszcze powiększyć zarząd (albo nie), co odpowiada wyborowi pewnej liczby spośród \(\displaystyle{ n-2}\) pozostałych, czyli wyborowi podzbioru zbioru \(\displaystyle{ n-2}\)-elementowego (na \(\displaystyle{ 2^{n-2}}\) sposobów). Takich możliwości jest zatem \(\displaystyle{ n(n-1)2^{n-2}}\).
Sumując, mamy
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2}=n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}}\)
To zadanie można zrobić inaczej, a mianowicie rozpisując
\(\displaystyle{ k^2{n \choose k}=k(k-1){n \choose k}+k {n\choose k}=n(n-1){n-2\choose k-2}+n{n-1\choose k-1}}\) dla \(\displaystyle{ n\ge 2}\), czyli
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2}=n \sum_{k=1}^{n-1} {n-1\choose k-1}+n(n-1) \sum_{k=2}^{n} {n-2\choose k-2}}\)
Z jednej strony wybieramy \(\displaystyle{ k}\) osób spośród n i na \(\displaystyle{ k^2}\) sposobów przydzielić możemy stanowiska przewodniczącego i skarbnika (\(\displaystyle{ {k \choose 1}{k \choose 1}}\)), z drugiej strony
albo przewodniczącym i skarbnikiem będzie ta sama osoba, albo nie, jeśli będzie ta sama, to na \(\displaystyle{ n}\) sposobów dobieramy przewodniczącego, który zarazem będzie skarbnikiem i możemy mu dobrać grupę z \(\displaystyle{ n-1}\) pozostałych, co odpowiada wyborowi podzbioru zbioru \(\displaystyle{ n-1}\)-elementowego, czyli takich wyborów jest \(\displaystyle{ n2^{n-1}}\). Jeśli natomiast przewodniczącym i skarbnikiem będą dwie różne osoby, to na \(\displaystyle{ n}\) sposobów wybieramy przewodniczącego, z pozostałych na \(\displaystyle{ n-1}\) sposobów wybieramy skarbnika, no i możemy jeszcze powiększyć zarząd (albo nie), co odpowiada wyborowi pewnej liczby spośród \(\displaystyle{ n-2}\) pozostałych, czyli wyborowi podzbioru zbioru \(\displaystyle{ n-2}\)-elementowego (na \(\displaystyle{ 2^{n-2}}\) sposobów). Takich możliwości jest zatem \(\displaystyle{ n(n-1)2^{n-2}}\).
Sumując, mamy
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2}=n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}}\)
To zadanie można zrobić inaczej, a mianowicie rozpisując
\(\displaystyle{ k^2{n \choose k}=k(k-1){n \choose k}+k {n\choose k}=n(n-1){n-2\choose k-2}+n{n-1\choose k-1}}\) dla \(\displaystyle{ n\ge 2}\), czyli
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2}=n \sum_{k=1}^{n-1} {n-1\choose k-1}+n(n-1) \sum_{k=2}^{n} {n-2\choose k-2}}\)