# Proving an identity algebraically

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

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

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

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