1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I've noticed that you have 16 questions recently during your first 4 days on the site. I wanted to make sure that you are aware of the quotas 50 questions/30 days and 6 questions/24 hours, so that you can plan posting your questions accordingly. (If you try to post more questions, StackExchange software will not allow you to do so.) For more details see meta. $\endgroup$ – Martin Sleziak Sep 14 '16 at 13:52
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice answer! Much simpler than mine. $\endgroup$ – jiyanez Sep 14 '16 at 4:26
  • $\begingroup$ @jiyanez Thanks. 'Symmetries' are always useful. $\endgroup$ – Felix Marin Sep 14 '16 at 4:30
  • $\begingroup$ Could you please explain how n/i = n/n-i? $\endgroup$ – user193203821309 Sep 14 '16 at 12:03
  • $\begingroup$ @differentialequation $$ {n \choose i} = {n! \over i!\,\left(n - i\right)!} = {n! \over \left(n - i\right)!\,\left[n - \left(n - i\right)\right]!} = {n \choose n - i} $$ $\endgroup$ – Felix Marin Sep 14 '16 at 19:46

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .