Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
Searching around at the OEIS turns up these two relevant sequences. Have a look at those entries, and the links therein. – J. M. Jul 7 '12 at 13:00
It seems difficult. Are you interested in exact solutions, or numerical/asymtotical? – leonbloy Jul 7 '12 at 13:01
I got the same results as @J.M. with relations to Poisson-Charlier Polynomial and W. Lang's reference – Raymond Manzoni Jul 7 '12 at 13:12
@J.M. thank you! I edited the post – pebox11 Jul 7 '12 at 15:16
I 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\}<B_{n+1}-B_n$, so $\sum\limits_{k=0}^n \frac1{k+1}\left\{ n \atop k\right\} >2B_n-B_{n+1}$. – pebox11 Jul 7 '12 at 22:26
up vote 6 down vote accepted

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
share|cite|improve this answer
Note 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... – J. M. Jul 11 '12 at 17:39
Leonbloy, you might be interested in seeing my follow-up to your answer. – Mike Spivey Nov 24 '12 at 7:07

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
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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