\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 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, & j0; \\ 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}