\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}

\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 On a Generalized Recurrence for Bell \\
\vskip .12in
Numbers
}
\vskip 1cm
\large
Jacob Katriel\\
Department of Chemistry\\
Technion - Israel Institute of Technology \\
Haifa 32000 \\
Israel \\
\href{mailto:jkatriel@technion.ac.il}{\tt jkatriel@technion.ac.il} \\
\end{center}

\vskip .2 in

\begin{abstract}
A novel recurrence relation for the Bell numbers was recently derived
by Spivey, using a beautiful combinatorial argument. An algebraic
derivation is proposed that allows straightforward $q$-deformation.
\end{abstract}


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


\section{Introduction}

Spivey \cite{Spivey} recently proposed a generalized recurrence relation
for the Bell numbers,
\begin{equation}
\label{eq:Spivey}
B_{n+m}=\sum_{k=0}^n\sum_{j=0}^m j^{n-k}
                   \left\{{m\atop j}\right\}\left({n\atop k}\right) B_k.
\end{equation}
Here, $B_n$ is the Bell number, $\left\{ {m\atop j}\right\}$ is the 
Stirling number of the second kind,
and $\left( {n\atop k}\right)$ is a binomial coefficient.
Recall that the Stirling numbers of the second kind can be defined via
$$x^k=\sum_{\ell=0}^k \left\{ {k\atop\ell} \right\}x(x-1)(x-2)\cdots (x-\ell+1)$$
and the Bell numbers are given by
$$B_k=\sum_{\ell=0}^k \left\{ {k\atop\ell} \right\}.$$
Spivey's derivation invokes a beautiful combinatorial argument.

An algebraic derivation of Spivey's identity is presented below, using 
the formalism due to Rota et al.\ \cite{Rota} that was specifically 
developed for the present context by Cigler \cite{Cigler}. 
The relevance to the normal ordering problem of boson operators has been
considered in Katriel \cite{Katriel74,Katriel}. 
The basic ingredients of the Rota-Cigler formalism are also known as the 
Bargmann representation of the boson operator algebra \cite{Bargmann}.
The main advantage of the algebraic derivation is that it readily yields 
the more general $q$-deformed identity.

\section{Algebraic derivation of Spivey's identity}

We shall use the operator $X$ of mutiplication by the variable $x$, 
and the $q$-derivative $D$
\begin{eqnarray*}
X f(x) &=& x f(x) \\
D f(x) &=& \frac{f(qx)-f(x)}{x(q-1)},
\end{eqnarray*}
that satisfy
\begin{equation}
\label{eq:qmutator}
D X -q X D =1 .
\end{equation}
From the definition of the $q$-derivative it follows that
\begin{equation}
\label{eq:xton}
D x^n = [n]_q x^{n-1},
\end{equation}
where $[n]_q=\frac{q^n-1}{q-1}$, and from Eq.\ (\ref{eq:qmutator}) it follows 
that
\begin{equation}
\label{eq:Xton}
D X^n = q^n X^n D +[n]_q X^{n-1}.
\end{equation}
Eq.\ (\ref{eq:Xton}) can also be written in the form
\begin{equation}
\label{eq:lemma}
(X D) X^n = X^n\Big( [n]_q + q^n(X D)\Big), 
\end{equation}
that will be useful below. 
The $q$-exponential function
$e_q(x)=\sum_{k=0}^{\infty} \frac{x^k}{[n]_q!}$, where $[0]_q!=1$ 
and $[n+1]_q!=[n]_q! [n+1]_q$, satisfies 
\begin{equation}
\label{eq:exp}
D e_q(x)=e_q(x).
\end{equation}

Repeated application of the $q$-commutation relation (\ref{eq:qmutator})
yields
\begin{equation}
\label{eq:normal}
(X D)^n = \sum_{k=0}^n \left\{ {n \atop k} \right\}_q X^k D^k
\end{equation}
where $\left\{ {0 \atop 0} \right\}_q = 1$ and
$$\left\{ {n+1 \atop k} \right\}_q =
  q^{k-1} \left\{ {n \atop k-1} \right\}_q
               + [k]_q \left\{ {n \atop k} \right\}_q . $$
The initial value and the recurrence relation are sufficient to identify
the coefficients $\left\{ {n \atop k} \right\}_q$ as the $q$-Stirling numbers,
hence the sum $B_n(q)=\sum_{k=0}^n \left\{ {n \atop k} \right\}_q $ is the $q$-Bell
number. 

Applying both sides of the identity (\ref{eq:normal}) to the $q$-exponential function
we obtain
\begin{equation}
\label{eq:qBell}
\frac{1}{e_q(x)}(X D)^n e_q(x) =\sum_{k=0}^n \left\{ {n \atop k} \right\}_q x^k
\equiv B_n(q;x).
\end{equation}
For $x=1$ the $q$-Bell polynomial $B_n(q;x)$ reduces to the $q$-Bell number
$B_n= \sum_{k=0}^n \left\{ {n \atop k} \right\}_q ,$
and for $x=-1$ it reduces to the $q$-R\'enyi number \cite{Fekete}
$R_n(q)= \sum_{k=0}^n (-1)^k\left\{ {n \atop k} \right\}_q .$  
Since $(X D) x^m = [m]_q x^m$ it follows that
$(X D)^n x^m = [m]_q^n x^m$ and 
$(X D)^n e_q(x)= \sum_{k=0}^{\infty} \frac{[k]_q^n}{[k]_q!} x^k ,$
yielding the Dobinski formula for the $q$-Bell polynomial. 

Using Eq.\ (\ref{eq:normal}), then Eq.\ (\ref{eq:lemma}), and finally the binomial 
theorem we obtain
\begin{eqnarray*}
(X D)^{n+m} &=& (X D)^n\sum_{j=0}^m \left\{ {m \atop j} \right\}_q X^j D^j \\
   &=& \sum_{j=0}^m \left\{ {m \atop j} \right\}_q X^j\Big([j]_q+q^j(X D)\Big)^n D^j \\
   &=& \sum_{j=0}^m\sum_{k=0}^n \left\{ {m \atop j} \right\}_q
                 \left( {n \atop k}\right) [j]_q^{n-k} q^{jk} X^j (X D)^k D^j
\end{eqnarray*}
Applying this operator identity to the $q$-exponential function, using 
Eqs.\ (\ref{eq:exp}) and (\ref{eq:qBell}), dividing by $e_q(x)$ and setting 
$x=1$ we obtain
$$B_{n+m}(q)=\sum_{j=0}^m\sum_{k=0}^n \left\{ {m \atop j} \right\}_q
                 \left( {n \atop k} \right) [j]_q^{n-k} q^{jk} B_k(q).$$
Note that the binomial coefficient is not deformed.
For $q=1$ this identity reduces to Eq.\ (\ref{eq:Spivey}).

\section{Acknowledgement} 
I wish to thank the referee for very helpful suggestions.


\begin{thebibliography}{99}

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

\bibitem{Rota}
G.-C. Rota, D. Kahaner and A. Odlyzko,
On the foundations of combinatorial theory. 
VIII. Finite operator calculus,
{\it{J. Math. Anal. Appl.}} {\bf{42}} (1973) 684--760.

\bibitem{Cigler}
J. Cigler, Operatormethoden f\"ur $q$-Identit\"aten,
{\it{Monatsh. Math.}} {\bf{88}} (1979) 87--105.

\bibitem{Katriel74}
J. Katriel, Combinatorial aspects of Boson algebra, 
{\it{Lett. Nuovo Cimento}} {\bf{10}} (1974) 565--567.

\bibitem{Katriel}
J. Katriel, Bell numbers and coherent states, 
{\it{Phys. Lett. A}} {\bf{273}} (2000) 159--161.

\bibitem{Bargmann}
V. Bargmann, On a Hilbert space of analytic functions and an associated 
integral transform, {\it{Commun. Pure Appl. Math.}} {\bf{14}} (1961) 187--214.

\bibitem{Fekete}
A. E. Fekete, Apropos Bell and Stirling numbers,
{\it{Crux Mathematicorum with Math. Mayhem}} {\bf{25}} (1999) 274--281.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B73;  Secondary 05A19, 05A30, 05A40 .

\noindent \emph{Keywords: } $q$-Bell numbers, $q$-Stirling numbers, umbral calculus.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000110} and
\seqnum{A008277}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 12 2008;
revised version received September 8 2008.  
Published in {\it Journal of Integer Sequences}, September 10 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}