It is known that $\sum\limits_{k=0}^n \left\{ n \atop k\right\} k = \varpi(n+1) - \varpi(n)$. Any ideas for computing $\sum\limits_{k=0}^n \frac1{k+1}\left\{ n \atop k\right\}$ ? ($\left\{ n \atop k\right\}$ denotes the Stirling numbers of the second kind and $\varpi(n)$ the $n$-th Bell number)
Expression for $\sum\limits_{k=0}^n \frac1{k+1}\left\{ n \atop k\right\}$?
-
3Searching around at the OEIS turns up [these](http://oeis.org/A130189) [two](http://oeis.org/A130190) relevant sequences. Have a look at those entries, and the links therein. – 2012-07-07
-
0It seems difficult. Are you interested in exact solutions, or numerical/asymtotical? – 2012-07-07
-
0I got the same results as @J.M. with relations to [Poisson-Charlier Polynomial](http://mathworld.wolfram.com/Poisson-CharlierPolynomial.html) and [W. Lang's reference](http://www-itp.particle.uni-karlsruhe.de/~wl/EISpub/A006232.text) – 2012-07-07
-
0@J.M. thank you! I edited the post – 2012-07-07
-
0@leonbloy exact would be perfect, but asymtotical would be fine as well. – 2012-07-07
-
1I had the following idea for a lower bound, do you thing it carries on? $\sum\limits_{k=0}^n \frac1{k+1}\left\{ n \atop k\right\}=\sum\limits_{k=0}^n \frac{k+1-k}{k+1}\left\{ n \atop k\right\}=B_n-\sum\limits_{k=0}^n \frac{k}{k+1}\left\{ n \atop k\right\}$. But $\sum\limits_{k=0}^n \frac{k}{k+1}\left\{ n \atop k\right\}
, so $\sum\limits_{k=0}^n \frac1{k+1}\left\{ n \atop k\right\} >2B_n-B_{n+1}$. – 2012-07-07
2 Answers
We know
$$B_n(x) = \sum_{k=0}^n \left\{ n \atop k\right\} x^k $$
where $B_n(x)$ is the Bell polynomial. Then
$$ \int_0^1 B_n(x) dx = \sum_{k=0}^n\frac1{k+1}\left\{ n \atop k\right\}$$
is what we are interested in computing. It's also known that
$$B_n(x) = e^{-x} \sum_{t=0}^{\infty} \frac{t^n x^t} {t!}$$
so we want the value of
$$ \sum_{k=0}^n\frac1{k+1}\left\{ n \atop k\right\}= \sum_{t=0}^{\infty} \frac{t^n I(t)} {t!}, \hspace{1cm} I(t)= \int_0^1 e^{-x}x^t dx$$
But it can be shown (eg) that $I(t) \sim \frac{1}{e \,t}$, so, asymptotically
$$ \sum_{k=0}^n\frac1{k+1}\left\{ n \atop k\right\} \sim e^{-1} \sum_{t=0}^{\infty} \frac{t^{n-1}}{t!} = B_{n-1}$$
which is the $n-1$-Bell number. Some values, taking the logarithm:
n exact approx 4 1.5114 1.6094 8 6.7348 6.7765 16 21.0308 21.0475 32 57.5872 57.5935
-
1Note that the $I(t)$ in leonbloy's answer is a special case of the (lower) incomplete gamma function, of which [much is known about its asymptotic behavior](http://dlmf.nist.gov/8.11)... – 2012-07-11
-
0Leonbloy, you might be interested in seeing my follow-up to your answer. – 2012-11-24
The error in leonbloy's approximation $\sum_{k=0}^n\frac1{k+1}\left\{ n \atop k\right\} = B_{n-1} + E_n$ is exactly $$E_n = - \sum_{k=0}^{n-1}\left\{ n-1 \atop k\right\} \frac1{(k+1)(k+2)}.$$ Moreover, the asymptotic can be improved to $$\sum_{k=0}^n\frac1{k+1}\left\{ n \atop k\right\} \sim B_{n-1} - B_{n-3},$$ (and probably further, for anyone who wants to continue the process below).
Theorem 4 of my paper "On Solutions to a General Combinatorial Recurrence" (Journal of Integer Sequences, 14 (9): Article 11.9.7, 2011), with $\left| {n \atop k} \right| = \left\{ n \atop k\right\}$ and $f(k,m) = \frac{1}{k+1}$ says that $$\begin{align}\sum_{k=0}^n\frac1{k+1}\left\{ n \atop k\right\} &= \sum_{k=0}^{n-1}\left\{ n-1 \atop k\right\} (k+1) \frac1{k+1} - \sum_{k=0}^{n-1}\left\{ n-1 \atop k\right\} \frac1{(k+1)(k+2)} \\ &= B_{n-1} - \sum_{k=0}^{n-1}\left\{ n-1 \atop k\right\} \frac1{(k+1)(k+2)}. \end{align} $$
Applying Theorem 4 again, this time with $f(k,m) = \frac{1}{(k+1)(k+2)}$, yields (after some simplification) $$\begin{align} &\sum_{k=0}^{n-1}\left\{ n-1 \atop k\right\} \frac1{(k+1)(k+2)} \\ &= \sum_{k=0}^{n-2}\left\{ n-2 \atop k\right\} \frac1{k+1} - \sum_{k=0}^{n-2}\left\{ n-2 \atop k\right\} \frac1{(k+1)(k+2)} - 2 \sum_{k=0}^{n-2}\left\{ n-2 \atop k\right\} \frac1{(k+1)(k+2)(k+3)}. \end{align}$$ The first term on the right-hand side dominates, and with leonbloy's approximation $$\sum_{k=0}^{n-2}\left\{ n-2 \atop k\right\} \frac1{k+1} \sim B_{n-3},$$ we get $$\sum_{k=0}^n\frac1{k+1}\left\{ n \atop k\right\} \sim B_{n-1} - B_{n-3}.$$
By comparison with leonbloy's results (again, after taking logarithms)
n exact B_{n-1} - B_{n-3} B_{n-1} 4 1.5114 1.3863 1.6094 8 6.7348 6.7154 6.7765 16 21.0308 21.0273 21.0475 32 57.5872 57.5866 57.5935