Prove that $\sum_{i=2}^n \binom{n}{i} \binom{i}{2} = 2^{(n - 3)} \cdot n(n - 1)$

When attempting to solve an asymptotic complexity problem, i got this summation $$\sum_{i=2}^n \binom{n}{i} \binom{i}{2}$$ Wolfram Alpha states that it equals to $$2^{(n - 3)} \cdot n(n - 1)$$ But I can't find how, and Wolfram is unable to produce the step-by-step solution.

• It has been asked here already also (looks bit differently and there is an typo in title but its the same) math.stackexchange.com/questions/1627311/…. – Sil Oct 15 '17 at 6:07
• Sorry for not finding that one before asking. Thx for the tip. – Gabriel Silva Oct 15 '17 at 8:02

Consider $$(1+x)^n=\sum_{i=0}^n\binom{n}ix^i.$$ Differentiate twice: $$n(n-1)(1+x)^{n-2}=\sum_{i=2}^n\binom{n}ii(i-1)x^i.$$ Now set $x=1$.

• Is differentiating twice meaning to find $f''(x)$ if $f(x) = (1 + x)^n?$ Basically finding the second derivative? I'm just trying to get used to the terminology – Mr Pie Oct 15 '17 at 23:02

This has nice combinatorical solution. Ask yourself on how many ways we can choose a set of pepople and then among them president and vice president.

$$\sum_{i=2}^n\binom ni\binom i2=\sum_{i=2}^n\binom n2\binom{n-2}{i-2}=\binom n2\sum_{i=2}^n\binom{n-2}{i-2}=\binom n2\sum_{j=0}^{n-2}\binom{n-2}j=\binom n22^{n-2}=n(n-1)2^{n-3}$$

Your expression is the value $f(1)$ of

$$f(x):=\sum_{i=2}^n \binom{n}{i} \dfrac{i(i-1)}{2}x^{i}=\dfrac12 x^2\underbrace{\sum_{i=0}^{n} \binom{n}{i} \dfrac{i(i-1)}{2}x^{i-2}}_{g(x)}$$

But $g(x)$ can be given another expression because it is the second derivative of $(1+x)^{n}$, i.e., $g(x)=(n)(n-1)(1+x)^{n-2}$.

It suffices now to set $x=1$ to obtain your result.