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

Question

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.

Answer 1

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)?

Answer 2

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

Answer 3

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.

Answer 4

$\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}