4
$\begingroup$

Here is a sum in combinatorics, $\sum\limits_{r = 2}^n \binom{n}{r} \binom{r}{2}$ where $n>2$, does this have a closed form?

$\endgroup$

3 Answers 3

8
$\begingroup$

Yes, the closed form is

$$\sum\limits_{r = 2}^n {C_n^rC_r^2} = n \cdot (n-1) \cdot 2^{n-3}$$

Seems there're various ways to prove this.

The combinatorial approach to prove this would be to think about this.

In how many ways can we choose from $n$ people a committee with $r$ members (where $ 2 \le r \le n$), and also choose $2$ chairmen from the committee. Express this number in two different ways and you get the above identity.

$\endgroup$
2
$\begingroup$

$$\sum_{r=2}^n \binom{n}{r} \binom{r}{2} =\sum_{r=2}^n \binom{n}{2} \binom{n-2}{r-2} =\binom{n}{2} \sum_{r=2}^n \binom{n-2}{r-2} =\binom{n}{2} 2^{n-2} =n(n-1) 2^{n-3} $$

$\endgroup$
2
$\begingroup$

We have the ordinary generating function for $$ (1+x)^n = \sum_{0\leq r\leq n }{ n\choose r} x^{ r}\cdots (1)$$ Now we differentiate $(1)$ twice and then divide by $2!$ giving us $$ \frac{(n)_2}{2!}(1+x)^{n-2}=\sum_{0\leq r\leq n} {n\choose r}\frac{(r)_2}{2!} x^{n-2}\\ {n\choose 2} (1+x)^{n-2}=\sum_{0\leq r\leq n} {n\choose r}{r\choose 2} x^{n-2}\cdots (2)$$ and where $\displaystyle \frac{(m)_n}{n!}={m\choose n}$ and setting $x=1$ in $(2)$ yield $$ \sum_{0\leq r\leq n}{n\choose r}{r\choose 2} =2^{n-2}{n\choose 2}=2^{n-2}T_n= 2^{n-3}n(n-1)$$ note that for $0\leq r\leq 2$ the coefficients ${r\choose 2} =0$ and hence we have $$\sum_{r=2}^{n}{n\choose r}{r\choose 2} = 2^{n-3}n(n-1)$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.