tożsamość symbolu newtona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
fafner
Użytkownik
Użytkownik
Posty: 198
Rejestracja: 11 sty 2008, o 22:29
Płeć: Mężczyzna
Lokalizacja: rumia
Podziękował: 25 razy
Pomógł: 9 razy

tożsamość symbolu newtona

Post autor: fafner »

Witam
nie mogę się uporać z tą równością:
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k}^{2}= {2n \choose n}}\)
Zdaję sobię sprawę, że można to rozwiązać kombinatorycznie bardzo łatwo, ale próbowałem rozwiązaćto rachunkowo. Trochę napisałem, nie wiem czy jestem bliżej czy dalej :
\(\displaystyle{ \left( \sum_{k=0}^{n} {n \choose k} \right)^{2}=2^{2n}= \sum_{k=0}^{2n} {2n \choose k} \\
\sum_{k=0}^{n} {n \choose k} ^2+ 2 \cdot \sum_{k=0}^{n-1} \left( {n \choose k} \cdot \sum_{j=k+1}^{n} {n \choose j} \right)= \sum_{k=0}^{n} {2n \choose k}}\)


Prawą stronę równania przekształcam aby wyodrębnić \(\displaystyle{ {2n \choose n}}\):

\(\displaystyle{ \sum_{k=0}^{n} {2n \choose n}= {2n \choose n} + 2 \cdot \sum_{k=0}^{n-1} {2n \choose k}}\)
teraz mam równanie:
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k} ^2+ 2 \cdot \sum_{k=0}^{n-1} \left( {n \choose k} \cdot \sum_{j=k+1}^{n} {n \choose j} \right)= {2n \choose n} + 2 \cdot \sum_{k=0}^{n-1} {2n \choose k}}\)

czyli teraz muszę tylko udowodnić, że:
\(\displaystyle{ 2 \cdot \sum_{k=0}^{n-1} \left( {n \choose k} \cdot \sum_{j=k+1}^{n} {n \choose j} \right)=2 \cdot \sum_{k=0}^{n-1} {2n \choose k}}\)

a tego nie umiem po prostu zbyt bardzo się zapętliłem można od tego miejsca to jakoś udowodnić? Może inną, sprytniejszą drogą? zależy mi na tym, aby zrobićto rachunkowo.
Dziękuje za wszelką pomoc, pozdrawiam
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

tożsamość symbolu newtona

Post autor: »

fafner pisze:\(\displaystyle{ \left( \sum_{k=0}^{n} {n \choose k} \right)^{2}=2^{2n}= \sum_{k=0}^{2n} {2n \choose k}}\)
Proponuję raczej wyjść od:
\(\displaystyle{ \left( \sum_{k=0}^{n} {n \choose k}x^k \right)^{2}=(1+x)^{2n}= \sum_{k=0}^{2n} {2n \choose k}x^k}\)
i porównać co stoi po obu stronach przy \(\displaystyle{ x^n}\) (mam nadzieję, że sposób wystarczająco "niekombinatoryczny").

Q.
Awatar użytkownika
fafner
Użytkownik
Użytkownik
Posty: 198
Rejestracja: 11 sty 2008, o 22:29
Płeć: Mężczyzna
Lokalizacja: rumia
Podziękował: 25 razy
Pomógł: 9 razy

tożsamość symbolu newtona

Post autor: fafner »

hmm wygląda ciekawie, mam nadzieje, że z tego mi się uda
dowód kombinatoryczny też jest fajny, ale zastanawiam się jak arytmetycznie się to dowodzi dlatego próbuję to ugryźć w ten sposób.
dzięki
ODPOWIEDZ