2
$\begingroup$

Find the following sum $$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!}.$$I found that , $$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!}=n!\left[\frac{1}{(n-2)!0!}+\frac{1}{(n-3)!1!}+\cdots +\frac{1}{0!(n-2)!}\right]$$From here how I proceed ?

$\endgroup$
1
  • 2
    $\begingroup$ $LHS=\frac{n!}{(n-2)!}\sum_{k=0}^{n-2}\frac{(n-2)!}{(n-2-k)!k!}=n(n-1)2^{n-2}$ $\endgroup$
    – Ziyuan
    Jan 11, 2016 at 16:27

4 Answers 4

10
$\begingroup$

Outline: By the Binomial Theorem we have $$(1+x)^n=\sum_{k=0}^n \frac{n!}{(n-k)!k!}x^k.$$ Differentiate twice and set $x=1$.

$\endgroup$
1
  • $\begingroup$ All to easy. +1 $\endgroup$
    – Mark Viola
    Jan 11, 2016 at 16:26
5
$\begingroup$

$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!}$

Observe that in each term of above summation, sum of the arguements of the factorial in the denominator is constant for each term and equal to $n-2$, so you should try to write each term as a binomial coefficient.

And since the constant is $n-2$ we are motivated to write the summation as,

$n(n-1)\sum_{k=2}^n \frac{(n-2)!}{(n-k)!(k-2)!}=n(n-1)\sum_{r=0}^{n-2} \dbinom{n-2}{r}$

Now as mentioned in the other posts $\sum_{r=0}^{n-2} \dbinom{n-2}{r}=2^{n-2}$

So, you are done.

$\endgroup$
1
  • 1
    $\begingroup$ Nice first principles argument. $\endgroup$ Jan 11, 2016 at 16:38
3
$\begingroup$

Note that $$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!} = \sum_{k=0}^n k(k-1) {n \choose k}.$$

Thus, consider $f$ defined by $f(x) = (1+x)^{n}$. Then $$f(x) = \sum_{k=0}^n {n \choose k} x^k.$$

Then $$f''(x) = \sum_{k=2}^n k(k-1) {n \choose k} x^{k-2},$$ and $$f''(x) = n(n-1)(1+x)^{n-2}.$$

All you have to do is take $x=1$.

$\endgroup$
1
$\begingroup$

A combinatorial aproach:

$\dfrac{n!}{(n-k)!(k-2)!}=(k-1)(k)\displaystyle\binom{n}{k}=2\binom{n}{k}\binom{k}{2}$. But the last can be thinking like total ways to select a team with $k$ elements from a set of $n$ and then select two captains from this $k$, which is the same that select first the two captains and then the other $k-2$: $\binom{n}{k}\binom{k}{2}=\binom{n}{2}\binom{n-2}{k-2}$. Then:

$$\displaystyle\sum_{k=2}^n\binom{n}{k}\binom{k}{2}=\displaystyle\sum_{k=2}^n\binom{n}{2}\binom{n-2}{k-2}=\binom{n}{2}\displaystyle\sum_{k=0}^{n-2}\binom{n-2}{k}=\binom{n}{2}2^{n-2}$$

Finally, $\sum_{k=2}^n\frac{n!}{(n-k)!(k-2)!}=\sum_{k=2}^n2\binom{n}{k}\binom{k}{2}=\binom{n}{2}2^{n-1}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy