2
$\begingroup$

Show that $$\sum_{i=0}^{n} \binom{n}{i} i (i-1)=n(n-1)2^{n-2}$$ knowing that $$\sum_{i=0}^{n}\binom{n}{i}i=n2^{n-1}$$

I ended up after a while with

$$\sum_{i=0}^{n}\frac{n-1}{2}\binom{n}{i}i=n(n-1)2^{n-2}$$

How can I transform of the $\frac{n-1}{2}$?

$\endgroup$
2
$\begingroup$

Note that $ \dbinom{n}{i} i(i-1) = \frac{n!}{(n-i)! (i - 2)!}= n(n-1) \dbinom{n-2}{i} $.

Because $ \dbinom{n}{-2} = \dbinom{n}{-1} = 0 $, $$\sum_{i = 0}^n n(n-1)\dbinom{n-2}{i-2} = n(n-1) \sum_{i = 0}^{n-2} \dbinom{n-2}{i} = n(n-1)2^{n-2} $$

This only requires the knowledge that $ \sum_{i = 0}^n \dbinom{n}{i} = 2^n $ which is immediately obvious from the Binomial Theorem applied to $ (x + y)^n $ when $ x = y = 1 $.

If you wanted to explicitly use the given sum, you would consider $ \displaystyle \sum_{i = 0}^n \dbinom{n}{i} i^2 $. From there, $ \dbinom{n}{i} i^2 = n\dbinom{n-1}{i - 1}i $. Then shift the index up by $ 1 $ and you will once again have a linear function of $ i $ and $ \dbinom{n}{i} $.

$\endgroup$
1
$\begingroup$

$\text{Consider}$ $$\sum_{i=0}^n \dbinom{n}i x^i = (1+x)^n \tag{$\star$}$$ $\text{Differentiating $(\star)$, we get that}$ $$\sum_{i=0}^n \dbinom{n}i i x^{i-1} = n(1+x)^{n-1} \tag{$\perp$}$$ $\text{Differentiating $(\perp)$, we get that}$ $$\boxed{\color{red}{\displaystyle \sum_{i=0}^n \dbinom{n}i i(i-1) x^{i-2} = n(n-1)(1+x)^{n-2}}}$$ $\text{Now, set $x=1$ to get the answer, i.e.,}$ $$\boxed{\color{blue}{\displaystyle \sum_{i=0}^n \dbinom{n}i i(i-1) = n(n-1)2^{n-2}}}$$

$\endgroup$
0
$\begingroup$

You can simply pull the constant factor of $\frac{n-1}2$ outside the summation: that’s just the distributive law. Alternatively, you start at the beginning and use the identity

$$\binom{n}ii=n\binom{n-1}{i-1}\;,$$

which you can verify either combinatorially or by expanding into factorials.

Then

$$\binom{n}i(i-1)=n\binom{n-1}{i-1}(i-1)=n(n-1)\binom{n-2}{i-2}\;,$$

and you can pull the factor of $n(n-1)$ out of the summation. Then you need only know that $\sum_{k=0}^m\binom{m}k=2^m$.

$\endgroup$

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.