szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 cze 2018, o 11:22 
Użytkownik

Posty: 152
Lokalizacja: obecnie Łódź
Hej, ostatnio zastanawiałem się nad wykazaniem poniższej równości:

\sum_{k=0}^n{n+k\choose n}\cdot \frac{1}{2^k}=2^n

Wygląda na to, że ją wykazałem, jednak ciekawi mnie, czy ktoś zna interpretację kombinatoryczną tej równości, ewentualnie dowód krótszy od mojego.

Poniżej mój tok rozumowania:

Ukryta treść:    


EDIT
Czy wystarczy wiedzieć, że funkcją tworzącą ciągu a_k={n+k\choose n} jest \frac{1}{(1-x)^{n+1}} ?
Wtedy
\sum_{k=0}^n{n+k\choose n}\cdot \frac{1}{2^k}=2^{n+1}-\sum_{k=n+1}^{\infty}\frac{1}{2^k} {n+k \choose n}=2^{n+1}-\frac{1}{2^n}\sum_{k=1}^{\infty}\frac{1}{2^k}{2n+k\choose n}
ale trzeba by było jeszcze znać funkcję tworzącą dla ciągu liczb b_k={2n+k\choose n} zgadza się?

Swoją drogą, wychodzi na to, że \sum_{k=1}^{\infty}\frac{1}{2^k}{2n+k\choose n}=4^n
Góra
Mężczyzna Offline
PostNapisane: 14 cze 2018, o 09:08 
Użytkownik

Posty: 12935
Moja propozycja dowodu, że
\sum_{k=0}^n{n+k\choose n}\cdot \frac{1}{2^k}=2^n:
mamy
\sum_{k=0}^n{n+k\choose n}\cdot \frac{1}{2^k}= \sum_{k=0}^{n} {2n-k \choose n}\cdot \frac{1}{2^{n-k}}=\\=\frac{1}{2^n} \sum_{k=0}^{n}{2n-k \choose n}2^k
(po prostu odwróciłem kolejność sumowania)
i teraz możemy uzasadnić, że
\sum_{k=0}^{n}{2n-k \choose n}2^k=4^n.
Niestety mam jakieś poważne zaćmienie i chwilowo nie potrafię tego pokazać kombinatorycznie, ale to na pewno jest prawda. :|

-- 14 cze 2018, o 09:22 --

Dobra, to było proste:
zliczamy funkcje ze zbioru \left\{ 1, 2, \ldots 2n\right\} w zbiór \left\{ 0,1\right\} (czy tam jakikolwiek dwuelementowy). Zauważmy, że któraś z wartości 0,1 pojawi się co najmniej n razy. Zatem dla pewnego k\in\left\{ 0,1, \ldots n\right\}
wyborów tej „częstszej wartości" wśród elementów 1,2, \ldots 2n-k będzie dokładnie n (ustalmy największe takie k, tj. najmniejsze 2n-k) – możemy je wybrać dla ustalonego k na {2n-k \choose n} sposobów, a pozostałym elementom 2n-k+1, \ldots 2n, których jest dokładnie k, możemy przypisać wartości na 2^k sposobów.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Własność symbolu Newtona. Dowód.  myszka9  13
 Własność symbolu Newtona  moss2  11
 Własność ciągu Fibonacciego, postać zwarta sumy  Stonek007  3
 Własność podzbiorów  mol_ksiazkowy  4
 Własność symbolu Newtona - zadanie 2  Nexus420  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl