How to prove that $\sum_{i=0}^n 2^i\binom{2n-i}{n} = 4^n$. So I've been struggling with this sum for some time and I just can't figure it out. I tried proving by induction that if the sum above is a $S_n$ then $S_{n+1} = 4S_n$, but I didn't really succeed so here I am. Thanks in advance.
 A: I can give a mildly ugly proof by induction. Let
$$S_n=\sum_{k=0}^n2^k\binom{2n-k}n=\sum_{k=0}^n2^k\binom{2n-k}{n-k}=\sum_{k=0}^n2^{n-k}\binom{n+k}n\;,$$
and assume that $S_n=4^n=2^{2n}$. Then
$$\begin{align*}
S_{n+1}&=\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+1+k}{n+1}\\
&=\sum_{k=0}^{n+1}2^{n+1-k}\left(\binom{n+k}n+\binom{n+k}{n+1}\right)\\
&=\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}n+\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\
&=\binom{2n+1}n+2\sum_{k=0}^n2^{n-k}\binom{n+k}n+\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\
&=\binom{2n+1}n+2^{2n+1}+\sum_{k=1}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\
&=2^{2n+1}+\binom{2n+1}n+\binom{2n+1}{n+1}+\sum_{k=1}^n2^{n+1-k}\binom{n+k}{n+1}\\
&=2^{2n+1}+\binom{2n+2}{n+1}+\sum_{k=0}^{n-1}2^{n-k}\binom{n+1+k}{n+1}\\
&=2^{2n+1}+\binom{2n+2}{n+1}+\frac12\left(S_{n+1}-\binom{2n+2}{n+1}-2\binom{2n+1}{n+1}\right)\\
&=2^{2n+1}+\binom{2n+2}{n+1}+\frac12\left(S_{n+1}-2\binom{2n+2}{n+1}\right)\\
&=2^{2n+1}+\frac12S_{n+1}\;,
\end{align*}$$
so $\frac12S_{n+1}=2^{2n+1}$, and $S_{n+1}=2^{2n+2}=4^{n+1}$.
A: Here is a way to rephrase Zac's proof as a combinatorial argument.

Question: How many binary sequences of length $2n+1$ have more ones than zeroes?

Answer $1$: Half of the sequences have more ones than zeroes, since a sequence has more ones than zeroes if and only if its complement does not. There are $2^{2n+1}$ sequences total; half of this is $2^{2n}$.
Answer $2$: Such a sequence will have at least $n+1$ ones. Let us count how many such sequences there are such that the $(n+1)^{st}$ instance of one (reading from left to right) occurs at spot number $2n+1-k$. Among the first $2n-k$ symbols, there will be exactly $n$ ones, whose locations can be chosen in $\binom{2n-k}n$ ways. Symbol number $2n-k+1$ must be a one, and then the remaining $k$ symbols can be chosen arbitrarily in $2^k$ ways. Summing over $k$, the number of possible sequences is $\sum_{k=0}^n \binom{2n-k}{n}2^k$. 
Note the bounds on $k$; $k=0$ corresponds to the situation where the $(n+1)^{st}$ one occurs at spot $2n+1$, and $k=n$ corresponds to the case where the $(n+1)^{st}$ one occurs at spot $n+1$. These are indeed the furthest possible locations.
A: A probabilistic argument is possible.
Hint: Consider two players, $A$ and $B$, who play a sequence of rounds in a game against each other in which both players are equally likely to win each round. Suppose that the first player to win $n+1$ rounds wins the game. Consider the probability that player $A$ wins the game.
A: Just to present another way:
$$
\eqalign{
  & \sum\limits_{0\, \le \,k\, \le \,\,n} {\left( \matrix{
  2n - k \cr 
  n \cr}  \right)2^{\,k} }  = \sum\limits_{0\, \le \,k\,\left( { \le \,\,n} \right)} {\left( \matrix{
  2n - k \cr 
  n - k \cr}  \right)2^{\,k} }  =   \cr 
  &  = \sum\limits_{0\, \le \,k\,\left( { \le \,\,n} \right)} {\left( \matrix{
  2n - k \cr 
  n - k \cr}  \right)\left( {1 + 1} \right)^{\,k} }  = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,\,n} \right)} {\sum\limits_{0\, \le \,k\,\left( { \le \,\,n} \right)} {\left( \matrix{
  2n - k \cr 
  n - k \cr}  \right)\left( \matrix{
  k \cr 
  j \cr}  \right)} }  =   \cr 
  &  = \sum\limits_{0\, \le \,j\,\left( { \le \,\,n} \right)} {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,\,n} \right)} {\left( \matrix{
  2n - k \cr 
  n - k \cr}  \right)\left( \matrix{
  k \cr 
  k - j \cr}  \right)} }  =   \cr 
  &  = \sum\limits_{0\, \le \,j\,\left( { \le \,\,n} \right)} {\left( \matrix{
  2n + 1 \cr 
  n - j \cr}  \right)}  = \sum\limits_{0\, \le \,\,l\, \le \,\,n} {\left( \matrix{
  2n + 1 \cr 
  l \cr}  \right)}  = {1 \over 2}\sum\limits_{0\, \le \,\,l\, \le \,\,2n + 1} {\left( \matrix{
  2n + 1 \cr 
  l \cr}  \right)}  =   \cr 
  &  = 2^{\,2n}  \cr} 
$$
A: Here is a variant using the coefficient of operator $[z^k]$  to denote the coefficient of $z^k$ in a series. We can write this way
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}
\end{align*}

We obtain
  \begin{align*}
\sum_{k=0}^{n}2^k\binom{2n-k}{n}&=\sum_{k=0}^{n}2^k\binom{2n-k}{n-k}\tag{1}\\
&=\sum_{k=0}^\infty2^k[z^{n-k}](1+z)^{2n-k}\tag{2}\\
&=[z^n](1+z)^{2n}\sum_{k=0}^{\infty}\left(\frac{2z}{1+z}\right)^k\tag{3}\\
&=[z^n]\frac{(1+z)^{2n+1}}{1-z}\tag{4}\\
&=[z^n]\sum_{k=0}^nz^k(1+z)^{2n+1}\tag{5}\\
&=\sum_{k=0}^n[z^k](1+z)^{2n+1}\tag{6}\\
&=\sum_{k=0}^{n}\binom{2n+1}{k}\tag{7}\\
&=\frac{1}{2}2^{2n+1}\tag{8}\\
&=4^n
\end{align*}

Comment:


*

*In (1) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$

*In (2) we apply the coefficient of operator. We also set the upper limit of the series to $\infty$ without changing anything, since we add only zeros.

*In (3) we rearrange the summand by using the linearity of the coefficient of operator and the rule $[z^{p-q}]A(z)=[z^p]z^{q}A(z)$

*In (4) we apply the geometric series formula and do some simplifications

*In (5) we expand the geometric series $\frac{1}{1-z}$. Since we are looking for $[z^n]$ we can restrict the upper limit of the sum with $n$ due to the factor $z^k$ inside the sum.

*In (6) we use $[z^n]z^k=[z^{n-k}]$ again and exchange the index $k$ with $n-k$

*In (7) we select the coefficient corresponding to $[z^k]$

*In (8) we use the symmetry $\binom{p}{q}=\binom{p}{p-q}$ which implies that the sum of the left half of a row in the Pascal triangle is equal the sum of the right half of this row. More formally
\begin{align*}
2^{2n+1}&=\sum_{k=0}^{2n+1}\binom{2n+1}{k}\\
&=\sum_{k=0}^{n}\binom{2n+1}{k}+\sum_{k=n+1}^{2n+1}\binom{2n+1}{k}\\
&=\sum_{k=0}^{n}\binom{2n+1}{k}+\sum_{k=0}^{n}\binom{2n+1}{n+1+k}\\
&=2\sum_{k=0}^n\binom{2n+1}{k}
\end{align*}
A: Derived this solution but just realised that it is a bit similar to the one posted by G Cab above, but here it is anyway. 
$$\begin{align}
\sum_{i=0}^n \color{blue}{2^i}\binom{2n-i}n
&=\sum_{i=0}^n\color{blue}{\sum_{j=0}^i\binom ij}\binom {2n-i}n\\
&=\sum_{j=0}^n\sum_{i=j}^n\binom i{i-j}\binom{2n-i}{n-i}
&&\text{swapping indices and using symmetry}\\
&=\sum_{j=0}^n\sum_{i=j}^n(-1)^{i-j}\binom{-j-1}{i-j}(-1)^{n-i}\binom{-n-1}{n-i}
&&\text{upper negation}\\
&=\sum_{j=0}^n(-1)^{n-j}\sum_{i=j}^n\binom {-j-1}{i-j}\binom{-n-1}{n-i}\\
&=\sum_{j=0}^n(-1)^{n-j}\binom{-n-j-2}{n-j}
&&\text{Vandermonde Identity}\\
&=\sum_{j=0}^n(-1)^{n-j}(-1)^{n-j}\binom{2n+1}{n-j}
&&\text{upper negation}\\
&=\sum_{j=0}^n\binom{2n+1}{n+1+j}
&&\text{symmetry}\\
&=\sum_{k=n+1}^{2n+1}\binom{2n+1}k
&&\text{putting $k=n+1+j$}\\
&=\frac 12 \sum_{k=0}^{2n+1}\binom{2n+1}k\\
&=\frac12\cdot 2^{2n+1}\\
&=4^n\qquad\blacksquare
\end{align}$$
A: We use the equivalent form
$$\sum_{k=n}^{2n}2^{-k}\binom{k}{n}=1$$
of @MotylaNogaTomkaMazura. This is obtained by noting that $4^n=2^{2n}$ and setting $k=2n-i$.
In order to make more money, the World Series rules have been modified, so that the first team to win $n+1$ games wins the Series. (The current rules have $n=3$.)
Let $p_k$ be the probability the World Series ends in $k+1$ games, if each team has probability $1/2$ of winning any game, and game results are independent. 
The series ends in $k+1$ games precisely if one of the $2$ teams wins $n$ of the first $k$ games, and then wins the next game. Thus 
$$p_k=2\binom{k}{n}(1/2)^{k}(1/2)=2^{-k}\binom{k}{n}.$$ 
Now add up, $k=n$ to $2n$. The probabilities must sum to $1$.
A: Combinatorial proof: we'll write $[n]$ for $\{1,2,\dots, n\}$, and $[n]^{(r)}$ for the collection of all $r$-sized subsets of $[n]$. 
We use the standard $[i, j]$ for $\{i, i+1, \dots, j \}$.
We exhibit a bijection between $$\{ (i, s \subseteq [i], t \subseteq [i+1, 2n]^{(n-i)}) : i = 0, 1, \dots, n \}$$
and the subsets of $[2n]$.
Let $$\begin{equation}
    \phi(i, s, t)=
    \begin{cases}
      ([i+1, 2n] \setminus t) \sqcup s, & \text{if}\ i \in s \\
      t \sqcup s, & \text{if}\ i \not \in s
    \end{cases}
  \end{equation}$$
where $\sqcup$ is a union where we emphasise that the arguments are disjoint.
In the first case, there are between $n$ and $n+i$ elements of $\phi(i, s, t)$; in the second, there are between $n-i$ and $n$ elements.
We claim that $\phi$ is a bijection.

Lemma: $\phi$ is injective.

Proof: if $\phi(i,s,t) = \phi(j,a,b)$ then it is enough to show that $i=j$, because then $$s = [i] \cap \phi(i,s,t) = [j] \cap \phi(j,a,b) = a$$ and:


*

*If $i \in s$, then $j \in a$ and so $$[i, 2n] \setminus t = [i, 2n] \cap \phi(i,s,t) = [j, 2n] \cap \phi(j,a,b) = [j, 2n] \setminus b$$

*If $i \not \in s$, then $j \not \in b$ and so $$t = [i, 2n] \cap \phi(i, s, t) = [j, 2n] \cap \phi(j, a, b) = b$$


Suppose then, for contradiction, that $i \not = j$. By symmetry, wlog $i$ is the smaller. Then we get a very tedious case-bash which I'm afraid I'm not going to go through, but we arrive at a contradiction.

Lemma: $\phi$ is surjective.

The only way I've got of proving this is a really long and boring specification of the inverse of $\phi$. I'm sure there must be a better way, but I can't find it.
A: This uses the Snake Oil Method from Wilf's generatingfunctionology. 
Auxiliary facts
Let $B=B(x)=\frac{1}{\sqrt{1-4x}}$ and $C=C(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating functions for the central binomial coefficients and Catalan numbers, respectively. Then
$$
B=\frac{1}{1-2xC}
$$
and
$$
\sum_{n=0}^{\infty}\binom{2n+k}{n}x^n=BC^k.
$$
The last inequality can be proved combinatorially: consider all lattice paths from $(0,0)$ to $(2n,k)$ using steps $u=(1,1)$ and $d=(1,-1)$. Then any such path can be written uniquely as $P_0uD_1uD_2u\dots uD_k$, where $P_0$ is a grand Dyck path and $D_1,\dots,D_k$ are Dyck paths, all together (with $P_0$) of total semilength $n$.
Main result
$$
\begin{split}
\sum_{n=0}^{\infty}\sum_{k=0}^{n}{2^k\binom{2n-k}{n}x^n}
&=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}{2^k\binom{2n-k}{n}x^n}\\
&=\sum_{k=0}^{\infty}2^kx^k\left(\sum_{n=k}^{\infty}{\binom{2n-k}{n-k}x^{n-k}}\right)\\
&=\sum_{k=0}^{\infty}2^kx^k\left(\sum_{n=0}^{\infty}{\binom{2n+k}{n}x^n}\right)\\
&=\sum_{k=0}^{\infty}2^kx^kBC^k\\
&=B\sum_{k=0}^{\infty}(2xC)^k
=B\cdot\frac{1}{1-2xC}=B^2=\frac{1}{1-4x}=\sum_{n=0}^{\infty}{4^nx^n}.
\end{split}
$$
