<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

%\usepackage{amsmath,amssymb,latexsym}
%\usepackage{times}
%\usepackage{graphicx}


\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Implications of Spivey's Bell Number \\
\vskip .15in
Formula
}
\vskip 1cm
\large
H. W. Gould and Jocelyn Quaintance\\
Department of Mathematics\\
West Virginia University\\
Morgantown, WV 26506 \\
USA\\
\href{mailto:gould@math.wvu.edu}{\tt gould@math.wvu.edu} \\
\href{mailto:jquainta@math.wvu.edu}{\tt jquainta@math.wvu.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
Recently, Spivey discovered a novel formula for $B(n+m)$, where
$B(n+m)$ is the $(n+m)^{\rm 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.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}


%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{remark}{Remark}[section]
%\newtheorem{lemma}{Lemma}[section]
%\newtheorem{proposition}{Proposition}[section]
%\newtheorem{guess}{Conjecture}[section]
%\newtheorem{corollary}{Corollary}[section]
%\newtheorem{proof}{Proof}[section]
%\numberwithin{equation}{section}



\section{Introduction}
Spivey \cite{ms08} gave a short combinatorial proof of the following Bell number addition formula.
\begin{align}\label{E:1}
B(n+m) &amp;= \sum_{j=0}^m\sum_{k=0}^{n}S(m,j){n\choose k}B(k)j^{n-k}.
\end{align}
Note that $B(n)$ is the $n^{\rm 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
\cite{jr58,jr68}.
The purpose of this note is to offer a short generating function proof of Equation~(\ref{E:1}).  
We discuss this proof in Section~\ref{sec2}.  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)$.


\section{Generating Function Proof of Equation~(\ref{E:1})}
\label{sec2}

First recall that 
\begin{align}
\sum_{k=0}^{\infty}B(k)\frac{x^k}{k!} &amp;= e^{e^x-1}\\
\sum_{k=0}^{\infty}S(k,j)\frac{x^k}{k!} &amp;= \frac{(e^x-1)^j}{j!}.
\end{align}
These standard expansions are found in references \cite{lc74,cj33,jr58,jr68}.
See also the definitive bibliography
\cite{hwg76} listing hundreds of references about
Bell and Stirling numbers.

Next, we form the double variable exponential
generating function $\sum_{\scriptstyle{m,n=0}}^{\infty}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
\begin{align*}  
\sum_{\scriptstyle{m,n=0}}^{\infty}B(n+m)\frac{x^n}{n!}\frac{y^m}{m!} &amp;= \sum_{m=0}^{\infty}D_x^m(e^{{e^x}-1})\frac{y^m}{m!} \\
&amp;=e^{yD_x}e^{{e^x}-1} = e^{e^{y+x}-1}.
\end{align*}
The last equality follows from the following version of Taylor's Theorem, namely
\begin{align}
e^{yD_x}f(x) &amp;= f(x+y).
\end{align}
This old form of the Taylor series follows by using the symbolic expansion
\begin{align*} e^{aL}f(x) = \sum_{k=0}^{\infty}\frac{a^{ k}L^{k}f(x)}{k!}
\end{align*}
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 \cite{wep30}.
However,
\begin{align*}
\sum_{\scriptstyle{m,n=0}}^{\infty}B(n+m)\frac{x^n}{n!}\frac{y^m}{m!} &amp;= e^{e^{x+y}-1} =e^{e^x-1}e^{(e^y-1)e^x}\\
&amp; = e^{e^x-1}\sum_{j=0}^{\infty}\frac{(e^y-1)^j}{j!}e^{jx}= e^{e^x-1}\sum_{\scriptstyle{m,j=0}}S(m,j)\frac{y^m}{m!}e^{jx} 
\end{align*}
\begin{align}\label{E:2}
&amp;\hspace{2.0cm}=\sum_{\scriptstyle{m,j=0}}S(m,j)\frac{y^m}{m!}\sum_{n=0}^{\infty}\frac{x^n}{n!}j^n\sum_{k=0}^{\infty}\frac{x^k}{k!}B(k)
\end{align}
\begin{align*}
&amp;\hspace{2.5cm}=\sum_{\scriptstyle{m,j=0}}S(m,j)\frac{y^m}{m!}\sum_{n=0}^{\infty}x^n\sum_{k=0}^{\infty}\frac{B(k)}{k!}\frac{j^{n-k}}{(n-k)!}\\
&amp;\hspace{2.5cm}=\sum_{\scriptstyle{m,n=0}}^{\infty}\frac{x^n}{n!}\frac{y^m}{m!}
\sum_{j=0}^{\infty}S(m,j)\sum_{k=0}^{\infty}{n\choose k}B(k)j^{n-k}
\end{align*}
The equality in Equation~(\ref{E:2}) 
comes from the Cauchy convolution formula.
By comparing the coefficients of $\frac{x^n}{n!}\frac{y^m}{m!}$, we note note that
\begin{align*}
B(n+m) &amp;=\sum_{j=0}^{\infty}S(m,j)\sum_{k=0}^{\infty}{n\choose k}B(k)j^{n-k}\\
&amp;= \sum_{j=0}^m\sum_{k=0}^{n}S(m,j){n\choose k}B(k)j^{n-k},
\end{align*}
which is identically Equation~(\ref{E:1}).

\section{New Bell Number Formula}
The purpose of this section is to use Equation~(\ref{E:1}) as a means of obtaining a new formula for $B(n)$.  In order to do this, we need the following
lemma.
\begin{lemma} Let $n\geq 0$ and $p\geq 1$.  Let $s(p,m)$ be the Stirling number of the first kind.  
\begin{align}\label{E:3}
\sum_{m=0}^{p}B(n+m)s(p,m) &amp;= \sum_{k=0}^n {n\choose k}B(n-k)p^k.
\end{align}
Using the standard notational convention that $0^{0}=1$, then (\ref{E:3}) is true for $n\geq 0$ and $p\geq 0$.
\end{lemma}
 
\begin{proof}Since Equation~(\ref{E:1}) is true, we can easily show that
\begin{align*}
\sum_{m=0}^{p}B(n+m)s(p,m) &amp;= \sum_{k=0}^n{n\choose k}B(n-k)\sum_{m=0}^p\sum_{j=0}^mS(m,j)s(p,m)j^k\\
&amp;= \sum_{k=0}^n{n\choose k}B(n-k)\sum_{j=0}^p j^k\sum_{m=j}^p s(p,m)S(m,j) \\
&amp;= \sum_{k=0}^n{n\choose k}B(n-k)p^k.
\end{align*}
The last equality follows by the orthogonal relationship between the two types of Stirling numbers, namely,
\begin{align*}
\sum_{m=j}^p s(p,m)S(m,j) &amp;= \delta_{j}^p,
\end{align*}
where the ``Kronecker delta" is defined by $\delta_{j}^p = 1$ if $j = p$, and $\delta_{j}^p = 0$ for $j\neq p$. 
\end{proof}

We now use Equation~(\ref{E:3}) to find a formula for $B(n)$ that does not seem to appear in the literature.
\begin{theorem} Let $n\geq 0$ and $p\geq 1$.
\begin{align}\label{E:4}
B(n) &amp;= \sum_{k=0}^n(-p)^{n-k}{n\choose k}\sum_{m=0}^pB(k+m)s(p,m).
\end{align}
Using the standard notational convention that $0^{0}=1$, then (\ref{E:4}) is true for $n\geq 0$ and $p\geq 0$.
\end{theorem}
\begin{proof}Let $k\rightarrow n-k$ in Equation~(\ref{E:3}). Then,
\begin{align}\label{E:5}
p^{-n}\sum_{m=0}^{p}B(n+m)s(p,m) &amp;= \sum_{k=0}^n{n\choose k}B(k	`)p^{-k}.
\end{align}
We now recall that given two functions $F(n)$ and $f(n)$, the following two statements are equivalent.
\begin{align}\label{E:6}
F(n) = \sum_{k=0}^n{n\choose k} f(k)\,\, \text{if and only if}\,\, f(n)
&amp;=\sum_{k=0}^n(-1)^{n-k}{n\choose k}F(k)
\end{align}
Thus, we can apply Equation~(\ref{E:6}) to Equation~(\ref{E:5}).  
In particular,  
we let $F(n) = p^{-n}\sum_{m=0}^{p}B(n+m)s(p,m)$ while  $f(k) = B(k)p^{-k}$.
Then, Equation~(\ref{E:6}) implies for $p\geq 1$
\begin{align}\label{E:7}
B(n)p^{-n} &amp;= \sum_{k=0}^n(-1)^{n-k}{n\choose k}p^{-k}\sum_{m=0}^pB(k+m)s(p,m)
\end{align}
Rewriting Equation~(\ref{E:7}) gives us Equation~(\ref{E:4}). 
\end{proof}

\section{An Independent Proof of Equation~(\ref{E:3})}
The purpose of this section is to provide a generating function proof for Equation~(\ref{E:3}) 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~(\ref{E:3}).
\begin{align*}
\sum_{n=0}^{\infty}\frac{x^n}{n!}\sum_{k=0}^n{n\choose k}B(n-k)p^k  &amp;=
\sum_{n=0}^{\infty}x^n\frac{p^n}{n!}\sum_{k=0}^{\infty}\frac{x^kB(k)}{k!}
\end{align*}
\begin{align}\label{E:e1}
\hspace{3.0cm}= e^{px}e^{e^x-1}
\end{align}
Now we look at the exponential generating function associated with the left side of Equation~(\ref{E:3}).
\begin{align*}
\sum_{n=0}^{\infty}\frac{x^n}{n!}\sum_{m=0}^pB(n+m)s(p,m) &amp;= \sum_{m=0}^p s(p,m)\sum_{n=0}^{\infty}\frac{x^n}{n!}B(n+m)\\
&amp;= \sum_{m=0}^p s(p,m) D_x^m\sum_{n=0}^{\infty}\frac{x^n}{n!}B(n) \\
&amp;= \sum_{m=0}^p s(p,m) D_x^m(e^{e^x-1})
\end{align*}
Recall that 
\begin{align*}
\sum_{m=0}^p s(p,m)y^m &amp;= {y\choose p}p!
\end{align*}
Hence,
\begin{align*} 
\sum_{m=0}^p s(p,m) D_x^m(e^{e^x-1}) &amp;= p!{D_x\choose p}(e^{e^x-1})\\
&amp;= z^pD_z^p(e^{z-1}),\,\,\text{where}\,\, z = e^x
\end{align*}
\begin{align}\label{E:e2}
\hspace{2.3cm}= \frac{z^p}{e}e^z = e^{xp}e^{e^x-1}.
\end{align}
Since (\ref{E:e1}) is equal to (\ref{E:e2}), we conclude that
\begin{align*}
\sum_{n=0}^{\infty}\frac{x^n}{n!}\sum_{m=0}^pB(n+m)s(p,m) &amp;= \sum_{n=0}^{\infty}\frac{x^n}{n!}\sum_{k=0}^n{n\choose k}B(n-k)p^k.
\end{align*}
Comparing coefficients proves the validity of Equation~(\ref{E:3}).\\

\section{Bell Polynomial Extension}
More may be done. We extend our results to ordinary single-variable Bell polynomials $\phi_n(t)$ as defined \cite{hwg76} by the generating function
\begin{align}
e^{t(e^x-1)} &amp;= \sum_{n=0}^{\infty}\phi_n(t)\frac{x^n}{n!}.
\end{align}
It is known from this that
\begin{align}  \phi_n(t) = \sum_{k=0}^{n}S(n,k){t^k},
\end{align}
 so that $B(n) =  \phi_n(1).$ We use $\phi_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:

\begin{align}\label{E:15}
\phi_{m+n}(t) &amp;= \sum_{j=0}^m\sum_{k=0}^{n}S(m,j){n\choose k}t^{j}\phi_k(t)j^{n-k}.
\end{align}

\begin{align}\label{E:16}
\sum_{m=0}^{p}\phi_{n+m}(t)s(p,m) &amp;=t^p \sum_{k=0}^n {n\choose k}\phi_{n-k}(t)p^k.
\end{align}
 and
\begin{align}\label{E:17}
t^p\phi_{n}(t) &amp;= \sum_{k=0}^n(-p)^{n-k}{n\choose k}\sum_{m=0}^p\phi_{k+m}(t)s(p,m).
\end{align}\\

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


\begin{thebibliography}{9}

\bibitem{lc74} L. Comtet, {\it Advanced Combinatorics}, D. Reidel,
Dordrecht, Holland, 1974.

\bibitem{hwg76} H. W. Gould, {\it Bell and Catalan Number
Bibliography}, revised edition, Morgantown, WV, 1976. Published by the
author.

\bibitem{cj33} Charles Jordan, On Stirling's numbers, {\it Tohoku Math.
Journal}, {\bf 37} (1933), 254--278.

\bibitem {wep30} W. E. Pennell, A generalized Fourier series
representation of a function, {\it Amer. Math. Monthly}, {\bf 37}
(1930), 462--472.

\bibitem {jr58} J. Riordan, {\it An Introduction to Combinatorial
Analysis}, Wiley, 1958.

\bibitem {jr68} J. Riordan, {\it Combinatorial Identities}, Wiley, 
1968.

\bibitem{ms08} Michael Z. Spivey, \href{http://www.emis.de/journals/JIS/VOL11/Spivey/spivey25.html}{A generalized recurrence for Bell numbers},
{\it J. Integer Sequences}, {\bf 11} (2008), Article 08.2.5.

\end{thebibliography}


2000 Mathematics Subject Classification: Primary 11B73


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 
Primary 11B73.

\noindent \emph{Keywords: } Bell number, Stirling number, Bell polynomial

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000110}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 14 2008;
revised version received  September 3 2008.
Published in {\it Journal of Integer Sequences}, September 7 2008.
Minor revision, September 19 2008.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                
</pre></body></html>