Matematyka.pl

udowodnić:
\(\displaystyle{ \sum_{k=0}^{n} {n\choose k}^2 = {2n \choose n}}\)

Najpierw próbowałem indukcją (ale nie wyszło), potem próbowałem wykorzystać fakt, że \(\displaystyle{ {p+1 \choose k+1}= {p \choose k}+ {p \choose k+1}}\), ale powstał problem z policzeniem \(\displaystyle{ \sum_{k=0}^{n-1} {n \choose k+1}}\)

jeśli ktoś umie, to można rozwiązywać drugą nierówność. Jeśli jednak robię niezbyt dobrze, to pierwsza równość jest równie mile widziana.

\(\displaystyle{ \sum_{k=0}^{n}{n\choose k}^2=2^{2n}=\sum_{k=0}^{n}{2n\choose k}}\)
Hmm takie coś mi wychodzi.

Dargi, z tego co wiem, to \(\displaystyle{ \sum_{k=0}^{n}{n\choose k} =2^n}\) ale też
\(\displaystyle{ \sum_{k=0}^{n} {n\choose k} ^2 < ( \sum_{k=0}^{n} {n\choose k} )^2=(2^n)^2=2^{2n}}\)

chyba, że znów mi coś nie wyszło...

Tak tak masz rację mój błąd

Niech dana będzie siatka punktów kratowych o rozmiarach n+1 x n+1.
Z lewego-dolnego do prawego-górnego rogu można dotrzeć na \(\displaystyle{ {2n\choose n}}\) sposobów, wykonując wyłącznie ruchy w prawo oraz w górę po siatce, ponieważ każda droga to sekwencja 2n ruchów, z których dokładnie n to ruchy w prawo i dokładnie n to ruchy w górę.
Każda z tych dróg przechodzi przez dokładnie jeden z n+1 punktów kratowych dużej przekątnej niezawierającej położenia początkowego. Łatwo pokazać, że liczby dróg przechodzących przez kolejne punkty owej przekątnej (patrząc z perspektywy jednego z jej końców) są równe odpowiednio \(\displaystyle{ {n\choose 0}^2,\ {n\choose 1}^2,\ \ldots, {n\choose n}^2}\).

Sorry, jeśli za bardzo skracałem myśli.

Mamy wielomian:
\(\displaystyle{ P(x)=(x+1)^{2n} \\ P(x)=({n \choose 0}x^n + {n \choose 1}x^{n-1}+\ldots+{n \choose n} 1) ({n \choose 0}x^n + {n \choose 1}x^{n-1}+\ldots+{n \choose n} 1)}\)

Na dwa sposoby zapiszmy współczynnik przy \(\displaystyle{ x^n}\) (oznaczmy Q). Z pierwszego równania mamy (bezpośrednio z dwumianu Newtona \(\displaystyle{ Q={2n \choose n}}\). Z drugiego równania wynosi on (wymnażamy wyrazy z \(\displaystyle{ x^k}\) przez wyrazy z \(\displaystyle{ x^{n-k}}\)):
\(\displaystyle{ Q={n \choose 0} {n \choose n} + {n \choose 1} {n \choose n-1} + \ldots = \\ ={n \choose 0} {n \choose 0} + {n \choose 1} {n \choose 1} + \ldots = \sum_{k=0}^{n} {n\choose k}^2}\)
Przedostatnia równość z najbardziej podstawowej własności symbolu Newtona.

\(\displaystyle{ f(x)=(1+x)^{n} (1+x)^{n}}\)
Współczynnik przy x^n w iloczynie będzie \(\displaystyle{ \sum_{k=0}^{n}{n\choose k} ^{2}}\) Natomiast w wielomianie \(\displaystyle{ f(x)=(1+x)^{2n}}\) wpółczynnik przy x^n wynosi \(\displaystyle{ {2n \choose n}}\) stąd juz otrymujemy co chcieliśmy.

edit
heh to samo co Sylwek

dzięki wszystkim.

Do tego typu zagadnień polecam książkę: Victor Bryant "Aspekty kombinatoryki"

zapamiętam, ale było mi to potrzebne do konkretnego zadania i tyle.