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.
 A: Your expression is $\displaystyle\sum_{k=0}^n \frac{x^{k+1}}{k+1} \binom{n}{k}$ evaluated at $x=2$.
Hint. Can you think of where else $\displaystyle\frac{x^{k+1}}{k+1}$ shows up (specifically, in calculus)?
A: 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}$
A: 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.
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\sum_{k = 0}^{n}{2^{k + 1} \over k + 1}{n \choose k} & =
2\sum_{k = 0}^{n}2^{k}{n \choose k}\int_{0}^{1}t^{k}\,\dd t =
2\int_{0}^{1}\sum_{k = 0}^{n}{n \choose k}\pars{2t}^{k}\,\dd t
\\[5mm] & =
2\int_{0}^{1}\pars{1 + 2t}^{n}\,\dd t =
\left. {\pars{1 + 2t}^{n + 1} \over n + 1}\,\right\vert_{\ 0}^{\ 1} =
\bbx{3^{n + 1} - 1 \over n + 1}\\ &
\end{align}
