udowodnij tożsamość chciała bym rachunkowo a jeśli by ktoś wiedział jak to jeszcze jakaś "bajka"
\(\displaystyle{ \sum_{k=1}^{n} k ^{2} {n\choose k}=n(n+1)2 ^{n-2}}\)
udowodnij tożsamość
- ares41
- Użytkownik
- Posty: 6499
- Rejestracja: 19 sie 2010, o 08:07
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 142 razy
- Pomógł: 922 razy
udowodnij tożsamość
Rozważmy sumę \(\displaystyle{ F(x)=\sum_{k=0}^{n}{n \choose k} x^k}\)
Ze wzoru dwumianowe Newtona otrzymujemy \(\displaystyle{ F(x)=(1+x)^n}\)
Różniczkując podane zależności po \(\displaystyle{ x}\) mamy :
\(\displaystyle{ n(1+x)^{n-1}=\sum_{k=0}^{n}k{n \choose k} x^{k-1}}\)
Obliczając drugą pochodną dostajemy:
\(\displaystyle{ n(n-1)(1+x)^{n-2}=\sum_{k=0}^{n}k(k-1){n \choose k} x^{k-2}}\)
Kładąc w obu powyższych równaniach \(\displaystyle{ x=1}\) otrzymujemy :
\(\displaystyle{ 1) \ \ \sum_{k=0}^{n}k{n \choose k} =n2^{n-1} \\2) \ \ \sum_{k=0}^{n}k(k-1){n \choose k} =n(n-1)2^{n-2}}\)
Rozpiszmy lewą stronę równania (2) :
\(\displaystyle{ \sum_{k=0}^{n}k \left( k-1 \right) {n \choose k} =\sum_{k=0}^{n} \left( k^2-k \right) {n \choose k} =\sum_{k=0}^{n} \left[ k^2 {n \choose k} -k {n \choose k} \right] = \\=\left( \sum_{k=0}^{n} k^2 {n \choose k} \right) - \left( \sum_{k=0}^{n}k {n \choose k} \right)=\sum_{k=0}^{n} k^2 {n \choose k} -n2^{n-1}}\)
Zatem
\(\displaystyle{ n(n-1)2^{n-2}=\sum_{k=0}^{n} k^2 {n \choose k} -n2^{n-1}}\)
skąd
\(\displaystyle{ \sum_{k=0}^{n} k^2 {n \choose k}=n(n-1)2^{n-2}+n2^{n-1}=n2^{n-2}(n-1+2)=n(n+1)2^{n-2}}\)
Ze wzoru dwumianowe Newtona otrzymujemy \(\displaystyle{ F(x)=(1+x)^n}\)
Różniczkując podane zależności po \(\displaystyle{ x}\) mamy :
\(\displaystyle{ n(1+x)^{n-1}=\sum_{k=0}^{n}k{n \choose k} x^{k-1}}\)
Obliczając drugą pochodną dostajemy:
\(\displaystyle{ n(n-1)(1+x)^{n-2}=\sum_{k=0}^{n}k(k-1){n \choose k} x^{k-2}}\)
Kładąc w obu powyższych równaniach \(\displaystyle{ x=1}\) otrzymujemy :
\(\displaystyle{ 1) \ \ \sum_{k=0}^{n}k{n \choose k} =n2^{n-1} \\2) \ \ \sum_{k=0}^{n}k(k-1){n \choose k} =n(n-1)2^{n-2}}\)
Rozpiszmy lewą stronę równania (2) :
\(\displaystyle{ \sum_{k=0}^{n}k \left( k-1 \right) {n \choose k} =\sum_{k=0}^{n} \left( k^2-k \right) {n \choose k} =\sum_{k=0}^{n} \left[ k^2 {n \choose k} -k {n \choose k} \right] = \\=\left( \sum_{k=0}^{n} k^2 {n \choose k} \right) - \left( \sum_{k=0}^{n}k {n \choose k} \right)=\sum_{k=0}^{n} k^2 {n \choose k} -n2^{n-1}}\)
Zatem
\(\displaystyle{ n(n-1)2^{n-2}=\sum_{k=0}^{n} k^2 {n \choose k} -n2^{n-1}}\)
skąd
\(\displaystyle{ \sum_{k=0}^{n} k^2 {n \choose k}=n(n-1)2^{n-2}+n2^{n-1}=n2^{n-2}(n-1+2)=n(n+1)2^{n-2}}\)
-
- Użytkownik
- Posty: 54
- Rejestracja: 17 sie 2011, o 11:27
- Płeć: Mężczyzna
- Podziękował: 12 razy
- Pomógł: 1 raz
udowodnij tożsamość
Bajka:
Z \(\displaystyle{ n}\) ludzi wybieramy osoby, które idą na wycieczkę. Dodatkowo potrzebują jednego kucharza i jednego przewodnika. Kucharzem i przewodnikiem może być ta sama osoba.
Lewa strona:
Z \(\displaystyle{ n}\) ludzi wybieramy \(\displaystyle{ k}\), a następnie na \(\displaystyle{ k}\) sposobów wybieramy kucharza i na \(\displaystyle{ k}\) sposobów wybieramy przewodnika.
Prawa strona:
Jeżeli przewodnik i kucharz to ta sama osoba to wybieramy ją z ludzi na \(\displaystyle{ n}\) sposobów, a następnie, każdego z \(\displaystyle{ n-1}\) ludzi (przewodniko-kucharz na pewno jedzie) pytamy czy jedzie (może odpowiedzieć na dwa sposoby: tak lub nie), czyli w sumie mamy
\(\displaystyle{ n2^{n-1}}\) możliwości.
Jeżeli przewodnik i kucharz to dwie różne osoby to wybieramy przewodnika na \(\displaystyle{ n}\) sposobów, następnie z pozostałych kucharza na \(\displaystyle{ n-1}\) sposobów, a resztę \(\displaystyle{ n-2}\) osób pytamy czy chce pojechać:
\(\displaystyle{ n(n-1)2^{n-2}}\)
A więc w sumie:
\(\displaystyle{ n(n-1)2^{n-2}+n2^{n-1}=n(n-1+2)2^{n-2}=n(n+1)2^{n-2}}\)
Z \(\displaystyle{ n}\) ludzi wybieramy osoby, które idą na wycieczkę. Dodatkowo potrzebują jednego kucharza i jednego przewodnika. Kucharzem i przewodnikiem może być ta sama osoba.
Lewa strona:
Z \(\displaystyle{ n}\) ludzi wybieramy \(\displaystyle{ k}\), a następnie na \(\displaystyle{ k}\) sposobów wybieramy kucharza i na \(\displaystyle{ k}\) sposobów wybieramy przewodnika.
Prawa strona:
Jeżeli przewodnik i kucharz to ta sama osoba to wybieramy ją z ludzi na \(\displaystyle{ n}\) sposobów, a następnie, każdego z \(\displaystyle{ n-1}\) ludzi (przewodniko-kucharz na pewno jedzie) pytamy czy jedzie (może odpowiedzieć na dwa sposoby: tak lub nie), czyli w sumie mamy
\(\displaystyle{ n2^{n-1}}\) możliwości.
Jeżeli przewodnik i kucharz to dwie różne osoby to wybieramy przewodnika na \(\displaystyle{ n}\) sposobów, następnie z pozostałych kucharza na \(\displaystyle{ n-1}\) sposobów, a resztę \(\displaystyle{ n-2}\) osób pytamy czy chce pojechać:
\(\displaystyle{ n(n-1)2^{n-2}}\)
A więc w sumie:
\(\displaystyle{ n(n-1)2^{n-2}+n2^{n-1}=n(n-1+2)2^{n-2}=n(n+1)2^{n-2}}\)