Prove the identity $ \sum_{i=0}^n {n \choose i} i = n2^{n-1} $ with the identity $\sum_{k=0}^n \binom{n}{k}=2^n.$

Question

Prove the identity $ \sum_{i=0}^n {n \choose i} i = n2^{n-1} $ with the identity $\sum_{k=0}^n \binom{n}{k}=2^n.$

I have already used calculus (differentiating both sides of the original identity) as one method, but I need help trying to do another.

Answer 1

You can do this by simply manipulating the combinatorial term.

$${n \choose i} i = \frac{i\cdot n!}{(n-i)!\cdot i!} = \frac{n!}{(n-i)!\cdot (i-1)!} = n\frac{(n-1)!}{((n-1)-(i-1))!\cdot (i-1)!}$$ (Notice that $((n-1)-(i-1)) = (n-i)$).

Then $$\sum_{i=0}^n {n\choose i}i = n\sum_{i=0}^n {n-1 \choose i-1} = n\sum_{i=0}^{n-1} {n-1\choose i} = n2^{n-1}$$

Answer 2

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \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{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\ol}[1]{\overline{#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{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \color{#f00}{\sum_{i = 0}^{n}{n \choose i}i} & = \half\bracks{\sum_{i = 0}^{n}{n \choose i}i + \sum_{i = 0}^{n}{n \choose n - i}\pars{n - i}}\qquad\pars{~Reflection~} \\[5mm] & = \half\,n\sum_{i = 0}^{n}{n \choose i}\qquad\qquad\qquad\pars{~\mbox{because}\ {n \choose i} = {n \choose n - i}~} \\[5mm] & = \half\,n\pars{2^{n}} = \color{#f00}{n\,2^{n - 1}} \end{align}

Note that $\ds{\sum_{i = 0}^{n}a_{i} = \sum_{i = -n}^{0}a_{i + n} = \sum_{i = n}^{0}a_{-i + n} = \sum_{i = 0}^{n}a_{n - i}\implies \sum_{i = 0}^{n}a_{i} = \half\sum_{i = 0}^{n}\pars{a_{i} + a_{n - i}}}$.