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.
 A: Let $s_n=\displaystyle\sum_{k=0}^n\binom{n+k}k\frac1{2^k}$. Then
$$\begin{align*}
s_{n+1}&=\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}\\
&=\binom{2n+1}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=0}^n\binom{n+1+k}k\frac1{2^{k+1}}\\
&=\binom{2n+1}{n+1}\frac1{2^{n+1}}+s_n+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\
&=s_n+\frac12\left(s_{n+1}-\binom{2n+2}{n+1}\frac1{2^{n+1}}\right)+\binom{2n+1}{n+1}\frac1{2^{n+1}}\\
&=s_n+\frac12s_{n+1}+\binom{2n+1}{n+1}\frac1{2^{n+1}}-\binom{2n+2}{n+1}\frac1{2^{n+2}}\;,
\end{align*}$$
and therefore
$$\begin{align*}
s_{n+1}&=2s_n+\binom{2n+1}{n+1}\frac1{2^n}-\binom{2n+2}{n+1}\frac1{2^{n+1}}\\
&=2s_n+\frac1{2^{n+1}}\left(2\binom{2n+1}{n+1}-\binom{2n+2}{n+1}\right)\\
&=2s_n+\frac1{2^{n+1}}\left(2\binom{2n+1}{n+1}-\binom{2n+1}{n+1}-\binom{2n+1}n\right)\\
&=2s_n+\frac1{2^{n+1}}\left(\binom{2n+1}{n+1}-\binom{2n+1}n\right)\\
&=2s_n\;.
\end{align*}$$
A: You correctly used Pascal's identity, but then you goofed going to the next line. (Should have an $n$ in that last exponent of $2$, not a $k$.) I recommend going a different way, though.
$\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+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^{n+1}\binom{n+k}{k-1}\frac1{2^k}\\
& = & \sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=1}^{n+1}\binom{n+k}{k-1}\frac1{2^k}\\
& = & \sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k+1}{k}\frac1{2^{k+1}}\\
& = & -\binom{2n+2}{n+1}\frac1{2^{n+2}}+\sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^{k+1}}\\
& = & -\binom{2n+2}{n+1}\frac1{2^{n+2}}+\sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\frac12\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}.
\end{eqnarray*}$
You see how we have half the original sum on the right-hand side now? If we subtract that and then multiply by $2$, we have 
$\begin{eqnarray*}
\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k} & = & -\binom{2n+2}{n+1}\frac1{2^{n+1}}+2\sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}\\
& = & -\binom{2n+2}{n+1}\frac1{2^{n+1}}+2\binom{2n+1}{n+1}\frac1{2^{n+1}}+2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.
\end{eqnarray*}$
Finally, applying Pascal's identity to $\binom{2n+2}{n+1}$, and using the fact that $\binom{2n+1}{n}=\binom{2n+1}{n+1},$ the extraneous binomial coefficients cancel out, and we're left with $$\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},$$ as desired.
A: 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.
A: The following is proving a scaled version of the required equation:
$$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^{n+k+2}}=\sum_{k=0}^n\binom{n+k}{k}\frac1{2^{n+k+1}},$$
and based on my answer in another question.
The product being summed is the PMF of the negative binomial distribution, which considers flipping a fair coin repeatedly until having a fixed number of heads, and counts the number of tails that showed up.

The left hand side models flipping a fair coin repeatedly until having $n+2$ heads, then add the probabilities of having $n+1$ or fewer tails. Let $\Pr(A)$ be the sum of probabilities.
Then $1-\Pr(A)$ is the probability of having the $(n+2)$th tail while only having $n+1$ heads or fewer.
For a fair coin, head and tail are symmetric, and so
$$\Pr(A) = 1-\Pr(A) = \frac 12$$

The right hand side is similar, this time modelling flipping a fair coin repeatedly until having $n+1$ heads, and adding the probabilities of having $n$ or fewer tails.
So both the left and right hand sides are equal to $\frac12$, which is also the "base case" where $n=0$:
$$\sum_{k=0}^0 \binom {0+k}k \frac{1}{2^{0+k+1}} = \binom00\frac{1}{2} = \frac12$$
