partial sum involving factorials Here is an interesting series I ran across.  
It is a binomial-type identity.  
$\displaystyle \sum_{k=0}^{n}\frac{(2n-k)!\cdot 2^{k}}{(n-k)!}=4^{n}\cdot n!$
I tried all sorts of playing around, but could not get it to work out.
This works out the same as $\displaystyle 2^{n}\prod_{k=1}^{n}2k=2^{n}\cdot 2^{n}\cdot n!=4^{n}\cdot n!$
I tried equating these somehow, but I could not get it. I even wrote out the series.
There were cancellations, but it did not look like the product of the even numbers.
$\displaystyle \frac{(2n)!}{n!}+\frac{(2n-1)!\cdot 2}{(n-1)!}+\frac{(2n-2)!2^{2}}{(n-2)!}+\cdot\cdot\cdot +n!\cdot 2^{n}=4^{n}\cdot n!$.
How can the closed form be derived from this?.  I bet I am just being thick. I see the last term is nearly the result except for being multiplied by $2^{n}$.  I see if the factorials are written out, $2n(2n-1)(2n-2)(2n-3)\dots$ for example,  then 2's factor out of $2n, \;\ 2n-2$ (even terms) in the numerator. 
There is even a general form I ran through Maple. It actually gave a closed from for it as well, but I would have no idea how to derive it. 
$\displaystyle \sum_{k=0}^{n}\frac{(2n-k)!\cdot 2^{k}\cdot (k+m)!}{(n-k)!\cdot k!}$.
In the above case, m=0.  But, apparently there is a closed form for $m\in \mathbb{N}$ as well.
Maple gave the solution in terms of Gamma:  $\displaystyle \frac{\Gamma(1+m)4^{n}\Gamma(n+1+\frac{m}{2})}{\Gamma(1+\frac{m}{2})}$
Would anyone have an idea how to proceed with this?.  Perhaps writing it in terms of Gamma and using some identities?. Thanks very much. 
 A: $$
\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}
$$


*

*rewrite $2^k$

*$k\mapsto n-k$

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

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

*Split $\sum_j\binom{2n+1}{j}=2^{2n+1}$ in half
A: 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$.
A: Dividing out $2^n\cdot n!$ and changing variables, your equation follows from (5.20) on page 167 of Concrete Mathematics by Graham, Knuth, and Patashnik. If you don't have this reference, I can add more details later.   
$$\sum_{k\leq m}{m+k\choose k}2^{-k}=2^m\qquad\text{integer}\quad m\geq 0.\qquad\qquad (5.20)$$

Just for fun, here is a probabilistic proof of (5.20).
Suppose we toss a fair coin until we see either $m+1$ heads
or $m+1$ tails. Let $J$ be the number of trials prior to the final 
toss, and consider $\mathbb{P}(J=j)$ for $m\leq j\leq 2m$. 
We get $J=j$ by either $m$ heads in the first $j$ tosses followed
by a head, or $m$ tails in the first $j$ tosses followed by a tail.
By symmetry, we find
$$\mathbb{P}(J=j)=2{j\choose m}\left({1\over 2}\right)^j\left({1\over 2}\right)
={j\choose m}\left({1\over 2}\right)^j.$$
Since the total probability adds to one, we get 
$$\sum_{m\leq j\leq 2m} {j\choose m}\left({1\over 2}\right)^j=1.$$
Putting $k=j-m$ in this sum and multiplying by $2^m$ gives (5.20).  
A: This identity can be re-written as
$$\sum_{k=0}^n {2n-k \choose n-k} 2^k = 4^n.$$
Start from
$${2n-k \choose n-k} =
\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-k}}{z^{n-k+1}} \; dz.$$
This yields for the sum
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} 
\sum_{k=0}^n \frac{(1+z)^{2n-k}}{z^{n-k+1}} 2^k \; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} 
\frac{(1+z)^{2n}}{z^{n+1}}
\sum_{k=0}^n \frac{(2z)^{k}}{(1+z)^k} \; dz.$$
We can extend the sum to infinity because when $n-k+1 \le 0$ or $k \ge n+1$ the integrand of the defining integral of the binomial coefficient is an entire function and the integral is zero. This yields
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} 
\frac{(1+z)^{2n}}{z^{n+1}}
\sum_{k=0}^\infty \frac{(2z)^{k}}{(1+z)^k} \; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} 
\frac{(1+z)^{2n}}{z^{n+1}} \frac{1}{1-2z/(1+z)} \; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} 
\frac{(1+z)^{2n+1}}{z^{n+1}} \frac{1}{1-z} \; dz.$$
Thus the value of the integral is given by
$$[z^n] \frac{1}{1-z} (1+z)^{2n+1}
= \sum_{q=0}^n {2n+1\choose q} = \frac{1}{2} 2^{2n+1} = 4^n.$$
A trace as to when this method appeared on MSE and by whom starts at this
MSE link.
