Wykaż tożsamość:
\(\displaystyle{ \sum_{k m} {n+m\choose k}x^ky^{m-k}=\sum_{k m} {-n\choose k}(-x)^k(x+y)^{m-k}}\)
gdzie m jest całkowite i \(\displaystyle{ {n\choose k}}\) jest uogólnionym współczynnikiem dwumianowym.
[Kombinatoryka] wykazać tożsamość
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
robin5hood
- Użytkownik
- Posty: 1676
- Rejestracja: 2 kwie 2007, o 14:43
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 178 razy
- Pomógł: 17 razy
-
ironleaf
- Użytkownik
- Posty: 66
- Rejestracja: 31 gru 2008, o 19:07
- Płeć: Mężczyzna
- Lokalizacja: Wojsławice
- Podziękował: 4 razy
- Pomógł: 8 razy
[Kombinatoryka] wykazać tożsamość
No to dwa fakciki:
1. tożsamość Cauchy'ego (lub Vandermonde'a) prawdziwa dla dowolnych \(\displaystyle{ a,b}\) rzeczywistych
\(\displaystyle{ \sum_{k \geq 0}{{a \choose k}{b \choose {n-k}}}={{a+b}\choose{n}}}\)
(znany jest szeroko dowód dla naturalnych, ale po obu stronach stoją wielomiany, a skoro pokrywają się w nieskończenie wielu punktach, to są równe)
2. negacja górnego indeksu
\(\displaystyle{ {n \choose k}=\frac{(-n)(-n+1)...(-n+k-1)}{k!} (-1)^{k}=(-1)^{k}{{k-n-1}\choose k}}\).
Do dzieła. Przepiszmy tezę, zmieniając mylącą nazwę indeksu i rozwijając potęgę z dwumianu Newtona
\(\displaystyle{ \sum_{k \leq m}{ {{n+m} \choose k}x^{k}y^{m-k} }=\sum_{s \leq m} {\left( (-1)^{s}{{-n} \choose s} x^{s} \sum_{t \geq 0}{ {{m-s} \choose t} x^{t}y^{m-s-t} } \right)}}\).
Wystarczy pokazać, że współczynnik przy jednomianie \(\displaystyle{ x^{k}y^{m-k}}\) po obu stronach jest jednakowy (\(\displaystyle{ k=s+t}\)), tj.
\(\displaystyle{ {{n+m} \choose k}=\sum_{s \leq m} {(-1)^{s} {{-n} \choose s} {{m-s} \choose {k-s}}}}\).
Fakcik 2 daje:
\(\displaystyle{ {{m-s} \choose {k-s}}=(-1)^{k-s}{ {k-m-1} \choose {k-s}}}\).
Mamy więc
\(\displaystyle{ \sum_{s \leq m} {(-1)^{s} {{-n} \choose s} {{m-s} \choose {k-s}}}=(-1)^{k}\sum_{s \leq m}{ {{-n} \choose s} {{k-m-1} \choose {k-s}}}}\)
Wyrazy niezerowe tylko dla \(\displaystyle{ s \leq k}\), ale \(\displaystyle{ k \leq m}\), więc suma przebiega po wszystkich wyrazach niezerowych. Ma więc zastosowanie fakcik 1 i dostajemy:
\(\displaystyle{ (-1)^{k}{ {k-m-n-1} \choose k}}\) a to jest właśnie \(\displaystyle{ {{n+m} \choose k}}\) na mocy 2.
Zainteresowanym podobonymi zabawami, a także obliczaniem skomplikowanych sum i rozwiązywaniem trudniejszych rekurencji (patrz ostatnio zamknięty Matmix) polecam "Matematykę konkretną". To z niej wziąłem negację górnego indeksu.
1. tożsamość Cauchy'ego (lub Vandermonde'a) prawdziwa dla dowolnych \(\displaystyle{ a,b}\) rzeczywistych
\(\displaystyle{ \sum_{k \geq 0}{{a \choose k}{b \choose {n-k}}}={{a+b}\choose{n}}}\)
(znany jest szeroko dowód dla naturalnych, ale po obu stronach stoją wielomiany, a skoro pokrywają się w nieskończenie wielu punktach, to są równe)
2. negacja górnego indeksu
\(\displaystyle{ {n \choose k}=\frac{(-n)(-n+1)...(-n+k-1)}{k!} (-1)^{k}=(-1)^{k}{{k-n-1}\choose k}}\).
Do dzieła. Przepiszmy tezę, zmieniając mylącą nazwę indeksu i rozwijając potęgę z dwumianu Newtona
\(\displaystyle{ \sum_{k \leq m}{ {{n+m} \choose k}x^{k}y^{m-k} }=\sum_{s \leq m} {\left( (-1)^{s}{{-n} \choose s} x^{s} \sum_{t \geq 0}{ {{m-s} \choose t} x^{t}y^{m-s-t} } \right)}}\).
Wystarczy pokazać, że współczynnik przy jednomianie \(\displaystyle{ x^{k}y^{m-k}}\) po obu stronach jest jednakowy (\(\displaystyle{ k=s+t}\)), tj.
\(\displaystyle{ {{n+m} \choose k}=\sum_{s \leq m} {(-1)^{s} {{-n} \choose s} {{m-s} \choose {k-s}}}}\).
Fakcik 2 daje:
\(\displaystyle{ {{m-s} \choose {k-s}}=(-1)^{k-s}{ {k-m-1} \choose {k-s}}}\).
Mamy więc
\(\displaystyle{ \sum_{s \leq m} {(-1)^{s} {{-n} \choose s} {{m-s} \choose {k-s}}}=(-1)^{k}\sum_{s \leq m}{ {{-n} \choose s} {{k-m-1} \choose {k-s}}}}\)
Wyrazy niezerowe tylko dla \(\displaystyle{ s \leq k}\), ale \(\displaystyle{ k \leq m}\), więc suma przebiega po wszystkich wyrazach niezerowych. Ma więc zastosowanie fakcik 1 i dostajemy:
\(\displaystyle{ (-1)^{k}{ {k-m-n-1} \choose k}}\) a to jest właśnie \(\displaystyle{ {{n+m} \choose k}}\) na mocy 2.
Zainteresowanym podobonymi zabawami, a także obliczaniem skomplikowanych sum i rozwiązywaniem trudniejszych rekurencji (patrz ostatnio zamknięty Matmix) polecam "Matematykę konkretną". To z niej wziąłem negację górnego indeksu.