# Does anyone recognise this recursion sastisfied by the Bell numbers?

I derived a recursion

$$B_n=\frac{1}{n}B_0+\frac{1}{n}\sum_{k=1}^{n-1}\left[\binom{n}{k}-(-1)^{n-k}\binom{n}{k-1}\right]B_k\tag{*}$$

which I know should be satisfied by the moments of the unit Poisson distribution ($B_n$ denoting the $n$th moment), which happen to be the Bell numbers. Trying to check that I hadn't mucked up the derivation I looked online for recursions satisfied by the Bell numbers hoping to find the above, however I only found the standard one

$$B_n = \sum_{k=0}^{n-1}\binom{n-1}{k}B_k.$$

I'm pretty sure now that the derivation of $(*)$ is fine (I've also computed the first few numbers obtained from $(*)$, with $B_0=1$, and they are the first few Bell numbers). So does anyone recognise the recursion $(*)$? Does it have a name, or, do you know of a reference that contains it? Thanks.

Edit: Happy to give the bounty to anyone that posts a proof that $(*)$ is (or isn't) satisfied by the Bell numbers or a reference containing such a proof.

• I would have checked my work by computing the first 10 and seeing if they give the right answer. And then if I wanted a proof, I would start by trying to compute $B_n - B_{n-1}$ both ways to see if they agree. (actually, I would have first tried to compute $B_n - B_n$ where I compute $B_n$ both ways and seeing if I could simplify it to zero)
– user14972
Aug 30, 2014 at 23:51

It is known that the Bell number $B_n$ satisfy a recurrence relation involving binomial coefficients:

$$B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k \quad\text{ for } n \in \mathbb{N}\tag{*1}.$$

Given any sequence $( a_n )_{n \in \mathbb{N}}$, we can generate another sequence $(b_n)_{n \in \mathbb{N}}$ by following transform:

$$b_n = \sum_{k=0}^n (-1)^{n-k}\binom{n}{k} a_k \tag{*2a}$$

This is known as the binomial transform and it has an inverse transform of the form:

$$a_n = \sum_{k=0}^n \binom{n}{k} b_k\tag{*2b}$$

Compare $(*1)$ with $(*2b)$, the recurrence relation $(*1)$ is really the inverse transform for the relation:

\begin{align} B_n &= \sum_{k=0}^n (-1)^{n-k}\binom{n}{k} B_{k+1} = B_{n+1} - n B_n - \sum_{k=1}^{n-1} (-1)^{n-k} \binom{n}{k-1} B_k\\ \iff n B_n &= (B_{n+1} - B_n) - \sum_{k=1}^{n-1} (-1)^{n-k} \binom{n}{k-1} B_k \end{align} Substitute $(*1)$ into last expression, we get \begin{align} n B_n &= B_0 + \sum_{k=1}^{n-1} \binom{n}{k} B_k - \sum_{k=1}^{n-1} (-1)^{n-k} \binom{n}{k-1} B_k\\ &= B_0 + \sum_{k=0}^{n-1}\left[ \binom{n}{k} - (-1)^{n-k}\binom{n}{k-1}\right] B_k \end{align} So the recurrence relation in the question is nothing really new but the recurrence relation $(*1)$ hidden behind a binomial transform.

• Great! Thank you, I'll award the bounty as soon as the site lets me (20 hours).
– jkn
Sep 2, 2014 at 11:21
• @jkn, thanks for the big bounty ;-) Sep 3, 2014 at 16:57
• no problem, I can't think of better way to use these points :). Thanks again for the neat reply.
– jkn
Sep 3, 2014 at 17:06

Since I am very lazy, I just computed $$R_n=\frac{1}{n}B_0+\frac{1}{n}\sum_{k=1}^{n-1}\left[\binom{n}{k}-(-1)^{n-k}\binom{n}{k-1}\right]B_k-\sum_{k=0}^{n-1}\binom{n-1}{k}B_k$$ and effectively found that $R_n=0$ for any positive value of $n$

• Thank you for the reply, just to check, you mean you computed the above numerically for different $n$s and for each $n$ you found $R_n$ to be zero?
– jkn
Sep 1, 2014 at 10:11
• You are very welcome ! As I told, I am very lazy (and not familiar with the area of Bell numbers) so this is what I did. Cheers :-) Sep 1, 2014 at 10:18
• mathworld.wolfram.com/BellNumber.html could be interesting to you. Sep 1, 2014 at 10:24