\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://oeis.org/#1}{\underline{#1}}}


\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
Generalized Catalan Numbers and\\
\vskip .15in
Generalized Hankel Transformations}

\vskip 1cm
\large
Marc Chamberland and Christopher French\\
Department of Mathematics and Statistics\\
Grinnell College\\
Grinnell, IA 50112 \\
USA\\
\href{mailto:chamberl@math.grinnell.edu}{\tt chamberl@math.grinnell.edu}\\
\href{mailto:frenchc@math.grinnell.edu}{\tt frenchc@math.grinnell.edu}\\
\end{center}

\vskip .2in

\begin{abstract}

Cvetkovi\'c, Rajkovi\'c and Ivkovi\'c proved
that the Hankel transformation of the sequence of sums of adjacent Catalan
numbers is a sequence of every other Fibonacci number.  In this paper, an
elementary proof is given and a generalization to 
sequences of generalized Catalan numbers.
\end{abstract}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 
\newtheorem{definition}{Definition}[section]

\section{Introduction}

Given a sequence of numbers $S=\{s_0,s_1,s_2,\ldots\}$, the Hankel
matrix of order $n$ generated by the sequence $S$ is the
$n\times n$-matrix whose $(i,j)$-entry is given by $s_{i+j}$ for
$0\leq i,j\leq n-1$.  The Hankel transform of the sequence $S$ is
the sequence of determinants of the Hankel matrices generated by $S$.

Suppose that \[a_n=\frac{1}{n+1}{2n\choose n}+\frac{1}{n+2}{2n+2\choose
n+1},\] so that $a_n$ is the sum of the $n^{\rm th}$ and $n+1^{\rm st}$ Catalan 
numbers.  Then the Hankel transform of $\{a_0,a_1,a_2,\ldots\}$ begins
$2,5,13,34,\ldots$.  Layman first conjectured in the On-Line Encyclopedia 
of Integer Sequences (\cite{OL}, see sequence A001906) that this sequence
consists of every other Fibonacci number, and subsequently
Cvetkovi\'c, Rajkovi\'c and Ivkovi\'c \cite{CRI}
proved this conjecture.  The current paper arose out of an attempt
to understand and generalize this result.

The Catalan numbers
$c_n=\frac{1}{n+1}{2n\choose n}$ uniquely satisfy the
nonlinear recurrence relation
\[c_{n+1}=\sum_{r=0}^{n}c_{n-r}c_r,{\hskip 10pt}c_0=1.\]
This sequence has been generalized to the 
recurrence relation
\[c_{n+1,k}=\sum_{r=0}^{\lfloor \frac{n}{k-1}\rfloor}
(c_{n-r(k-1),k})*(c_{r(k-1),k}),{\hskip 10pt}c_{0,k}=1.\]
When $k=2$, $c_{n,k}$ is simply the $n^{th}$ Catalan number.
It can be shown (\cite{HP}) that
\[c_{(k-1)n+l-1,k}=\frac{l}{kn+l}{kn+l\choose n},{\hskip 10pt}1\leq l\leq
k-1.\]

Some notation is necessary to state our more general result.
Let $a'_{n,k}=c_{n,k}+c_{n+1,k}$ and $a''_{n,k}=c_{n,k}+c_{n+k-1,k}$.
Note that $a'_{n,2}$ and $a''_{n,2}$ both coincide with the sequence
$a_n$ described above.  Let $A'_{n,k}$ and $A''_{n,k}$ be
the $n\times n$-matrices whose $(i,j)$-entries are given respectively by
$a'_{(k-1)i+j,k}$ and $a''_{(k-1)i+j,k}$ for $0\leq i,j\leq n-1$.
Let $F'_{n,k}$ be the sequence determined by the recurrence
relation \[F'_{n+1,k}=F'_{n-(k-2),k}+F'_{n-(k-1),k}\] with initial
conditions
\[F'_{1,k}=F'_{2,k}=\cdots=F'_{k,k}=1,\] and let $F''_{n,k}$ be the
sequence determined by
\[F''_{n+1,k}=F''_{n,k}+F''_{n-(k-1),k}\]
with the same initial conditions.
Note that $F'_{n,2}=F''_{n,2}=F_n$ (the $n^{th}$ Fibonacci number).

We can now state our main theorem:

\begin{theorem}\label{thm:general}
\[\det(A'_{n,k})=F'_{kn+1,k},\text{ and }
\det(A''_{n,k})=F''_{kn+1,k}.\]
\end{theorem}

Note that when $k=2$, our theorem reduces to the result of Cvetkovi\'c, Rajkovi\'c
and Ivkovi\'c \cite{CRI}.

In Section \ref{sec:gen}, we find $LU$ decompositions
of the inverses of a sequence of matrices $C_{n,k}$
obtained from the generalized Catalan numbers.  It turns out that these
take surprisingly simple forms, and can be used to prove our main result,
as seen in Section \ref{sec:main}.

\section{Generalized Catalan numbers}\label{sec:gen}

\begin{definition}
Let $C_{n,k}$ be the $n\times n$ matrix whose $(i,j)$ entry is
given by $c_{(k-1)i+j,k}$ for $0\leq i,j\leq n-1$.
Let $L_{n,k}$ be the $n\times n$ matrix whose $(i,j)$ entry
is given by $(-1)^{i-j}{i+(k-1)j\choose i-j}$ for $0\leq i,j\leq n-1$.
Let
$U_{n,k}$ be the $n\times n$ matrix whose $(i,j)$ entry is given by
 $(-1)^{j-i}{j+\lfloor \frac{i}{k-1}\rfloor \choose j-i}$ for $0\leq
i,j\leq n-1$.
\end{definition}

It is easy to see that $L_{n,k}$ is lower triangular with 1's on the
diagonal
and $U_{n,k}$ is upper triangular with 1's on the diagonal.  Our goal
in this section is to prove that the product $L_{n,k}C_{n,k}U_{n,k}$
is equal to the identity matrix.

Our first step is to show that the product $L_{n,k}C_{n,k}$ is upper
triangular
with 1's on the diagonal.  We will then show that $C_{n,k}U_{n,k}$ is
lower triangular
with 1's on the diagonal.  From these two facts, the result will follow
formally.

The proof makes use of certain generating functions.

\begin{definition} For $1\leq l\leq k-1$, let
$g_l(z)=\sum_{n=0}^\infty c_{(k-1)n+l-1}z^n$, and let $g(z)=g_1(z)$.
\end{definition}

It follows from the recurrence relation defining $c_{n,k}$
that $g_l(z)g(z)=g_{l+1}(z)$ for $1\leq l\leq k-2$, and also that
$g_{k-1}(z)g(z)=\frac{g(z)-1}{z}$.  Thus,

\begin{equation}\label{eq:gl} g(z)^l=g_l(z),{\hskip 5pt} 1\leq l\leq k-1
\end{equation}
and
\begin{equation}\label{eq:gk} g(z)^k=\frac{g(z)-1}{z}. \end{equation}

Bajunaid, Cohen, Colonna, and Signman
\cite{BCCS} prove that the function
\begin{equation}\label{f1} f(z):=(1-z)g(z(1-z)^{k-1}) \end{equation}
converges to the constant
function at 1 for $z$ close to 0. This is then used to show that
\[\sum_{n=\lceil m/k\rceil}^m(-1)^nc_{(k-1)n,k} {kn-n\choose
kn-m}=(-1)^m.\] (Note that the cited reference refers to $c_{(k-1)n,k}$
as $a_{n,k}$.)
We use exactly the same technique to prove the following
slightly stronger result.



\begin{lemma}\label{lem:identity} Suppose $i$ and $j$ are nonnegative
integers.
Then \[\sum_{m=0}^{i}(-1)^{i-m}{i+(k-1)m\choose
i-m}c_{(k-1)m+j,k} = \begin{cases} 0, & j< i; \\ 1, &
j=i.\end{cases}\]
\end{lemma}

\begin{proof}
It follows from Equation \ref{eq:gl} that, \begin{equation}\label{fl}
f_l(z):=(1-z)^lg_l(z(1-z)^{k-1}) \end{equation} is equal to
$f(z)^l$, and therefore (by \ref{f1}) converges to 1 for $z$
close to $0$.  From this, we find that for any $s\geq 0$,
the series \[\sum_{m=0}^\infty
c_{(k-1)m+(l-1),k}[z(1-z)^{k-1}]^m(1-z)^{s}=(1-z)^{s-l}f_l(z)\]
converges to $(1-z)^{s-l}$ for $z$ close to 0.
Expanding $(1-z)^{m(k-1)+s}$, we can rewrite this sum
as \[\sum_{m=0}^\infty c_{(k-1)m+(l-1),k}
\left(\sum_{t=0}^{mk-m+s}(-1)^t{(k-1)m+s\choose t}z^{t+m}\right)\]
\[=\sum_{n=0}^\infty \left(\sum_{m=\lceil \frac{n-s}{k}\rceil}^n(-1)^{n-m}
{(k-1)m+s\choose n-m}c_{(k-1)m+(l-1),k}\right)z^n.\]
Therefore, if $n>s-l$ \[\sum_{m=\lceil
\frac{n-s}{k}\rceil}^n(-1)^{n-m} {(k-1)m+s\choose n-m}c_{(k-1)m+(l-1),k}
=\begin{cases} 0, & s>l-1; \\ 1, & s=l-1.\end{cases}\]

Now, by the division algorithm, we may write $j$
as $(k-1)r+(l-1)$, for some nonnegative integer $r$ and some $l$ with
$1\leq l\leq k-1$.
Letting $s=i-(k-1)r$ and $n=i+r$,
gives \[\sum_{m=r}^{i+r}(-1)^{i-(m-r)}{(k-1)(m-r)+i\choose
n-m}c_{(k-1)(m-r)+j,k}
=\begin{cases} 0, & j<i; \\ 1, & j=i.\end{cases}\]
The result now follows by an index shift. \end{proof}

\begin{corollary}\label{cor:UT} The product $L_{n,k}C_{n,k}$ is upper
triangular with
1's on the diagonal.
\end{corollary}

\begin{proof} The $(i,j)$ entry of
$L_{n,k}C_{n,k}$ is \[\sum_{m=0}^{n-1}(-1)^{i-m}{i+(k-1)m\choose
i-m}c_{(k-1)m+j,k}.\]
\end{proof}

We now turn to consider the product $C_{n,k}U_{n,k}$.

\begin{lemma}
\[\sum_{m=0}^j c_{(k-1)i+m,k}(-1)^{j-m} {j+\lfloor
\frac{m}{k-1}\rfloor\choose j-m} =\begin{cases} 0, & i<j; \\ 1, &
i=j.\end{cases}\]
\end{lemma}

\begin{proof} By Equation \ref{eq:gk} \[\sum_{l=0}^{k-1}
\left(zg(z^{k-1}(1-z))\right)^l
=\frac{(z g(z^{k-1}(1-z)))^k-1}{z g(z^{k-1}(1-z))-1}
=\frac{z^k\frac{g(z^{k-1}(1-z))-1}{z^{k-1}(1-z)}-1} {z
g(z^{k-1}(1-z))-1} =\frac{1}{1-z}\] for $z$ close to $0$.
It follows by Equation \ref{eq:gl} that
\[\sum_{l=0}^{k-1} z^lg_l(z^{k-1}(1-z))=\frac{1}{1-z},\] so subtracting 1,
dividing by $z$, and multiplying by $(1-z)^s$ gives
\[\sum_{l=1}^{k-1} (1-z)^s z^{l-1}g_l(z^{k-1}(1-z))=(1-z)^{s-1}.\]
 Now,
\[(1-z)^s z^{l-1}g_l(z^{k-1}(1-z))= \sum_{p=0}^\infty
c_{(k-1)p+l-1,k}(1-z)^{p+s} z^{p(k-1)+l-1}\] \[=\sum_{p=0}^\infty
c_{(k-1)p+l-1,k}\sum_{t=0}^{p+s} (-1)^t{p+s\choose t}z^{p(k-1)+l-1+t}\]
\[=\sum_{n=0}^\infty\left( \sum_{p} (-1)^{n-p(k-1)-(l-1)} {p+s\choose
n-p(k-1)-(l-1)}c_{(k-1)p+l-1,k}\right)z^n.\] Therefore, \[\sum_{l=1}^{k-1}
(1-z)^s z^{l-1}g_l(z^{k-1}(1-z))=\sum_{n=0}^\infty
\left(\sum_{m} (-1)^{n-m} {s+\lfloor
\frac{m}{k-1}\rfloor\choose n-m} c_{m,k}\right)z^n.\] Here, we
have used the division algorithm to substitute $m=p(k-1)+l-1$, where
$1\leq l\leq k-1$.
So,
\[\sum_{m} (-1)^{n-m} {s+\lfloor
\frac{m}{k-1}\rfloor\choose n-m} c_{m,k}= \begin{cases} 0, &
n\geq s>0; \\ 1, & s=0.\end{cases}\] Letting $s=j-i$, $n=j+(k-1)i$ and
shifting index
yields the result.
\end{proof}

\begin{corollary}\label{cor:LT}
The product $C_{n,k}U_{n,k}$ is lower triangular with 1's on the diagonal.
\end{corollary}

\begin{theorem} The product $L_{n,k}C_{n,k}U_{n,k}$ is equal to the
identity matrix.
\end{theorem}

\begin{proof}
By Corollaries \ref{cor:UT} and \ref{cor:LT}, the products
$L_{n,k}^{-1}(L_{n,k}C_{n,k})$ and
$(C_{n,k}U_{n,k})U_{n,k}^{-1}$ are both LU decompositions of $C_{n,k}$.
By uniqueness of LU
decompositions, $L_{n,k}^{-1}=C_{n,k}U_{n,k}$.
\end{proof}

\section{Proof of the Main Theorem}\label{sec:main}

In this section, we prove our main result, which will follow from
two additional lemmas.

\begin{lemma}\label{lem:minor}
The determinant of the $(n-1)\times (n-1)$
minor of $C_{n,k}$ obtained by removing the final column and the $j$th row
is
${n-1+(k-1)j\choose n-1-j}$.  The determinant of the $(n-1)\times (n-1)$
minor of $C_{n,k}$ obtained by removing the final row and the $i$th column
is
${n-1+\lfloor \frac{i}{k-1}\rfloor\choose n-1-i}$.
\end{lemma}

\begin{proof}
Since the determinant of $L_{n,k}$ and
$U_{n,k}$ are both 1, the determinant of $C_{n,k}$ is 1, so $C_{n,k}^{-1}$
is equal to the adjoint of $C_{n,k}$.
Since $C_{n,k}^{-1}=U_{n,k}L_{n,k}$, the final row of the adjoing of
$C_{n,k}$
is equal to the final row of $L_{n,k}$ and the final column of the adjoing
of $C_{n,k}$ is
equal to the final column of $U_{n,k}$.  Now the $(i,j)$ entry in the
adjoint of
$C_{n,k}$ is the product of $(-1)^{i+j}$ and the determinant of the
$(n-1)\times (n-1)$
minor of $C_{n,k}$ obtained by removing the $i$th column and the $j$th
row.
The claim follows.
\end{proof}

\begin{lemma}\label{lem:deta'} The determinants
of $A'_{n,k}$ and $A''_{n,k}$ are respectively given by
\[\sum_{i=0}^n{n+\lfloor \frac{i}{k-1}\rfloor\choose n-i}\]
and
\[\sum_{j=0}^n{n+(k-1)j\choose n-j}.\]
\end{lemma}

\begin{proof} We consider only the determinant of $A'_{n,k}$, the other
argument being similar.
For each $j$ between $1$ and $n+1$, let
${\bf c}_j$ be the column vector consisting of the first $n$ terms in the
$j$th
row of $C_{n+1,k}$. Then the $j$th column vector of $A'_{n,k}$ is ${\bf
c}_j+{\bf c}_{j+1}$. Therefore, the determinant of $A'_{n,k}$ could be
written
as the sum of the determinants of $2^n$ matrices, where the $j$th column
vector of each matrix is either ${\bf c}_j$ or ${\bf c}_{j+1}$. Most of
these determinants are zero, since the determinant of any matrix with two
identical column vectors is zero. The nonzero determinants belong to those
matrices whose column vectors are $n$ distinct vectors from the set
$\{{\bf c}_1,{\bf c}_2,\ldots,{\bf c}_{n+1}\}$, in order. But these are
just the determinants of the minors of $C_{n+1,k}$ obtained by removing
the
final row and one of the columns. The result follows by Lemma
\ref{lem:minor}.

\end{proof}

We now prove Theorem \ref{thm:general}.

\begin{proof}
For $n\geq 0$ and $1\leq l\leq k$, let
$G'_{kn+l,k}=\sum_{i=0}^n{n+\lfloor \frac{i+l-1}{k-1}\rfloor\choose n-i}$.
We now show that $G'_{kn+l,k}=F'_{kn+l}$ for all $n\geq 0$, $1\leq l\leq
k$.  This follows from
the following three observations.
\begin{enumerate}

        \item For $1\leq l\leq k$, $G'_{l,k}=1.$

        \item For $1\leq l\leq k-1$, \[G'_{kn+l,k}+G'_{kn+l+1,k}
        =\sum_{i=0}^n{n+\lfloor \frac{i+l-1}{k-1}\rfloor\choose n-i}+
        \sum_{i=0}^n{n+\lfloor \frac{i+l}{k-1}\rfloor\choose n-i}\]
        \[=\sum_{i=0}^n{n+\lfloor \frac{i+l-1}{k-1}\rfloor\choose n-i}+
        \sum_{i=1}^{n+1}{n+\lfloor \frac{i-1+l}{k-1}\rfloor \choose
n-(i-1)}
        =\sum_{i=0}^{n+1}{n+1+\lfloor \frac{i+l-1}{k-1}\rfloor\choose n-i}
        =G'_{k(n+1)+l,k}.\]

        \item \[G'_{kn+k,k}+G'_{k(n+1)+1,k}=\sum_{i=0}^n{n+\lfloor
\frac{i+k-1}{k-1}\rfloor\choose n-i}+
        \sum_{i=0}^{n+1}{n+1+\lfloor \frac{i}{k-1}\rfloor\choose n+1-i}\]
        \[=\sum_{i=0}^{n+1}\left({n+1+\lfloor \frac{i}{k-1}\rfloor \choose
n-i}+
        {n+1+\lfloor \frac{i}{k-1}\rfloor\choose n+1-i}\right)\]
        \[=\sum_{i=0}^{n+1}{n+2+\lfloor \frac{i}{k-1}\rfloor \choose
n+1-i}
        =\sum_{i=0}^{n+1}{n+1+\lfloor \frac{i+k-1}{k-1}\rfloor\choose
n+1-i}
        =G'_{k(n+1)+k,k}.\]

\end{enumerate}

Now for $n\geq 0$ and $1\leq l\leq k$, let
$G''_{kn+l,k}=\sum_{j=0}^n{n+(k-1)j+l-1\choose n-j}$.
We now show that $G''_{kn+l,k}=F''_{kn+l}$ for all $n\geq 0$, $1\leq l\leq
k$.  This follows from
the following three observations.

\begin{enumerate}

        \item For $1\leq l\leq k$, $G''_{l,k}=1.$

        \item For $1\leq l\leq k-1$, \[G''_{kn+l,k}+G''_{k(n-1)+(l+1),k}
        =\sum_{j=0}^n\left({n+(k-1)j+l-1\choose n-j}
        +{n-1+(k-1)j+l\choose n-1-j}\right)\]
        \[=\sum_{j=0}^n{n+(k-1)j+l\choose n-j}=G''_{kn+l+1,k}.\]

        \item \[G''_{kn+k,k}+G''_{kn+1,k}
        =\sum_{j=0}^n\left({n+(k-1)j+k-1\choose n-j}
        +{n+(k-1)j\choose n-j}\right)\]
        \[=\sum_{j=1}^{n+1}({n+(k-1)j\choose
n-(j-1)})+\sum_{j=0}^n{n+(k-1)j\choose n-j}
        =\sum_{j=0}^{n+1}({n+1+(k-1)j\choose n+1-j}
        =G''_{k(n+1)+1,k}.\]

\end{enumerate}

The statement of the theorem now follows from Lemma \ref{lem:deta'}.
\end{proof}

\begin{thebibliography}{4}

\bibitem{BCCS} I.~Bajunaid,
J.~M.~Cohen, F.~Colonna and D.~Signman, Function series, Catalan
numbers, and random walks on trees, {\it Amer. Math. Monthly.} {\bf 112}
(2005), 765--785.

\bibitem{CRI} A.~Cvetkovi\'c, P.~Rajkovi\'c and
M.~Ivkovi\'c, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Ivkovic/ivkovic3.html}{Catalan numbers, and Hankel transform,
and Fibonacci numbers}, {\it J. Integer Seq.} {\bf 5} (2002), no. 1, Article
02.1.3, 8 pp.  (electronic).

\bibitem{HP} P.~Hilton and J.~Pederson, Catalan numbers, their
generalization, and their uses, {\it Math. Int.} {\bf 13} (1991), 64--75.


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

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent {\it Keywords}: Generalized Catalan numbers, Hankel transform.

\bigskip
\hrule
\bigskip


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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 28 2006;
revised version received December 6 2006.  
Published in {\it Journal of Integer Sequences}, December 8 2006.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

