MHB Binomial Sum \displaystyle \sum^{n}_{k=0}\binom{n+k}{k}\cdot \frac{1}{2^k}

[juantheron]

Evaluation of $\displaystyle \sum^{n}_{k=0}\binom{n+k}{k}\cdot \frac{1}{2^k}$

 

[juantheron]

Spoiler

$$S = \sum_{k=0}^n {n+k\choose n} \frac{1}{2^k}
= \sum_{k=0}^n \frac{1}{2^k} [z^n] (1+z)^{n+k}
= [z^n] (1+z)^n \sum_{k=0}^n \frac{1}{2^k} (1+z)^k
\\ = [z^n] (1+z)^n
\frac{1-(1+z)^{n+1}/2^{n+1}}{1-(1+z)/2}
= [z^n] (1+z)^n
\frac{2-(1+z)^{n+1}/2^{n}}{1-z}
\\ = 2\times 2^n
- [z^n] (1+z)^{2n+1} \frac{1}{2^n} \frac{1}{1-z}
\\ = 2\times 2^n
- \frac{1}{2^n} \sum_{k=0}^n {2n+1\choose k}
= 2\times 2^n - \frac{1}{2^n} \frac{1}{2} 2^{2n+1}
= 2^n.$$