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*}