Implications of Spivey’s Bell Number Formula

H. W. Gould and Jocelyn Quaintance Department of Mathematics West Virginia University Morgantown, WV 26506 USA

                      gould@math.wvu.edu
                     jquainta@math.wvu.edu

Abstract Recently, Spivey discovered a novel formula for B(n + m), where B(n + m) is the (n + m)^{th} Bell number. His proof was combinatorial in nature. This paper provides a generating function proof of Spivey’s result. It also uses Spivey’s formula to determine a new formula for B(n). The paper concludes by extending all three identities to ordinary single variable Bell polynomials.

1 Introduction

Spivey [7] gave a short combinatorial proof of the following Bell number addition formula.

B(n + m) = ∑_{j=0}^{m} ∑_{k=0}^{n} S(m, j)\binom{n}{k}B(k)j^{n−k}.  (1)

Note that B(n) is the n^{th} Bell number while S(n, k) is the Stirling number of the second kind. We have translated Spivey’s notation into Riordan’s familiar notation which we find more preferable in our work [5, 6]. The purpose of this note is to offer a short generating function proof of Equation (1). We discuss this proof in Section 2. We also use Spivey’s formula, in conjunction with the Stirling numbers of the first kind, to find a new double sum expression for B(n).

2 Generating Function Proof of Equation (1)

First recall that

∑_{k=0}^{∞} B(k)\frac{x^{k}}{k!} = e^{e^{x}−1}  (2)

∑_{k=0}^{∞} S(k, j)\frac{x^{k}}{k!} = \frac{(e^{x} − 1)^{j}}{j!} .  (3)

These standard expansions are found in references [1, 3, 5, 6]. See also the definitive bibliography [2] listing hundreds of references about Bell and Stirling numbers.

Next, we form the double variable exponential generating function ∑_{m,n=0}^{∞} B(n+m)\frac{x^{n}}{n!} \frac{y^{m}}{m!} . Let D_{x}^{m}f(x) denote the derivative operator acting on f(x) m times and note that

∑_{m,n=0}^{∞} B(n + m)\frac{x^{n}}{n!} \frac{y^{m}}{m!} = ∑_{m=0}^{∞} D_{x}^{m}(e^{e^{x}−1})\frac{y^{m}}{m!}
= e^{yD_{x}}e^{e^{x}−1} = e^{e^{y+x}−1}.

The last equality follows from the following version of Taylor’s Theorem, namely

e^{yD_{x}}f(x) = f(x + y).  (4)

This old form of the Taylor series follows by using the symbolic expansion

e^{aL}f(x) = ∑_{k=0}^{∞} \frac{a^{k}L^{k}f(x)}{k!}

where L is a linear operator. The idea may be traced back to the time of George Boole, For an old reference using this form of the Taylor theorem, see Pennell [4]. However,

∑_{m,n=0}^{∞} B(n + m)\frac{x^{n}}{n!} \frac{y^{m}}{m!} = e^{e^{x+y}−1} = e^{e^{x}−1}e^{(e^{y}−1)e^{x}}

= e^{e^{x}−1} ∑_{j=0}^{∞} \frac{(e^{y} − 1)^{j}}{j!} e^{jx} = e^{e^{x}−1} ∑_{m,j=0} S(m, j)\frac{y^{m}}{m!}e^{jx}

= ∑_{m,j=0} S(m, j)\frac{y^{m}}{m!} ∑_{n=0}^{∞} \frac{x^{n}}{n!} j^{n} ∑_{k=0}^{∞} \frac{x^{k}}{k!} B(k)  (5)

= ∑_{m,j=0} S(m, j)\frac{y^{m}}{m!} ∑_{n=0}^{∞} x^{n} ∑_{k=0}^{∞} \frac{B(k)}{k!} \frac{j^{n−k}}{(n − k)!}

= ∑_{m,n=0}^{∞} \frac{x^{n}}{n!} \frac{y^{m}}{m!} ∑_{j=0}^{∞} S(m, j) ∑_{k=0}^{∞} \binom{n}{k}B(k)j^{n−k}

The equality in Equation (5) comes from the Cauchy convolution formula. By comparing the coefficients of \frac{x^{n}}{n!} \frac{y^{m}}{m!} , we note note that

B(n + m) = ∑_{j=0}^{∞} S(m, j) ∑_{k=0}^{∞} \binom{n}{k}B(k)j^{n−k}

= ∑_{j=0}^{m} ∑_{k=0}^{n} S(m, j)\binom{n}{k}B(k)j^{n−k},

which is identically Equation (1).

3 New Bell Number Formula

The purpose of this section is to use Equation (1) as a means of obtaining a new formula for B(n). In order to do this, we need the following lemma.

Lemma 1. Let n ≥ 0 and p ≥ 1. Let s(p, m) be the Stirling number of the first kind.

∑_{m=0}^{p} B(n + m)s(p, m) = ∑_{k=0}^{n} \binom{n}{k}B(n − k)p^{k}.  (6)

Using the standard notational convention that 0^{0} = 1, then (6) is true for n ≥ 0 and p ≥ 0.

Proof. Since Equation (1) is true, we can easily show that

∑_{m=0}^{p} B(n + m)s(p, m) = ∑_{k=0}^{n} \binom{n}{k}B(n − k) ∑_{m=0}^{p} ∑_{j=0}^{m} S(m, j)s(p, m)j^{k}

= ∑_{k=0}^{n} \binom{n}{k}B(n − k) ∑_{j=0}^{p} j^{k} ∑_{m=j}^{p} s(p, m)S(m, j)

= ∑_{k=0}^{n} \binom{n}{k}B(n − k)p^{k}.

The last equality follows by the orthogonal relationship between the two types of Stirling numbers, namely,

∑_{m=j}^{p} s(p, m)S(m, j) = δ_{j}^{p},

where the “Kronecker delta” is defined by δ_{j}^{p} = 1 if j = p, and δ_{j}^{p} = 0 for j ≠ p.

We now use Equation (6) to find a formula for B(n) that does not seem to appear in the literature.

Theorem 2. Let n ≥ 0 and p ≥ 1.

B(n) = ∑_{k=0}^{n}(−p)^{n−k}\binom{n}{k} ∑_{m=0}^{p} B(k + m)s(p, m).  (7)

Using the standard notational convention that 0^{0} = 1, then (7) is true for n ≥ 0 and p ≥ 0. Proof. Let k → n − k in Equation (6). Then,

p^{−n} ∑_{m=0}^{p} B(n + m)s(p, m) = ∑_{k=0}^{n} \binom{n}{k}B(k‘)p^{−k}.  (8)

We now recall that given two functions F (n) and f(n), the following two statements are equivalent.

F (n) = ∑_{k=0}^{n} \binom{n}{k}f(k) if and only if f(n) = ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}F (k)  (9)

Thus, we can apply Equation (9) to Equation (8). In particular, we let F (n) = p^{−n} ∑_{m=0}^{p} B(n+ m)s(p, m) while f(k) = B(k)p^{−k}. Then, Equation (9) implies for p ≥ 1

B(n)p^{−n} = ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}p^{−k} ∑_{m=0}^{p} B(k + m)s(p, m)  (10)

Rewriting Equation (10) gives us Equation (7).

4 An Independent Proof of Equation (6)

The purpose of this section is to provide a generating function proof for Equation (6) that does not depend on the validity of Spivey’s formula. With this proof in place, we have a second means of algebraically proving Spivey’s formula.

First, we look at the following exponential generating function derived from the right side of Equation (6).

∑_{n=0}^{∞} \frac{x^{n}}{n!} ∑_{k=0}^{n} \binom{n}{k}B(n − k)p^{k} = ∑_{n=0}^{∞} x^{n} \frac{p^{n}}{n!} ∑_{k=0}^{∞} \frac{x^{k}B(k)}{k!}

= e^{px}e^{e^{x}−1}  (11)

Now we look at the exponential generating function associated with the left side of Equation (6).

∑_{n=0}^{∞} \frac{x^{n}}{n!} ∑_{m=0}^{p} B(n + m)s(p, m) = ∑_{m=0}^{p} s(p, m) ∑_{n=0}^{∞} \frac{x^{n}}{n!} B(n + m)

= ∑_{m=0}^{p} s(p, m)D_{x}^{m} ∑_{n=0}^{∞} \frac{x^{n}}{n!} B(n)

= ∑_{m=0}^{p} s(p, m)D_{x}^{m}(e^{e^{x}−1})

Recall that

∑_{m=0}^{p} s(p, m)y^{m} = \binom{y}{p}p!

Hence,

∑_{m=0}^{p} s(p, m)D_{x}^{m}(e^{e^{x}−1}) = p!\binom{D_{x}}{p}(e^{e^{x}−1})
= z^{p}D_{z}^{p}(e^{z−1}), where z = e^{x}

= \frac{z^{p}}{e} e^{z} = e^{xp}e^{e^{x}−1}.  (12)

Since (11) is equal to (12), we conclude that

∑_{n=0}^{∞} \frac{x^{n}}{n!} ∑_{m=0}^{p} B(n + m)s(p, m) = ∑_{n=0}^{∞} \frac{x^{n}}{n!} ∑_{k=0}^{n} \binom{n}{k}B(n − k)p^{k}.

Comparing coefficients proves the validity of Equation (6).

5 Bell Polynomial Extension

More may be done. We extend our results to ordinary single-variable Bell polynomials ϕ_{n}(t) as defined [2] by the generating function

e^{t(e^{x}−1)} = ∑_{n=0}^{∞} ϕ_{n}(t)\frac{x^{n}}{n!} .  (13)

It is known from this that

ϕ_{n}(t) = ∑_{k=0}^{n} S(n, k)t^{k},  (14)

so that B(n) = ϕ_{n}(1). We use ϕ_{n}(t) instead of B_{n}(t) to avoid confusion with Bernoulli polynomials.

It is straightforward algebra to parallel the steps for the Bell numbers and obtain the following three identities:

ϕ_{m+n}(t) = ∑_{j=0}^{m} ∑_{k=0}^{n} S(m, j)\binom{n}{k}t^{j}ϕ_{k}(t)j^{n−k}.  (15)

∑_{m=0}^{p} ϕ_{n+m}(t)s(p, m) = t^{p} ∑_{k=0}^{n} \binom{n}{k}ϕ_{n−k}(t)p^{k}.  (16)

and

t^{p}ϕ_{n}(t) = ∑_{k=0}^{n}(−p)^{n−k}\binom{n}{k} ∑_{m=0}^{p} ϕ_{k+m}(t)s(p, m).  (17)

The middle identity (16) is the central formula of importance. As before, ordinary binomial inversion of (16) gives (17) whereas Stirling number inversion yields (15).

References

[1] L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, Holland, 1974.

[2] H. W. Gould, Bell and Catalan Number Bibliography, revised edition, Morgantown, WV, 1976. Published by the author.

[3] Charles Jordan, On Stirling’s numbers, Tohoku Math. Journal, 37 (1933), 254–278.

[4] W. E. Pennell, A generalized Fourier series representation of a function, Amer. Math. Monthly, 37 (1930), 462–472.

[5] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958.

[6] J. Riordan, Combinatorial Identities, Wiley, 1968.

[7] Michael Z. Spivey, A generalized recurrence for Bell numbers, J. Integer Sequences, 11 (2008), Article 08.2.5.

2000 Mathematics Subject Classification: Primary 11B73

2000 Mathematics Subject Classification: Primary 11B73. Keywords: Bell number, Stirling number, Bell polynomial

(Concerned with sequence \underline{A000110}.)

Received July 14 2008; revised version received September 3 2008. Published in Journal of Integer Sequences, September 7 2008. Minor revision, September 19 2008.

Return to Journal of Integer Sequences home page.