<s>[INST] 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
 [/INST] 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.$$
</s>