\(\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.
Dowod tożsamości - funkcje tworzące
-
- 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
\(\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.
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.
-
- 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
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..
interpretację kombinatoryczną tego kiedyś widziałem, ale wydawała się być bardzo ciężka..
- acmilan
- 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
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}}\)
\(\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}}\)
-
- 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
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}}\)
-- 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.