Доказательство тождества с биноном

[kthxbye]

Какие существуют элементарные доказательства приведенного ниже тождества?

$$\sum\limits_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^n$$

Одно из не элементарных использует тождество

$$\sum\limits_{k=0}^{n}\binom{k+m}{m}z^k=\frac{1}{(1-z)^{m+1}}-\frac{z^{n+1}}{(1-z)^{m+1}}\sum\limits_{k=0}^{m}\binom{n+k}{k}(1-z)^k$$

куда мы подставляем $n=m$ и $z=\frac{1}{2}$

$$\sum\limits_{k=0}^{n}\binom{k+n}{n}\frac{1}{2^k}=\frac{1}{\frac{1}{2^{n+1}}}-\frac{\frac{1}{2^{n+1}}}{\frac{1}{2^{n+1}}}\sum\limits_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}$$

$$S=2^{n+1}-S, 2S = 2^{n+1}, S=2^n$$

[nnosipov]

kthxbye в сообщении #1490113 писал(а):

Какие существуют элементарные доказательства приведенного ниже тождества?

А индукция по $n$ не годится?

Upd. Годится, но не совсем. Напишем тождество $C_{n+1+k}^k=C_{n+k}^k+C_{n+k}^{k-1}$, разделим его обе части на $2^k$ и просуммируем по $k$ от $0$ до $n+1$. В результате возникнет рекуррентное соотношение $f(n+1)=2f(n)$, где $f(n)$ --- сумма, которую хочется вычислить.

[lek]

Есть простое комбинаторное доказательство этого тождества, предложенное Тамасом Лендьелом в 1993 г. (См. здесь, стр. 1).

[abs135]

Наверное, можно через перемножение производящих функций.
Если, конечно, это достаточно элементарно

[kotenok gav]

Формула (5.20) в Конкретной математике, доказательство буквально в две строчки.

[nnosipov]

kotenok gav в сообщении #1495553 писал(а):

доказательство буквально в две строчки

Ну конечно, две строчки. Сначала нужно придумать тождество (5.19) с многочленами от двух переменных $x$ и $y$ (вот это самое нетривиальное), потом доказать его (одно из доказательств, кстати, по индукции) и, наконец, рассмотреть частный случай $x=y=1$.

[TOTAL]

То есть доказать

$$\sum\limits_{k=0}^{n}2^{n-k}C_{n+k}^{n}=2^{2n}$$

Слева стоит коэффициент при $x^n$ в полиноме

$$\dfrac{2^{2n+1}-(1+x)^{2n+1}}{1-x}$$

Почленно

$$2^{2n+1}-\sum\limits_{k=0}^{n}C_{2n+1}^k=2^{2n+1}-2^{2n}$$