\documentclass[12pt,reqno]{amsart}

\usepackage[usenames]{color}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{amsthm,amssymb,latexsym}
\usepackage{psfig,epsf}
\usepackage{float,color}

\setlength{\textwidth}{5.9in}
\setlength{\oddsidemargin}{.4in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.6in}

\setlength{\parskip}{2mm plus 2pt minus 1pt}
 \jot 3mm


\newcommand{\bega}{\begin{eqnarray}}
\newcommand{\ega}{\end{eqnarray}}
\newcommand{\bb}{\begin{equation}}
\newcommand{\ee}{\end{equation}}

\newtheorem{te}{Theorem}
\newtheorem{lema}{Lemma}

\allowdisplaybreaks[1]
\begin{document}

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

\vskip .4in

\begin{center}
{\Large Catalan Numbers, the Hankel Transform,\\ and Fibonacci Numbers}
\end{center}

\vskip .4in

\begin{center}
Aleksandar Cvetkovi\'c \\
Faculty of Electrical Engineering\\
University of Ni\v s, Yugoslavia\\
e-mail: {\tt aca@elfak.ni.ac.yu}\\
\ \\
Predrag Rajkovi\'c\\
Faculty of Mechanical Engineering\\
University of Ni\v s, Yugoslavia\\
e-mail: {\tt nispeca@yahoo.com} \\
\ \\
Milo\v{s} Ivkovi\'c \\
IMECC-UNICAMP, C.P. 6065, 13083-970 \\
  Campinas-SP, Brazil \\
e-mail: {\tt milos@ime.unicamp.br}
\end{center}


%\maketitle

\vskip .4in

\begin{center}
{\bf Abstract}
\end{center}

{\em We  prove that the Hankel transformation of a sequence whose
elements are the sums of two adjacent Catalan numbers is a
subsequence of the Fibonacci numbers. This is done by finding the
explicit form for the coefficients in the three-term recurrence
relation that  the corresponding orthogonal polynomials satisfy.}

\vskip .4in

 \section{Introduction}

 Let $A=\{a_0,a_1,a_2,...\}$ be a sequence of
real numbers. The Hankel matrix generated by $A$ is the infinite
matrix $H=[h_{i,j}],$ where $h_{i,j}=a_{i+j-2},$ i.e.,

\begin{center}
\[
 H=\left[
\begin{array}{ccccc}
 a_0\ & a_1\  & a_2\  & a_3\  & ... \\
 a_1\ & a_2\  & a_3\  & a_4\  & ... \\
 a_2\ & a_3\  & a_4\  & a_5\  & ... \\
 a_3\ & a_4\  & a_5\  & a_6\  & ... \\
 a_4\ & a_5\  & a_6\  & a_7\   & ... \\
\vdots & \vdots & \vdots & \vdots & \ddots
\end{array}
\right]
\]

\end{center}

The {\it Hankel matrix $H_n$ of order n} is the upper-left $n
\times n$ submatrix
of $H$ and the {\it Hankel determinant of order n} of $A$,
denoted by $h_n$, is the determinant of the
corresponding Hankel matrix.

For a given sequence  $A=\{a_0,a_1,a_2,...\},$ the {\it Hankel transform} of $A$ is
the corresponding sequence of Hankel determinants $\{h_0, h_1, h_2,\dots \}$
(see Layman \cite{layman}).

The elements of the sequence in which we are interested
(\htmladdnormallink{A005807}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005807}
 of the On-Line Encyclopedia of Integer Sequences (EIS) \cite{eis}, also INRIA \cite{inria}) are the sums of two
  adjacent Catalan numbers:
\begin{eqnarray*}
  a_n&=&c(n)+c(n+1)=
\frac1{n+1} {2n \choose n}+\frac1{n+2} {2n+2 \choose n+1} \\
&=&\frac{(2n)!(5n+4)}{n!(n+2)!}  \qquad (n=0,1,2,\ldots).
\end{eqnarray*}

This sequence starts as follows:
$$2,\quad 3,\quad 7,\quad 19,\quad 56,\quad 174 \ldots$$

 In a comment stored with sequence
 \htmladdnormallink{A001906}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001906}
  Layman conjectured that the Hankel transformation of
 $\{a_n\}_{n \geq 0}$  equals the sequence
 \htmladdnormallink{A001906}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001906}, i.e., the
bisection of Fibonacci sequence. In this paper we shall prove a
slight generalization of Layman's conjecture.

The generating function $G(x)$ for the sequence $\{a_n\}_{n \geq
0}$ is given by
\bb
 \label{gen}
G(x)=\sum_{n=0}^{\infty}a_n x^n=\frac1x \left(
\frac{(1-\sqrt{1-4x})(1+x)}{2x}-1 \right)
 \ee

It is known (for example, see Krattenthaler \cite{kratt}) that the
Hankel determinant $h_n$ of  order $n$ of the sequence
$\{a_n\}_{n\geq 0}$ equals
 \bb
 \label{formula}
 h_n=a_0^n \beta_1^{n-1} \beta_2^{n-2} \cdots \beta_{n-2}^2 \beta_{n-1},
 \ee
  where $ \{ \beta_n \}_{n \geq 1}$ is the  sequence given by:

\bb \label{bes} G(x)=\sum_{n=0}^{\infty}a_n x^n=
\frac{a_0}{\displaystyle 1+\alpha_0x -\frac{\displaystyle
\beta_1x^2}{1+\alpha_1x-\frac{\displaystyle
\beta_2x^2}{\displaystyle 1+\alpha_2x- \cdots}}} \ee

The sequences $ \{ \alpha_n \}_{n \geq 0}$ and $ \{ \beta_n \}_{n
\geq 1}$ are the coefficients in the recurrence relation

$$ P_{n+1}(x)=(x-\alpha_n)P_n(x) -\beta_nP_{n-1}(x)$$

 \noindent where  $\{P_n(x)\}_{n \geq 0}$ is the monic polynomial sequence  orthogonal with respect to
  the functional $L$ determined by

\bb \label{funk}
 L[x^n]=a_n \quad (n=0,1,2,\ldots). \ee

In the next section this functional is  constructed and a
theorem concerning  the polynomials $\{P_n(x)\}_{n \geq 0}$ and the
sequences $ \{ \alpha_n \}_{n \geq 0}$ and $ \{ \beta_n \}_{n
\geq 1}$ is proved.

\section{ Main Theorem }

We would like  to express $L[f]$ in the form:

 $$ L[f(x)]=\int_R f(x) d\psi (x),$$
\noindent where $\psi (x)$ is a distribution, or, even more, to
find the weight function $w(x)$ such that $w(x)=\psi'(x).$

 Denote by $F(z)$ the function
  $$F(z)=\sum_{k=0}^{\infty} a_k z^{-k-1},$$
 From the generating function (\ref{gen}), we have: \bb
 F(z)=z^{-1}\ G\bigl(z^{-1} )=\frac1{2} \left\{ z-1-(z+1)\sqrt{1-\frac4{z}} \right\}.
\ee
 From the theory of distribution functions (see Chihara
  \cite{chihara}), we have Stieltjes inversion function
  \bb
  \psi (t) - \psi (s) =-\frac1{\pi} \int_s^t \Im F(x+i y) dx.
  \ee
  Since $F(\bar z)=\overline{F(z)},$ it can be written in the form
\bb
     \psi (t) - \psi (0) =-\frac1{2 \pi i} \lim_{y\to 0^+}\int_0^t
     \Bigl[F(x+i y) - F(x-i y)\Bigr] dx.
     \ee
Knowing that 
\begin{eqnarray*}
 \int_0^t F(x+a) dx = \frac{1}{4}
   \left\{
   a^2\ \sqrt{1-\frac4{a}}-2t+2at+t^2 -(a+t)^2
   \sqrt{1-\frac{4}{a+t}} \right\} \\
   - 2\log \Bigl( -2+a+a\ \sqrt{1-\frac4{a}} \Bigr)
   + 2\log \Bigl(-2+a+t+(a+t)\ \sqrt{1-\frac4{a+t}} \Bigr),
\end{eqnarray*}
     we find  the distribution function
 $$\psi (t)=
 \left\{
 \begin{array}{lr}
      \frac1{4\pi} \left\{t\ \sqrt{t(4-t)} - 8 \Bigl(\pi -\arctan
\frac{\sqrt{(4-t)t}}{2-t} \Bigr)\right\},& 0\leq t<2; \\
\frac{1}{4\pi} \left\{t\ \sqrt{t(4-t)} - 8 \arctan
\frac{\sqrt{(4-t)t}}{t-2}
      \right\};
        & 2\leq t\leq 4.
           \end{array}
           \right. $$

After differentiation of $\psi (t)$ and simplification of the
resulting expression, we finally have:
  \bb
  w(x)=\frac1{2} (x+1)\sqrt{\frac4{x}-1}, \quad x\in (0,4).
  \ee
In this way, we  obtained  the positive-definite $L$ that
satisfies (\ref{funk})
and  proved that the corresponding orthogonal polynomial sequence
exists. We have
\begin{te}
\label{main}  The monic polynomial sequence $\{P_n(x)\}$
 orthogonal with  respect to the linear functional
\bb L (f):= \frac1{2\pi} \int_0^4 f(x)
 (x+1)\sqrt{\frac4{x}-1}dx,
\ee
  satisfies the three-term recurrence relation
\bb
 P_{n+1}(x)=(x-\alpha_n)P_n(x) -\beta_nP_{n-1}(x),
 \ee
with \bb \alpha_n=2-\frac1{F_{2n+1}F_{2n+3}}, \quad
\beta_n=1+\frac1{F_{2n+1}^2},
 \qquad k \ge 0
\ee where $F_i$ is the i-th Fibonacci number.
\end{te}

 {\bf  Example 1.} The first members of
this sequence are:
 \begin{eqnarray*}
 P_0(x)&=&1;\\ \
 P_1(x)&=&x-\frac32;\\
P_2(x)&=&x^2 - \frac{17}5 x +\frac8{5}; \\ P_3(x)&=&x^3 -
\frac{70}{13} x^2+\frac{95}{13} x -\frac{21}{13};\\
 P_4(x)&=&x^4 -
\frac{251}{34} x^3 + \frac{290}{17} x^2-\frac{435}{34} x
+\frac{55}{34}.
\end{eqnarray*}
Notice  that   $P_n(0)=(-1)^nF_{2n+2}/F_{2n+1}.$



{\bf Proof of Theorem 1.} Denoting by $W_n(x)=P^{(1/2,-1/2)}_{n}(x)\ (n \ge 0)$ a special
Jacobi polynomial, which is also known as {\it the Chebyshev
polynomial of the fourth kind}.

\noindent The sequence
of these polynomials is orthogonal with respect to
$p^{(1/2,-1/2)}(x)=(1-x)^{1/2}(1+x)^{-1/2}$ on the interval
$(-1,1).$
 These polynomials can be expressed (Szeg\" o \cite{seg}) by
$$W_n(\cos \theta
)= \frac{\sin (n+\frac12)\theta}{2^n \sin \frac12 \theta}.
$$


\noindent and satisfy the three-term recurrence relation (Chihara
\cite{chihara}):

$$W_{n+1}(x)=(x -\alpha^*_n) \ W_n(x) - \beta^*_n W_{n-1}(x) \quad
(n=0,1,\ldots),$$ $$W_{-1}(x)=0, \quad W_0(x)=1, $$
  where $$\alpha^*_0=-\frac12,\quad \alpha^*_n=0,
\qquad \beta^*_0=\pi, \quad \beta^*_n=\frac14 \qquad (n \ge 1). $$

If we use the weight function $\hat p(t)=(t-c)p^{(1/2,-1/2)}(t),$
then the corresponding coefficients $\hat \alpha_n$ and $\hat
\beta_n$ can be evaluated as follows (see, for  example,  Gautschi
\cite{gautschi})
 \bb
 \hat \alpha_n = c- \frac{W_{n+1}(c)}{W_n(c)}
-\beta^*_{n+1} \frac{W_{n}(c)}{W_{n+1}(c)}, \ee
 \bb
  \hat \beta_n =\beta^*_n \frac{W_{n-1}(c)W_{n+1}(c)}{W^2_n(c)} ,\quad n\in \mathbb N.
\ee
Here, we use $c=-3/2$ and $\hat
p(x)=(x+3/2)(1-x)^{1/2}(1+x)^{-1/2}.$

If we write $\lambda_n=W_n(-3/2)$ then, using the three-term
recurrence relation for $W_n(x)$, we have
$$4\lambda_{n+1} + 6\lambda_n + \lambda_{n-1}=0,$$
with initial values
$\lambda_0=1,\quad \lambda_1=-1.$

So, we find
 $$ \lambda_n=W_n(-3/2)=\frac{(-1)^n}{2 \sqrt5 \
4^n}\left\{(\sqrt5+1)(3+\sqrt5)^n+(\sqrt5-1)(3-\sqrt5)^n\right\}.$$

 Denoting by
\bb \phi=\frac{1+\sqrt{5}}{2},\qquad
\overline{\phi}=\frac{1-\sqrt{5}}{2} \ee
the golden section numbers, we can write:
 \bb
  \lambda_n=W_n(-3/2)=\frac{(-1)^n}{ \sqrt5 \
2^n}(\phi^{2n+1}-\overline{\phi}^{2n+1})=\frac{(-1)^n}{2^n}F_{2n+1}.
\ee

In order to simplify further algebraic manipulations
we shall use
\bb
 \label{neparni}
  F_{2n-1}F_{2n+3}=F_{2n+1}^2+1
 \ee
This formula
  is a special case
of the identity (Vajda \cite{vajda}):
\bb \label{opsti}
G(n+i)H(n+k)-G(n)H(n+i-k)=(-1)^n(G(i)H(k)-G(0)H(i+k)) \ee
where $G$ and $H$ are sequences that satisfy the same recurrence
relation as the Fibonacci numbers  with possibly different
initial conditions. However, we take both $G$ and $H$ to be the
Fibonacci numbers and $n \rightarrow 2n+1$, $i=2, k=-2$.

Now
 \bega
 \hat \beta_n &=& \frac14 \frac{\lambda_{n-1}\lambda_{n+1}}{\lambda^2_n}
 =\frac14 \frac{F_{2n-1}F_{2n+3}}{F^2_{2n+1}} \nonumber\\
&=&\frac14 \left \{1+ \frac1{F_{2n+1}^2} \right \}
 \ega
and
 \begin{eqnarray*}
  \hat \alpha_n &=& -\frac32- \frac{\lambda_{n+1}}{\lambda_n}
-\frac14 \frac{\lambda_n}{\lambda_{n+1}}\\
&=& \frac{-3F_{2n+1}F_{2n+3}+F^2_{2n+3}+F^2_{2n+1}}{2F_{2n+1}F_{2n+3}}\\
 &=&\frac{F_{2n+2}^2-F_{2n+1}F_{2n+3}}{2F_{2n+1}F_{2n+3}}\\
&=&-\frac{1}{2F_{2n+1}F_{2n+3}}.
\end{eqnarray*}

If  a new weight function $p(x)$ is introduced by
$$p(x)=\hat p(ax+b)$$
then we have
$$\alpha_n= \frac{\hat\alpha_n-b}{a}, \qquad
\beta_n=\frac{\hat\beta_n}{a^2}\qquad (n\geq 0).$$
 Now, by using $x\mapsto x/2-1,$ i.e., $a=1/2$ and $b=-1,$ we have
the wanted weight  function
$$w(x)=\hat p(\frac x2-1)=\frac12 (x+1)\sqrt{\frac{4-x}{x}}.$$

Thus
 \bb
 \alpha_n =2-\frac{5}
 {(\phi^{2n+1}-\overline{\phi}^{2n+1})
(\phi^{2n+3}-\overline{\phi}^{2n+3})}
 =2-\frac1{F_{2n+1}F_{2n+3}}
\ee
 and
 \bb
  \beta_n = 1+ \frac5{(\phi^{2n+1}-\overline{\phi}^{2n+1})^2} =1+\frac1{F_{2n+1}^2}
   \ee
  finishing the proof of (\ref{main}) .$\square$

\section{Layman's conjecture}

By making use of  (\ref{formula}) we have that:

\bb \label{nesredjeni}
h_n=a_0^n\left(1+\frac1{F_3^2}\right)^{n-1}\left(1+\frac1{F_5^2}\right)^{n-2}\!\!\cdots\left(1+\frac1{F_{2n-1}^2}\right)
\ee


 Using (\ref{neparni}) we can write (\ref{nesredjeni}) as:
 \bb
 h_n=a_0^n\left(\frac{F_1F_5}{F_3^2}\right)^{n-1}\!\!\left(\frac{F_3F_7}{F_5^2}\right)^{n-2}\!\!\left(\frac{F_5F_9}{F_7^2}\right)^{n-3}\!\!\cdots \frac{F_{2n-3}F_{2n+1}}{F_{2n-1}^2}
\ee

Since $a_0=2=F_3$ the corresponding factors cancel, therefore:
 $$h_n=F_{2n+1} \qquad \qquad (n \geq 0),$$
thus proving  that Hankel transform of
\htmladdnormallink{A005807}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005807}
equals
\htmladdnormallink{A001519}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001519}
-sequence of Fibonacci numbers with odd indices.

As we have mentioned in the introduction, Layman observed that
the Hankel transform of
\htmladdnormallink{A005807}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005807}
equals
\htmladdnormallink{A001906}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001906}
-sequence of Fibonacci numbers with even indices. This sequence is
obtained if we start the Hankel matrix from $a_1=3$, i.e., determinants
will have $a_1$ on the  position $(1,1)$.

The proof of this fact is almost identical with the proof presented
here, and so we do not include it.
 Notice that now we construct $ L[x^n]=a_{n+1}$ and that $a_1=3=F_4$; in
(\ref{opsti}) we take $n \rightarrow 2n$. We also use the easily
provable fact
  $P_n(0)=(-1)^nF_{2n+2}/F_{2n+1}$ (see Example 1).


 Finally we mention that,
following Layman \cite{layman}, it is known that the Hankel
transform is invariant with the respect to the Binomial and Invert
transform, so all the sequences obtained from
\htmladdnormallink{A005807}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005807}
using these two transformations have the Hankel transform shown
here.




\begin{thebibliography}{20}

\bibitem{chihara}
T. S. Chihara,  {\it An Introduction to Orthogonal Polynomials},
Gordon and Breach, New York, 1978.

 \bibitem{gautschi} W. Gautschi,  Orthogonal polynomials:
applications and computations, in {\it  Acta Numerica, 1996},
Cambridge University Press, 1996, pp.\ 45--119.

\bibitem{inria} INRIA Algorithms Project,
Encyclopedia of Combinatorial Structures, \\
at  \htmladdnormallink{http://algo.inria.fr/bin/encyclopedia?Search=ESCnb\&argseach=431}{http://algo.inria.fr/bin/encyclopedia?Search=ESCnb\&argseach=431}.

\bibitem{kratt} C. Krattenthaler, Advanced Determinant
Calculus,\\at
\htmladdnormallink{http://www.mat.univie.ac.at/People/kratt/artikel/detsurv.html}{http://www.mat.univie.ac.at/People/kratt/artikel/detsurv.html}.

\bibitem{layman}
J. W. Layman, The Hankel Transform and Some of its Properties,
{\em \htmladdnormallink{Journal of Integer Sequences, Article
01.1.5,  Volume 4, 2001.}
{http://www.research.att.com/~njas/sequences/JIS/index.html\#P01.1.5}}

\bibitem{PW}
P. Peart and W. J. Woan, Generating functions via Hankel and
Stieltjes matrices, {\em \htmladdnormallink{Journal of Integer
Sequences, Article 00.2.1, Issue 2, Volume 3, 2000.}
{http://www.research.att.com/~njas/sequences/JIS/index.html\#P00.2.1}}

\bibitem{woan}
 W. J. Woan,  Hankel Matrices and Lattice Paths, {\em \htmladdnormallink{Journal of Integer Sequences,
Article 01.1.2,  Volume 4, 2001.}
{http://www.research.att.com/~njas/sequences/JIS/index.html\#P01.1.2}}

\bibitem{sa3} J. P. O. Santos and M. Ivkovi\'{c},  Fibonacci
numbers and partitions,
 {\it Fibonacci Quarterly}, to appear.

\bibitem{seg}G. Szeg\" o, {\it Orthogonal Polynomials},
 AMS, 4th.\ ed., Vol.\ 23 (Colloquium publications), 1975.

\bibitem{eis}
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
Published electronically at \\
\htmladdnormallink{http://www.research.att.com/$\sim$njas/sequences/}{http://www.research.att.com/~njas/sequences/}.

\bibitem{tosic} R. Tosi\'c, {Kombinatorika} (in Serbian)
Univerzitet u Novom Sadu (1999), Novi Sad.

\bibitem{vajda} S. Vajda,
{\it Fibonacci and Lucas numbers, and the Golden Section: Theory and Applications},
Halsted Press, 1989.

\bibitem{z1} D. Zeilberger and T. Amdeberhan, DODGSON: A Maple
package for conjecturing and proving determinant identities by
Dodgson's condensation method,\\
at \htmladdnormallink{http://astro.ocis.temple.edu/~doron/programs.html}{http://astro.ocis.temple.edu/~doron/programs.htm}.

\end{thebibliography}


\vspace*{+.5in}
\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
{\small
(Mentions sequences
\seqnum{A005807}
\seqnum{A001906}
\seqnum{A001519}.)
}

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Received April 8, 2002;
revised version received May 14, 2002.
Published in Journal of Integer Sequences May 14, 2002.

\centerline{\rule{6.5in}{.01in}}

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

\centerline{\rule{6.5in}{.01in}}


\end{document}










