Big-O and Big-Theta of $\sum_{i=0}^{n}{\binom{n}{i}i}$

Question

I'm trying to find upper and lower limit of:

$\sum_{i=0}^{n}{\binom{n}{i}i}$

At the moment the only idea I have is:

$\sum_{i=0}^{n}{\binom{n}{i}i} \ge \sum_{i=0}^{n}{\binom{n}{i}} = 2^n$

Any other suggestion to Big-$O$ & Big-$\Theta$?

There is a closed formula for $\sum_i i\binom ni$. – Angina Seng Nov 18 '17 at 18:27 — Angina Seng, Nov 18 '17 at 18:27
Thank you @LordSharktheUnknown, Any name/reference/link ? – ChaosPredictor Nov 18 '17 at 18:28 — ChaosPredictor, Nov 18 '17 at 18:28

score 2 · Answer 1 · answered Nov 18 '17 at 18:27

2

Note that $$\sum_{i=0}^{n}{\binom{n}{i}i}=n2^{n-1}$$ by considering $\frac{d}{dx}(1+x)^n$ evaluated at $x=1$.

answered Nov 18 '17 at 18:27

Sri-Amirthan Theivendran

31,116

Thank you @FoobazJohn, Is it have any name? – ChaosPredictor Nov 18 '17 at 18:32

score 2 · Answer 2 · answered Nov 18 '17 at 18:29

2

$$\sum_{i=0}^{n}{\binom{n}{i}i} = \frac{d}{dx} \left(\sum_{i=0}^{n}{\binom{n}{i}x^i}\right)\bigg|_{x=1} = \frac{d}{dx}(x+1)^n\bigg|_{x=1}= n2^{n-1}$$

answered Nov 18 '17 at 18:29

Guy Fsone

23,903

Markus Scheuer · Answer 3 · 2017-11-18T19:55:40.777

1

Another derivation is based upon $\binom{n}{i}=\frac{n}{i}\binom{n-1}{i-1}$.

We obtain \begin{align*} \color{blue}{\sum_{i=0}^n\binom{n}{i}i}&=n\sum_{i=1}^n\binom{n-1}{i-1} =n\sum_{i=0}^{n-1}\binom{n-1}{i} \color{blue}{=n2^{n-1}} \end{align*}

edited Nov 18 '17 at 19:55

answered Nov 18 '17 at 19:50

Markus Scheuer

108,315

Big-O and Big-Theta of $\sum_{i=0}^{n}{\binom{n}{i}i}$

3 Answers3