2
$\begingroup$

Consider the sum $$\frac{1}{n!} \sum_{k=0}^n k(n-k)!$$ How fast does it grow (as a function of $n$)? I can prove that it grows slower than or equal to linearly (but I expect this is very crude), so I am looking for a better bound of growth.

The closed form I found in Wolfram Alpha includes subtracting some factorials, so is not a keen indicator of growth. I tried bounding this using the Gamma function: It is $\le \int_0^n x\Gamma(n-x+1)$, but I am not sure what I can do from here.

Where does this crop up? Well, it is the expected stopping time to a common "puzzle" question.

$\endgroup$
  • $\begingroup$ Thanks for all the answers. $\endgroup$ – Maithreya Sitaraman Mar 23 '18 at 17:56
3
$\begingroup$

This sum is bounded above, and it's easy to show a crude estimate. Let

$$f_n(x) = \sum_{k=0}^n\,\frac{(n-k)!}{n!}\,x^k=\sum_{k=0}^n\,\frac{1}{\binom{n}k}\,\frac{x^k}{k!}.$$

Then

\begin{align} f_n'(x) = \sum_{k=0}^n\,\frac{k\,(n-k)!}{n!}\,x^k =\sum_{k=1}^n\,\frac{1}{\binom{n}k}\,\frac{x^{k-1}}{(k-1)!} &\leq \sum_{k=1}^n\,\frac{x^{k-1}}{(k-1)!}\\ &= \sum_{k=0}^{n-1}\,\frac{x^{k}}{k!}\\ &\leq \sum_{k=0}^{\infty}\,\frac{x^{k}}{k!}=\exp(x), \end{align}

and observe that this bound does not depend on $n$. Moreover, notice that $\frac{1}{n!} \sum_{k=0}^n k(n-k)! =$ $f'(1)$. It follows that

$$\frac{1}{n!} \sum_{k=0}^n k(n-k)! \leq e$$

$\endgroup$
3
$\begingroup$

We can rewrite the series as $$\sum_{k = 0}^n k(n-k)! = \sum_{k = 0}^n (n-k)k! = n\sum_{k = 0}^n k! - \sum_{k=0}^n k \cdot k! = n\sum_{k = 0}^n k! - (n+1)!+1$$ where the last equality follows from the identity $\sum_{i = 0}^n k \cdot k! = (n+1)! - 1$. If this post is to be believed, we have an asymptotic expansion

$$ \sum_{k = 0}^n k! = n!\left(1 + \frac{1}{n} + \frac{1}{n^2} + O\left(\frac{1}{n^3}\right)\right)$$

Using these two observations to your series gives $$\frac{1}{n!}\sum_{k=0}^nk(n-k)! = n\left(1 + \frac{1}{n} + \frac{1}{n^2} + O\left(\frac{1}{n^3}\right)\right) - (n+1)+\frac{1}{n!} = \frac{1}{n} + O\left(\frac{1}{n^2}\right)$$

And hence as $n \to \infty$, the series goes to $0$.

(Disclaimer: I don't really know much about asymptotic series, so some of my reasoning there may be off).

$\endgroup$
  • $\begingroup$ This is pretty good! +1 $\endgroup$ – Fimpellizieri Mar 2 '18 at 14:28
2
$\begingroup$

As shown in the table below, the function $$f_n=\frac{1}{n!} \sum_{k=0}^n k\,(n-k)!$$ is decreasing as soon as $n>2$ $$\left( \begin{array}{ccc} n & f_n & f_n\approx \\ 0 & 0 & 0.00000 \\ 1 & 1 & 1.00000 \\ 2 & \frac{3}{2} & 1.50000 \\ 3 & \frac{7}{6} & 1.16667 \\ 4 & \frac{17}{24} & 0.70833 \\ 5 & \frac{17}{40} & 0.42500 \\ 6 & \frac{41}{144} & 0.28472 \\ 7 & \frac{1079}{5040} & 0.21409 \\ 8 & \frac{111}{640} & 0.17344 \\ 9 & \frac{53227}{362880} & 0.14668 \\ 10 & \frac{462341}{3628800} & 0.12741 \end{array} \right)$$ For the interval $2 \leq n \leq 100$, it seems that is varies "almost" as $$f_n=\frac{a+b n}{1+c n + d n^2}$$ A quick and dirty nonlinear regression gives $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} \\ a & +0.106334 & 0.029581 \\ b & +0.155564 & 0.005736 \\ c & -0.740640 & 0.010730 \\ d & +0.189945 & 0.002423 \\ \end{array}$$

Edit

After Jack D'Aurizio's answer, which clearly shows the limit, we can get the expression for $f_n$ since $$\int_{0}^{+\infty}(n-k)x^k e^{-x}\,dx=(n-k)\, \Gamma (k+1)$$ making $$\sum_{k=0}^{n}(n-k)k! =-n\, \text{Subfactorial}[-1]-(-1)^n n\, \Gamma (n+2)\, \text{Subfactorial}[-n-2]-\Gamma (n+2)+1$$ where appears the subfactorial function and, as Jack D'Aurizio showed, this is $\ll (n-1)!$.

$\endgroup$
1
$\begingroup$

$$\sum_{k=0}^{n}(n-k)k! = \int_{0}^{+\infty}\sum_{k=0}^{n}(n-k)x^k e^{-x}\,dx =\int_{0}^{+\infty}\underbrace{\frac{n-(n+1)x+x^{n+1}}{(1-x)^2}}_{\ll x^{n-1}}e^{-x}\,dx$$ hence the LHS is $\ll (n-1)!$ and the wanted limit is clearly zero.

$\endgroup$

Your Answer

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

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