\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) &= \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!} &= e^{e^x-1}\\ \sum_{k=0}^{\infty}S(k,j)\frac{x^k}{k!} &= \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!} &= \sum_{m=0}^{\infty}D_x^m(e^{{e^x}-1})\frac{y^m}{m!} \\ &=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) &= 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!} &= e^{e^{x+y}-1} =e^{e^x-1}e^{(e^y-1)e^x}\\ & = 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} &\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*} &\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)!}\\ &\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) &=\sum_{j=0}^{\infty}S(m,j)\sum_{k=0}^{\infty}{n\choose k}B(k)j^{n-k}\\ &= \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) &= \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) &= \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\\ &= \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) \\ &= \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) &= \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) &= \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) &= \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) &=\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} &= \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 &= \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) &= \sum_{m=0}^p s(p,m)\sum_{n=0}^{\infty}\frac{x^n}{n!}B(n+m)\\ &= \sum_{m=0}^p s(p,m) D_x^m\sum_{n=0}^{\infty}\frac{x^n}{n!}B(n) \\ &= \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 &= {y\choose p}p! \end{align*} Hence, \begin{align*} \sum_{m=0}^p s(p,m) D_x^m(e^{e^x-1}) &= p!{D_x\choose p}(e^{e^x-1})\\ &= 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) &= \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)} &= \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) &= \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) &=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) &= \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}