Witam,
siedzę już od ponad godziny i nie mogę rozwiązać. A wygląda tak niepozornie:
\(\displaystyle{ 1^2{n \choose 1 } + 2^2 {n \choose 2} + ... + n^2{n \choose n} = n(n+1)2^{n-2}}\)
Dodatkowo możliwe, że rozwiązanie ułatwia skorzystanie z któregoś z (było w tym samym zadaniu co to powyżej):
a) \(\displaystyle{ {n \choose 0 } + {n \choose 1} + ... + {n \choose n} = 2^n}\)
b) \(\displaystyle{ 1{n \choose 1 } + 2 {n \choose 2} + ... + n{n \choose n} = n2^{n-1}}\)
c) \(\displaystyle{ 1{n \choose 0 } + \frac{1}{2}{n \choose 1} + ... + \frac{1}{n+1}{n \choose n} = \frac{1}{n+1}(2^{n+1}-1)}\)
d) Rozwinięcie \(\displaystyle{ (1+x)^n}\)
suma k^2*(n po k)
-
- Użytkownik
- Posty: 93
- Rejestracja: 31 maja 2007, o 17:53
- Płeć: Mężczyzna
- Lokalizacja: Chojnice
- Podziękował: 1 raz
- Pomógł: 3 razy
-
- Użytkownik
- Posty: 93
- Rejestracja: 31 maja 2007, o 17:53
- Płeć: Mężczyzna
- Lokalizacja: Chojnice
- Podziękował: 1 raz
- Pomógł: 3 razy
suma k^2*(n po k)
Dzielisz obustronnie przez n, że
\(\displaystyle{ \frac{k}{n} {n \choose k} = {n-1 \choose k-1 }}\)
czyli masz po prostu
\(\displaystyle{ {n-1 \choose 0 } + {n-1 \choose 1} + ... + {n-1 \choose n-1} = 2^{n-1}}\)
\(\displaystyle{ \frac{k}{n} {n \choose k} = {n-1 \choose k-1 }}\)
czyli masz po prostu
\(\displaystyle{ {n-1 \choose 0 } + {n-1 \choose 1} + ... + {n-1 \choose n-1} = 2^{n-1}}\)
-
- Użytkownik
- Posty: 2
- Rejestracja: 22 cze 2010, o 16:41
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
suma k^2*(n po k)
Nie wiem, czy rozwiązanie za pomocą interpretacji kombinatorycznej jest dla Ciebie satysfakcjonujące, ale tak czy owak je przedstawię.
Zliczamy ogólnie delegacje (o dowolnej liczbie osób) z grupy n-osobowej, a następnie w delegacji wyznaczamy szefa i skarbnika, z tymże jedna osoba może pełnić obie funkcje naraz. Po lewej stronie równości mamy sumę po liczności delegacji - każdy składnik odpowiada za wybranie \(\displaystyle{ k}\) osób z \(\displaystyle{ n}\) wszystkich uczestników, a następnie szefa (\(\displaystyle{ k}\) możliwości) i skarbnika (\(\displaystyle{ k}\) możliwości), co daje \(\displaystyle{ k^{2}}\) przed każdym składnikiem sumy. Z \(\displaystyle{ k}\) idziemy oczywiście od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\). Z kolei można to też zinterpretować tak:
Wybieramy szefa i skarbnika, a następnie dobieramy delegacje.
1) Szef i skarbnik to ta sama osoba, więc możemy wybrać ją na \(\displaystyle{ n}\) sposobów, a następnie pozostałych uczestników delegacji na \(\displaystyle{ 2^{n-1}}\) sposobów (liczba podzbiorów zbioru \(\displaystyle{ (n-1)}\)-elementowego).
Daje nam to \(\displaystyle{ n \cdot 2^{n-1}}\).
2) Szef i skarbnik to dwie różne osoby. Wybieramy szefa na \(\displaystyle{ n}\) sposobów, skarbnika na \(\displaystyle{ n-1}\) sposobów, a pozostałą delegację na \(\displaystyle{ 2^{n-2}}\) sposobów. W ten sposób mamy \(\displaystyle{ n \cdot (n-1) \cdot 2^{n-2}}\).
Po zsumowaniu daje nam to \(\displaystyle{ n \cdot (n+1) \cdot 2^{n-2}}\), czyli tyle co po prawej stronie równania.
Zliczamy ogólnie delegacje (o dowolnej liczbie osób) z grupy n-osobowej, a następnie w delegacji wyznaczamy szefa i skarbnika, z tymże jedna osoba może pełnić obie funkcje naraz. Po lewej stronie równości mamy sumę po liczności delegacji - każdy składnik odpowiada za wybranie \(\displaystyle{ k}\) osób z \(\displaystyle{ n}\) wszystkich uczestników, a następnie szefa (\(\displaystyle{ k}\) możliwości) i skarbnika (\(\displaystyle{ k}\) możliwości), co daje \(\displaystyle{ k^{2}}\) przed każdym składnikiem sumy. Z \(\displaystyle{ k}\) idziemy oczywiście od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\). Z kolei można to też zinterpretować tak:
Wybieramy szefa i skarbnika, a następnie dobieramy delegacje.
1) Szef i skarbnik to ta sama osoba, więc możemy wybrać ją na \(\displaystyle{ n}\) sposobów, a następnie pozostałych uczestników delegacji na \(\displaystyle{ 2^{n-1}}\) sposobów (liczba podzbiorów zbioru \(\displaystyle{ (n-1)}\)-elementowego).
Daje nam to \(\displaystyle{ n \cdot 2^{n-1}}\).
2) Szef i skarbnik to dwie różne osoby. Wybieramy szefa na \(\displaystyle{ n}\) sposobów, skarbnika na \(\displaystyle{ n-1}\) sposobów, a pozostałą delegację na \(\displaystyle{ 2^{n-2}}\) sposobów. W ten sposób mamy \(\displaystyle{ n \cdot (n-1) \cdot 2^{n-2}}\).
Po zsumowaniu daje nam to \(\displaystyle{ n \cdot (n+1) \cdot 2^{n-2}}\), czyli tyle co po prawej stronie równania.
-
- Użytkownik
- Posty: 93
- Rejestracja: 31 maja 2007, o 17:53
- Płeć: Mężczyzna
- Lokalizacja: Chojnice
- Podziękował: 1 raz
- Pomógł: 3 razy
suma k^2*(n po k)
Zarąbiste rozwiązanie, podoba mi się strasznie. Niemniej jednak chętnie poznałbym rozwiązanie polegające na przekształceniach, bo takie rozwiązanie najprawdopodobniej jest oczekiwane...
-
- Użytkownik
- Posty: 2
- Rejestracja: 22 cze 2010, o 16:41
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
suma k^2*(n po k)
Znalazłem też rozwiązanie przez "normalne", ale niestety jest trochę skomplikowane (pewnie gdzieś sam coś sobie utrudniłem).
A więc tak - przekształcamy z lewej do prawej.
Po lewej stronie mamy:
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2} = \sum_{k=0}^{n} {n \choose k} k^{2} = S_n}\)
Mamy teraz:
\(\displaystyle{ S_{n+1} = \sum_{k=0}^{n+1} {n+1 \choose k} k^{2} = \sum_{k=0}^{n+1} {n \choose k} k^{2} + \sum_{k=0}^{n+1} {n \choose k-1} k^{2} = \sum_{k=0}^{n} {n \choose k} k^{2} + \sum_{k=0}^{n+1} {n \choose k-1} k^{2} = S_n + \sum_{k=0}^{n+1} {n \choose k-1} k^{2} = S_n + \sum_{k=-1}^{n} {n \choose k} (k+1)^{2} = S_n + \sum_{k=0}^{n} {n \choose k} (k+1)^{2} = S_n + \sum_{k=0}^{n} {n \choose k} (k^{2}+2k+1) = S_n + \sum_{k=0}^{n} {n \choose k} k^2 + 2\sum_{k=0}^{n} {n \choose k} k + \sum_{k=0}^{n} {n \choose k} = 2S_n + 2n \cdot 2^{n-1}+2^n}\)
Z tego mamy:
\(\displaystyle{ S_{n+1} = 2S_n + (n+1)2^n}\), czyli:
\(\displaystyle{ S_n = 2S_{n-1} + n2^{n-1}}\)
\(\displaystyle{ S_0 = 0}\)
Po rozwinięciu mamy:
\(\displaystyle{ S_n = 2S_{n-1} + n2^{n-1} = 2 \cdot (2S_{n-2} + (n-1) \cdot 2^{n-2}) + n2^{n-1} = ... = \sum_{k=0}^{n}2^{k}(n-k)2^{n-k-1}= \sum_{k=0}^{n} 2^{n-1} \cdot (n-k) = 2^{n-1} \cdot \sum_{k=0}^{n}(n-k) = 2^{n-1} \cdot \sum_{k=0}^{n}k = 2^{n-1} \cdot \frac{n(n+1)}{2} = n(n+1) \cdot 2^{n-2}}\)
A więc tak - przekształcamy z lewej do prawej.
Po lewej stronie mamy:
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k^{2} = \sum_{k=0}^{n} {n \choose k} k^{2} = S_n}\)
Mamy teraz:
\(\displaystyle{ S_{n+1} = \sum_{k=0}^{n+1} {n+1 \choose k} k^{2} = \sum_{k=0}^{n+1} {n \choose k} k^{2} + \sum_{k=0}^{n+1} {n \choose k-1} k^{2} = \sum_{k=0}^{n} {n \choose k} k^{2} + \sum_{k=0}^{n+1} {n \choose k-1} k^{2} = S_n + \sum_{k=0}^{n+1} {n \choose k-1} k^{2} = S_n + \sum_{k=-1}^{n} {n \choose k} (k+1)^{2} = S_n + \sum_{k=0}^{n} {n \choose k} (k+1)^{2} = S_n + \sum_{k=0}^{n} {n \choose k} (k^{2}+2k+1) = S_n + \sum_{k=0}^{n} {n \choose k} k^2 + 2\sum_{k=0}^{n} {n \choose k} k + \sum_{k=0}^{n} {n \choose k} = 2S_n + 2n \cdot 2^{n-1}+2^n}\)
Z tego mamy:
\(\displaystyle{ S_{n+1} = 2S_n + (n+1)2^n}\), czyli:
\(\displaystyle{ S_n = 2S_{n-1} + n2^{n-1}}\)
\(\displaystyle{ S_0 = 0}\)
Po rozwinięciu mamy:
\(\displaystyle{ S_n = 2S_{n-1} + n2^{n-1} = 2 \cdot (2S_{n-2} + (n-1) \cdot 2^{n-2}) + n2^{n-1} = ... = \sum_{k=0}^{n}2^{k}(n-k)2^{n-k-1}= \sum_{k=0}^{n} 2^{n-1} \cdot (n-k) = 2^{n-1} \cdot \sum_{k=0}^{n}(n-k) = 2^{n-1} \cdot \sum_{k=0}^{n}k = 2^{n-1} \cdot \frac{n(n+1)}{2} = n(n+1) \cdot 2^{n-2}}\)