Sum involving binomial coefficients - generalisation of hockey stick identity? I am trying to evaluate a sum involving binomial coefficients, and by some manipulations, I have reduced it to $$\sum_{i=0}^{n} \binom{n+i}{i} 2^{n-i}$$
where $n$ is a constant ($n=1009$ in my particular case). (This looks like the LHS of the Hockey Stick Identity, except for the presence of the $2^{n-i}$ term. I would also be interested in further generalisation, replacing the $2$ by an arbitrary constant).
To evaluate this, I attempted writing $$2^{n-i} = \sum_{k=0}^{n-i} \binom{n-i}{k}$$ which gave a more symmetric expression, but otherwise didn't seem to help much.
So, given that the answer (according to Mathematica) is $4^n$, how can this be proved?
 A: $$ \text{Let } f(n)= \sum_{i=0}^{n} \binom{n+i}{i} 2^{n-i}.$$
$$f(n+1)=\sum_{i=0}^{n+1} \binom{n+i+1}{i} 2^{n+1-i}=\sum_{i=0}^{n+1} \binom{n+i}{i} 2^{n+1-i}+ \sum_{i=0}^{n+1} \binom{n+i}{i-1}2^{n+1-i}$$$$=\binom {2n+1}{n} + 2{\sum_{i=0}^{n} \binom{n+i}{i} 2^{n-i}}+ \sum_{i=0}^{n} \binom{n+i+1}{i}2^{n-i}$$$$=2f(n)+\frac{1}{2}\binom{2n+2}{n+1}+\frac{1}{2}\sum_{i=0}^{n} \binom{n+i+1}{i}2^{n+1-i}=2f(n)+\frac{1}{2}f(n+1)$$
$$\therefore f(n+1)=4f(n) \implies f(n)=4^{n-1}f(1)=4^n\ .$$
$\blacksquare$
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{equation}
\bbx{\mbox{Nothe that}\
\sum_{k = 0}^{n}{n + k \choose k}2^{n - k} =
\left. 2^{n}\sum_{k = 0}^{n}{n + k \choose k}x^{k}
\,\right\vert_{\ x\ =\ 1/2}}\label{1}\tag{1}
\end{equation}

Let $\ds{\mrm{f}\pars{x} \equiv \sum_{k = 0}^{n}{n + k \choose k}x^{k}}$ such that

$\ds{\bbox[#ffd,10px,border:1px groove navy]
{\sum_{k = 0}^{n}{n + k \choose k}2^{n - k} =
2^{n}\,\mrm{f}\pars{1 \over 2}}\qquad}$ and
\begin{align}
\mrm{f}'\pars{x} & =
\sum_{k = 1}^{n}{\pars{n + k}! \over \pars{k - 1}!\, n!}x^{k - 1} =
\sum_{k = 0}^{n - 1}{\pars{n + 1 + k}! \over k!\, n!}x^{k} \\[5mm] & =
\sum_{k = 0}^{n - 1}\pars{n + 1 + k}{n + k \choose k}x^{k}
\\[5mm] & =
\sum_{k = 0}^{n}\pars{n + 1 + k}{n + k \choose k}x^{k} -
\pars{2n + 1}{2n \choose n}x^{n}
\\[5mm] & =
\pars{n + 1}\,\mrm{f}\pars{x} + x\,\mrm{f}'\pars{x} -
\pars{2n + 1}{2n \choose n}x^{n}
\end{align}
which leads to
\begin{align}
&\mrm{f}'\pars{x} - {n + 1 \over 1 - x}\,\mrm{f}\pars{x} =
-\pars{2n + 1}{2n \choose n}{x^{n} \over 1 - x}\,,\qquad
\left\{\begin{array}{lcl}
\ds{\mrm{f}\pars{0}} & \ds{=} & \ds{1}
\\[2mm]
\ds{\mrm{f}\pars{1 \over 2}} & \ds{=} & \ds{\LARGE ?}
\end{array}\right.
\\[5mm] &\
\totald{\bracks{\pars{1 - x}^{n + 1}\,\mrm{f}\pars{x}}}{x} =
-\pars{2n + 1}{2n \choose n}\pars{x - x^{2}}^{n}
\\[1cm] &\
{1 \over 2^{n + 1}}\,\mrm{f}\pars{1 \over 2} - 1
\\ = &\
-\pars{2n + 1}{2n \choose n}\,
\underbrace{\int_{0}^{1/2}\pars{x - x^{2}}^{n}\,\dd x}
_{\ds{1/2 \over \pars{2n + 1}{2n \choose n}}}
\implies\bbx{\mrm{f}\pars{1 \over 2} = 2^{n}}
\end{align}

Then,
$$
\sum_{k = 0}^{n}{n + k \choose k}2^{n - k} =
2^{n}\,\mrm{f}\pars{1 \over 2} = \bbx{\large 4^{n}}
$$
A: Throw a fair coin repeatedly until the number of heads or the number of
tails has exceeded $n$.
Let $H$ denote the number of heads and let $T$ denote the number
of tails that have been thrown then.
In that situation $H\neq T$ so that $P\left(H<T\right)+P\left(T<H\right)=1$.
By symmetry $P\left(H<T\right)=P\left(T<H\right)$ so we conclude
that $P\left(H<T\right)=\frac{1}{2}$.
Also we have $P\left(H<T\right)=\sum_{i=0}^{n}P\left(H=i\right)=\sum_{i=0}^{n}\binom{n+i}{i}2^{-n-i-1}=\frac12\sum_{i=0}^{n}\binom{n+i}{i}2^{-n-i}$.
Proved is now that: 
$$\sum_{i=0}^{n}\binom{n+i}{i}2^{-n-i}=1$$ or equivalently: $$\sum_{i=0}^{n}\binom{n+i}{i}2^{n-i}=2^{2n}=4^n$$
