Is there a closed form for a sum $nPk +(n-1)Pk + (n-2)Pk + ... + kPk$?

Question

I would like to know if there is some closed form to solve for a sum in the form:

$nPk +(n-1)Pk + (n-2)Pk + ... + kPk$

For instance, if $n=7$ and $k=2$:

$7P2 + 6P2 + 5P2 + ... + 2P2$ = $\frac{7!}{5!} + \frac{6!}{4!} + \frac{5!}{3!}+ ...+ \frac{2!}{0!}$

Answer 1

The sum you want is$$\sum_{i=0}^{n-k}\frac{(n-i)!}{(n-i-k)!}=k!\sum_{i=0}^{n-k}\frac{(n-i)!}{(n-i-k)!k!}=k!\sum_{i=0}^{n-k}\binom{n-i}{k}.$$ Here, note that $\sum_{i=0}^{n-k}\binom{n-i}{k}$ is the coefficient of $x^k$ in $$(1+x)^n+(1+x)^{n-1}+\cdots+(1+x)^k$$ $$=(1+x)^k\cdot\frac{(1+x)^{n-k+1}-1}{x}=\frac{(1+x)^{n+1}}{x}-\frac{(1+x)^k}{x}.$$ Since there is no term $x^k$ in $\frac{(1+x)^k}{x}$, $\sum_{i=0}^{n-k}\binom{n-i}{k}$ is the coefficient of $x^{k+1}$ in $(1+x)^{n+1}$, which is $\binom{n+1}{k+1}$.

Hence, your sum is $$k!\binom{n+1}{k+1}=\frac{(n+1)\cdot n\cdot (n-1)\cdots (n-k+1)}{k+1}.$$

Answer 2

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} &\color{#66f}{\large% \sum_{\ell\ =\ 0}^{n - k}{\pars{n - \ell}! \over \pars{n - \ell -k}!}} =k!\sum_{\ell\ =\ 0}^{n - k}{\pars{n - \ell}! \over k!\pars{n - \ell -k}!} =k!\sum_{\ell\ =\ 0}^{n - k}{n - \ell\choose k} \end{align}

Note that $\ds{\sum_{\ell\ =\ 0}^{n - k}{n - \ell\choose k} =\sum_{\ell\ =\ 0}^{\color{#c00000}{\LARGE\infty}}{n - \ell\choose k}}$ since $\ds{{n - \ell\choose k} = 0}$ when $\ds{\ell > n - k}$. Then,

with $\ds{a > 2}$: \begin{align} &\color{#66f}{\large% \sum_{\ell\ =\ 0}^{n - k}{\pars{n - \ell}! \over \pars{n - \ell -k}!}} =k!\sum_{\ell\ =\ 0}^{\infty}\oint_{\verts{z}\ =\ a} {\pars{1 + z}^{n - \ell} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} \\[5mm]&=k!\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{k + 1}} \sum_{\ell\ =\ 0}^{\infty}\pars{1 \over 1 + z}^{\ell}\,{\dd z \over 2\pi\ic} =k!\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n} \over z^{k + 1}} {1 \over 1 - 1/\pars{1 + z}}\,{\dd z \over 2\pi\ic} \\[5mm]&=k!\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{n + 1} \over z^{k + 2}} \,{\dd z \over 2\pi\ic} =\color{#66f}{\Large k!\ {n + 1 \choose k + 1}} \end{align}

Answer 3

Here is a combinatorial proof of the identity $$ (k+1) \sum_{t=k}^n t^{\underline{k}} = (n+1)^\underline{k+1}. $$ The left-hand side counts the number of possibilities of choosing a number $s \leq n+1$ and $k$ distinct numbers less than $s$, and in addition a position $p \in \{1,\ldots,k+1\}$. If you put $s$ at position $p$ and the $k$ distinct numbers in the other position, you get $k+1$ distinct numbers at most $n+1$, and moreover this mapping is bijective.

Another simple proof uses induction. When $k = n$, the identity reads $(k+1) k! = (k+1)!$, which is clearly correct. For the inductive step, we need to prove that $n^\underline{k+1} + (k+1) n^\underline{k} = (n+1)^\underline{k+1}$. Indeed, $$ n^\underline{k+1} + (k+1) n^\underline{k} = \frac{n!}{(n-k-1)!} + \frac{(k+1)n!}{(n-k)!} = \frac{(n-k)n! + (k+1)n!}{(n-k)!} = \frac{(n+1)n!}{(n-k)!} = \frac{(n+1)!}{(n-k)!} = (n+1)^\underline{k+1}. $$