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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.