1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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/…. $\endgroup$ – Sil Oct 15 '17 at 6:07
  • $\begingroup$ Sorry for not finding that one before asking. Thx for the tip. $\endgroup$ – Gabriel Silva Oct 15 '17 at 8:02
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mr Pie Oct 15 '17 at 23:02
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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