<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 expression looks like it has something to do with binomial expansion of $\left(x+1\right)^n=\sum_{k=0}^{n}{\binom{n}{k}x^k}$ evaluated at $x=2$ but with each term being integrated. So we need to integrate both sides with respect to $x$ to get $\frac{\left(x+1\right)^{n+1}}{n+1}+c=\sum_{k=0}^{n}{\binom{n}{k}\frac{x^{k+1}}{k+1}}$
Putting $x=0$ we get $c=\frac{-1}{n+1}$.
Finally we need to evaulate the expression at $x=2$
Which will make the sum equal to $\frac{\left(3\right)^{n+1}}{n+1}-\frac{1}{n+1}$
</s>