Własność współczynników dwumianowych

[tomwanderer]

Hej, ostatnio zastanawiałem się nad wykazaniem poniższej równości:

\(\displaystyle{ \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ść:    

\(\displaystyle{ \sum_{k=0}^n{n+k\choose n}\cdot \frac{1}{2^k}=}\)
rozpisuję
\(\displaystyle{ ={n\choose n}+\frac{1}{2}\cdot {n+1\choose n}+\frac{1}{4}\cdot{n+2\choose n}+...+\frac{1}{2^{n-1}}\cdot{2n-1 \choose n}+\frac{1}{2^n}\cdot{2n\choose n}=}\)
przekształcam pierwszy składnik
\(\displaystyle{ ={n+1\choose n+1}+\frac{1}{2}\cdot {n+1\choose n}+\frac{1}{4}\cdot{n+2\choose n}+...+\frac{1}{2^{n-1}}\cdot{2n-1 \choose n}+\frac{1}{2^n}\cdot{2n\choose n}=}\)
rozdzielam pierwszy składnik na dwa składniki
\(\displaystyle{ =\frac{1}{2}\cdot{n+1\choose n+1}+\frac{1}{2}\cdot{n+1\choose n+1}+\frac{1}{2}\cdot {n+1\choose n}+\frac{1}{4}\cdot{n+2\choose n}+...+\frac{1}{2^{n-1}}\cdot{2n-1 \choose n}+\frac{1}{2^n}\cdot{2n\choose n}=}\)
"zwijam" drugi i trzeci składnik ze znanej zależności
\(\displaystyle{ =\frac{1}{2}\cdot {n+1\choose n+1}+\frac{1}{2}\cdot {n+2\choose n+1}+\frac{1}{4}\cdot{n+2\choose n}+...+\frac{1}{2^{n-1}}\cdot{2n-1 \choose n}+\frac{1}{2^n}\cdot{2n\choose n}=}\)
rozpisuję drugi składnik
\(\displaystyle{ =\frac{1}{2}\cdot {n+1\choose n+1}+\frac{1}{4}\cdot {n+2\choose n+1}+\frac{1}{4}\cdot {n+2\choose n+1}+\frac{1}{4}\cdot{n+2\choose n}+...+\frac{1}{2^{n-1}}\cdot{2n-1 \choose n}+\frac{1}{2^n}\cdot{2n\choose n}=}\)
"zwijam" trzeci i czwarty składnik
\(\displaystyle{ =\frac{1}{2}\cdot {n+1\choose n+1}+\frac{1}{4}\cdot {n+2\choose n+1}+\frac{1}{4}\cdot {n+3\choose n+1}+...+\frac{1}{2^{n-1}}\cdot{2n-1 \choose n}+\frac{1}{2^n}\cdot{2n\choose n}=}\)
robię tak dalej, aż otrzymam:
\(\displaystyle{ =\frac{1}{2}\cdot {n+1\choose n+1}+\frac{1}{4}\cdot {n+2\choose n+1}+\frac{1}{8}\cdot {n+3\choose n+1}+...+\frac{1}{2^n}\cdot{2n \choose n+1}+\frac{1}{2^n}\cdot{2n \choose n+1}+\frac{1}{2^n}\cdot{2n\choose n}=}\)
gdzie ostatni składnik jest jedynym, jaki pozostał ze "starej" postaci sumy. Teraz przekształcam dwa ostatnie składniki i otrzymuję:
\(\displaystyle{ =\frac{1}{2}\cdot {n+1\choose n+1}+\frac{1}{4}\cdot {n+2\choose n+1}+\frac{1}{8}\cdot {n+3\choose n+1}+...+\frac{1}{2^n}\cdot{2n \choose n+1}+\frac{1}{2^n}\cdot{2n+1 \choose n+1}=}\)
następnie rozpisuję dwa ostatnie składniki:
\(\displaystyle{ =\frac{1}{2}\cdot {n+1\choose n+1}+\frac{1}{4}\cdot {n+2\choose n+1}+\frac{1}{8}\cdot {n+3\choose n+1}+...+\frac{1}{2^n}\cdot{2n \choose n+1}+\frac{1}{2^{n+1}}\cdot{2n+1 \choose n+1}+\frac{1}{2^{n+1}}\cdot{2n+1 \choose n+1}=}\)

Teraz pozostało zauważyć, że:
\(\displaystyle{ {2n+1 \choose n+1}={2n+1 \choose n}}\)
oraz
\(\displaystyle{ {2n+2\choose n+1}={2n+1 \choose n}\cdot \frac{2n+2}{n+1}=2\cdot {2n+1 \choose n}}\)
wobec czego ostatni składnik możemy zapisać jako:
\(\displaystyle{ \frac{1}{2^{n+1}}\cdot{2n+1 \choose n+1}=\frac{1}{2^{n+1}}\cdot{2n+1 \choose n}=\frac{1}{2^{n+1}}\cdot \frac{1}{2}\cdot {2n+2\choose n+1}=\frac{1}{2^{n+2}}\cdot {2n+2\choose n+1}}\)

W związku z tym cała prawa strona wynosi:
\(\displaystyle{ \sum_{k=0}^{n+1}\frac{1}{2^{k+1}}{n+1+k\choose n+1}=\frac{1}{2}\sum_{k=0}^{n+1}\frac{1}{2^k}{n+1+k\choose n+1}}\)
A to oznacza, że:
\(\displaystyle{ \sum_{k=0}^n\frac{1}{2^k}\cdot{n+k\choose n}=\frac{1}{2}\sum_{k=0}^{n+1}\frac{1}{2^k}{n+1+k\choose n+1}}\)

Po oznaczeniu odpowiednich sum przez \(\displaystyle{ S(n)}\) i \(\displaystyle{ S(n+1)}\) możemy zapisać, że:
\(\displaystyle{ S(n+1)=2S(n)}\)

W połączeniu z faktem, że \(\displaystyle{ S(0)={0\choose 0}=1=2^0}\), otrzymujemy tezę.

EDIT
Czy wystarczy wiedzieć, że funkcją tworzącą ciągu \(\displaystyle{ a_k={n+k\choose n}}\) jest \(\displaystyle{ \frac{1}{(1-x)^{n+1}}}\) ?
Wtedy
\(\displaystyle{ \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 \(\displaystyle{ b_k={2n+k\choose n}}\) zgadza się?

Swoją drogą, wychodzi na to, że \(\displaystyle{ \sum_{k=1}^{\infty}\frac{1}{2^k}{2n+k\choose n}=4^n}\)

[Premislav]

Moja propozycja dowodu, że
\(\displaystyle{ \sum_{k=0}^n{n+k\choose n}\cdot \frac{1}{2^k}=2^n}\):
mamy
\(\displaystyle{ \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
\(\displaystyle{ \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 \(\displaystyle{ \left\{ 1, 2, \ldots 2n\right\}}\) w zbiór \(\displaystyle{ \left\{ 0,1\right\}}\) (czy tam jakikolwiek dwuelementowy). Zauważmy, że któraś z wartości \(\displaystyle{ 0,1}\) pojawi się co najmniej \(\displaystyle{ n}\) razy. Zatem dla pewnego \(\displaystyle{ k\in\left\{ 0,1, \ldots n\right\}}\)
wyborów tej „częstszej wartości" wśród elementów \(\displaystyle{ 1,2, \ldots 2n-k}\) będzie dokładnie \(\displaystyle{ n}\) (ustalmy największe takie \(\displaystyle{ k}\), tj. najmniejsze \(\displaystyle{ 2n-k}\)) – możemy je wybrać dla ustalonego \(\displaystyle{ k}\) na \(\displaystyle{ {2n-k \choose n}}\) sposobów, a pozostałym elementom \(\displaystyle{ 2n-k+1, \ldots 2n}\), których jest dokładnie \(\displaystyle{ k}\), możemy przypisać wartości na \(\displaystyle{ 2^k}\) sposobów.