Hidden random walk in shallow sums? Prove that $\sum_{k=0}^n k \cdot \binom{2n-k}n 2^k = (2n+1) \cdot \binom{2n}n - 4^n $ Motivation: I was perusing through Laurent's solution to a recent online puzzle here.
Basically he managed to prove that, from the expected value of the probability distribution (in that question), we can obtain $\displaystyle \sum_{k=0}^n \binom{2n-k}n 2^k = 4^n $. 
Now suppose that I want to find the variance of the same distribution, then I'm left to prove that $\displaystyle \sum_{k=0}^n k \binom{2n-k}n 2^k = (2n+1) \binom{2n}n - 4^n $. 
Plugging in the values of $n=1,2,3,4,5,\ldots$ outputs this Random walk sequence.
Which got me curious: Is there a combinatorial proof for this sum? (Actually, I'm interested in any proof)
Further notes: If my claim is correct, then $$\text{Var}[T] = 4n + 2 - \frac{4^n}{\binom{2n}n} - \frac{16^n}{\binom{2n}n ^2} \to n(4-\pi) $$
which agrees with Laurent's claim that the probability distribution of $T$ asymptotically follows a Rayleigh distribution.
I also want to point out that this question is related. That is (upon division by $4^n$),
$$ \frac1{4^n} \sum_{k=0}^n k \binom {2n-k}n 2^k = \frac{2n+1}{4^n} \binom{2n}n - 1 $$ 
is the expected number of returns in a symmetric random walk of $2n$ moves.

In evaluating
$$\sum_{k=0}^n {2n-k\choose n} k 2^k$$
we write
$$\sum_{k=0}^n {2n-k\choose n-k} k 2^k
= \sum_{k=0}^n k 2^k [z^{n-k}] (1+z)^{2n-k}
\\ = [z^n] (1+z)^{2n} \sum_{k=0}^n k 2^k z^k (1+z)^{-k}.$$
Now  we may  extend the  sum in  $k$ beyond  $n$ because  there is  no
contribution to the coefficient extractor $[z^n]$ in that case:
$$[z^n] (1+z)^{2n} \sum_{k\ge 0} k 2^k z^k (1+z)^{-k}.$$
We also have
$$\sum_{k\ge 0} k w^k = \frac{w}{(1-w)^2}$$
which yields for the sum
$$[z^n] (1+z)^{2n} \frac{2z/(1+z)}{(1-2z/(1+z))^2}
= 2 [z^n] (1+z)^{2n+1} \frac{z}{(1-z)^2}$$
This is
$$2 \sum_{q=0}^n (n-q) {2n+1\choose q}
= 2n \sum_{q=0}^n  {2n+1\choose q}
- 2 \sum_{q=0}^n q {2n+1\choose q}
\\ = 2n \frac{1}{2} 2^{2n+1}
- 2 \sum_{q=1}^n q {2n+1\choose q}
\\ = n 2^{2n+1}
- 2 (2n+1) \sum_{q=1}^n {2n\choose q-1}
\\ = n 2^{2n+1}
- 2 (2n+1) \sum_{q=0}^{n-1} {2n\choose q}
\\ = n 2^{2n+1}
- 2 (2n+1) \frac{1}{2} \left(2^{2n}-{2n\choose n}\right)
\\ = (2n+1) {2n\choose n} + 2 n 2^{2n} - (2n+1) 2^{2n}
= (2n+1) {2n\choose n} - 4^n.$$
