partial sum involving factorials

Solution 1:

$$ \begin{align} \sum_{k=0}^{n}\frac{(2n-k)!}{(n-k)!}2^k\tag{1} &=n!\sum_{k=0}^n\binom{2n-k}{n-k}\sum_{j=0}^k\binom{k}{j}\\\tag{2} &=n!\sum_{k=0}^n\sum_{j=0}^{n-k}\binom{n+k}{k}\binom{n-k}{j}\\\tag{3} &=n!\sum_{j=0}^n\sum_{k=0}^{n-j}\binom{n+k}{n}\binom{n-k}{j}\\\tag{4} &=n!\sum_{j=0}^n\binom{2n+1}{n+j+1}\\\tag{5} &=n!\;2^{2n} \end{align} $$

1. rewrite $2^k$

2. $k\mapsto n-k$

3. change order of summation and $\binom{n}{k}=\binom{n}{n-k}$

4. $\sum_k\binom{n-k}{i}\binom{m+k}{j}=\binom{n+m+1}{i+j+1}$

5. Split $\sum_j\binom{2n+1}{j}=2^{2n+1}$ in half

Solution 2:

Here's a combinatorial proof for J.M.'s reformulation (after dividing out $n!$):

$$\sum\limits_{k=0}^n \binom{n+k}{k} 2^{n-k}= 4^n.$$

Suppose you flip coins until you obtain either $n+1$ heads or $n+1$ tails. After either heads or tails "wins" you keep flipping until you have a total of $2n+1$ coin flips. The two sides count the number of ways for heads to win.

For the left side: Condition on the number of tails $k$ obtained before head $n+1$. There are $\binom{n+k}{k}$ ways to choose the positions at which these $k$ tails occurred from the $n+k$ total options, and then $2^{n-k}$ possibilities for the remaining flips after head $n+1$. Summing up yields the left side.

For the right side: Heads wins on half of the total number of sequences; i.e., $\frac{1}{2}(2^{2n+1}) = 4^n$.