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 $

Question

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.

Answer 1

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