\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}