Witam,
posiłkuję się z tożsamością już któryś dzień z rzędu:
\(\displaystyle{ \binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}}\)
Doprowadziłam do takowej postaci (nie wykluczam błędów), nie wiem czy mój tok rozumowania jest poprawny.
[ciach]
Tożsamość - Wykaż, że...
Tożsamość - Wykaż, że...
Ostatnio zmieniony 30 kwie 2020, o 20:21 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Nieregulaminowy zapis - obrazki zamiast zapisu w LaTeX-u.
Powód: Nieregulaminowy zapis - obrazki zamiast zapisu w LaTeX-u.
-
Janusz Tracz
- Użytkownik
- Posty: 4068
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1393 razy
Re: Tożsamość - Wykaż, że...
A może historyjka kombinatoryczna wystarczy? Weź dwa zbiory o \(\displaystyle{ n}\) elementach (parami różnych). Na ile sposobów można wybrać z nich \(\displaystyle{ n}\) elementów?
\(\displaystyle{ 1)}\) Można połączyć te dwa zbiory w zbiór \(\displaystyle{ 2n}\) elementowy i wybrać \(\displaystyle{ n}\) na \(\displaystyle{ {2n \choose n} }\) sposobów.
\(\displaystyle{ 2)}\) można z pierwszego wybrać \(\displaystyle{ k}\) na \(\displaystyle{ {n \choose k} }\) i z drugiego \(\displaystyle{ n-k}\) na \(\displaystyle{ {n \choose n-k} }\) sposobów idąc po wszystkich \(\displaystyle{ k\in\left\{ 0,1,...,n\right\} }\) dostaniemy wszystkie możliwości. Stąd mamy \(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}}\)
Czyli mamy \(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}= {2n \choose n} }\)
\(\displaystyle{ 1)}\) Można połączyć te dwa zbiory w zbiór \(\displaystyle{ 2n}\) elementowy i wybrać \(\displaystyle{ n}\) na \(\displaystyle{ {2n \choose n} }\) sposobów.
\(\displaystyle{ 2)}\) można z pierwszego wybrać \(\displaystyle{ k}\) na \(\displaystyle{ {n \choose k} }\) i z drugiego \(\displaystyle{ n-k}\) na \(\displaystyle{ {n \choose n-k} }\) sposobów idąc po wszystkich \(\displaystyle{ k\in\left\{ 0,1,...,n\right\} }\) dostaniemy wszystkie możliwości. Stąd mamy \(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}}\)
Czyli mamy \(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}= {2n \choose n} }\)
Re: Tożsamość - Wykaż, że...
Wiem, że
\(\displaystyle{ \binom{n}{n-k}=\binom{n}{k}}\)
Niestety nadal nie wiem jak przeprowadzić dowód.
Byłabym wdzięczna za wytłumaczenie krok po kroku.
\(\displaystyle{ \binom{n}{n-k}=\binom{n}{k}}\)
Niestety nadal nie wiem jak przeprowadzić dowód.
Byłabym wdzięczna za wytłumaczenie krok po kroku.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Tożsamość - Wykaż, że...
dosia, Twoja próba jest niestety niepoprawna, a to dlatego, że \(\displaystyle{ (2n)!\neq 2\cdot n!}\), więc nie możesz tam sobie skrócić \(\displaystyle{ n!}\). Poza tym uważam, że wyjaśnienie, które przedstawił Janusz Tracz, jest dość dokładne.
Skoro wiesz, czego masz dowodzić, to można też przeprowadzić indukcję po \(\displaystyle{ n}\), choć jest to znacznie mniej eleganckie i nie polecam. Jeszcze inny pomysł to policzenie na dwa sposoby współczynnika przy \(\displaystyle{ x^{n}}\) w wielomianie \(\displaystyle{ P(x)=(1+x)^{2n}}\). Z jednej strony na mocy wzoru dwumianowego Newtona wynosi on oczywiście \(\displaystyle{ {2n\choose n}}\), z drugiej strony możemy zapisać
\(\displaystyle{ (1+x)^{2n}=(1+x)^{n}(1+x)^{n}}\), rozwinąć to ze wzoru dwumianowego Newtona w
\(\displaystyle{ \left(\sum_{k=0}^{n}{n\choose k}x^{k}\right)\left(\sum_{l=0}^{n}{n\choose l}x^{l}\right)}\)
i wymnożyć. Po wymnożeniu widzimy, że przy \(\displaystyle{ x^{n}}\) będzie stal współczynnik równy
\(\displaystyle{ \sum_{0\le k, l\le n, \ k+l=n}{n\choose k}{n\choose l}=\sum_{k=0}^{n}{n\choose k}{n\choose n-k}}\)
Skoro wiesz, czego masz dowodzić, to można też przeprowadzić indukcję po \(\displaystyle{ n}\), choć jest to znacznie mniej eleganckie i nie polecam. Jeszcze inny pomysł to policzenie na dwa sposoby współczynnika przy \(\displaystyle{ x^{n}}\) w wielomianie \(\displaystyle{ P(x)=(1+x)^{2n}}\). Z jednej strony na mocy wzoru dwumianowego Newtona wynosi on oczywiście \(\displaystyle{ {2n\choose n}}\), z drugiej strony możemy zapisać
\(\displaystyle{ (1+x)^{2n}=(1+x)^{n}(1+x)^{n}}\), rozwinąć to ze wzoru dwumianowego Newtona w
\(\displaystyle{ \left(\sum_{k=0}^{n}{n\choose k}x^{k}\right)\left(\sum_{l=0}^{n}{n\choose l}x^{l}\right)}\)
i wymnożyć. Po wymnożeniu widzimy, że przy \(\displaystyle{ x^{n}}\) będzie stal współczynnik równy
\(\displaystyle{ \sum_{0\le k, l\le n, \ k+l=n}{n\choose k}{n\choose l}=\sum_{k=0}^{n}{n\choose k}{n\choose n-k}}\)