Evaluate $\sum_{r=0}^n 2^{n-r} \binom{n+r}{r}$ 
Evaluate: $$\sum_{r=0}^n 2^{n-r} \binom{n+r}{r}$$


This looks like an unusual hockey stick sum. Here are my attempts:
Method 1:
The sum is equivalent to
$$S=\sum_{r=0}^n 2^{n-r} \binom{n+r}{n}=\sum_{r=0}^n 2^{r} \binom{2n-r}{n-r}$$
and I could evaluate neither of these.
Method 2:
$$S=\text{coefficient of $x^n$ in }:$$
$$2^n(1+x)^n\Bigg( 1+\frac{1+x}{2}+\left(\frac{1+x}{2}\right)^2+\cdots+\left(\frac{1+x}{2}\right)^n \Bigg)$$
$$=(1+x)^n\left(\frac{(1+x)^{n+1}-2^{n+1}}{(x-1)}\right)$$
It looks like a heavy task to collect all the $x^n$ coefficients from this expression.

Im out of ideas. Any hint is appreciated.
From Putnam 2020, Q A2
 A: Let
$$
S_n:=\sum_{k=0}^n\frac{\binom{n+k}{k}}{2^{n+k}}
$$
Obviously $S_0=1$. Assume that equality
$$S_{n-1}=1\tag1$$
is valid for some $n$. Then it is valid for $n+1$ as well:
$$
\begin{align}
S_n
&=\sum_{k=0}^n\frac{\binom{n+k}{k}}{2^{n+k}}\\
&=\sum_{k=0}^n\frac{\binom{n+k-1}{k-1}+\binom{n-1+k}{k}}{2^{n+k}}\\
&=\frac12\sum_{k=0}^{n-1}\frac{\binom{n+k}{k}}{2^{n+k}}+\frac12\sum_{k=0}^n\frac{\binom{n-1+k}{k}}{2^{n-1+k}}\\
&=\frac12S_n-\frac{\binom{2n}{n}}{2^{2n+1}}+\frac12S_{n-1}+\frac{\binom{2n-1}{n}}{2^{2n}}\\
&=\frac12S_n+\frac12S_{n-1}\implies S_n=S_{n-1}\stackrel{I.H.}=1.
\end{align}
$$
Thus, by induction the equality $(1)$ is valid for all integer $n\ge0$.
Accordingly your sum is $2^{2n}S=4^n$.
A: Consider the number of binary strings that are $(2n+1)$ digits long with at least $(n+1)$ digits equal to $1$. Let this number be $S$.
Method 1: Flip the $1$'s into $0$'s and vice versa. This covers all binary strings of length $2n+1$: so $2S=2^{2n+1}\implies S=2^{2n}$
Method 2: Consider the $(n+1)th$ $1$ digit. Suppose this is the $(n+1+r)$th digit of the string. Then this yields the desired sum by hockey stick.
So the answer is $\boxed{2^{2n}}$.
A: In another way
$$
\eqalign{
  & S = \sum\limits_{r = 0}^n {2^{\,n - r}
 \left( \matrix{ n + r \cr  r \cr}  \right)}  =   \cr 
  &  = \sum\limits_{k = 0}^n {\left( \matrix{ 2n - k \cr n - k \cr}  \right)2^{\,k}  = }   \quad (1)\cr 
  &  = \sum\limits_{0\, \le \,k} {\left( \matrix{ 2n - k \cr n - k \cr}  \right)2^{\,k} }  = \quad (2)  \cr 
  &  = \sum\limits_{0\, \le \,k} {\left( \matrix{ 2n - k \cr   n - k \cr}  \right)\left( {1 + 1} \right)^{\,k} }
  = \sum\limits_{0\, \le \,k} {\sum\limits_{0\, \le \,j} {\left( \matrix{ 2n - k \cr  n - k \cr}  \right)
\left( \matrix{ k \cr   k - j \cr}  \right)} }  =  \quad (3) \cr 
  &  = \sum\limits_{0\, \le \,j} {\left( { - 1} \right)^{\,n - j} \sum\limits_{\left( {0\, \le } \right)\,k}
 {\left( \matrix{  - n - 1 \cr  n - k \cr}  \right)\left( \matrix{ - j - 1 \cr   k - j \cr}  \right)} }  =  \quad (4) \cr 
  &  = \sum\limits_{0\, \le \,j} {\left( { - 1} \right)^{\,n - j}
 \left( \matrix{ - n - j - 2 \cr  n - j \cr}  \right)}  = \quad (5)  \cr 
  &  = \sum\limits_{0\, \le \,j} {\left( \matrix{  2n + 1 \cr   n - j \cr}  \right)}
  = \sum\limits_{k = 0}^n {\left( \matrix{ 2n + 1 \cr   k \cr}  \right)}  =   \quad (6)\cr 
  &  = {1 \over 2}\sum\limits_{k = 0}^{2n + 1} {\left( \matrix{ 2n + 1 \cr   k \cr}  \right)}
  = 2^{\,2n} \quad (7) \cr} 
$$
where the steps are:

*

*

*

*change index;



*


*remove upper bound (it is implicit in the binomial);



*


*split the $2$;



*


*upper negation ( $\binom{n}{m}=(-1)^m \binom{m-n-1}{m}$ ) on both binomials;



*


*convolution in $k$,



*


*upper negation;



*


*symmetry of the binomial .



A: 
$$(1+x)^n\left(\frac{(1+x)^{n+1}-2^{n+1}}{(x-1)}\right)$$

You were on the right path, but you just didn't take the final step. Finish:
$$ \frac{(1+x)^n 2^{n+1} }{(1-x)} - \frac{(1+x)^{2n+1} }{(1-x)}$$
Now, I will introduce a 'nice' result( By the cauchy product rule):
$$ \frac{ P(x)}{1-x}= (\sum_i x^i) \sum_{i} a_i x^i = \sum_u c_ux^u$$
Where:
$$ c_u =   \sum_{i=0}^u a_i \tag{1}$$
Hence, the applying the coefficient operator and use(1) while I'm at it:
$$ [x^n] \left[\frac{(1+x)^n 2^{n+1} }{(1-x)} - \frac{(1+x)^{2n+1} }{(1-x)} \right] = 2^{n+1} [x^n] \left[ \frac{(1+x)^n}{1-x} \right]- [x^n] \left[ \frac{(1+x)^{2n+1} }{1-x} \right]\\= 2^{n+1} \sum_{i=0}^n \binom{n}{i}-\sum_{i=0}^n \binom{2n+1}{i}$$
Now, by standard results we can work out the first binomial sum:
$$ 2^{n+1} \sum_{i=0}^n \binom{n}{i} = 2^{2n+1}$$
And, the tricky sum/one step more complicated sum is:
$$ S= \sum_{i=0}^n \binom{2n+1}{i} = \sum_{i=0}^n \binom{2n+1}{(2n+1)-i} = \sum_{i=0}^n \binom{2n+1}{(2n+1) - (n-i) } = \sum_{i=0}^n \binom{2n+1}{n+1+i}$$
This leads to:
$$ 2S = \sum_{i=0}^n \binom{2n+1}{i} + \sum_{i=0}^n \binom{2n+1}{n+1+i} = \sum_{i=0}^n \binom{2n+1}{i} = 2^{2n+1}$$
Or,
$$ S= 2^{2n}$$
Put everything together and you have the answer of $4^n$.
For more information about cauchy product rule, you can check out my article about it here
A: Consider
$$\left( \begin{matrix}
   n  \\
   k  \\
\end{matrix} \right)=\frac{1}{2\pi i}\int\limits_{\left| z \right|=R}^{{}}{\frac{{{\left( 1+z \right)}^{n}}}{{{z}^{k+1}}}dz}$$
so
$$\sum\limits_{r=0}^{n}{{{2}^{n-r}}\left( \begin{matrix}
   n+r  \\
   r  \\
\end{matrix} \right)}=\frac{1}{2\pi i}\int\limits_{\left| z \right|<1}^{{}}{\sum\limits_{r=0}^{n}{{{2}^{n-r}}}\frac{{{\left( 1+z \right)}^{n+r}}}{{{z}^{r+1}}}dz}=\\\frac{1}{2\pi i}\int\limits_{\left| z \right|<1}^{{}}{\frac{{{2}^{n+1}}{{\left( 1+z \right)}^{n}}}{z-1}-\frac{{{\left( 1+z \right)}^{1+2n}}}{\left( z-1 \right){{z}^{n+1}}}dz}\\=\frac{1}{2\pi i}\int\limits_{\left| z \right|<1}^{{}}{\frac{{{\left( 1+z \right)}^{1+2n}}}{\left( 1-z \right){{z}^{n+1}}}dz}$$
Where for convenience we've chosen a circular contour enclosing the origin with radius less than $1$.  We can do this because directly after the summation the only contribution comes from a residue at $z=0$ (note there is no residue at $z=1$ in the second line).  The final line above reflects this. Now to get the residue at $z=0$...
$$res\frac{{{\left( 1+z \right)}^{1+2n}}}{\left( 1-z \right){{z}^{n+1}}}=res\sum\limits_{m=0}^{\infty }{{}}\sum\limits_{k=0}^{\infty }{\left( \begin{matrix}
   1+2n  \\
   k  \\
\end{matrix} \right)\frac{1}{{{z}^{n+1-m-k}}}}\\=\sum\limits_{m=0}^{\infty }{\left( \begin{matrix}
   1+2n  \\
   n-m  \\
\end{matrix} \right)=}\sum\limits_{m=0}^{n}{\left( \begin{matrix}
   1+2n  \\
   n-m  \\
\end{matrix} \right)}=\sum\limits_{m=0}^{n}{\left( \begin{matrix}
   1+2n  \\
   m  \\
\end{matrix} \right)}={{4}^{n}}$$
hence
$$\sum\limits_{r=0}^{n}{{{2}^{n-r}}\left( \begin{matrix}
   n+r  \\
   r  \\
\end{matrix} \right)}={{4}^{n}}$$
A: In seeking to evaluate
$$S_n = \sum_{r=0}^n 2^{n-r} {n+r\choose r}$$
we find that it is
$$[z^n] \frac{1}{1-2z} \frac{1}{(1-z)^{n+1}}
= \mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
\frac{1}{1-2z} \frac{1}{(1-z)^{n+1}}.$$
We will use the fact that residues sum to zero, which requires the
residue at $z=1/2$ and the residue at $z=1$ as well as the residue at
infinity. The latter is zero by inspection, however  . We get for the
residue at  $z=1/2$
$$-\frac{1}{2} \mathrm{Res}_{z=1/2}
\frac{1}{z^{n+1}} \frac{1}{z-1/2} \frac{1}{(1-z)^{n+1}}$$
We obtain
$$- \frac{1}{2} 2^{n+1} 2^{n+1} = - 2 \times 4^n.$$
We also have for the residue at $z=1$
$$\mathrm{Res}_{z=1} \frac{1}{z^{n+1}}
\frac{1}{1-2z} \frac{1}{(1-z)^{n+1}}
\\ = \mathrm{Res}_{z=1} \frac{1}{(1+(z-1))^{n+1}}
\frac{1}{-1-2(z-1)} \frac{1}{(1-z)^{n+1}}
\\ = (-1)^n
\mathrm{Res}_{z=1} \frac{1}{(1+(z-1))^{n+1}}
\frac{1}{1+2(z-1)} \frac{1}{(z-1)^{n+1}}.$$
This is
$$(-1)^n \sum_{r=0}^n (-1)^r {n+r\choose r} (-1)^{n-r} 2^{n-r}
= \sum_{r=0}^n 2^{n-r} {n+r\choose r} = S_n.$$
We have shown that $S_n - 2 \times 4^n + S_n = 0$ or
$$\bbox[5px,border:2px solid #00A000]{
S_n = 4^n.}$$
For the residue at infinity we get
$$-\mathrm{Res}_{z=0} \frac{1}{z^2} z^{n+1} \frac{1}{1-2/z}
\frac{1}{(1-1/z)^{n+1}}
= - \mathrm{Res}_{z=0}
z^n \frac{1}{z-2} \frac{z^{n+1}}{(z-1)^{n+1}}
\\ = - \mathrm{Res}_{z=0} z^{2n+1} \frac{1}{z-2}
\frac{1}{(z-1)^{n+1}} = 0.$$
A: OP's second method can be made to work and it gives the simplest as in the following solution.
$$S=\text{Coefficient of $x^n$ in}~~ (1+x)^n\left(\frac{(1+x)^{n+1}-2^{n+1}}{(x-1)}\right).$$
$$S=-\text{Coefficient of $x^n$}~ \text{in} \left((1+x)^{2n+1}(1-x)^{-1}-2^{n+1}(1-x)^{-1}\right)$$
$$S=-\text{Coefficient of $x^n$}~ \text{in} \left((1+x)^{2n+1}\sum_{k=0}^{\infty} x^k-2^{n+1}\sum_{k=0}^{\infty}x^k\right)$$
$$S=- \left(\sum_{k=0}^{n} {2n+1\choose k}-2^{n+1}\sum_{k=0}^{\infty}{n \choose k}\right)=-2^{2n}+2^{2n+1}=2^{2n}$$
A: A combinatorial proof.
Let $U=\{A\subseteq \{1,2,\dots,2n+1\}, |A|>n\}.$
We have that $|U|=2^{2n+1}/2=2^{2n}.$
Given an $A\in U,$ define $m(A)$ as the largest number such that $|A\cap\{1,2,\dots,n+r\}|=n.$ $m(A)$ can be anywhere from $0$ to $n,$ and we always have $m(A)+1\in A.$
Let $U_r=\{A\in U\mid m(A)=r\}.$ What is the size of $U_r?$ We can choose any $n$ elements from $1,2,\dots,n+r$, add the element $n+r+1,$ and then any subset of elements from the remaining $n-r$ elements. So $$|U_r|=\binom{n+r}{n}2^{n-r}.$$
and:
$$4^{n}=2^{2n}=|U|=\sum_{r=0}^{n}|U_r|=\sum_{r=0}^{n}2^{n-r}\binom{n+r}n$$
