For $k$ a non-negative integer, evaluate \begin{align*} \sum_{j=0}^k 2^{k-j} \binom{k +j}{j}. \end{align*}

Apparently, I only know how to do induction anymore now but this problem is straightforward using it. We suppose the inductive hypothesis, and assume that for a fixed $k$ that \begin{align*} \sum_{j=0}^k 2^{k-j} \binom{k +j}{j} = 2^{2k}. \end{align*} We will proceed to show \begin{align*} \sum_{j=0}^{k + 1} 2^{k + 1-j} \binom{k + 1 +j}{j} = 2^{2k + 2}. \end{align*}

By a simple binomial identity, we have \begin{align*} \sum_{j=0}^{k + 1} 2^{k + 1-j} \binom{k + 1 +j}{j} &= \sum_{j=0}^{k + 1} 2^{k + 1-j} \binom{k+j}{j} + \sum_{j=0}^{k + 1} 2^{k + 1-j} \binom{k +j}{j – 1}. \end{align*} Let $A$, $B$ be the first and second term respectively on the right hand side, then \begin{align*} A &= 2\sum_{j=0}^{k} 2^{k-j} \binom{k+j}{j} + \binom{2k + 1}{k+1} &= 2^{2k + 1} + \binom{2k + 1}{k+1}. \end{align*} For the other term, \begin{align*} B &= \sum_{j=1}^{k + 1} 2^{k + 1-j} \binom{k +j}{j – 1} &= \sum_{j=0}^{k} 2^{k-j} \binom{k +1 +j}{j} &= \frac{1}{2} \sum_{j=0}^{k + 1} 2^{k + 1-j} \binom{k +1 +j}{j} – \frac{1}{2} \binom{2k + 2}{k + 1}. \end{align*} Thus, we rearranging, we have our result \begin{align*} \frac{1}{2}\sum_{j=0}^{k + 1} 2^{k + 1-j} \binom{k + 1 +j}{j} &= 2^{2k+1} + \binom{2k + 1}{k+1} – \frac{1}{2} \binom{2k + 2}{k + 1} &= 2^{2k+1}. \end{align*}