Putnam 2020, Problem A-2

Let \( k \) be a nonnegative integer. Evaluate
\[
\sum_{j=0}^{k} 2^{k-j} \binom{k+j}{j}.
\]

Solution:
The answer is $4^k$.

**First solution.** Let $S_k$ denote the given sum. Then, with the convention that $\binom{n}{-1} = 0$ for any $n \geq 0$, we have for $k \geq 1$,
$$S_k = \sum_{j=0}^k 2^{k-j} \left[ \binom{k-1+j}{j} + \binom{k-1+j}{j-1} \right]$$
$$= 2 \sum_{j=0}^{k-1} 2^{k-1-j} \binom{k-1+j}{j} + \binom{2k-1}{k} + \sum_{j=1}^k 2^{k-j} \binom{k-1+j}{j-1}$$
$$= 2S_{k-1} + \binom{2k-1}{k} + \sum_{j=0}^{k-1} 2^{k-1-j} \binom{k+j}{j}$$
$$= 2S_{k-1} + \frac{S_k}{2}$$

and so $S_k = 4S_{k-1}$. Since $S_0 = 1$, it follows that $S_k = 4^k$ for all $k$.

**Second solution.** Consider a sequence of fair coin flips $a_1, a_2, \ldots$ and define the random variable $X$ to be the index of the $(k+1)$-st occurrence of heads. Then
$$P[X = n] = \binom{n-1}{k} 2^{-n};$$

writing $n = k + j + 1$, we may thus rewrite the given sum as
$$2^{2k+1} P[X \leq 2k+1].$$

It now suffices to observe that $P[X \leq 2k+1] = \frac{1}{2}$: we have $X \leq 2k+1$ if and only if there are at least $k+1$ heads among the first $2k+1$ flips, and there are exactly as many outcomes with at most $k$ heads.

**Third solution.** (by Pankaj Sinha) The sum in question is the coefficient of $x^k$ in the formal power series
$$\sum_{j=0}^k 2^{k-j} (1+x)^{k+j} = 2^k (1+x)^k \sum_{j=0}^k 2^{-j} (1+x)^j$$
$$= 2^k (1+x)^k \frac{1 - (1+x)^{k+1}/2^{k+1}}{1 - (1+x)/2}$$
$$= \frac{2^{k+1} (1+x)^k - (1+x)^{2k+1}}{1-x}$$
$$= (2^{k+1} (1+x)^k - (1+x)^{2k+1})(1 + x + \cdots).$$

This evidently equals
$$2^{k+1} \sum_{j=0}^k \binom{k}{j} - \sum_{j=0}^k \binom{2k+1}{j} = 2^{k+1} (2^k) - \frac{1}{2} 2^{2k+1}$$
$$= 2^{2k+1} - 2^{2k} = 2^{2k} = 4^k.$$

**Remark.** This sum belongs to a general class that can be evaluated mechanically using the WZ method. See for example the book $A = B$ by Petvoksek-Wilf-Zeilberger.