<s>[INST] Computing $2 \binom{n}{0} + 2^2 \frac{\binom{n}{1}}{2} + 2^3 \frac{\binom{n}{2}}{3} + \cdots + 2^{n+1} \frac{\binom{n}{n}}{n+1}$ How can I compute the sum $2 \binom{n}{0} + 2^2 \frac{\binom{n}{1}}{2} + 
2^3 \frac{\binom{n}{2}}{3} + \cdots + 2^{n+1} \frac{\binom{n}{n}}{n+1}$? I think I should expand $(1+ \sqrt{2})^n$ or something like this and then find some kind of linear recurrence, but I'm not sure.
 [/INST] The hint given by @ThomasAndrews indicates a purely algebraic approach.

We obtain
\begin{align*}
\color{blue}{\sum_{j=0}^n\frac{2^{j+1}}{j+1}\binom{n}{j}}
&=\frac{1}{n+1}\sum_{j=0}^n2^{j+1}\binom{n+1}{j+1}\tag{1}\\
&=\frac{1}{n+1}\sum_{j=1}^{n+1}2^j\binom{n+1}{j}\tag{2}\\
&\,\,\color{blue}{=\frac{1}{n+1}\left(3^{n+1}-1\right)}\tag{3}
\end{align*}

Comment:

*

*In (1) we use the binomial identity $\frac{n+1}{j+1}\binom{n}{j}=\binom{n+1}{j+1}$.


*In (2) we shift the index by one and start with $j=1$.


*In (3) we apply the binomial theorem.
</s>