7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – user14972
    Aug 30, 2014 at 23:51

2 Answers 2

10
+200
$\begingroup$

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.

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

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$

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – jkn
    Sep 1, 2014 at 10:11
  • $\begingroup$ 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 :-) $\endgroup$ Sep 1, 2014 at 10:18
  • $\begingroup$ mathworld.wolfram.com/BellNumber.html could be interesting to you. $\endgroup$ Sep 1, 2014 at 10:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .