3

This answer showed that $$\sum_{k = 0}^n \frac{k}{(n-k)!} = e \frac{\Gamma(n+1,1) - \Gamma(n,1)}{\Gamma(n)} \label{a}\tag{1}$$ using the fact that $\sum_{k=0}^n \frac{1}{k!} = e \frac{\Gamma(n+1,1)}{\Gamma(n+1)}$.

Now, the generating function for $n$ is $\frac{x}{(1 - x)^2}$ and the generating function for $\frac{1}{n!}$ is $e^x$, so it follows that $$F(x) = \frac{x e^x}{(1 - x)^2}$$ is the generating function for the LHS of \ref{a}. Is it possible to derive the closed form on the RHS of \ref{a} (or some other closed form for that matter) by manipulating $F(x)$ rather than using properties of sums?

I am interested in solving the problem via this method as this generating function seems difficult to work with based on what I know, and I would like to expand my repertoire of techniques for dealing with generating functions.

Qudit
  • 3,221

1 Answers1

6

By setting $S_n=\sum_{h=0}^{n}\frac{1}{h!}$ we have $$\sum_{k=0}^{n}\frac{k}{(n-k)!}=\sum_{k=0}^{n}\frac{n-k}{k!}= n S_n-S_{n-1}=(n-1)S_{n-1}+\frac{1}{(n-1)!} $$ hence the LHS essentially behaves like $e(n-1)$. Such approximation should be enough for the practical purposes of analytic combinatorics. Any closed form for the LHS has to involve the incomplete $\Gamma$ or Beta functions, but the behaviour of the Taylor coefficients of $\frac{xe^x}{(1-x)^2}$ is pretty clear since such function only has a double pole at $x=1$, leading to

$$ \frac{x e^x}{(1-x)^2} = \frac{e}{(x-1)^2}+\frac{2e}{x-1}+\underbrace{\text{entire function}}_{e+x+(3-e)x^2+\ldots}.$$ The Taylor coefficients are related to the incomplete $\Gamma$ function since $\sum_{h > n}\frac{1}{h!}$ can be written as the integral remainder of a Taylor polynomial for the exponential function.

Jack D'Aurizio
  • 353,855