How to prove that $\sum_{i=0}^n 2^i\binom{2n-i}{n} = 4^n$.

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


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