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

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

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

\begin{center}
\vskip 1cm{\LARGE\bf Multiple Binomial Transforms \\ \vskip .1in
and Families of Integer Sequences} \vskip 1cm \large Jiaqiang
Pan\\ School of Biomedical Engineering and Instrumental Science\\
Zhejiang University\\ Hangzhou 210027\\ China\\
\href{mailto:panshw@mail.hz.zj.cn} {\tt panshw@mail.hz.zj.cn}
\\
\end{center}

\vskip .2 in

\begin{abstract}
Based on the multiple binomial transforms introduced in this
paper, the $n$-fold generating and generated sequences of a given
integer sequence can be defined and a family of this integer
sequence can be constructed. The family sets form a partition of
the set of integer sequences. Special attention is paid to the
recurrent integer sequences, which are produced by some linear and
homogeneous recurrence relations or difference equations. For the
recurrent integer sequences, a distinct rule to construct their
families is obtained based on the linear difference calculus.
\end{abstract}

\section{Introduction}
We know that if for an integer sequence $a(t),$
$t\in{\mathbb{N}}_0=\{0,1,2,\ldots\}$, a function $g(x)$,
$x\in\mathbb{R},$ has a power series form:
$g(x)=\sum_{j=0}^{\infty}a(j)\frac{x^j}{j!},$ then $g(x)$ is
called \emph{exponential generating function} of the integer
sequence $a(t)$ (see \cite{ref1}). However, the generating
function is a real function defined on real numbers $\mathbb{R}$,
not another integer sequence. If the generating function itself
still is an integer sequence, then we can continuously repeat such
operation on the new integer sequence and generate a series of
integer sequences, one after another.

In fact, we can accomplish this thinking, for we know that in
sense of the calculus on time scales, the binomial coefficients
$\{\binom{t}{j},j=0,1,2,\ldots\},$ are just the ``polynomials on
time scale ${\mathbb{N}}_0,$'',  like
$\{\frac{x^j}{j!},j=0,1,2,\ldots\}$, which are the polynomials on
time scale $\mathbb{R}$ (see \cite{ref2}). Any integer sequence
can be expanded to be a ``binomial coefficient series'' with
integer coefficients (called \emph{the discrete Taylor series},
or \emph{the inverse binomial transform} \cite{ref1,ref2}),
and on the other hand, any integer sequence also always can be
``binomial expansion'' coefficients of another integer sequence
(called \emph{the binomial transform} \cite{ref3}). In this way, we
tie one given integer sequence in with others by using successive
binomial transforms or inverse binomial transforms (we call it the
\emph{Multiple Binomial Transform}), which form a series of new
integer sequences and naturally compose a large family of the given
integer sequence.

The successive binomial transforms or inverse binomial transforms
have been used in some authors' work. For example, Spivey and
Steil \cite{ref5} used successive binomial transforms or inverse
binomial transforms to prove the invariance of the Hankel
transform of integer sequences under the falling $k$-binomial
transform when $k$ is an integer. The falling $k$-binomial
transform is a new variation of the binomial transform introduced
in \cite{ref5}.

In this paper, we give a special attention to the recurrent
integer sequences (The integer geometric sequence, the Fibonacci
sequence, and the Tribonacci sequence are some examples), and
describe a distinct rule to construct their families based on the
linear difference calculus. By the way, please note that in the
text of this paper, for any integer sequence $a(t)$, we always
regard $t\in{\mathbb{N}}_0$.


\section{Multiple binomial transforms}

\begin{definition}[Multiple binomial transform]\label{d:MultiTrans}
Let $a(t)$ be an integer sequence. Then we define the following
transform $\phi_n(a)$ to be the $n$-fold binomial transform of
$a(t)$: for $n=1,2,\ldots$,
\begin{equation}\label{e:MultiTrans1}
b(t)=\phi_n(a)=\sum_{k_n=0}^{t}\sum_{k_{n-1}=0}^{k_n}\cdots\sum_{k_2=0}^{k_3}\sum_{k_1=0}^{k_2}
a(k_1)\binom{k_2}{k_1}\binom{k_3}{k_2}\cdots\binom{k_n}{k_{n-1}}\binom{t}{k_n}.
\end{equation}
The integer sequence $b(t)$ is called the \emph{image sequence} of
$a(t)$ with respect to the $n$-fold binomial transform, denoted by
$b=\phi_n(a)$. Conversely, the integer sequence $a(t)$ is called
the \emph{inverse image sequence} of $b(t)$, and can be denoted by
$a=\phi_{-n}(b)$. For the case of $n=0$, define $\phi_0=1$ (the
identity transform).
\end{definition}

\begin{remark}\label{r:Phin}
We can see from (\ref{e:MultiTrans1}), the $\phi_1(a)$
($\phi_{-1}(a)$) is just well-known binomial (inverse binomial)
transform of $a(t)$ (see \cite{ref3}). $\phi_n(a)$ can be
considered as $n$ successive binomial transform $\phi_1$ on
$a(t)$:
$\phi_n(a)=\underbrace{\phi_1(\phi_1(\cdots(\phi_1}_{n-fold}(a)))$,
and $\phi_{-n}(a)$ can be considered as $n$ successive inverse
binomial transform $\phi_{-1}$ on $a(t)$:
$\phi_{-n}(a)=\underbrace{\phi_{-1}(\phi_{-1}(\cdots(\phi_{-1}}_{n-fold}(a)))$
\end{remark}

\begin{proposition}\label{p:Group}
If defining successive two multiple binomial transforms on an
integer sequence as a transform multiplication, then the set of
the multiple binomial transform on integer sequences,
$\Phi(a)=\{\phi_n(a), n=0,\pm 1,\pm 2,\ldots\}$ ($a$ is any
integer sequence) is an Abelian transformation group. We can call
it the binomial transformation group.
\end{proposition}

\begin{proof}
  From (\ref{e:MultiTrans1}) we can see that for any
two transforms, $\phi_n$ and $\phi_m$,
$(\phi_m\cdot\phi_n)(a)=\phi_m(\phi_n(a))=\phi_{n+m}(a),$ and
$(\phi_n\cdot\phi_m)(a)=\phi_n(\phi_m(a))=\phi_{m+n}(a),$ that is,
$\phi_n\cdot\phi_m=\phi_m\cdot\phi_n$ (the commutative law). For
three successive transforms $\phi_n$, $\phi_m$ and $\phi_p$, we
have that
$(\phi_n\cdot\phi_m)\cdot\phi_p=\phi_{m+n}\cdot\phi_p=\phi_{p+m+n},$
and
$\phi_n\cdot(\phi_m\cdot\phi_p)=\phi_n\cdot\phi_{p+m}=\phi_{p+m+n},$
that is,
$(\phi_n\cdot\phi_m)\cdot\phi_p=\phi_n\cdot(\phi_m\cdot\phi_p)$
(the associative law). Besides for any $n$, noticing $\phi_0=1,$
we have that $\phi_n\cdot\phi_0=\phi_0\cdot\phi_n=\phi_n$ and
$\phi_{-n}\phi_n=\phi_n\phi_{-n}=\phi_0.$ Hence, $(\Phi(a),\cdot)$
is an Abelian transformation group.
\end{proof}

\begin{proposition}\label{p:TaylorEx}
Let $a(t)$ be an integer sequence. Then the terms of the inverse
image sequence of $a(t)$ with respect to the binomial transform,
$a^{(-1)}(t)=\phi_{-1}(a)$, are the discrete Taylor expansion
coefficients of $a(t)$, that is,
\begin{equation}\label{e:GeneratedSe2}
a^{(-1)}(t)=\triangle^{t}a(0)=\sum_{j=0}^t(-1)^{j}\binom{t}{j}a(t-j)=
\sum_{j=0}^t(-1)^{t-j}\binom{t}{j}a(j).
\end{equation}
The inverse image sequence of $a(t)$ with respect to the $n$-fold
binomial transform, denoted by $a^{(-n)}(t)=\phi_{-n}(a)$, can be
calculated by $n$ successive $\phi_{-1}$ transforms.
\end{proposition}

\begin{proof}
  From Definition \ref{d:MultiTrans}, we have that
$a(t)=\sum_{k=0}^{t}a^{(-1)}(k)\binom{t}{k}$. On the other hand,
the discrete Taylor expansion of $a(t)$ is that
$a(t)=\sum_{k=0}^{t} \triangle^{k}a(0)\binom{t}{k}$ (see \cite{ref2}).
Hence, integer sequence $a^{(-1)}(t)-\triangle^{t}a(0)$ is the
$1$-generated sequences of the zero sequence
$\omega(t)=0,t=0,1,2,\ldots$ (\seqnum{A000004} in \cite{ref3}), that is,
$\omega(t)$ itself. Therefore, $a^{(-1)}(t)=\triangle^{t}a(0)$.
For $a^{(-n)}(t)=\phi_{-n}(a)$, from Definition \ref{d:MultiTrans}
and Remark \ref{r:Phin}, we have that
$\phi_{-n}(a)=\underbrace{\phi_{-1}(\phi_{-1}(\cdots(\phi_{-1}}_{n-fold}(a)))$.
\end{proof}

\section{Families of integer sequences}

\begin{definition}[Generating and generated sequences]\label{d:GeneSe}
Let $a(t)$ be an integer sequence. Define  the image sequence of
the $n$-fold binomial transform of $a(t)$, denoted by
$a^{(n)}(t)$, as the $n$-fold generating sequence of $a(t)$, and
the inverse image sequence of the $n$-fold binomial transform of
$a(t)$, denoted by $a^{(-n)}(t)$, as the $n$-fold generated
sequence of $a(t)$, where $n=1,2,\ldots.$ In case $n=0$,
$a^{(0)}(t)=a(t)$.
\end{definition}

   From Definition \ref{d:MultiTrans} and \ref{d:GeneSe}, and
Proposition \ref{p:TaylorEx}, we can get the following two
Corollaries.

\begin{corollary}\label{c:corres}
If integer sequence $a(t)$ is the $n$-fold generating ($n$-fold
generated) sequence of integer sequence $b(t)$, then $b(t)$ is the
$n$-fold generated ($n$-fold generating) sequence of $a(t)$.
\end{corollary}

\begin{corollary}\label{c:TaylorEx}
The terms of the $n$-fold generated integer sequence of an integer
sequence $a(t)$ can be calculated as follows,
\begin{equation}\label{e:GeneratedSe1}
a^{(-1)}(t)=\triangle^{t}a(0),
a^{(-2)}(t)=\triangle^{t}a^{(-1)}(0),\ldots,
a^{(-n)}(t)=\triangle^{t}a^{(-(n-1))}(0).
\end{equation}
\end{corollary}

\begin{remark}\label{r:zerose}
For the zero sequence $\omega(t)$, obviously, each of its
$n$-generating and $n$-generated sequences ($n=1,2,\ldots$) is
still the zero sequence itself.
\end{remark}

\begin{remark}\label{r:unitse}
For the unit pulse sequence $\delta(t)$: $\delta(0)=1$, and
$\delta(t)=0$ for $t=1,2,\ldots$ (\seqnum{A000007} in \cite{ref3}).
$\delta^{(n)}(t)=n^t$ ($n=\pm 1,\pm 2,\ldots$). Hence, we may
obtain some interesting identities, such as for $n=1,2,\ldots,$
\begin{equation}\label{e:Identity1}
\sum_{k_n=0}^{t}\sum_{k_{n-1}=0}^{k_n}\cdots\sum_{k_2=0}^{k_3}\sum_{k_1=0}^{k_2}
\delta(k_1)\binom{k_2}{k_1}\binom{k_3}{k_2}\cdots\binom{k_n}{k_{n-1}}\binom{t}{k_n}=n^t,
\nonumber
\end{equation}
and
\begin{equation}\label{e:Identity2}
\sum_{k_n=0}^{t}\sum_{k_{n-1}=0}^{k_n}\cdots\sum_{k_2=0}^{k_3}\sum_{k_1=0}^{k_2}
(-n)^{k_1}\binom{k_2}{k_1}\binom{k_3}{k_2}\cdots\binom{k_n}{k_{n-1}}\binom{t}{k_n}=\delta(t),
\nonumber
\end{equation}
Furthermore, because the identical sequence $b(t)=1$
(\seqnum{A000012} in \cite{ref3}) is the $1$-generating sequence of
$\delta(t)$, from the above identity we have that for
$n=1,2,\ldots$,
\begin{equation}\label{e:Identity3}
\sum_{k_{n+1}}^{t}\sum_{k_n=0}^{k_{n+1}}\cdots\sum_{k_2=0}^{k_3}\sum_{k_1=0}^{k_2}
(-n)^{k_1}\binom{k_2}{k_1}\binom{k_3}{k_2}\cdots\binom{k_{n+1}}{k_{n}}\binom{t}{k_{n+1}}\equiv
1, \nonumber
\end{equation}
\end{remark}

\begin{definition}[Family of integer sequences]\label{d:family}
Let $a(t)$ be an integer sequence, and $a^{(n)}(t)$, $n=\pm 1,\pm
2,\ldots$ be respectively the $n$-fold generating and $n$fold
-generated sequences of $a(t)$. Then we define the set
$\{a^{(n)}(t)$, $n=0,\pm 1,\pm 2, \ldots\}$ to be the
\emph{family} of $a(t)$, and denote it by $\mathcal{F}[a]$.
\end{definition}

\begin{proposition}\label{p:familyequiv}
Let ${\mathcal{F}}_1$ and ${\mathcal{F}}_2$ be two families of
integer sequences. Then ${\mathcal{F}}_1={\mathcal{F}}_2$ iff set
${\mathcal{F}}_1\bigcap {\mathcal{F}}_2$ is nonempty.
\end{proposition}

\begin{proof}
If ${\mathcal{F}}_1={\mathcal{F}}_2$, obviously
${\mathcal{F}}_1\bigcap {\mathcal{F}}_2$ is nonempty. Conversely,
if ${\mathcal{F}}_1\bigcap {\mathcal{F}}_2$ is a nonempty set and
integer sequence $c(t)\in {\mathcal{F}}_1\bigcap {\mathcal{F}}_2$,
then from Definition {\ref{d:family}} and Corollary
{\ref{c:corres}}, an arbitrary element of ${\mathcal{F}}_1$ is a
certain generation generating or generated sequence of $c(t)$, and
hence it is also an element of ${\mathcal{F}}_2$. Vice versa.
Hence, ${\mathcal{F}}_1={\mathcal{F}}_2$.
\end{proof}

\begin{corollary}\label{c:familyequiv}
Let $n$ be an arbitrary integer, and integer sequence $a^{(n)}$ be
the $n$-generating or $n$-generated sequence of integer sequence
$a$. If ${\mathcal{F}}_1[a]$ is family of $a$ and
${\mathcal{F}}_2[a^{(n)}]$ is family of $a^{(n)}$, then
${\mathcal{F}}_1[a]={\mathcal{F}}_2[a^{(n)}]$.
\end{corollary}

\begin{theorem}[Existence and Uniqueness]\label{t:Unique}
Every integer sequence belongs to one and only one family.
\end{theorem}

\begin{proof}
We can directly construct a family of a given sequence by using
Definitions \ref{d:GeneSe} and \ref{d:family}. This is Existence
proof. Uniqueness is a direct conclusion of Proposition
\ref{p:familyequiv}.
\end{proof}

\begin{remark}\label{r:Partition}
Theorem \ref{t:Unique} implies that the family sets form a
partition of the set of all integer sequences.
\end{remark}

\begin{remark}\label{r:zerofamily}
Most of the families of integer sequences are infinite sets.
However, the family of zero sequence $\omega(t)$ is a one element
set $\{\omega(t)\}$.
\end{remark}

We now give an interesting property of the families of integer
sequences as follows.

\begin{theorem}\label{t:Hankel}
Let $\mathcal{F}[a]$ be the family of an integer sequence $a(t)$,
and $a^{(n)}(t), n=0,\pm 1,\pm 2,\ldots,$ be all the elements of
set $\mathcal{F}[a]$. Then all of the sequences, $a^{(n)}(t)$,
have the same Hankel transform.
\end{theorem}

\begin{proof}
We know from \cite{ref4} that the Hankel transform is
invariant under the binomial transform. Hence from they
definitions, all of the sequences $a^{(n)}(t), n=0,\pm 1,\pm
2,\ldots,$ have the same Hankel transform.
\end{proof}


\section{Families of recurrent integer sequences}

An integer sequence $a(t)$ is called a recurrent integer sequence,
if it is produced by a linear and homogeneous recursion formula as
follows:
\begin{equation}\label{e:RecurSe}
a(0)=a_0, a(1)=a_1, \ldots, a(p-1)=a_{p-1},\quad \mbox{and} \quad
a(t+p)=\sum_{k=1}^{p}\xi_k a(t+p-k),\,t=0,1,2,\ldots,
\end{equation}
where, all of $a_j$ ($j=0,1,2,\ldots,p-1$) and $\xi_k$
($k=1,2,\ldots,p$) are integers, and $\xi_p\neq 0$. The positive
integer $p$ is called the recurrence order of $a(t)$. For such a
recurrent integer sequence $a(t)$, we know the following basic
results.

The recursion formula (\ref{e:RecurSe}) corresponds to a linear
and homogeneous difference equation for $a(t)$. By using a basic
relation in the difference equation theory (see \cite{ref6}):
$a(t+k)=\sum_{j=0}^{k}\binom{k}{j}\triangle^{k-j}a(t),$ $
k=1,2,\ldots,p$ in (\ref{e:RecurSe}), and then merging the
coefficients of every identical order difference of $a(t)$, we can
get that
\begin{equation}\label{e:DiffEq}
\Delta^p a(t)+\sum_{k=1}^{p}\eta_{k}\Delta^{p-k}a(t)=0,
\end{equation}
where,
\begin{equation}\label{e:EigenEq1}
\eta_k=\binom{p}{k}-\sum_{j=1}^{k}\binom{p-j}{k-j}\xi_j.
\end{equation}
Conversely, if the difference equation (\ref{e:DiffEq}) is given,
then by using another basic relation in the difference equation
theory:
$\triangle^{k}a(t)=\sum_{j=0}^{k}(-1)^j\binom{k}{j}a(t+k-j),$ $
k=1,2,\ldots,p$, in (\ref{e:DiffEq}), and merging the coefficients
of every identical backward term of $a(t)$, we can obtain the
corresponding recursion formula of $a(t)$ in the form of
(\ref{e:RecurSe}), where
\begin{equation}\label{e:EigenEq2}
\xi_k=(-1)^{k+1}\binom{p}{k}+\sum_{j=1}^{k}(-1)^{k-(j-1)}\binom{p-j}{k-j}\eta_j.
\end{equation}

In this paper, we call the characteristic values of difference
equation (\ref{e:DiffEq}), that is, the roots $\lambda_k$
($k=1,2,\ldots,p$) of characteristic equation
$\lambda^p+\sum_{k=1}^{p}\eta_k \lambda^{p-k}=0$, as {\em
$\Delta$-characteristic values} of $a(t)$, to avoid confusing with
the roots of recurrence characteristic equation
$\sigma^p-\sum_{k=1}^{p}\xi_k \sigma^{p-k}=0$. (The later is often
called by some authors as characteristic values of a recurrent
sequence.)

According to the difference equation theory, the general term of
$a(t)$ is
\begin{equation}\label{e:GeneralTerm1}
a(t)=\sum_{k=1}^{p}c_k(1+\lambda_k)^t,
\end{equation}
where coefficients $c_1,c_2,\ldots,c_p$ are determined by the
initial conditions, which lead to the following linear algebraic
equation:
\begin{equation}\label{e:GeneralTerm2}
\sum_{k=1}^p\lambda_k^{j}c_k=\triangle^{j}a(0)=
\sum_{k=0}^{j}(-1)^{j-k}\binom{j}{k}a_{k},\quad j=0,1,\ldots,p-1.
\end{equation}

For the $n$-generating ($n$-generated) sequence of a recurrent
integer sequence $a(t)$, we can prove the following theorem.

\begin{theorem}
Let $a(t)$ be a recurrent integer sequence defined in
(\ref{e:RecurSe}), and $\lambda_k$ and $c_k$ ($k=1,2,\ldots,p$) be
respectively the $\Delta$-characteristic values and general term
coefficients of $a(t)$, and $a^{(n)}(t)$ ($a^{(-n)}(t)$) be the
$n$-fold generating ($n$-fold generated) sequence of $a(t)$,
$n=1,2,\ldots$. Then for $n=\pm 1,\pm 2,\ldots,$
\begin{enumerate}
\item[(A1)] the
$\Delta$-characteristic values of $a^{(n)}(t)$ are
\begin{equation}\label{e:LambdaN}
\lambda^{(n)}_k=\lambda_k+n, \quad k=1,2,\ldots,p,
\end{equation}
\item[(A2)] the general term
of $a^{(n)}(t)$ is
\begin{equation}\label{e:GeneralTermN}
a^{(n)}(t)=\sum_{k=1}^{p}c_k(1+n+\lambda_k)^t,
\end{equation}
\item[(A3)] the $p$-th order linear and
homogeneous difference equation for $a^{(n)}(t)$ is
\begin{equation}\label{e:EigenEq3}
\triangle^p
a^{(n)}(t)+\sum_{k=1}^{p}\eta^{(n)}_k\triangle^{p-k}a^{(n)}(t)=0,
\end{equation}
with integer coefficients
\begin{equation}\label{e:EigenEq4}
\eta^{(n)}_k=(-n)^k\binom{p}{k}+\sum_{j=1}^{k}(-n)^{k-j}\binom{p-j}{k-j}\xi_j,\quad
k=1,2,\ldots,p.
\end{equation}
\item[(A4)] the recursion formula of $a^{(n)}(t)$ is
\begin{equation}\label{e:RecurSe3}
a^{(n)}(t+p)=\sum_{k=1}^{p}\xi^{(n)}_k a^{(n)}(t+p-k),
\end{equation}
with recursion coefficients
\begin{equation}\label{e:RecurSe4}
\xi^{(n)}_k=(-1)^{k-1}\binom{p}{k}-
\sum_{j=1}^{k}(-1)^{k-j}\binom{p-j}{k-j}\eta^{(n)}_j,\quad
k=1,2,\ldots,p.
\end{equation}
\end{enumerate}
\end{theorem}

\begin{proof}
Using induction we get that
$\triangle^{j}[c_k(1+\lambda_k)^t]=c_k\lambda_k^{j}(1+\lambda_k)^t,$
($k=1,2,\ldots,p$), for $j=0,1,2,\ldots$. Hence, the general term
of $a^{(-1)}(t)$ is that
$a^{(-1)}(t)=\triangle^{t}a(0)=\sum_{k=1}^{p}c_k\lambda_k^t$. This
means that $a^{(-1)}(t)$ has the $\Delta$-characteristic values of
$\lambda^{(-1)}_k=\lambda_k-1$ and the general term coefficients
are identical to the coefficients of $a(t)$, $c_k$, ($
k=1,2,\ldots,p$). From Corollary \ref{c:corres}, we see that
$a(t)$ is the $1$-generated sequence of $a^{(1)}(t)$. Hence,
$\lambda_k=\lambda^{(1)}_k-1$, or $\lambda^{(1)}_k=\lambda_k+1$,
($k=1,2,\ldots,p$), and the general term coefficients are still
$c_k$, ($ k=1,2,\ldots,p$). Using induction, we can see that for
any fold generating (generated) sequence of $a(t)$, (A1) and (A2)
hold. From (\ref{e:DiffEq}), we get that the
$\Delta$-characteristic polynomial of $a(t)$ is
$a(\lambda)=\lambda^p+\sum_{k=1}^{p}\eta_{k}\lambda^{p-k}=
\prod_{k=1}^{p}(\lambda-\lambda_k)$. Hence from (A1), for $n=\pm
1,\pm 2,\ldots,$ the $\Delta$-characteristic polynomials of
$a^{(n)}(t)$ are
$a^{(n)}(\lambda)=\prod_{k=1}^{p}[\lambda-(\lambda_k+n)]=
\prod_{k=1}^{p}[(\lambda-n)-\lambda_k]=(\lambda-
n)^p+\sum_{k=1}^{p}\eta_{k}(\lambda-n)^{p-k}$. Expanding
$(\lambda-n)^j$ ($j=1,2,\ldots,p$) and then merging the
coefficients of the same power of $\lambda$, we get
$a(\lambda)=\lambda^p+\sum_{k=1}^{p}\eta^{(n)}_{k}\lambda^{p-k}$
which leads to (\ref{e:EigenEq3}) and (\ref{e:EigenEq4}). This is
(A3). Replacing $\eta_k$ and $\xi_k$ by $\eta^{(n)}_k$ and
$\xi^{(n)}_k$ ($k=1,2,\ldots,p$) in (\ref{e:EigenEq2}), we get
(\ref{e:RecurSe4}), that is, (A4) holds.
\end{proof}


\begin{remark}
For the first order recurrent integer sequence: $a(0)=a_0$ and
$a(t+1)=\xi a(t)$, $t=0,1,2,\ldots$, the corresponding difference
equation is $\triangle a - (\xi-1)a=0$, the $\Delta$-eigenvalue of
$a(t)$ is $\lambda_1=\xi-1$, the general term is $a(t)=a_0 \xi^t$.
The $\Delta$-eigenvalues of $a^{(n)}(t)$ are
$\lambda^{(n)}_1=\xi-1+n$, and their general terms are
$a^{(n)}(t)=a_0 (\xi+n)^t$ ($n=\pm 1,\pm 2,\ldots,$). Hence, the
family of $a(t)$ is just the set of whole integer geometric
sequences with identical initial value $a_0$. Noticing that
$a^{(-\xi)}(t)=a_0\delta(t)$, we see that the case of $a_0=1,$ is
the family of the unit pulse sequence $\delta(t)$ (Remark
\ref{r:unitse}). Obviously, the case of $a_0=0,$ is the family of
the zero sequence $\omega(t)$ (Remarks \ref{r:zerose}).
\end{remark}

\begin{remark}
For the second order recurrent integer sequence, we take the
Fibonacci sequence (\seqnum{A000045} in \cite{ref3}) as an example:
$F(0)=0,$ $F(1)=1,$ and $F(t+2)=F(t+1)+F(t),$ $t=0,1,2,\ldots.$
Its difference equation is $\triangle^2 F+\triangle F -F=0,$ and
the $\Delta$-eigenvalues of $F(t)$ are
$\lambda_{1,2}=-\frac{1}{2}\pm\frac{\sqrt{5}}{2}$, and the general
term is
$F(t)=\frac{1}{\sqrt{5}}[(\frac{1}{2}+\frac{\sqrt{5}}{2})^t
-(\frac{1}{2}-\frac{\sqrt{5}}{2})^t]$. The $\Delta$-eigenvalues of
$F^{(n)}(t)$ are $\lambda^{(n)}_1=\frac{2n-1}{2}+
\frac{\sqrt{5}}{2}$, and $\lambda^{(n)}_2=\frac{2n-1}{2}-
\frac{\sqrt{5}}{2}$, ($n=\pm 1,\pm 2,\ldots$). The general term of
$F^{(n)}(t)$ is $F^{(n)}(t)=\frac{1}{\sqrt{5}}[(\frac{2n+1}{2}+
\frac{\sqrt{5}}{2})^t-(\frac{2n+1}{2}-\frac{\sqrt{5}}{2})^t]$, and
recurrence formula is $F^{(n)}(0)=0,$ $F^{(n)}(1)=1,$ and
\begin{equation}\label{e:Fibonacci}
F^{(n)}(t+2)=(2n+1)F^{(n)}(t+1)-(n^2+n-1)F^{(n)}(t),
\end{equation}
where $t=0,1,2,\ldots$. Table 1 lists some family elements of the
Fibonacci sequence.
\end{remark}

\begin{remark}
For the third order recurrent integer sequence, we take the
Tribonacci sequence (\seqnum{A000073} in \cite{ref3}) as an example:
$T(0)=0,$ $T(1)=0,$ $T(2)=1,$ and $T(t+3)=T(t+2)+T(t+1)+T(t),$
$t=0,1,2,\ldots$. Its difference equation is $\triangle^3
T+2\triangle^2 T -2T=0,$ and the corresponding
$\Delta$-eigenvalues, $\lambda_1,$ $\lambda_2,$ and $\lambda_3$,
are the roots of the $\Delta$-characteristic equation
$\lambda^3+2\lambda^2-2=0$ ($\lambda_1$ is a real root, and
$\lambda_2,$ and $\lambda_3$ are a pair of conjugate complex
roots). Its general term is
$T(t)=c_{1}(1+\lambda_1)^{t}+c_{2}(1+\lambda_2)^{t}+c_{3}(1+\lambda_3)^{t}.$
The $\Delta$-eigenvalues of $T^{(n)}(t)$ are
$\lambda^{(n)}_{k}=\lambda_{k}+n,$ $k=1,2,3$, and the
corresponding general term is
$T^{(n)}(t)=c_{1}(1+n+\lambda_1)^{t}+c_{2}(1+n+\lambda_2)^{t}+c_{3}(1+
n+\lambda_3)^{t}$ for $n=\pm 1,\pm 2,\ldots$. All of $T^{(n)}(t)$
have the same first three terms $0,0,1,$ and the same general term
coefficients $c_{1},c_{2},c_{3}$. The recurrence formula is
$T^{(n)}(0)=0,$ $T^{(n)}(1)=0,$ $T^{(n)}(2)=1$ and
\begin{equation}\label{e:Tribonacci}
T^{(n)}(t+3)=(1+3n)T^{(n)}(t+2)+(1-2n-3n^2)T^{(n)}(t+1)+(1-n+n^2+n^3)T^{(n)}(t),
\end{equation}
where $t=0,1,2,\ldots$. Table 2 lists some family elements of the
Tribonacci sequence.
\end{remark}


\begin{table}
\caption{Elements in family of the Fibonacci sequence
($F^{(n)}(t),$ $n=0,\pm 1,\pm 2, \pm 3, \pm 4$) }\label{tab:1}
\begin{tabular}{|c|l|l|c|}\hline
Sequence & Initial values & Recurrence formula & Number in
\cite{ref3}\\ \hline $F(t)$ & $0,1$ & $F(t+2)=F(t+1)+F(t)$ &
$A000045$\\ \hline $F^{(1)}(t)$ & $0,1$ &
$F^{(1)}(t+2)=3F^{(1)}(t+1)-F^{(1)}(t)$ & $A001906$\\ \hline
$F^{(2)}(t)$ & $0,1$ & $F^{(2)}(t+2)=5F^{(2)}(t+1)-5F^{(2)}(t)$ &
$A093131$\\ \hline $F^{(3)}(t)$ & $0,1$ &
$F^{(3)}(t+2)=7F^{(3)}(t+1)-11F^{(3)}(t)$ & nil\\ \hline
$F^{(4)}(t)$ & $0,1$ & $F^{(4)}(t+2)=9F^{(4)}(t+1)-19F^{(4)}(t)$ &
nil\\ \hline $F^{(-1)}(t)$ & $0,1$ &
$F^{(-1)}(t+2)=-F^{(-1)}(t+1)+F^{(-1)}(t)$ & $A039834$\\ \hline
$F^{(-2)}(t)$ & $0,1$ &
$F^{(-2)}(t+2)=-3F^{(-2)}(t+1)-F^{(-2)}(t)$ & nil\\ \hline
$F^{(-3)}(t)$ & $0,1$ &
$F^{(-3)}(t+2)=-5F^{(-3)}(t+1)-5F^{(-3)}(t)$ & nil\\ \hline
$F^{(-4)}(t)$ & $0,1$ &
$F^{(-4)}(t+2)=-7F^{(-4)}(t+1)-11F^{(-4)}(t)$ & nil\\ \hline
\end{tabular}
\end{table}

\begin{table}
\caption{Elements in family of the Tribonacci sequence
($F^{(n)}(t),$ $n=0,\pm 1,\pm 2, \pm 3, \pm 4$) }\label{tab:2}
\begin{tabular}{|c|l|l|c|}\hline
Sequence & Initial & Recurrence formula & Number\\
         & values  &                    &  in \cite{ref3}    \\
\hline $T(t)$ & $0,0,1$ & $T(t+3)=T(t+2)+T(t+1)+T(t)$ &
$A000073$\\ \hline $T^{(1)}(t)$ & $0,0,1$ &
$T^{(1)}(t+3)=4T^{(1)}(t+2)-4T^{(1)}(t+1)+2T^{(1)}(t)$ &
$A115390$\\ \hline $T^{(2)}(t)$ & $0,0,1$ &
$T^{(2)}(t+3)=7T^{(2)}(t+2)-15T^{(2)}(t+1)+11T^{(2)}(t)$ & nil\\
\hline $T^{(3)}(t)$ & $0,0,1$ &
$T^{(3)}(t+3)=10T^{(3)}(t+2)-32T^{(3)}(t+1)+34T^{(3)}(t)$ & nil\\
\hline $T^{(4)}(t)$ & $0,0,1$ &
$T^{(4)}(t+3)=13T^{(4)}(t+2)-55T^{(4)}(t+1)+77T^{(4)}(t)$ & nil\\
\hline $T^{(-1)}(t)$ & $0,0,1$ &
$T^{(-1)}(t+3)=-2T^{(-1)}(t+2)+2T^{(-1)}(t)$ & nil\\ \hline
$T^{(-2)}(t)$ & $0,0,1$ &
$T^{(-2)}(t+3)=-5T^{(-2)}(t+2)-7T^{(-2)}(t+1)-T^{(-2)}(t)$ & nil\\
\hline $T^{(-3)}(t)$ & $0,0,1$ &
$T^{(-3)}(t+3)=-8T^{(-3)}(t+2)-20T^{(-3)}(t+1)-14T^{(-3)}(t)$ &
nil\\ \hline $T^{(-4)}(t)$ & $0,0,1$ &
$T^{(-4)}(t+3)=-11T^{(-4)}(t+2)-39T^{(-4)}(t+1)-43T^{(-4)}(t)$ &
nil\\ \hline
\end{tabular}
\end{table}


\section{Acknowledgement}
The author's research was supported by the The International
Cooperation Project of Zhejiang Province, P.R. China, through
Grant No.\ 2008C24004. The author would like to thank all of the
referees for their helpful comments and suggestions.

\begin{thebibliography}{9}

\bibitem{ref1}
R.~A.~Brualdi,
\newblock {\em Introductory Combinatorics}, Fifth Edition,
Pearson Education, 2009.

\bibitem{ref2}
M.~Bohner and A.~Peterson,
\newblock {\em Dynamic Equations on Time Scales: An Introduction with Applications}.
\newblock Birkh\"{a}user, 2001.

\bibitem{ref3}
Neil J.~A. Sloane,
\newblock {\em The On-Line Encyclopedia of Integer Sequences},
\newblock published electronically at
\href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/$\sim$njas/sequences/}.

\bibitem{ref4}
John~W. Layman,
\newblock The Hankel transform and some of its properties,
\newblock {\em J. Integer Seq.}, {\bf 4} (2001), 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html}{Article 01.1.5}.

\bibitem{ref5}
M.~Z.~Spivey,
\newblock The $k$-binomial transforms and the Hankel
transform,
\newblock {\em J. Integer Seq.}, {\bf 9} (2006), 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html}{Article 06.1.1}.

\bibitem{ref6}
R.~P.~Agarwal,
\newblock Difference calculus with applications to difference equations.
\newblock In {\it General Inequalities, 4 (Oberwolfach, 1983)},
\newblock {\it Internat. Schriftenreihe Numer. Math.}, {\bf 71},
\newblock Birkh\"{a}user, 1999, pp.\ 95--110.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11B99; Secondary 11B37.

\noindent {\it Keywords}:  multiple binomial transform, generating
sequences, family of integer sequences.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A000004},
\seqnum{A000007},
\seqnum{A000012},
\seqnum{A000045},
\seqnum{A000073},
\seqnum{A001906},
\seqnum{A039834},
\seqnum{A093131}, and
\seqnum{A115390}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 24 2009;
revised version received March 8 2010; March 20 2010.
Published in {\it Journal of Integer Sequences},
March 23 2010.

\bigskip
\hrule
\bigskip

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


\end{document}