\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{graphicx,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} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{question}[theorem]{Question} \newtheorem{notn}[theorem]{Notation} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Hankel Transforms of Linear Combinations \\ \vskip .1in of Catalan Numbers} \vskip 1cm \large Michael Dougherty, Christopher French, Benjamin Saderholm, and Wenyang Qian\\ Department of Mathematics and Statistics\\ Grinnell College\\ Grinnell, IA 50112\\ USA\\ \href{mailto:doughert@grinnell.edu}{\tt doughert@grinnell.edu}\\ \href{mailto:frenchc@grinnell.edu}{\tt frenchc@grinnell.edu}\\ \href{mailto:saderhol@grinnell.edu}{\tt saderhol@grinnell.edu}\\ \href{mailto:qianwney@grinnell.edu}{\tt qianweny@grinnell.edu}\\ \end{center} \vskip .2in \begin{abstract} Cvetkovi\'c, Rajkovi\'c, and Ivkovi\'c proved that the Hankel transform of the sequence of sums of adjacent Catalan numbers is the bisection of the sequence of Fibonacci numbers. Here, we find recurrence relations for the Hankel transform of more general linear combinations of Catalan numbers, involving up to four adjacent Catalan numbers, with arbitrary coefficients. Using these, we make certain conjectures about the recurrence relations satisfied by the Hankel transform of more extended linear combinations. \end{abstract} \section{Introduction}\label{sec:intro} Given a sequence of integers $\{a_n\}_{n=0}^\infty$, the Hankel matrix of the sequence is the infinite matrix $H$ whose $(i,j)$ entry is $a_{i+j}$. Here, we allow $i$ and $j$ to be $0$, so our rows and columns are numbered beginning with $0$. That is, \[H=\left(\begin{matrix} a_0 & a_1 & a_2 & \cdots \\ a_1 & a_2 & a_3 & \cdots \\ a_2 & a_3 & a_4 & \cdots \\ a_3 & a_4 & a_5 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{matrix}\right).\] In general, if $A$ is an infinite matrix, with row and column indices beginning at $0$, and $n\geq 0$ is an integer, we let $A(n)$ denote the upper-left $(n+1)\times (n+1)$ submatrix of $A$. Thus, $H(0)$ is the $1\times 1$ matrix $(a_0)$, $H(1)$ is the $2\times 2$-matrix \[H(1)=\left(\begin{matrix} a_0 & a_1 \\ a_1 & a_2 \end{matrix}\right),\] and \[H(2)=\left(\begin{matrix} a_0 & a_1 & a_2 \\ a_1 & a_2 & a_3 \\ a_2 & a_3 & a_4 \end{matrix}\right).\] We let $h_n=\det(H(n))$. Then the sequence $\{h_n\}_{n=0}^\infty$ is called the {\it Hankel transform} of the sequence $\{a_n\}_{n=0}^\infty$. The Hankel transform is particularly interesting when applied to the Catalan numbers. Recall that the Catalan numbers $c_n$ are defined by the recurrence relation \[c_{n+1}=c_nc_0+c_{n-1}c_1+c_{n-2}c_2+\cdots +c_0c_n\] where $c_0=1$. It is well-known that the Hankel transform of the sequence of Catalan numbers is the sequence of all $1$'s. Mays and Wojciechowski \cite{MW} found the Hankel transform of the sequences obtained by removing $1$, $2$, or $3$ terms from the beginning of the Catalan number sequence. If we remove $1$ term, then the Hankel transform is a sequence of $1$'s; if we remove $2$ terms, the Hankel transform is the sequence $\{n+2\}_{n=0}^\infty$; if we remove $3$ terms, the Hankel transform is the sequence $\left\lbrace\frac{(n+2)(n+3)(2n+5)}{6}\right\rbrace_{n=0}^\infty$. (Note that our $n$ is $k-1$ in \cite{MW}.) Cvetkovi\'c, Rajkovi\'c, and Ivkovi\'c \cite{CRI} proved that the Hankel transform of the sequence $\{c_n+c_{n+1}\}$ is the sequence $2, 5, 13, 34, 89, \cdots$ consisting of every other Fibonacci number. Benjamin, Cameron, Quinn, and Yerger \cite{BCQY} also reproved this result using a more combinatorial approach. Notice that, in particular, the Hankel transform of the sequence $\{c_n+c_{n+1}\}$ satisfies the homogeneous linear recurrence relation \begin{equation}\label{eqn:131} h_{n+2}-3h_{n+1}+h_n=0. \end{equation} In this paper, we take up the question of finding recurrence relations satisfied by more general linear combinations of Catalan numbers. In particular, we ask \begin{question}\label{question} Suppose given $k+1$ integers $\alpha_0, \alpha_1, \alpha_2, \cdots, \alpha_k$. Let $\{h_n\}$ denote the Hankel transform of the sequence whose $n^{\text th}$ term is $\sum_{i=0}^k \alpha_i c_{n+i}$. What homogeneous linear recurrence relation, if any, is satisfied by the sequence $h_n$? \end{question} For example, in the case where $k=1$ and $\alpha_0=\alpha_1=1$, we know that $h_n$ satisfies the recurrence relation of Equation \ref{eqn:131}. Of course, if $k=0$ and $\alpha_0=1$, then $\{h_n\}$ is just the Hankel transform of the sequence of Catalan numbers, so $h_n=1$ for all $n$. From this, it is easy to see that when $k=0$ and $\alpha_0$ is arbitrary, we have $h_n=\alpha_0^{n+1}$. Thus, the sequence $\{h_n\}$ satisfies the first-order homogeneous linear recurrence relation \[h_{n+1}-\alpha_0h_n=0.\] Our next three theorems, which we will prove in this paper, answer Question \ref{question} when $k=1$, $k=2$, and $k=3$. For ease of reading, we adjust our notation, replacing $\alpha_0$, $\alpha_1$, $\alpha_2$, and $\alpha_3$ by $\alpha$, $\beta$, $\gamma$, $\delta$. \begin{theorem}\label{thm:1} The Hankel transform of the sequence $\{\alpha c_n+\beta c_{n+1}\}$ satisfies the second-order homogeneous linear recurrence relation \[h_{n+2}-(\alpha+2\beta)h_{n+1}+\beta^2 h_n=0.\] \end{theorem} \begin{theorem}\label{thm:2} The Hankel transform of the sequence $\{\alpha c_n+\beta c_{n+1}+\gamma c_{n+2}\}$ satisfies the fourth-order homogeneous linear recurrence relation \begin{eqnarray*} h_{n+4}+(-\alpha-2\beta-4\gamma)h_{n+3}+ (\beta^2-2\alpha\gamma+4\beta\gamma +6\gamma^2)h_{n+2}\\ +(-\alpha-2\beta-4\gamma)\gamma^2 h_{n+1}+\gamma^4h_n=0. \end{eqnarray*} \end{theorem} \begin{theorem}\label{thm:3} The Hankel transform of the sequence $\{\alpha c_n+\beta c_{n+1}+\gamma c_{n+2}+\delta c_{n+3}\}$ satisfies the eighth-order homogeneous linear recurrence relation {\scriptsize \begin{eqnarray*} h_{n+8}\\ + (-\alpha-2\beta-4\gamma-8\delta)h_{n+7}\\ +(\beta^2-2\alpha\gamma+4\beta\gamma+6\gamma^2-12\alpha\delta+4\beta\delta+24\gamma\delta+28\delta^2)h_{n+6}\\ +(-\alpha\gamma^2-2\beta\gamma^2-4\gamma^3+2\alpha\beta\delta+4\beta^2\delta-4\alpha\gamma\delta -24\gamma^2\delta-7\alpha\delta^2+2\beta\delta^2-60\gamma\delta^2-56\delta^3)h_{n+5}\\ +(\gamma^4-4\beta\gamma^2\delta+8\gamma^3\delta+\alpha^2\delta^2+4\alpha\beta\delta^2 +6\beta^2\delta^2+12\alpha\gamma\delta^2-8\beta\gamma\delta^2+36\gamma^2\delta^2+ 40\alpha\delta^3-8\beta\delta^3 +80\gamma\delta^3+70\delta^4)h_{n+4}\\ +(-\alpha\gamma^2-2\beta\gamma^2-4\gamma^3+2\alpha\beta\delta+4\beta^2\delta-4\alpha\gamma\delta -24\gamma^2\delta-7\alpha\delta^2+2\beta\delta^2-60\gamma\delta^2-56\delta^3)\delta^2 h_{n+3}\\ +(\beta^2-2\alpha\gamma+4\beta\gamma+6\gamma^2-12\alpha\delta+4\beta\delta+24\gamma\delta+28\delta^2) \delta^4 h_{n+2}\\ +(-\alpha-2\beta-4\gamma-8\delta)\delta^6 h_{n+1}\\ +\delta^8 h_n=0. \end{eqnarray*} } \end{theorem} Of course, Theorem \ref{thm:2} follows from Theorem \ref{thm:3} by setting $\delta$ equal to $0$, and Theorem \ref{thm:1} follows from Theorem \ref{thm:2} by setting $\gamma=0$. Notice also that the result of Cvetkovi\'c, Rajkovi\'c, and Ivkovi\'c \cite{CRI} follows from Theorem \ref{thm:1} by setting $\alpha=\beta=1$. In this case, it is trivial to check that the initial two terms of the Hankel transform are $2$ and $5$, and then the recurrence relation implies the rest. While the recurrence relations given above quickly grow in complexity as $k$ increases, there are several features of these recurrence relations that seem interesting. On the basis of these features, we make the following conjectures. First, we note that the order of the recurrence relations doubles each time we increase $k$ by $1$. \begin{conjecture}\label{con:1} The Hankel transform of the sequence whose $n^{\text th}$ term is \[\sum_{i=0}^k \alpha_i c_{n+i}\] satisfies a homogeneous linear recurrence relation of order $2^k$. \end{conjecture} We also notice that the coefficient of $h_{n+2^k-1}$ is of a particularly simple form. \begin{conjecture} The coefficient of $h_{n+2^k-1}$ in the recurrence relation of Conjecture \ref{con:1} is \[-(\alpha_0+2\alpha_1+4\alpha_2+\cdots+2^k\alpha_k).\] \end{conjecture} Finally, we note that the coefficients of $h_{n+2^k-r}$ and $h_{n+r}$ seem to be related. For example, in Theorem \ref{thm:2}, the coefficient of $h_{n+1}$ is the product of $\gamma^2$ and the coefficient of $h_{n+3}$. Likewise, the coefficient of $h_n$ is the product of $\gamma^4$ and the coefficient of $h_{n+4}$. \begin{conjecture} When $r<2^{k-1}$, the coefficient of $h_{n+r}$ in the recurrence relation of Conjecture \ref{con:1} is equal to the product of $\alpha_k^{2^k-2r}$ and the coefficient of $h_{n+2^k-r}$. \end{conjecture} Using Theorem \ref{thm:2}, we can show that certain sequences in the OEIS \cite{OEIS} are Hankel transforms of linear combinations of Catalan numbers. For example, if we set $\alpha=1, \beta=1, \gamma=1$, we get the sequence \[4, 20, 111, 624, 3505, 19676, 110444, 619935, 3479776, 19532449, \ldots\] which is sequence \seqnum{A014523} in the OEIS, the number of Hamiltonian paths in a $4\times (2n+1)$ grid (see also \cite{CK}). To see this, we simply observe from the OEIS that sequence \seqnum{A014523} satisfies the recurrence relation \[a_{n+4}-7a_{n+3}+9a_{n+2}-7a_{n+1}+a_n=0.\] By Theorem \ref{thm:2}, this is the same as the recurrence relation satisfied by the Hankel transform of $c_n+c_{n+1}+c_{n+2}$. One now simply observes that the first four terms of the two sequences coincide! Likewise, if we set $\alpha=1, \beta=2, \gamma=1$, we get the sequence \[5, 30, 199, 1355, 9276, 63565, 435665, 2986074, 20466835, 140281751, \ldots\] which is sequence \seqnum{A103433} in the OEIS, namely the sequence $\sum_{i=0}^n F_{2i-1}^2$ where $F_k$ denotes the $k^{\text th}$ Fibonacci number. To see this, we note from the OEIS that sequence \seqnum{A103433} has generating function \[G(x)=\frac{x(1-4x+x^2)}{(1-7x+x^2)(1-x)^2}=\frac{x-4x^2+x^3}{x^4-9x^3+16x^2-9x+1}.\] From here, it is easy to check that the sequence satisfies the recurrence relation \[h_{n+4}-9h_{n+3}+16h_{n+2}-9h_{n+1}+h_n=0.\] By Theorem \ref{thm:2}, this is the same as the recurrence relation satisfied by the Hankel transform of $c_n+2c_{n+1}+c_{n+2}$. Again, one simply observes that the first four terms of the two sequences coincide. Our paper is organized as follows. In Section \ref{sec:CNHM}, we state some basic results concerning Hankel matrices and shifts of Catalan numbers. These results are proved in Section \ref{sec:proofs}. Using only these basic results, we prove Theorem \ref{thm:1} in Section \ref{sec:CNHM}. For Theorems \ref{thm:2} and \ref{thm:3} we need somewhat more sophisticated arguments. To prepare for these, we state and prove two easy lemmas about recurrence relations in Section \ref{sec:recurrence}. The work of Section \ref{sec:CNHM} shows that we can simplify our study of the Hankel matrices of linear combinations of Catalan numbers by investigating a class of matrices which we call hyperdiagonal. We carry out this investigation in Section \ref{sec:hyper}, and use the results from there to finish off the proofs of Theorems \ref{thm:2} and \ref{thm:3} in Section \ref{sec:end}. \section{Catalan Numbers and Hankel Matrices}\label{sec:CNHM} In this section, we state some results about the Hankel matrices of shifts of the sequence of Catalan numbers; we will prove these results in the next section. Using these results, we give an easy proof of Theorem \ref{thm:1}. To begin, we need some definitions. \begin{definition} Let $C$ be the Hankel matrix of the sequence of Catalan numbers, so $C_{i,j}=c_{i+j}$, where $i,j$ are non-negative integers. Let $C\{k\}$ denote the Hankel matrix of the sequence of Catalan numbers with the first $k$ terms removed, so $C\{k\}_{i,j}=c_{i+j+k}$. In particular, $C=C\{0\}$. \end{definition} \begin{definition}\label{def:LSUC} Let $L$ be the infinite matrix defined by $L_{i,j}=(-1)^{i+j}{i+j\choose i-j}$. (When $in$. We will later use this proposition in the proofs of Theorems \ref{thm:2} and \ref{thm:3}. As an example, $LC\{2\}U$ takes the form \[\left(\begin{matrix} 2 & 3 & 1 & 0 & 0 & 0 & \cdots\\ 3 & 6 & 4 & 1 & 0 & 0 & \cdots \\ 1 & 4 & 6 & 4 & 1 & 0 & \cdots \\ 0 & 1 & 4 & 6 & 4 & 1 & \cdots \\ 0 & 0 & 1 & 4 & 6 & 4 & \cdots \\ 0 & 0 & 0 & 1 & 4 & 6 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{matrix}\right).\] The $3$ entries in the top left (the $2$ and the two $3$'s) are not given by Proposition \ref{prop:LCKU2}, but can easily be computed directly. Likewise, $LC\{3\}U$ takes the form \[\left(\begin{matrix} 5 & 9 & 5 & 1 & 0 & 0 & 0 &\cdots\\ 9 & 19 & 15 & 6 & 1 & 0 & 0 & \cdots \\ 5 & 15 & 20 & 15 & 6 & 1 & 0 &\cdots \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & \cdots \\ 0 & 1 & 6 & 15 & 20 & 15 & 6 & \cdots \\ 0 & 0 & 1 & 6 & 15 & 20 & 15 & \cdots \\ 0 & 0 & 0 & 1 & 6 & 15 & 20 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{matrix}\right).\] Again, the six entries in the top left (the three $5$'s, the two $9$'s, and the $19$) are not given by Proposition \ref{prop:LCKU2}, but can easily be computed directly. \section{Proofs of Propositions \ref{prop:LC1U} and \ref{prop:LCKU2}}\label{sec:proofs} In this section, as the title suggests, we prove Propositions \ref{prop:LC1U} and \ref{prop:LCKU2}. The main technical tool in these proofs is the following Lemma. The second author used this idea previously \cite{CF} having found it originally in a paper by Bajunaid, Cohen, Colonna, and Signman \cite{BCCS}. \begin{lemma}\label{lem:genfun} Let $g(z)$ be the power series $\sum_{n=0}^\infty c_k z^k$. Then, $g(z(1-z))=\sum_{k=0}^\infty z^k$. \end{lemma} \begin{proof} By definition of the Catalan numbers, \[g(z)^2=\sum_{k=0}^\infty \left(\sum_{l=0}^k c_lc_{k-l}\right) z^k =\sum_{k=0}^\infty c_{k+1}z^k.\] Thus, \[zg(z)^2=\sum_{k=0}^\infty c_{k+1}z^{k+1}=\sum_{k=1}^\infty c_kz^k=g(z)-1.\] We may substitute $z(1-z)$ into this equation to obtain \[z(1-z)g(z(1-z))^2=g(z(1-z))-1.\] Multiplying by $z(1-z)$ yields \[\left(z(1-z)g(z(1-z))\right)^2=\left(z(1-z)g(z(1-z))\right)-z(1-z).\] If we let $h(z)=z(1-z)g(z(1-z))$, then the above equation implies $h(z)^2-h(z)+z(1-z)=0,$ so that $(h(z)-z)(h(z)-(1-z))=0$. Since the ring of power series is an integral domain, this implies $h(z)=z$ or $h(z)=1-z$. But we know $h(0)=0$, so $h(z)=z$, whence $z(1-z)g(z(1-z))=z$. This implies $g(z(1-z))=\frac{1}{1-z}=\sum_{k=0}^\infty z^k$. \end{proof} \begin{corollary}\label{cor:genfun} Suppose $i\geq t\geq 1$. Then, we have \[\sum_{k=i-t}^{2i-t} (-1)^{k+t} {k+t\choose 2i-t-k} c_k=0.\] For any $i\geq 0$, we have \[\sum_{k=i}^{2i} (-1)^{k} {k\choose 2i-k} c_k=1,\] and \[\sum_{k=i+1}^{2i+1} (-1)^{k-1} {k-1\choose 2i+1-k} c_k=2i+1.\] \end{corollary} \begin{proof} First, we have \[(1-z)^tg(z(1-z))=\sum_{k=0}^\infty c_k z^k(1-z)^{k+t} =\sum_{k=0}^\infty \sum_{m=0}^{k+t} (-1)^m {k+t\choose m} c_k z^{k+m}.\] For an integer $i\geq 0$, the coefficient of $z^{2i-t}$ is \[\sum_{k=i-t}^{2i-t} (-1)^{k+t} {k+t\choose 2i-t-k} c_k.\] On the other hand, by Lemma \ref{lem:genfun}, $(1-z)^tg(z(1-z))=(1-z)^{t-1}$, so if $i\geq t$, then $2i-t\geq t$, so the coefficient of $i-t$ is $0$. For the second formula, we have \[g(z(1-z))=\sum_{k=0}^\infty c_k z^k(1-z)^k =\sum_{k=0}^\infty \sum_{m=0}^k (-1)^m {k\choose m} c_k z^{k+m}.\] For an integer $i\geq 0$, the coefficient of $z^{2i}$ is \[\sum_{k=i}^{2i} (-1)^{k} {k\choose 2i-k} c_k.\] By Lemma \ref{lem:genfun}, this coefficient is equal to $1$. Finally, we have \[\frac{g(z(1-z))-1}{1-z}=\sum_{k=1}^\infty c_k z^k(1-z)^{k-1} =\sum_{k=1}^\infty \sum_{m=0}^{k-1} (-1)^m {k-1\choose m} c_k z^{k+m}.\] For an integer $i\geq 0$, the coefficient of $z^{2i+1}$ is \[\sum_{k=i+1}^{2i+1} (-1)^{k-1} {k-1\choose 2i+1-k} c_k.\] But by Lemma \ref{lem:genfun} again, \[\frac{g(z(1-z))-1}{1-z}=\frac{1/(1-z) -1}{1-z}=\frac{z}{(1-z)^2}= \sum kz^k,\] so the coefficient of $z^{2i+1}$ is $2i+1$. \end{proof} \begin{lemma}\label{lem:LC} The product $LC$ is an upper triangular matrix, with $LC_{i,i}=1$ for all $i\geq 0$, and $LC_{i,i+1}=2i+1$. \end{lemma} \begin{proof} First, we observe that since $L$ is lower triangular, \[(LC)_{i,j}=\sum_{k=0}^\infty L_{i,k}C_{k,j}=\sum_{k=0}^i L_{i,k}C_{k,j},\] so that the matrix product $LC$ is well-defined. Now, by definition of $L$ and $C$, \[(LC)_{i,j}=\sum_{k=0}^i (-1)^{i+k} {i+k\choose i-k}c_{k+j} =\sum_{k=j}^{i+j} (-1)^{i-j+k} {i-j+k\choose i+j-k} c_k.\] When $jj+1$. Since $U_{i,j}=0$ for $i>j$, it follows easily that $(LC\{1\}U)_{i,j}=0$ whenever $i>j+1$. Moreover, when $i\geq 1$, we have \[(LC\{1\}U)_{i,i-1}=\sum_{k=0}^\infty (LC\{1\})_{i,k}U_{k,i-1}\] \[=\sum_{k=i-1}^{i-1} (LC\{1\})_{i,k} U_{k,i-1}=(LC\{1\})_{i,i-1}U_{i-1,i-1}=LC_{i,i}U_{i-1,i-1}.\] By Lemma \ref{lem:LC}, this is $1$. When $i\geq 1$, we have \[(LC\{1\}U)_{i,i}=\sum_{k=0}^\infty (LC\{1\})_{i,k}U_{k,i}\] \[=\sum_{k=i-1}^i (LC\{1\})_{i,k} U_{k,i}=(LC\{1\})_{i,i-1}U_{i-1,i}+(LC\{1\})_{i,i}U_{i,i}\] \[=(LC)_{i,i}U_{i-1,i}+LC_{i,i+1}U_{i,i}.\] By Lemma \ref{lem:LC} and the definition of $U$, this is $-(2i-1)+2i+1=2$. Likewise, $(LC\{1\}U)_{0,0}=(LC\{1\})_{0,0}U_{0,0}=(LC)_{0,1}U_{0,0}=1$. The rest of the claim follows since $LC\{1\}U$ is symmetric. \end{proof} We now turn to considering $LC\{k\}U$. The following definition will be useful. \begin{definition} Let $S$ be the infinite matrix defined by $S_{i,j}=\delta_{i,j+1}$, where $\delta$ is the Kronecker delta symbol. \end{definition} We note that if $A$ is an infinite matrix, then $AS$ is the matrix obtained by removing the first column of $A$. In particular, if $A$ is the Hankel matrix of a sequence $\{a_i\}_{i=0}^\infty$, then $AS$ is the Hankel matrix of the sequence $\{a_i\}_{i=1}^\infty$. Thus, $CS^k=C\{k\}$. \begin{proposition}\label{prop:LCKU} For any $k\geq 0$, we have $(LC\{1\}U)^k=LC\{k\}U$. \end{proposition} \begin{proof} We have seen already in Proposition \ref{prop:LC1U} that $LCU=I$, so $LC\{0\}U=(LC\{1\}U)^0$. It is easy to check that if $A$ and $B$ are both upper triangular, then $(AB)(n)=A(n)B(n)$. Thus, $(LC)(n)U(n)$ is the $n+1\times n+1$ identity matrix. Thus, $LC(n)=U(n)^{-1}$, so $(ULC)(n)=U(n)(LC)(n)$ is the $n+1\times n+1$ identity matrix for each $n$. Therefore, $ULC$ is the infinite identity matrix. Thus, \[(LC\{1\}U)=(LCSU)^k=LCS(ULCS)^{k-1}U\] \[=LCS(S^{k-1})U=LCS^kU=LC\{k\}U.\] \end{proof} We now can prove Proposition \ref{prop:LCKU2}. \begin{proof} (of Proposition \ref{prop:LCKU2}) We prove this by induction on $k$. The cases when $k=0$ or $k=1$ follow easily from Proposition \ref{prop:LC1U}. Now, suppose the claim holds when $k=t\geq 1$. Then by Proposition \ref{prop:LCKU} we have \[LC\{t+1\}U=(LC\{1\}U)^{t}(LC\{1\}U)=(LC\{t\}U)(LC\{1\}U).\] Thus, we have \[(LC\{t+1\}U)_{i,j}=\sum_{l} (LC\{t\}U)_{i,l}(LC\{1\}U)_{l,j}.\] If $j\geq 1$, then by Proposition \ref{prop:LC1U}, we get \[(LC\{t+1\}U)_{i,j}=(LC\{t\}U)_{i,j-1}+2(LC\{t\}U)_{i,j}+(LC\{t\}U)_{i,j+1}.\] Now, assuming $i+j\geq t+1$, we have $i+(j-1)\geq t$, so by the inductive hypothesis, the above sum is \[{2t\choose t+i-j+1}+2{2t\choose t+i-j}+{2t\choose t+i-j-1}\] \[=\left({2t\choose t+i-j+1}+{2t\choose t+i-j}\right)+\left({2t\choose t+i-j}+ {2t\choose t+i-j-1}\right) \] \[={2t+1\choose t+i-j+1}+{2t+1\choose t+i-j}={2(t+1)\choose (t+1)+i-j},\] as needed. On the other hand, if $j=0$, then by Proposition \ref{prop:LC1U}, we get \[(LC\{t+1\}U)_{i,j}=\sum_{l} (LC\{t\}U)_{i,l}(LC\{1\}U)_{l,j} =(LC\{t\}U)_{i,0}+(LC\{t\}U)_{i,1}.\] Now, since we may assume $i+j\geq t+1$, we have $i\geq t+1$, so by the inductive hypothesis, the above term is ${2t\choose t+i}+{2t\choose t+i-1}={2t+1\choose t+i}$. If $i=t+1$, then \[{2t+1\choose t+i}=1={2(t+1)\choose (t+1)+i},\] while if $i>t+1$, then \[{2t+1\choose t+i}=0={2(t+1)\choose (t+1)+i},\] as needed. \end{proof} \section{Recurrence Relations}\label{sec:recurrence} In this section, we make two observations about solutions to recurrence relations. The second observation, Lemma \ref{lem:characteristic}, is an easy application of the Cayley-Hamilton theorem to recurrence relations. The first observation, Lemma \ref{lem:shorter}, describes a technique for showing that a given solution of a recurrence relation in fact satisfies a recurrence relation of lower order. An example will help to illustrate this idea. \begin{example} Suppose a sequence $\{x_n\}$ satisfies the recurrence relation \[a_{n+3}-2a_{n+2}+a_n=0,\] and suppose that $x_2=x_1+x_0$. Then the sequence $\{x_n\}$ satisfies the recurrence relation \[a_{n+2}-a_{n+1}-a_n=0.\] To see this, define a new sequence $\{y_n\}$ by $y_n=x_{n+2}-x_{n+1}-x_n$. Then \[y_{n+1}-y_n=(x_{n+3}-x_{n+2}-x_{n+1})-(x_{n+2}-x_{n+1}-x_n)\] \[=x_{n+3}-2x_{n+2}+x_n=0,\] so $y_{n+1}=y_n$ for all $n$. At the same time, $y_0=x_2-x_1-x_0=0$. Thus, $y_n=0$ for all $n$, so that $x_{n+2}-x_{n+1}-x_n=0$ for all $n$. \end{example} To generalize the example above, recall that a recurrence relation \[c_ka_{n+k}+c_{k-1}a_{n+k-1}+\cdots+c_1a_{n+1}+c_0a_n=0\] has an associated characteristic polynomial \[p(x)=c_kx^k+c_{k-1}x^{k-1}+\cdots +c_1x+c_0.\] In the following lemma, we suppose given two polynomials of degree $k_1$ and $k_2$ respectively: \[p_1(x)=\sum_j c_{j,1} x^j,\quad p_2(x)=\sum_j c_{j,2} x^j.\] Here, the summations are over all integers, but $c_{j,1}=0$ for all $j>k_1$ and all $j<0$, while $c_{j,2}=0$ for all $j>k_2$ and all $j<0$. We let \[q(x)=p_1(x)\cdot p_2(x)=\sum_j \left(\sum_l c_{l,1}c_{j-l,2}\right)x^j.\] \begin{lemma}\label{lem:shorter} Suppose given a sequence $\{x_n\}$ such that for some positive integer $m$, we have \begin{enumerate} \item $\{x_n\}$ satisfies the recurrence relation with characteristic polynomial $q(x)$ for $n\geq m$, and \item For $0\leq n\leq m+k_1-1$, we have $\sum_j c_{j,2}x_{n+j}=0$. That is, for $0\leq n\leq m+k_1-1$, $\{x_n\}$ satisfies the recurrence relation with characteristic polynomial $p_2(x)$. \end{enumerate} Then $\{x_n\}$ satisfies the recurrence relation with characteristic polynomial $p_2(x)$ for all $n\geq 0$. \end{lemma} \begin{proof} Let $y_n=\sum_j c_{j,2} x_{n+j}$. Then \[\sum_l c_{l,1} y_{n+l}=\sum_l \sum_j c_{l,1}c_{j,2} x_{n+l+j} =\sum_j\left(\sum_l c_{l,1}c_{j-l,2}\right) x_{n+j}.\] By our first hypothesis, this last term is $0$ whenever $n\geq m$, so $\{y_n\}$ satisfies the $k_1^{\text{th}}$-order homogeneous linear recurrence relation with characteristic polynomial $p_1(x)$ for $n\geq m$. By our second hypothesis, $y_n=0$ for $0\leq n\leq m+k_1-1$, which includes the $k_1$ consecutive values of $n$ beginning at $m$. It follows by induction that $y_n=0$ for all $n\geq 0$. Thus, $\{x_n\}$ satisfies the recurrence relation with characteristic polynomial $p_2(x)$. \end{proof} Now, we turn to our application of the Cayley-Hamilton theorem. Consider a sequence $\{\vec v_n\}$ of vectors in $\mathbb R^m$; we let $v_n^i$ denote the $i^\text{th}$ component of $\vec v_n$. \begin{lemma}\label{lem:characteristic} Suppose $\{\vec v_n\}$ satisfies the recurrence relation $\vec v_{n+1}=A\vec v_n$, where $A$ is an $m\times m$ matrix. Then for each $i\in \{1, 2, \ldots, m\}$, the sequence $v_n^i$ satisfies a recurrence relation whose characteristic polynomial is equal to the characteristic polynomial of the matrix $A$, $\det(\lambda I-A)$. \end{lemma} \begin{proof} Let $p(\lambda)=\det(\lambda I-A)=c_m\lambda^m+c_{m-1}\lambda^{m-1}+\cdots+c_0$. Then by the Cayley-Hamilton theorem, $p(A)=0$, so for any $n$, \[c_mA^m\vec v_n+c_{m-1}A^{m-1}\vec v_n+\cdots +c_0\vec v_n=\vec 0.\] Since $\vec v_{n+1}=A\vec v_n$ for all $n$, this yields \[c_m\vec v_{n+m}+c_{m-1}\vec v_{n+m-1}+\cdots +c_0\vec v_n=\vec 0.\] Now, taking the $i^\text{th}$ component of the above equation yields the result. \end{proof} \section{Hyperdiagonal matrices}\label{sec:hyper} Just as Proposition \ref{prop:LC1U} allowed us to study the Hankel transform of the sequence $\alpha c_n+\beta c_{n+1}$ in the proof of Theorem \ref{thm:1}, so Proposition \ref{prop:LCKU2} allows us to investigate the Hankel transforms of more complicated linear combinations of Catalan numbers. Proposition \ref{prop:LCKU2} motivates studying a class of matrices which we now describe. \begin{definition}\label{def:hyperdiagonal} An infinite matrix $M$ is {\it $k$-hyperdiagonal} if $M_{i,j}=0$ whenever $|j-i|>k$, and for $j+i\geq k$, $M_{i,j}$ only depends on $|j-i|$. We let $m_t$ and $m_{-t}$ denote the value of $M_{i,j}$ when $|j-i|=t$ and $j+i\geq k$ (so $m_t=0$ when $t>k$ or $t<-k$.) \end{definition} \begin{example}\label{ex:k=123} By Proposition \ref{prop:LCKU2}, the matrix $LC\{k\}U$ is $k$-hyperdiagonal, with $m_t={2k\choose k-t}={2k\choose k+t}$. \end{example} In this section, we will investigate the determinants of the sequence of upper left $(n+1)\times (n+1)$ submatrices of a $k$-hyperdiagonal matrix $M$. \begin{notn} Suppose $M$ is a $k$-hyperdiagonal infinite matrix, and let $\vec r$ denote the integer-valued vector $\langle r_1, r_2, \cdots, r_k\rangle$, where $-kk$ and $M$ is $k$-hyperdiagonal. Thus, since $n-k+l