Does anyone recognise this recursion sastisfied by the Bell numbers?

477 Views Asked by At

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.

2

There are 2 best solutions below

3
On BEST ANSWER

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.

3
On

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$