Udowodnij tożsamości

[Akiro]

a) \(\displaystyle{ \sum_{k=1}^{n} k(k-1) {n \choose k} = n(n-1)2 ^{n-2}}\)
b) \(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k (-1)^{k-1}=0 ^{n-1}}\)



ad. a) \(\displaystyle{ L = \sum_{k=1}^{n} k(k-1) {n \choose k} = \sum_{k=1}^{n} \frac{k(k-1)n!}{(n-k)!k!}}\)
tutaj widzimy, że możemy skrócić k! w mianowniku z k(k-1) w liczniku
\(\displaystyle{ \sum_{k=1}^{n} \frac{n!}{(n-k)!(k-2)!}}\)
teraz zauważamy, że możemy to zwinąć w dwumian
\(\displaystyle{ \sum_{k=1}^{n} {n-2 \choose k-2}}\)
I dalej nie mam pojęcia co zrobić (być może nie znam jakiś wzorów do przekształceń.

ad. b)\(\displaystyle{ L= \sum_{k=1}^{n} {n \choose k} k (-1)^{k-1}=0 ^{n-1} = \sum_{k=1}^{n} \frac{n!}{k!(n-k)!}k(-1) ^{k-1} =\sum_{k=1}^{n} \frac{n!}{(k-1)!(n-k)!}(-1) ^{k-1}}\)
No i tutaj też juz dalej nie wiem co zrobić. Z przykładów mam jeszcze c i d ale myślę, że jak ogarnę jak zrobić te dwa to z resztą pójdzie łatwo.

[Premislav]

a) Niech \(\displaystyle{ f(x)= \sum_{k=0}^{n}{n \choose k}x^k}\). Ze wzoru dwumianowego Newtona mamy \(\displaystyle{ f(x)=(1+x)^n}\).
Druga pochodna tej funkcji (pochodna sumy to suma pochodnych) to
\(\displaystyle{ \sum_{k=2}^{n}k(k-1){n \choose k}x^{k-2}}\)
Policz ją z powyższej zwartej postaci \(\displaystyle{ f(x)=(1+x)^n}\) i wstaw \(\displaystyle{ x=1}\).
b) Na razie w porządku (poza pierwszą równością, bo to wygląda, jakbyś zakładał tezę), teraz proponuję wyłączyć przed wszystko \(\displaystyle{ n}\) i masz:
\(\displaystyle{ n \sum_{k=1}^{n}{n-1\choose k-1}(-1)^{k-1}=n\sum_{k=0}^{n-1}{n-1\choose k}(-1)^{k}1^{n-1-k}}\)
i zwiń to ze wzoru dwumianowego Newtona.

[Akiro]

a) Niech \(\displaystyle{ f(x)= \sum_{k=0}^{n}{n \choose k}x^k}\). Ze wzoru dwumianowego Newtona mamy \(\displaystyle{ f(x)=(1+x)^n}\).
Druga pochodna tej funkcji (pochodna sumy to suma pochodnych) to
\(\displaystyle{ \sum_{k=2}^{n}k(k-1){n \choose k}x^{k-2}}\)
Policz ją z powyższej zwartej postaci \(\displaystyle{ f(x)=(1+x)^n}\) i wstaw \(\displaystyle{ x=1}\).

1. Mógłbyś mi wyjaśnić fakt po co wyznaczać drugą pochodną tej funkcji?
2. Ten krok "policz ją z powyższej zwartej postaci", tego nie rozumiem, mógłbyś sprecyzować?

[Premislav]

To jest taka sztuczka. Mamy równość
\(\displaystyle{ (1+x)^n= \sum_{k=0}^{n}{n \choose k}x^k}\)
Dwukrotnie różniczkując ją stronami, mamy
\(\displaystyle{ n(n-1)(1+x)^{n-2}=\sum_{k=2}^{n}k(k-1){n \choose k}x^{k-2}}\)
Wstawiamy \(\displaystyle{ x=1}\) i koniec dowodu.

[Akiro]

To jest taka sztuczka. Mamy równość
\(\displaystyle{ (1+x)^n= \sum_{k=0}^{n}{n \choose k}x^k}\)
Dwukrotnie różniczkując ją stronami, mamy
\(\displaystyle{ n(n-1)(1+x)^{n-2}=\sum_{k=2}^{n}k(k-1){n \choose k}x^{k-2}}\)
Wstawiamy \(\displaystyle{ x=1}\) i koniec dowodu.

No dobra rozumiem na czym polega ta sztuczka ale nie wiem za bardzo jak to ma się do postaci, do której doprowadziłem
\(\displaystyle{ \sum_{k=2}^{n} {n-2 \choose k-2} = n(n-1)2 ^{n-2}}\)

[Premislav]

Nijak, przedstawiłem inne rozwiązanie problemu. Coś tam źle poskracałeś najwyraźniej, bo to nie jest \(\displaystyle{ {n-2 \choose k-2}}\), brakuje tam pewnego czynnika. Jak już koniecznie chcemy te silnie rozpisywać (jest to najmniej lubiany przeze mnie sposób):
\(\displaystyle{ \sum_{k=1}^{n} k(k-1) {n \choose k} = \sum_{k=2}^{n}k(k-1){n \choose k}= \sum_{k=2}^{n} \frac{k(k-1)n!}{k!(n-k)!}=\\= \sum_{k=2}^{n} \frac{n(n-1)(n-2)!}{(k-2)!(n-k)!}=\\=n(n-1) \sum_{k=2}^{n}{n-2 \choose k-2}=n(n-1)\sum_{k=0}^{n-2}{n \choose k}=n(n-1)2^{n-2}}\)

[Akiro]

Nijak, przedstawiłem inne rozwiązanie problemu. Coś tam źle poskracałeś najwyraźniej, bo to nie jest \(\displaystyle{ {n-2 \choose k-2}}\), brakuje tam pewnego czynnika. Jak już koniecznie chcemy te silnie rozpisywać (jest to najmniej lubiany przeze mnie sposób):
\(\displaystyle{ \sum_{k=1}^{n} k(k-1) {n \choose k} = \sum_{k=2}^{n}k(k-1){n \choose k}= \sum_{k=2}^{n} \frac{k(k-1)n!}{k!(n-k)!}=\\= \sum_{k=2}^{n} \frac{n(n-1)(n-2)!}{(k-2)!(n-k)!}=\\=n(n-1) \sum_{k=2}^{n}{n-2 \choose k-2}=n(n-1)\sum_{k=0}^{n-2}{n \choose k}=n(n-1)2^{n-2}}\)

Tak, źle przepisałem z kartki.

No i tu jest ostatni krok, że
\(\displaystyle{ n(n-1)\sum_{k=0}^{n-2}{n \choose k}=n(n-1)2^{n-2}}\)
Skąd nagle to się tak cudownie przemienia?

[Premislav]

Sorry, literówka, powinno być:
\(\displaystyle{ n(n-1)\sum_{k=0}^{n-2}{n-2 \choose k}=n(n-1)2^{n-2}}\)
wynika to natychmiast ze wzoru dwumianowego Newtona, bo \(\displaystyle{ {n-2 \choose k}={n-2 \choose k}1^k 1^{n-2-k}}\)

[Akiro]

Sorry, literówka, powinno być:
\(\displaystyle{ n(n-1)\sum_{k=0}^{n-2}{n-2 \choose k}=n(n-1)2^{n-2}}\)
wynika to natychmiast ze wzoru dwumianowego Newtona, bo \(\displaystyle{ {n-2 \choose k}={n-2 \choose k}1^k 1^{n-2-k}}\)

Nie wiem, coś to dla mnie mało jasne.
Może inaczej, dlaczego:
\(\displaystyle{ \sum_{k=0}^{n-2}{n-2 \choose k}=2.^{n-2}}\)
Najbardziej mnie interesuje ta dwojka bezpośrednio po znaku równości (dałem po niej kropkę)

[Premislav]

Gdy się zabierasz za takie rzeczy, to jednak warto znać podstawy (no offence).

Ogólnie mamy \(\displaystyle{ \sum_{k=0}^n{n\choose k}=2^n}\) (co można udowodnić na wiele sposobów, np. ze wzoru dwumianowego Newtona lub przez interpretację kombinatoryczną), to teraz w miejsce \(\displaystyle{ n}\) wpisz \(\displaystyle{ n-2.}\)

[Akiro]

a)
b) Na razie w porządku (poza pierwszą równością, bo to wygląda, jakbyś zakładał tezę), teraz proponuję wyłączyć przed wszystko \(\displaystyle{ n}\) i masz:
\(\displaystyle{ n \sum_{k=1}^{n}{n-1\choose k-1}(-1)^{k-1}=n\sum_{k=0}^{n-1}{n-1\choose k}(-1)^{k}1^{n-1-k}}\)
i zwiń to ze wzoru dwumianowego Newtona.

Widzisz, na początku powinienem spisać wszystkie wzory, które mogę wykorzystać bo później da mnie niektóre kroki są niejasne, jak na przykład ten, w którym dopisałeś do sumy \(\displaystyle{ 1^{n-1-k}}\) bo przecież to nic nie zmienia (dalej wynosi \(\displaystyle{ 1}\)) a wtedy możemy to podstawić do wzorku i końcowy wynik to \(\displaystyle{ n(-1+1)^{n}}\)

[PiotrAH]

Podobnie a) ma bardzo ładne uzasadnienie kombinatoryczne.