4

Question is to Evaluate $$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!} $$

What i have done so far is $$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!}=n(n-1)\sum_{k=2}^n \frac{(n-2)!}{(n-k)!(k-2)!}=n(n-1)\sum_{k=2}^n \binom{n-2}{k-2}$$

I could see that $$\sum_{k=2}^n \binom{n-2}{k-2}$$looks much similar to $$\sum_{k=0}^n \binom{n}{k}=(1+1)^n$$

So, we should have something like $$\sum_{k=2}^n \binom{n-2}{k-2}=(1+1)^{n-2}$$

But i am not very sure if this is even true.

I tried adding $\binom{n-2}{k-2}$ with $\binom{n-2}{k-1}$ with a formula $\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{k}$ hoping to reduce $n-2$ in the expansion to $n$ but is was not helpful.

I tried to consider $(1+x)^n$ expansion and tried differentiating it but this was also not very helpful.

I would be thankful if some one can help me to clear this.

Thank you

Did
  • 279,727

2 Answers2

5

$$\sum_{k=2}^n{n-2\choose k-2}\quad=\quad\sum_{j=0}^{n-2}{n-2\choose j}=2^{n-2}\qquad\iff\qquad S=n(n-1)2^{n-2}$$

Lucian
  • 48,334
  • 2
  • 83
  • 154
  • Oh my bad... how could i miss this simple relation... Thank you @Lucian.. I was sure about that what i have expected should be true was not sure how to get it.. Thank you once again –  Nov 23 '13 at 17:02
  • Changing variables in a sum (here, replacing $k-2$ by $j$, or putting $k=j+2$) is one of those simple procedures that people nevertheless seem to have great problems with. I remember having a hard time with grasping it myself when I was a student, yet presently I can no longer understand what was so difficult about it. – Harald Hanche-Olsen Nov 23 '13 at 17:04
2

$$\sum_{k=2}^n\frac{n!}{(n-k)!(k-2)!}=\sum_{k=2}^n\frac{n!k(k-1)}{(n-k)!k!} $$ $$=\sum_{k=2}^nk(k-1)\binom{n}{k}=\sum_{k=2}^nk(k-1)\frac{n(n-1)}{k(k-1)}\binom{n-2}{k-2}$$ $$=n(n-1)\sum_{k=2}^n\binom{n-2}{k-2}=n(n-1)\sum_{j=0}^{n-2}\binom{n-2}{j}=n(n-1)2^{n-2}$$

Adi Dani
  • 16,949
  • I do not get your idea of again trying to prove every thing else which i have already done and write nothing about what i had problem with.... :O –  Nov 23 '13 at 17:11