Give a combinatorial proof: For n and k satisfying $\displaystyle 1\leq k\leq n$,

$\displaystyle _{n}P_{k}=(n)_{k}=\sum_{j=k}^{n}k*(j-1)_{k-1}$.

$\displaystyle \sum_{j=k}^{n}k*(j-1)_{k-1}$

$\displaystyle =k(k-1)_{k-1}+k(k)_{k-1}+k(k+1)_{k-1}+\ldots+k(n-2)_{k-1}+k(n-1)_{k-1}$

$\displaystyle =\frac{k*(k-1)!}{[(k-1)-(k-1)]!}+\frac{k*k!}{[k-(k-1)]!}+\frac{k(k+1)!}{[(k+1)-(k-1)]!}+\ldots+\frac{k(n-2)!}{[(n-2)-(k-2)]!}+\frac{k(n-1)!}{[(n-1)-(k-1)]!}

$

$\displaystyle =\frac{k(k-1)!}{0!}+\frac{k*k!}{1!}+\frac{k(k+1)!}{2!}+\ldots +\frac{k(n-2)!}{(n-k-1)!}+\frac{k(n-1)!}{(n-k)!}$. When we factor out k(k-1)! we are left with

$\displaystyle 1+k+\frac{k(k+1)}{2!}+\ldots+\frac{(n-k-1)!}{(n-k-1)!}+\frac{(n-k)!}{(n-k)!}=(n-k)??$

Now take (n-k)k(k-1)!=(n-k)k! and if we multiply by (n-k)!/(n-k)! we get (n-k)k!(n-k)!/(n-k)! = (n-k)n!/(n-k)!

This would equal $\displaystyle _{n}P_{k}=(n)_{k}=n!/(n-k)!$ except for the extra (n-k) in the numerator. Can someone please point out my mistake?