\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, Hankel \\ \vskip .1in Transforms and Somos-4 Sequences} \vskip 1cm \large Paul Barry\\ School of Science\\ Waterford Institute of Technology\\ Ireland\\ \href{mailto:pbarry@wit.ie}{\tt pbarry@wit.ie} \\ \end{center} \vskip .2 in \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} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{abstract} We study families of generalized Catalan numbers, defined by convolution recurrence equations. We explore their relations to series reversion, Riordan array transforms, and in a special case, to Somos-$4$ sequences via the mechanism of the Hankel transform. \end{abstract} \section{Introduction} This note is concerned with the solutions to the following two convolution recurrences: \begin{equation}\label{First_order} a_n = \begin{cases} 1, & \text{if $n=0$;}\\ \alpha a_{n-1}+\beta \sum_{k=0}^{n-1}a_k a_{n-1-k}, & \text{if $n>0$.} \end{cases} \end{equation} and \begin{equation}\label{Second_order} a_n = \begin{cases} 1, & \text{if $n=0$;}\\ \alpha, & \text{if $n=1$;} \\ \alpha a_{n-1}+\beta a_{n-2} + \gamma \sum_{k=0}^{n-2}a_k a_{n-2-k}, & \text{if $n>1$.} \end{cases} \end{equation} We call the elements of these sequences generalized Catalan numbers, since the Catalan numbers $C_n=\frac{1}{n+1}\binom{2n}{n}$ satisfy equation (\ref{First_order}) with $\alpha=0$ and $\beta=1$: \begin{equation}\label{Catalan} C_n = \begin{cases} 1, & \text{if $n=0$;}\\ \sum_{k=0}^{n-1}C_k C_{n-1-k}, & \text{if $n>0$.} \end{cases} \end{equation} Many of the sequences that we will encounter have interesting Hankel transforms \cite{BRP, CRI, Layman}, and many will have generating functions that we can describe using Riordan arrays \cite{CMS, SGWW, Spru} and continued fractions \cite{Wall}. Many interesting examples of sequences and Riordan arrays can be found in Neil Sloane's On-Line Encyclopedia of Integer Sequences (OEIS), \cite{SL1, SL2}. Sequences are frequently referred to by their A$nnnnnn$ OEIS number. For instance, the Motzkin numbers $M_n$ \seqnum{A001006} satisfy equation (\ref{Second_order}) with $\alpha=1$, $\beta=0$ and $\gamma=1$: \begin{equation}\label{Motzkin} M_n = \begin{cases} 1, & \text{if $n=0$;}\\ 1, & \text{if $n=1$;} \\ M_{n-1} + \sum_{k=0}^{n-2}M_k M_{n-2-k}, & \text{if $n>1$.} \end{cases} \end{equation} To see why this should be so, we translate this equation into the corresponding algebraic equation for generating functions: $$G(x)=1+xG(x)+x^2G(x)^2,$$ with solution $$m(x)=G(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}.$$ Now we can express the g.f. $m(x)$ of the Motzkin numbers in terms of the g.f. of the Catalan numbers \seqnum{A000108}, which is $$c(x)=\frac{1-\sqrt{1-4x}}{2x}.$$ Thus we have \begin{equation} \label{Mgf} m(x)=\frac{1}{1-x}c\left(\frac{x^2}{(1-x)^2}\right).\end{equation} In other words, the generating function of the Motzkin numbers, solution of equation (\ref{Motzkin}), results from operating on the generating function $c(x)$ of the Catalan numbers by the (generalized, or stretched) Riordan array $$\left(\frac{1}{1-x},\frac{x^2}{(1-x)^2}\right).$$ We immediately obtain that $$M_n=\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} C_k.$$ Now since the g.f. $c(x)$ of the Catalan numbers may be expressed as the continued fraction \begin{equation}\label{Cat_CF}c(x)=\cfrac{1}{1- \cfrac{x}{1- \cfrac{x}{1-\cdots}}}, \end{equation} we can infer from equation (\ref{Mgf}) that the continued fraction expression for $m(x)$ is given by \begin{equation}\label{Mgfcf} m(x)=\cfrac{1}{1-x- \cfrac{x^2}{1-x- \cfrac{x^2}{1-\cdots}}}.\end{equation} Thus $m(x)$ satisfies the relation $$m(x)=\frac{1}{1-x-x^2 m(x)}.$$ The continued fraction expression in equation (\ref{Mgfcf}) shows in particular that the Hankel transform of the Motzkin numbers is given by the all $1$'s sequence $1,1,1,\ldots$. In the next section, we will review known results concerning Riordan arrays and Hankel transforms that will be useful in the sequel. \section{Preliminaries on integer sequences, Riordan arrays and Hankel transforms} For an integer sequence $a_n$, that is, an element of $\mathbb{Z}^\mathbb{N}$, the power series $f(x)=\sum_{k=0}^{\infty}a_k x^k$ is called the \emph{ordinary generating function} or g.f. of the sequence. $a_n$ is thus the coefficient of $x^n$ in this series. We denote this by $a_n=[x^n]f(x)$. For instance, $F_n=[x^n]\frac{x}{1-x-x^2}$ is the $n$-th Fibonacci number \seqnum{A000045}, while $C_n=[x^n]\frac{1-\sqrt{1-4x}}{2x}$ is the $n$-th Catalan number \seqnum{A000108}. We use the notation $0^n=[x^n]1$ for the sequence $1,0,0,0,\ldots,$ \seqnum{A000007}. Thus $0^n=[n=0]=\delta_{n,0}=\binom{0}{n}$. For a power series $f(x)=\sum_{n=0}^{\infty}a_n x^n$ with $f(0)=0$ and $f'(0)\neq 0$ we define the \emph{reversion} or \emph{compositional inverse} of $f$ to be the power series $\bar{f}(x)$ (also written as $f^{[-1]}(x)$) such that $f(\bar{f}(x))=x$. We sometimes write $\bar{f}= \text{Rev}f$. The \emph{aeration} of a sequence with g.f. $f(x)$ is the sequence with g.f. $f(x^2)$. For a lower triangular matrix $(a_{n,k})_{n,k \ge 0}$ the row sums give the sequence with general term $\sum_{k=0}^n a_{n,k}$ while the diagonal sums form the sequence with general term $$\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} a_{n-k,k}.$$ The \emph{Riordan group} \cite{SGWW,Spru}, is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions $g(x)=1+g_1x+g_2x^2+\cdots$ and $f(x)=f_1x+f_2x^2+\cdots$ where $f_1\ne 0$ \cite{Spru}. The associated matrix is the matrix whose $i$-th column is generated by $g(x)f(x)^i$ (the first column being indexed by 0). The matrix corresponding to the pair $g, f$ is denoted by $(g, f)$ or $\cal{R}$$(g,f)$. The group law is then given by \begin{displaymath} (g, f)\cdot(h, l)=(g, f)(h, l)=(g(h\circ f), l\circ f).\end{displaymath} The identity for this law is $I=(1,x)$ and the inverse of $(g, f)$ is $(g, f)^{-1}=(1/(g\circ \bar{f}), \bar{f})$ where $\bar{f}$ is the compositional inverse of $f$. If $\mathbf{M}$ is the matrix $(g,f)$, and $\mathbf{a}=(a_0,a_1,\ldots)'$ is an integer sequence with ordinary generating function $\cal{A}$$(x)$, then the sequence $\mathbf{M}\mathbf{a}$ has ordinary generating function $g(x)$$\cal{A}$$(f(x))$. The (infinite) matrix $(g,f)$ can thus be considered to act on the ring of integer sequences $\mathbb{Z}^\mathbb{N}$ by multiplication, where a sequence is regarded as a (infinite) column vector. We can extend this action to the ring of power series $\mathbb{Z}[[x]]$ by $$(g,f):\cal{A}(\mathnormal{x}) \mapsto \mathnormal{(g,f)}\cdot \cal{A}\mathnormal{(x)=g(x)}\cal{A}\mathnormal{(f(x))}.$$ \begin{example} The so-called \emph{binomial matrix} $\mathbf{B}$ \seqnum{A007318} is the element $(\frac{1}{1-x},\frac{x}{1-x})$ of the Riordan group. It has general element $\binom{n}{k}$, and hence as an array coincides with Pascal's triangle. More generally, $\mathbf{B}^m$ is the element $(\frac{1}{1-m x},\frac{x}{1-mx})$ of the Riordan group, with general term $\binom{n}{k}m^{n-k}$. It is easy to show that the inverse $\mathbf{B}^{-m}$ of $\mathbf{B}^m$ is given by $(\frac{1}{1+mx},\frac{x}{1+mx})$. \end{example} \begin{example} If $a_n$ has generating function $g(x)$, then the generating function of the sequence $$b_n=\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} a_{n-2k}$$ is equal to $$\frac{g(x)}{1-x^2}=\left(\frac{1}{1-x^2},x\right)\cdot g(x),$$ while the generating function of the sequence $$d_n=\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n-k}{k} a_{n-2k}$$ is equal to $$\frac{1}{1-x^2}g\left(\frac{x}{1-x^2}\right)=\left(\frac{1}{1-x^2},\frac{x}{1-x^2}\right)\cdot g(x).$$ \end{example} The row sums of the matrix $(g, f)$ have generating function $$(g,f)\cdot \frac{1}{1-x}=\frac{g(x)}{1-f(x)}$$ while the diagonal sums of $(g, f)$ (sums of left-to-right diagonals in the North East direction) have generating function $g(x)/(1-xf(x))$. These coincide with the row sums of the ``generalized'' Riordan array $(g,xf)$: $$(g,xf)\cdot\frac{1}{1-x}=\frac{g(x)}{1-xf(x)}.$$ For instance the Fibonacci numbers $F_{n+1}$ are the diagonal sums of the binomial matrix $\mathbf{B}$ given by $\left(\frac{1}{1-x},\frac{x}{1-x}\right)$\,: \begin{displaymath}\left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\1 & 1 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 2 & 1 & 0 & 0 & 0 & \cdots \\ 1 & 3 & 3 & 1 & 0 & 0 & \cdots \\ 1 & 4 & 6 & 4 & 1 & 0 & \cdots \\1 & 5 & 10 & 10 & 5 & 1 &\cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right)\end{displaymath} while they are the row sums of the ``generalized'' or ``stretched'' (using the nomenclature of \cite{CMS} ) Riordan array $\left(\frac{1}{1-x},\frac{x^2}{1-x}\right)$\,: \begin{displaymath}\left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 1 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 2 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 3 & 1 & 0 & 0 & 0 & \cdots \\1 & 4 & 3 & 0 & 0 & 0 &\cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right).\end{displaymath} It is often the case that we work with ``generalized'' Riordan arrays, where we relax some of the defining conditions above. Thus for instance \cite{CMS} discusses the notion of the ``stretched'' Riordan array. In this note, we shall encounter ``vertically stretched'' arrays of the form $(g,h)$ where now $f_0=f_1=0$ with $f_2 \ne 0$. Such arrays are not invertible, but we may explore their left inversion. In this context, standard Riordan arrays as described above are called ``proper'' Riordan arrays. We note for instance that for any proper Riordan array $(g,f)$, its diagonal sums are just the row sums of the vertically stretched array $(g,xf)$ and hence have g.f. $g/(1-xf)$. The {\it Hankel transform} of a given sequence $A=\{a_0,a_1,a_2,...\}$ is the sequence of Hankel determinants $\{h_0, h_1, h_2,\ldots \}$ where $h_{n}=|a_{i+j}|_{i,j=0}^{n}$, i.e \begin{center} \begin{equation} \label{gen1} A=\{a_n\}_{n\in\mathbb N_0}\quad \rightarrow \quad h=\{h_n\}_{n\in\mathbb N_0}:\quad h_n=\left| \begin{array}{ccccc} a_0\ & a_1\ & \cdots & a_n & \\ a_1\ & a_2\ & & a_{n+1} \\ \vdots & & \ddots & \\ a_n\ & a_{n+1}\ & & a_{2n} \end{array} \right|. \end{equation} \end{center} The Hankel transform of a sequence $a_n$ and that of its binomial transform are equal. In the case that $a_n$ has g.f. $g(x)$ expressible in the form $$g(x)=\cfrac{a_0}{1-\alpha_0 x- \cfrac{\beta_1 x^2}{1-\alpha_1 x- \cfrac{\beta_2 x^2}{1-\alpha_2 x- \cfrac{\beta_3 x^2}{1-\alpha_3 x-\cdots}}}}$$ then we have \cite{Kratt, Kratt1, Wall} \begin{equation}h_n = a_0^n \beta_1^{n-1}\beta_2^{n-2}\cdots \beta_{n-1}^2\beta_n=a_0^n\prod_{k=1}^n \beta_k^{n-k}.\end{equation} Note that this independent from $\alpha_n$. We note that $\alpha_n$ and $\beta_n$ are in general not integers. Now let $H\left(\begin{array}{ccc} u_1&\cdots&u _k\\ v_1&\cdots& v_k\end{array}\right)$ be the determinant of Hankel type with $(i,j)$-th term $\mu_{u_i+v_j}$ \cite{JonesThron, Viennot}. Let $$\Delta_n=H\left(\begin{array}{cccc} 0&1&\cdots&n\\ 0&1&\cdots&n\end{array}\right),\qquad \Delta'=H\left(\begin{array}{ccccc} 0&1&\cdots&n-1&n\\ 0&1&\cdots&n-1&n+1\end{array}\right).$$ Then we have \begin{equation}\alpha_n=\frac{\Delta'_n}{\Delta_n}-\frac{\Delta'_{n-1}}{\Delta_{n-1}},\qquad \beta_n=\frac{\Delta_{n-2} \Delta_n}{\Delta_{n-1}^2}.\end{equation} An integer sequence $t_n$ is said to have the generalized Somos-$4$ property if there exists a pair of integers $(r, s)$ such that \begin{equation} t_n=\frac{r t_{n-1}t_{n-3}+s t_{n-2}^2}{t_{n-4}}, \quad n \ge 4.\end{equation} Alternatively (to avoid division by zero), we require that \begin{equation} t_n t_{n-4}=r t_{n-1}t_{n-3}+s t_{n-2}^2, \quad n \ge 4. \label{eq2} \end{equation} Note that it is sometimes useful to relax the integer condition on the pair $(r, s)$ and to allow them to be rational integers. Somos-$4$ sequences are most commonly associated with the $x$-coordinate of rational points on an elliptic curve \cite{Hone, Swart, Poorten}. The link between these sequences and Hankel transforms is made explicit in Theorem 7.1.1 of \cite{Swart}, for instance. Letting $[n]P$ denote the $n$-fold sum $P+ \cdots +P$ of points on an elliptic curve $E$, this result implies the following: if $P=(\bar{x},\bar{y})$ and $Q=(x_0,y_0)$ are two distinct non-singular rational points on an elliptic curve $E$, denote, for all $n \in \mathbb{Z}$ such that $Q+[n]P\neq \mathcal{O}$ (the point at infinity on $E$), by $(x_n,y_n)$ the coordinates of the point $Q+[n]P$. Then under these circumstances the numbers determined by $$s_n =(-1)^{\binom{n+1}{2}}(x_{n-1}-\bar{x})(x_{n-2}-\bar{x})^2\cdots(x_{1}-\bar{x})^{n-1}(x_0-\bar{x})^n s_0\left(\frac{s_0}{s_{-1}}\right)^n$$ are elements of a Somos 4 sequence (given appropriate $s_0,s_{-1}\neq 0$). We can re-write this as $$s_n=s_0\left(\frac{s_0}{s_{-1}}\right)^n\prod_{k=0}^{n-1} (\bar{x}-x_k)^{n-k}.$$ \section{The equation $a_n=\alpha a_{n-1}+\beta \sum_{k=0}^{n-1}a_k a_{n-1-k}, n>0, a_0=1$} In this section, we look in more detail at the solution to the equation (\ref{First_order}): $$ a_n = \begin{cases} 1, & \text{if $n=0$};\\ \alpha a_{n-1}+\beta \sum_{k=0}^{n-1}a_k a_{n-1-k}, & \text{if $n >0$.} \end{cases} $$ We have the following proposition: \begin{proposition} We let $a_n$ be a solution of the convolution recurrence $$ a_n = \begin{cases} 1, & \text{if $n=0$;}\\ \alpha a_{n-1}+\beta \sum_{k=0}^{n-1}a_k a_{n-1-k}, & \text{if $n >0$.} \end{cases} $$ Then the g.f. of $a_n$ is given by \begin{equation} g(x)=\frac{1}{1-\alpha x}c\left(\frac{\beta x}{(1-\alpha x)^2}\right).\end{equation} The g.f. $g(x)$ may be expressed in continued fraction form as follows: \begin{eqnarray*} g(x)&=&\cfrac{1}{1- \cfrac{(\alpha+\beta)x}{1- \cfrac{\beta x}{1- \cfrac{(\alpha+\beta)x}{1- \cfrac{\beta x}{1-\cdots}}}}}\\ &=&\cfrac{1}{1-\alpha x- \cfrac{\beta x}{1-\alpha x- \cfrac{\beta x}{1-\cdots}}}\\ &=&\cfrac{1}{1-(\alpha+\beta)x- \cfrac{\beta (\alpha+\beta)x^2}{1-(\alpha+2\beta)x- \cfrac{\beta (\alpha+\beta)x^2}{1-(\alpha+2\beta)x- \cfrac{\beta (\alpha+\beta)x^2}{1-\cdots}}}}.\end{eqnarray*} We have the following expressions for $a_n$: \begin{eqnarray*} a_n&=&\sum_{k=0}^n \binom{n+k}{2k}C_k\alpha^{n-k}\beta^k\\ &=&\sum_{k=0}^n \binom{2n-k}{k}C_{n-k}\alpha^k \beta^{n-k}\\ &=&\frac{1}{n}\sum_{k=0}^n \binom{n}{k}\binom{n}{k-1}\beta^{n-k}(\alpha+\beta)^k,n>0,a_0=1\\ &=&\frac{1}{n}\sum_{k=0}^n \binom{n}{k}\binom{n}{k+1}\beta^k(\alpha+\beta)^{n-k},n>0,a_0=1. \end{eqnarray*} In addition, we have \begin{equation} a_n=[x^{n+1}]\text{Rev}\frac{x(1-\beta x)}{1+\alpha x}.\end{equation} \end{proposition} \begin{proof} The g.f. $g(x)$ of the solution $a_n$ of equation (\ref{First_order}) satisfies the equation $$g(x)=1+\alpha x g(x)+\beta x g(x)^2.$$ Hence \begin{equation}\label{First_order_gf} g(x)=\frac{1-\alpha x-\sqrt{1-2x(\alpha+2 \beta)+\alpha^2 x^2}}{2\beta x}.\end{equation} Thus $$ g(x)=\frac{1}{1-\alpha x}c\left(\frac{\beta x}{(1-\alpha x)^2}\right).$$ Now the reversion of the expression $\frac{x(1-\beta x)}{1+\alpha x}$ is the solution $u=u(x)$ of the equation $$\frac{u(1-\beta u)}{1+\alpha u}=x.$$ We find that \begin{equation}\label{Rev} u(x)=\frac{1-\alpha x-\sqrt{1-2x(\alpha+2 \beta)+\alpha^2 x^2}}{2\beta}=xg(x).\end{equation} Thus $$a_n=[x^{n+1}]\text{Rev}\frac{x(1-\beta x)}{1+\alpha x}.$$ We deduce from the fact that \begin{eqnarray*} g(x)&=&\frac{1}{1-\alpha x}c\left(\frac{\beta x}{(1-\alpha x)^2}\right)\\ &=&\left(\frac{1}{1-\alpha x},\frac{\beta x}{(1-\alpha x)^2}\right)\cdot c(x) \end{eqnarray*} that $$a_n=\sum_{k=0}^n \binom{n+k}{2k}C_k\alpha^{n-k}\beta^k$$ and the other expressions follow. From the fact that $g(x)=\frac{1}{1-\alpha x}c\left(\frac{\beta x}{(1-\alpha x)^2}\right)$ we can infer that $$g(x)=\cfrac{1}{1-\alpha x- \cfrac{\beta x}{1-\alpha x- \cfrac{\beta x}{1-\cdots}}}.$$ The expression $$g(x)=\cfrac{1}{1- \cfrac{(\alpha+\beta)x}{1- \cfrac{\beta x}{1- \cfrac{(\alpha+\beta)x}{1- \cfrac{\beta x}{1-\cdots}}}}}$$ follows from the fact that the equation $$v=\cfrac{1}{1-\cfrac{(\alpha+\beta)x}{1-\beta x v}}$$ has solution $v=g(x)$. Finally standard contraction techniques \cite{Muir} for continued fractions allow us to transform this last expression to $$g(x)=\cfrac{1}{1-(\alpha+\beta)x- \cfrac{\beta (\alpha+\beta)x^2}{1-(\alpha+2\beta)x- \cfrac{\beta (\alpha+\beta)x^2}{1-(\alpha+2\beta)x- \cfrac{\beta (\alpha+\beta)x^2}{1-\cdots}}}}.$$ \end{proof} \begin{corollary} The Hankel transform of $a_n$ is given by $(\beta(\alpha+\beta))^{\binom{n+1}{2}}$. \end{corollary} \begin{corollary} The Hankel transform of $a_n$ is a $(\beta^3(\alpha+\beta)^3,0)$ Somos-$4$ sequence, and a $(0, \beta^4 (\alpha+\beta)^4)$ Somos $4$ sequence. \end{corollary} Notable examples of these sequences are the little Schr\"oder numbers \seqnum{A001003} ($\alpha=-1$, $\beta=2$), the Catalan numbers \seqnum{A000108} ($\alpha=0$, $\beta=1$), and the large Schr\"oder numbers \seqnum{A006318} ($\alpha=1$, $\beta=1$). \section{The equation $a_n=\alpha a_{n-1}+\beta a_{n-2}+\gamma \sum_{k=0}^{n-2}a_k a_{n-2-k}$.} In this section, we shall consider solutions to the equation \begin{equation*} a_n= \begin{cases} 1, & \text{if $n= 0$;}\\ \alpha, & \text{if $n = 1$;}\\ \alpha a_{n-1}+\beta a_{n-2}+\gamma \sum_{k=0}^{n-2} a_k a_{n-2-k}, & \text{if $n >1$.} \end{cases} \end{equation*} \begin{example}\label{Example_13} We take the example of $\alpha=\beta=\gamma=1$. In this case, we find that the solution to \begin{equation*} a_n= \begin{cases} 1, & \text{if $n= 0$;}\\ 1, & \text{if $n = 1$;}\\ a_{n-1}+a_{n-2}+ \sum_{k=0}^{n-2} a_k a_{n-2-k}, & \text{if $n >1$;} \end{cases} \end{equation*} is given by $$a_n=[x^n] \frac{1}{1-x-x^2}c\left(\frac{x^2}{(1-x-x^2)^2}\right)=[x^n]\frac{1}{1-x^2}m\left(\frac{x}{1-x^2}\right).$$ Thus $$a_n=\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n-k}{k} M_{n-2k}.$$ This is \seqnum{A128720}. We now observe the following. We have $$\frac{1}{1-x-x^2}c\left(\frac{x^2}{(1-x-x^2)^2}\right)=\frac{1-x-x^2-\sqrt{1-2x-5x^2+2x^3+x^4}}{2x^2}$$ from which we can deduce the following integral representation (using the Stieltjes transform) for $a_n$: $$a_n=\frac{1}{\pi}\int_{\frac{\sqrt{5}}{2}-\frac{1}{2}}^{\frac{3}{2}+\frac{\sqrt{13}}{2}} x^n \frac{\sqrt{-1-2x+5x^2+2x^3-x^4}}{2x}\,dx-\frac{1}{\pi}\int_{\frac{-\sqrt{5}}{2}-\frac{1}{2}}^{\frac{3}{2}-\frac{\sqrt{13}}{2}} x^n \frac{\sqrt{-1-2x+5x^2+2x^3-x^4}}{2x}\,dx$$ or $$a_n=\frac{1}{\pi}\int_{\frac{\sqrt{5}}{2}-\frac{1}{2}}^{\frac{3}{2}+\frac{\sqrt{13}}{2}} x^n \frac{\sqrt{-(1+3x-x^2)(1-x-x^2)}}{2x}\,dx-\frac{1}{\pi}\int_{\frac{-\sqrt{5}}{2}-\frac{1}{2}}^{\frac{3}{2}-\frac{\sqrt{13}}{2}} x^n \frac{\sqrt{-(1+3x-x^2)(1-x-x^2)}}{2x}\,dx.$$ We now observe that the Hankel transform $h_n$ of $a_n$ satisfies a $(1,3)$ Somos-$4$ relation: $$ h_n=\frac{h_{n-1}h_{n-3}+3 h_{n-2}^2}{h_{n-4}}.$$ In this case, we obtain the sequence $h_n$ that starts $$1, 2, 5, 17, 109, 706, 9529, 149057, 3464585, 141172802,\ldots,$$ which is \seqnum{A174168}. \end{example} In the general case, we have the following proposition: \begin{proposition} We let $a_n$ be the solution of the convolution recurrence \begin{equation*} a_n= \begin{cases} 1, & \text{if $n= 0$};\\ \alpha, & \text{if $n = 1$};\\ \alpha a_{n-1}+\beta a_{n-2}+\gamma \sum_{k=0}^{n-2} a_k a_{n-2-k}, & \text{if $n>1$.} \end{cases} \end{equation*} Then the g.f. $g(x)$ of $a_n$ is given by $$g(x)=\frac{1}{1-\alpha x - \beta x^2}c\left(\frac{\gamma x^2}{(1-\alpha x-\beta x^2)^2}\right).$$ The general term of the sequence $a_n$ is given by \begin{equation}\label{Gen_Term} a_n=\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \sum_{j=0}^{n-2k} \binom{2k+j}{j}\binom{j}{n-2k-j}\alpha^{2k+2j-n}\beta^{n-2k-j}\gamma^k C_k. \end{equation} The g.f. $g(x)$ of $a_n$ has the continued fraction expansion \begin{equation}\label{CF_eq}g(x)=\cfrac{1}{1-\alpha x - \beta x^2 - \cfrac{\gamma x^2}{1-\alpha x - \beta x^2 - \cfrac{\gamma x^2}{1-\cdots}}}.\end{equation} \end{proposition} \begin{proof} The g.f. $g(x)$ of the solution $a_n$ of equation (\ref{Second_order}) satisfies the equation $$g(x)=1+\alpha xg(x) +\beta x^2 g(x)+\gamma x^2 g(x)^2.$$ Solving this equation for $g(x)$ we find that $$g(x)=\frac{1-\alpha x-\beta x^2-\sqrt{1-2\alpha x+(\alpha^2-2\beta - 4 \gamma)x^2+2\alpha \beta x^3+\beta^2 x^4}}{2 \gamma x^2},$$ which is equal to $$\frac{1}{1-\alpha x - \beta x^2}c\left(\frac{\gamma x^2}{(1-\alpha x-\beta x^2)^2}\right).$$ Now $$\frac{1}{1-\alpha x - \beta x^2}c\left(\frac{\gamma x^2}{(1-\alpha x-\beta x^2)^2}\right)=\left(\frac{1}{1-\alpha x - \beta x^2},\frac{\gamma x^2}{(1-\alpha x-\beta x^2)^2}\right)\cdot c(x),$$ where the general term of the stretched Riordan array $\left(\frac{1}{1-\alpha x - \beta x^2},\frac{\gamma x^2}{(1-\alpha x-\beta x^2)^2}\right)$ is given by $$\sum_{j=0}^{n-2k} \binom{2k+j}{j}\binom{j}{n-2k-j}\alpha^{2k+2j-n}\beta^{n-2k-j}\gamma^k.$$ The second assertion follows from this. The continued fraction expansion follows directly from $$g(x)=\frac{1}{1-\alpha x - \beta x^2}c\left(\frac{\gamma x^2}{(1-\alpha x-\beta x^2)^2}\right)$$ and the form of the continued fraction expansion (Eq. (\ref{Cat_CF})) for $c(x)$. \end{proof} \begin{corollary} If $\beta=0$, then we have $$a_n=\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor}\binom{n}{2k}\alpha^{n-2k}\gamma^k C_k.$$ \end{corollary} \begin{proof} This follows since in this case, we have $$g(x)=\frac{1}{1-\alpha x} c\left(\frac{\gamma x^2}{(1-\alpha x)^2}\right)$$ and the fact that the general element of the Riordan array $\left(\frac{1}{1-\alpha x},\frac{x}{(1-\alpha x)^2}\right)$ is $\binom{n+k}{2k}\alpha^{n-k}$. \end{proof} Note that in this case, the Hankel transform of $a_n$ is $\gamma^{\binom{n+1}{2}}$. We also have, in this case, $$a_n=[x^{n+1}]\text{Rev}\frac{x}{1+\alpha x + \gamma x^2}.$$ \begin{corollary} If $\alpha=0$, then we have $$a_n=\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor}\binom{\frac{n+2k}{2}}{2k}\frac{1+(-1)^{n-2k}}{2}\beta^{\frac{n-2k}{2}}\gamma^k C_k.$$ \end{corollary} \begin{proof} In this case, we have $$a_n=\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \sum_{j=0}^{n-2k} \binom{2k+j}{j}\binom{j}{n-2k-j}0^{2k+2j-n}\beta^{n-2k-j}\gamma^k C_k.$$ Thus the surviving element of the $j$-summation occurs when $j=\frac{n-2k}{2}$. \end{proof} Note that when $\alpha=0$, we have $$g(x)=\frac{1}{1-\beta x^2}c\left(\frac{\gamma x^2}{(1-\beta x^2)^2}\right).$$ Thus $a_n$ in this case is an aerated sequence. \section{A Somos-$4$ conjecture} We can now state the following conjecture. \begin{conjecture} Let $a_n$ be the solution to the second order convolution recurrence \begin{equation*} a_n= \begin{cases} 1, & \text{if $n= 0$};\\ \alpha, & \text{if $n = 1$};\\ \alpha a_{n-1}+\beta a_{n-2}+\gamma \sum_{k=0}^{n-2} a_k a_{n-2-k}, & \text{if $n >1$;} \end{cases} \end{equation*} and let $h_n$ be the Hankel transform of $a_n$. Then $h_n$ is a $(\alpha^2 \gamma^2, \gamma^2(\gamma^2+\gamma(2\beta - \alpha^2)+\beta^2))$ Somos-$4$ sequence. \end{conjecture} \begin{example} We return to the Example \ref{Example_13}, where $\alpha=\beta=\gamma=1$. A simple calculation shows that then $\alpha^2 \gamma^2=1$ and $\gamma^2(\gamma^2+\gamma(2\beta - \alpha^2)+\beta^2))$=3. \end{example} \begin{example} We take $\alpha=1$, $\beta=0$ and $\gamma=-1$. $a_n$ then begins $$1, 1, 0, -2, -3, 1, 11, 15, -13, -77, -86,\ldots$$ which is a variant of the sequence \seqnum{A007440}, derived from the series reversion of the g.f. of the Fibonacci numbers. Then the Hankel transform of $a_n$ is $h_n=(-1)^{\binom{n+1}{2}}$, which is a (trivial) $(1,2)$ Somos-$4$ sequence. \end{example} \begin{example} We take $\alpha=1$, $\beta=2$ and $\gamma=-1$. Then the sequence $a_n$ begins $$1, 1, 2, 2, 1, -3, -11, -21, -23, 7, 104,\ldots, $$ and has a Hankel transform $h_n$ which begins $$1, 1, -3, -1, 17, -49, -209, -1249, 8739, -26399, -888577,\ldots$$ By the conjecture, $h_n$ is a $(1,2)$ Somos-$4$ sequence. \end{example} The following table gives a small sample of $(\alpha, \beta, \gamma)$ values and corresponding Somos-$4$ $(r,s)$ values. \begin{center}\begin{tabular}{|c|c|c|c|} \hline $\alpha$ & $\beta$ & $\gamma$ & $(r,s)$ \\ \hline $2$ & $-2$ &$-1$& $(4,13)$ \\ \hline $-1$ & $-2$ &$-1$& $(1,10)$ \\ \hline $-1$ & $0$ &$-1$& $(1,2)$ \\ \hline $1$ & $2$ &$-1$& $(1,2)$ \\ \hline $3$ & $-3$ &$-1$& $(9,25)$ \\ \hline $3$ & $3$ &$1$& $(9,7)$ \\ \hline $-2$ & $-2$ &$1$& $(4,-3)$ \\ \hline $1$ & $-1$ &$1$& $(1,-1)$ \\ \hline $1$ & $1$ &$-1$& $(1,1)$ \\ \hline $1$ & $3$ &$-1$& $(1,5)$ \\ \hline $1$ & $2$ &$-2$& $(4,8)$ \\ \hline $1$ & $0$ &$2$& $(4,8)$ \\ \hline $1$ & $2$ &$1$& $(1,8)$ \\ \hline $-1$ & $-3$ &$1$& $(1,3)$ \\ \hline $-1$ & $1$ &$1$& $(1,3)$ \\ \hline $1$ & $-1$ &$1$& $(1,-1)$ \\ \hline $1$ & $-1$ &$1$& $(1,-1)$ \\ \hline \end{tabular}\end{center} An approach to the proof of this conjecture would be to employ the methods of \cite{BRP, CRI}. As indicated by the form of the density functions in Example \ref{Example_13}, this would lead to an excursion into the area of elliptic orthogonal polynomials. This is outside the scope of the current study. An alternative approach would be to characterize the Hankel transforms of sequences with generating functions of the form given in Eq. (\ref{CF_eq}). \section{Acknowledgements} The author would like to thank the anonymous referees for their careful reading and cogent suggestions which have hopefully led to clearer paper. \begin{thebibliography}{9} \bibitem{BRP} P. Barry, P. Rajkovi\'c \& M. Petkovi\'c, An application of Sobolev orthogonal polynomials to the computation of a special Hankel determinant, in W. Gautschi, G. Rassias, and M. Themistocles, eds., \emph{Approximation and Computation}, Springer, 2010. \bibitem{CMS} C. Corsani, D. Merlini, R. Sprugnoli, Left-inversion of combinatorial sums, \emph{Discrete Math.} \textbf{180} (1998), 107--122. \bibitem{CRI} A. Cvetkovi\'c, P. Rajkovi\'c and M. Ivkovi\'c, Catalan numbers, the Hankel transform and Fibonacci numbers, \emph{J. Integer Sequences}, {\bf 5} (2002), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Ivkovic/ivkovic3.html}{Article 02.1.3}. \bibitem{Hone} A. N. W. Hone, Elliptic curves and quadratic recurrence sequences, \emph{ Bull. London Math. Soc.}, {\bf 37} (2006), 161--171. \bibitem{JonesThron} W. Jones and W. Thron, \emph{Continued Fractions: Analytic Theory and Applications}, Vol.\ 11 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2009. \bibitem{Kratt1} C. Krattenthaler, Advanced Determinant Calculus, available electronically at \href{http://arxiv.org/PS_cache/math/pdf/9902/9902004.pdf}{\tt http://arxiv.org/PS\_cache/math/pdf/9902/9902004.pdf}, 2006. \bibitem{Kratt} C. Krattenthaler, Advanced determinant calculus: a complement, {\it Linear Algebra Appl.} \textbf{411} (2005), 68--166. \bibitem{Layman} J. W. Layman, The Hankel Transform and some of its properties, \emph{J. Integer Sequences}, {\bf 4} (2001), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html}{Article 01.1.5}. \bibitem{Merlini_MC} D. Merlini, R. Sprugnoli and M.~C. Verri, The method of coefficients, \emph{Amer. Math. Monthly}, \textbf{114} (2007), 40--57. \bibitem{Muir} T. Muir, The condensation of continuants, \emph{Proc. Edinburgh Math. Soc.} \textbf{23} (1904), 35--39. \bibitem{SGWW} L. W. Shapiro, S. Getu, W-J. Woan, and L. C. Woodson, The Riordan Group, \emph{Discr. Appl. Math.} \textbf{34} (1991), 229--239. \bibitem{SL1} N. J. A.~Sloane, \emph{The On-Line Encyclopedia of Integer Sequences}. Published electronically at \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\char'176njas/sequences/}, 2010. \bibitem{SL2} N. J. A.~Sloane, The On-Line Encyclopedia of Integer Sequences, \emph{Notices Amer. Math. Soc.} \textbf{50} (2003), 912--915. \bibitem{Spru} R. Sprugnoli, Riordan arrays and combinatorial sums, \emph{Discrete Math.} \textbf{132} (1994), 267--290. \bibitem{Swart} C.~S.~Swart, Elliptic curves and related sequences, PhD Thesis, Royal Holloway, University of London, 2003. \bibitem{Poorten} Alfred J. van der Poorten, Elliptic curves and continued fractions, {\it J. Integer Sequences\/} {\bf 8} (2005), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Poorten/vdp40.html}{Article 05.2.5}. \bibitem{Viennot} G. Viennot, A combinatorial theory for general orthogonal polynomials with extensions and applications, in: {\it Polynomes Orthogonaux et Applications}, Lecture Notes in Mathematics, Vol.\ 1171, Springer, 1985, pp.\ 139--157. \bibitem{Wall} H.~S. Wall, \emph{Analytic Theory of Continued Fractions}, AMS Chelsea Publishing, 2000. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B83; Secondary 11B37, 11C20, 15B05, 15B36. \noindent \emph{Keywords:} Integer sequence, linear recurrence, Riordan arrays, continued fraction, Hankel transform, Somos sequence. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000007}, \seqnum{A000045}, \seqnum{A000108}, \seqnum{A001003}, \seqnum{A001006}, \seqnum{A006318}, \seqnum{A007318}, \seqnum{A007440}, \seqnum{A128720}, and \seqnum{A174168}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received May 10 2010; revised version received June 23 2010. Published in {\it Journal of Integer Sequences}, July 9 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}