<s>[INST] Prove the following relation: I must prove the relation $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$
I got this far before I got stuck:
$\begin{eqnarray*}
\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k} & = & \sum_{k=0}^{n+1}\left\{\binom{n+k}{k}+\binom{n+k}{k-1}\right\}\frac1{2^k}\\
& = & \sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k-1}\frac1{2^k}+\binom{2n+1}{n}\frac1{2^k}.
\end{eqnarray*}$
If I can combine the second and third terms and get something same as first term, I am done but I could not do that.
 [/INST] By  way of  enrichment here  is  another algebraic  proof using  basic
complex variables.

Suppose we are trying to show that
$$\sum_{k=0}^{n+1} {n+1+k\choose k} \frac{1}{2^k}
= 2 \sum_{k=0}^n {n+k\choose k} \frac{1}{2^k}.$$
Introduce the integral representations
$${n+1+k\choose k}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{n+1+k}}{z^{k+1}} \; dz.$$

This gives for the LHS the integral
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{n+1}}{z} 
\sum_{k=0}^{n+1} \frac{(1+z)^k}{z^k\times 2^k}\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{n+1}}{z} 
\frac{1-((1+z)/z/2)^{n+2}}{1-(1+z)/z/2} \; dz
\\ = 2\times \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{n+1}}{z} 
\frac{1-((1+z)/z/2)^{n+2}}{2-(1+z)/z} \; dz
\\ = 2\times \frac{1}{2\pi i}
\int_{|z|=\epsilon}
(1+z)^{n+1} 
\frac{1-((1+z)/z/2)^{n+2}}{2z-(1+z)} \; dz
\\ = 2\times \frac{1}{2\pi i}
\int_{|z|=\epsilon}
(1+z)^{n+1} 
\frac{1-((1+z)/z/2)^{n+2}}{z-1} \; dz.$$
Now the first term in the numerator clearly gives a zero contribution
so we get
$$2\times \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{n+1}}{1-z}
\frac{(1+z)^{n+2}}{z^{n+2} 2^{n+2}} \; dz
\\ \frac{1}{2^{n+1}} \times \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{2n+3}}{1-z}
\frac{1}{z^{n+2}} \; dz.$$
Extracting the residue we find
$$\frac{1}{2^{n+1}} \sum_{q=0}^{n+1} {2n+3\choose q}
= \frac{1}{2^{n+2}} \sum_{q=0}^{2n+3} {2n+3\choose q}
= \frac{1}{2^{n+2}} 2^{2n+3} = 2^{n+1}.$$
Now the RHS is just twice the LHS with $n+1$ replaced by $n$ so we get
$$2\times 2^n = 2^{n+1}$$
and the two are indeed the same as claimed.

We have  not made use of  the properties of complex  integrals here so
this  computation  can  also   be  presented  using  just  algebra  of
generating functions.

Apparently  this method is  due to  Egorychev although  some of  it is
probably folklore.
</s>