Dowod tożsamości - funkcje tworzące

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
dusiek
Użytkownik
Użytkownik
Posty: 24
Rejestracja: 19 paź 2011, o 19:39
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy

Dowod tożsamości - funkcje tworzące

Post autor: dusiek »

\(\displaystyle{ \sum_{k = 0}^{n} {2k \choose k} {2n - 2k \choose n - k} = 4^{n}}\)

Muszę to udowodnić za pomocą funkcji tworzących, ale niestety nie mam za bardzo pomysłu jak
Próbowałem w ten sposób:

\(\displaystyle{ \sum_{n = 0}^{\infty} \left( \sum_{k = 0}^{n} {2k \choose k} {2n - 2k \choose n - k} \right) x^{n} = \left( \sum_{n = 0}^{\infty} {2n \choose n} x^{n} \right) ^{2} = \sum_{n = 0}^{ \infty } 4^{n} x^{n}}\) i później indukcyjnie, ale nic sensownego mi nie wychodzi...

Prosiłbym o wskazówki Jakby ktoś znał dodatkowo jakąś interpretacje kombinatoryczną to też byłoby dobrze, ale rozwiązanie z funkcjami tworzącymi byłoby lepsze.
luka52
Użytkownik
Użytkownik
Posty: 8601
Rejestracja: 1 maja 2006, o 20:54
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 47 razy
Pomógł: 1816 razy

Dowod tożsamości - funkcje tworzące

Post autor: luka52 »

Pokaż, że:
\(\displaystyle{ \sum_{n = 0}^{\infty} {2n \choose n} x^{n} = \frac{1}{\sqrt{1 - 4x}}}\)
dusiek
Użytkownik
Użytkownik
Posty: 24
Rejestracja: 19 paź 2011, o 19:39
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy

Dowod tożsamości - funkcje tworzące

Post autor: dusiek »

\(\displaystyle{ \sum_{n = 0}^{\infty} {2n \choose n} x^{n} = \sum_{n = 0}^{\infty} (-4)^n{ -\frac{1}{2} \choose n} *x^{n}}\)

Bazę indukcji pomijam. Załóżmy, że \(\displaystyle{ {2n \choose n} = \left(-4\right)^{n}{ -\frac{1}{2} \choose n}}\)

\(\displaystyle{ {2n + 2 \choose n + 1} = \frac{\left(2n + 2 \right)\left( 2n + 1\right) }{\left( n + 1\right)^2 } {2n \choose n} = \frac{2\left(2n + 1 \right) }{n + 1}*\left(-4\right)^{n}{ -\frac{1}{2} \choose n} = \\
\frac{-4\left(-\frac{1}{2} - n \right) }{n + 1}*\left(-4\right)^{n}{ -\frac{1}{2} \choose n} =
\left(-4\right)^{n+1}{ -\frac{1}{2} \choose n + 1}}\)


Wcześniej jakoś mi nie wychodziło Dzięki za pomoc. Może ktoś jeszcze spróbuje to udowodnić interpretacja kombinatoryczną, ale chyba będzie ciężko.
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

Dowod tożsamości - funkcje tworzące

Post autor: adambak »

można też sobie przypomnieć jak wygląda funkcja tworząca ciągu liczb Catalana i wtedy wystarczy domnożyć przez \(\displaystyle{ x}\), zróżniczkować i gotowe..

interpretację kombinatoryczną tego kiedyś widziałem, ale wydawała się być bardzo ciężka..
Awatar użytkownika
acmilan
Użytkownik
Użytkownik
Posty: 402
Rejestracja: 27 kwie 2009, o 15:29
Płeć: Mężczyzna
Lokalizacja: Warszawa-Praga
Podziękował: 40 razy
Pomógł: 50 razy

Dowod tożsamości - funkcje tworzące

Post autor: acmilan »

Mam pytanie, skąd bierze się równość:

\(\displaystyle{ \frac{1}{\sqrt{1-4x}}=\sum_{n = 0}^{\infty} (-4)^n{ -\frac{1}{2} \choose n} *x^{n}}\)?

Według mnie powinno być:

\(\displaystyle{ \frac{1}{\sqrt{1-4x}}=\sum_{n = 0}^{\infty} 4^n{ n-\frac{1}{2} \choose -\frac{1}{2}} *x^{n}}\)
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

Dowod tożsamości - funkcje tworzące

Post autor: adambak »

bo to jest to samo

-- 4 wrz 2012, o 16:20 --

o czym można się przekonać negując górny wskaźnik: \(\displaystyle{ (-1)^n {-\frac{1}{2} \choose n}}\)
Ostatnio zmieniony 4 wrz 2012, o 15:22 przez adambak, łącznie zmieniany 2 razy.
Awatar użytkownika
acmilan
Użytkownik
Użytkownik
Posty: 402
Rejestracja: 27 kwie 2009, o 15:29
Płeć: Mężczyzna
Lokalizacja: Warszawa-Praga
Podziękował: 40 razy
Pomógł: 50 razy

Dowod tożsamości - funkcje tworzące

Post autor: acmilan »

No tak, już widzę, dzięki.
ODPOWIEDZ