Vrftsjtryk

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?

$$ 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$

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 $Hneq T$ so that $Pleft(H<Tright)+Pleft(T<Hright)=1$.

By symmetry $Pleft(H<Tright)=Pleft(T<Hright)$ so we conclude
that $Pleft(H<Tright)=frac{1}{2}$.

Also we have $Pleft(H<Tright)=sum_{i=0}^{n}Pleft(H=iright)=sum_{i=0}^{n}binom{n+i}{i}2^{-n-i-1}=frac12sum_{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$$

$newcommand{bbx}[1]{,bbox[15px,border:1px groove navy]{displaystyle{#1}},}
newcommand{braces}[1]{leftlbrace,{#1},rightrbrace}
newcommand{bracks}[1]{leftlbrack,{#1},rightrbrack}
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]{leftvert,{#1},rightvert}$
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}
,rightvert_{ x = 1/2}}label{1}tag{1}
end{equation}