Evaluation of $\mathop{\displaystyle \sum_{r=1}^{n}r\cdot (r-1)\cdot \binom{n}{r} = }$

$\bf{My\; Try::}$ Given $$\displaystyle \sum_{r=1}^{n}r\cdot (r-1)\cdot \binom{n}{r}\;,$$ Now Using the formula $$\displaystyle \binom{n}{r} = \frac{n}{r}\cdot \binom{n-1}{r-1}.$$

$$\mathop{\displaystyle =\sum_{r=1}^{n}r\cdot (r-1)\cdot \frac{n}{r}\cdot \binom{n-1}{r-1}}$$

$$\mathop{\displaystyle = n\sum_{r=2}^{n}(r-1)\cdot \frac{n-1}{r-1}\cdot \binom{n-2}{r-2} = n\cdot (n-1)\sum_{r=2}^{n}\binom{n-2}{r-2}}$$

$$\mathop{\displaystyle = n\cdot (n-1)\cdot \left[\binom{n-2}{0}+\binom{n-2}{1}+..........+\binom{n-2}{n-2}\right] = n(n-1)\cdot 2^{n-2}}$$

My question is can we solve it using combinatorial argument, If yes then plz explain here



This is the number of ways to select a sub committee of $n$ people where you designate a president and a vice president. One way is to pick the president and vice president, and then go around asking everyone else if they want to be in the committee or not. The other way is to first pick $r$ people, $1 \le r \le n$ and then assign the roles.


$\sum_{r=0}^{n} r(r-1)\binom{n}{r} = 2 \sum_{r=0}^n \binom{n}{r} \binom{r}{2}$. The summand is the number of ways of choosing from $n$ objects an $r$-tuple and a 2-subtuple, so the right-hand sum is just the number of ways of choosing a 2-tuple multiplied by the number of possible tuples the 2-subtuple could have been drawn from. That is, the number of 2-tuples multiplied by $2^{n-2}$, or $\binom{n}{2} \times 2^{n-2}$.

Therefore, the left-hand sum is $n(n-1) \times 2^{n-2}$.

To expand on the $2^{n-2}$: the set of tuples from which a given 2-subtuple $(a,b)$ has been drawn, bijects with the set of tuples drawn from a set of size $n-2$, by the bijection "remove $a$ and $b$ from the tuple".


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.