Catalan Numbers, the Hankel Transform, and Fibonacci Numbers

Aleksandar Cvetković Faculty of Electrical Engineering University of Niš, Yugoslavia

                      e-mail: aca@elfak.ni.ac.yu

Predrag Rajković Faculty of Mechanical Engineering University of Niš, Yugoslavia

                      e-mail: nispeca@yahoo.com

Miloš Ivković IMECC-UNICAMP, C.P. 6065, 13083-970 Campinas-SP, Brazil

                     e-mail: milos@ime.unicamp.br

Abstract

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.

1. 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.,

H = [ \begin{matrix}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} & ... \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ]

The Hankel matrix H_{n} of order n is the upper-left n × n submatrix of H and the 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 Hankel transform of A is the corresponding sequence of Hankel determinants {h_{0}, h_{1}, h_{2}, … } (see Layman [5]).

The elements of the sequence in which we are interested (A005807 of the On-Line Encyclopedia of Integer Sequences (EIS) [10], also INRIA [3]) are the sums of two adjacent Catalan numbers:

a_{n} = c(n) + c(n + 1) = \frac{1}{n + 1}\binom{2n}{n} + \frac{1}{n + 2}\binom{2n + 2}{n + 1}
= \frac{(2n)!(5n + 4)}{n!(n + 2)!}  (n = 0, 1, 2, …).

This sequence starts as follows:

2, 3, 7, 19, 56, 174 …

In a comment stored with sequence A001906 Layman conjectured that the Hankel transformation of {a_{n}}_{n≥0} equals the sequence 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≥0} is given by

G(x) = ∑_{n=0}^{∞} a_{n}x^{n} = \frac{1}{x} (\frac{(1 − \sqrt{1 − 4x})(1 + x)}{2x} − 1)  (1)

It is known (for example, see Krattenthaler [4]) that the Hankel determinant h_{n} of order n of the sequence {a_{n}}_{n≥0} equals

h_{n} = a_{0}^{n}β_{1}^{n−1}β_{2}^{n−2} ⋯ β_{n−2}^{2}β_{n−1},  (2)

where {β_{n}}_{n≥1} is the sequence given by:

G(x) = ∑_{n=0}^{∞} a_{n}x^{n} = \frac{a_{0}}{1 + α_{0}x − \frac{β_{1}x^{2}}{1 + α_{1}x − \frac{β_{2}x^{2}}{1 + α_{2}x − ⋯}}}  (3)

The sequences {α_{n}}_{n≥0} and {β_{n}}_{n≥1} are the coefficients in the recurrence relation

P_{n+1}(x) = (x − α_{n})P_{n}(x) − β_{n}P_{n−1}(x)

where {P_{n}(x)}_{n≥0} is the monic polynomial sequence orthogonal with respect to the functional L determined by

L[x^{n}] = a_{n} (n = 0, 1, 2, …).  (4)

In the next section this functional is constructed and a theorem concerning the polynomials {P_{n}(x)}_{n≥0} and the sequences {α_{n}}_{n≥0} and {β_{n}}_{n≥1} is proved.

2. Main Theorem

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

L[f(x)] = ∫_{R} f(x)dψ(x),

where ψ(x) is a distribution, or, even more, to find the weight function w(x) such that w(x) = ψ′(x).

Denote by F (z) the function

F (z) = ∑_{k=0}^{∞} a_{k}z^{−k−1},

From the generating function (1), we have:

F (z) = z^{−1} G(z^{−1}) = \frac{1}{2} \{z − 1 − (z + 1)\sqrt{1 − \frac{4}{z}}\} .  (5)

From the theory of distribution functions (see Chihara [1]), we have Stieltjes inversion function

ψ(t) − ψ(s) = −\frac{1}{π} ∫_{s}^{t} ℑF (x + iy)dx.  (6)

Since F (z̄) = \overline{F (z)}, it can be written in the form

ψ(t) − ψ(0) = −\frac{1}{2πi} lim_{y→0^{+}} ∫_{0}^{t}[F (x + iy) − F (x − iy)]dx.  (7)

Knowing that

∫_{0}^{t} F (x + a)dx = \frac{1}{4} \{a^{2} \sqrt{1 − \frac{4}{a}} − 2t + 2at + t^{2} − (a + t)^{2}\sqrt{1 − \frac{4}{a + t}}\}

−2 log(−2 + a + a \sqrt{1 − \frac{4}{a}}) + 2 log(−2 + a + t + (a + t) \sqrt{1 − \frac{4}{a + t}}),

we find the distribution function

ψ(t) = \{ \begin{matrix}\frac{1}{4π} \{t \sqrt{t(4 − t)} − 8(π − arctan ^{\frac{\sqrt{(4−t)t}}{2−t}})\} , & 0 ≤ t < 2; \\ \frac{1}{4π} \{t \sqrt{t(4 − t)} − 8 arctan ^{\frac{\sqrt{(4−t)t}}{t−2}}\}; & 2 ≤ t ≤ 4. \end{matrix}

After differentiation of ψ(t) and simplification of the resulting expression, we finally have:

w(x) = \frac{1}{2}(x + 1)\sqrt{\frac{4}{x} − 1}, x ∈ (0, 4).  (8)

In this way, we obtained the positive-definite L that satisfies (4) and proved that the corresponding orthogonal polynomial sequence exists. We have

Theorem 1. The monic polynomial sequence {P_{n}(x)} orthogonal with respect to the linear functional

L(f) := \frac{1}{2π} ∫_{0}^{4} f(x)(x + 1)\sqrt{\frac{4}{x} − 1}dx,  (9)

satisfies the three-term recurrence relation

P_{n+1}(x) = (x − α_{n})P_{n}(x) − β_{n}P_{n−1}(x),  (10)

with

α_{n} = 2 − \frac{1}{F_{2n+1}F_{2n+3}} , β_{n} = 1 + \frac{1}{F_{2n+1}^{2}} ,  k ≥ 0  (11)

where F_{i} is the i-th Fibonacci number.

Example 1. The first members of this sequence are:

P_{0}(x) = 1;
P_{1}(x) = x − \frac{3}{2};
P_{2}(x) = x^{2} − \frac{17}{5}x + \frac{8}{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}.

Notice that P_{n}(0) = (−1)^{n}F_{2n+2}/F_{2n+1}.

Proof of Theorem 1. Denoting by W_{n}(x) = P_{n}^{(1/2,−1/2)}(x) (n ≥ 0) a special Jacobi polynomial, which is also known as the Chebyshev polynomial of the fourth kind.

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ö [9]) by

W_{n}(cos θ) = \frac{sin(n + \frac{1}{2})θ}{2^{n} sin \frac{1}{2}θ}.

and satisfy the three-term recurrence relation (Chihara [1]):

W_{n+1}(x) = (x − α_{n}^{∗}) W_{n}(x) − β_{n}^{∗}W_{n−1}(x) (n = 0, 1, …),
W_{−1}(x) = 0, W_{0}(x) = 1,

where

α_{0}^{∗} = −\frac{1}{2}, α_{n}^{∗} = 0,  β_{0}^{∗} = π, β_{n}^{∗} = \frac{1}{4}  (n ≥ 1).

If we use the weight function p̂(t) = (t − c)p^{(1/2,−1/2)}(t), then the corresponding coefficients α̂_{n} and β̂_{n} can be evaluated as follows (see, for example, Gautschi [2])

α̂_{n} = c − \frac{W_{n+1}(c)}{W_{n}(c)} − β_{n+1}^{∗} \frac{W_{n}(c)}{W_{n+1}(c)},  (12)
β̂_{n} = β_{n}^{∗} \frac{W_{n−1}(c)W_{n+1}(c)}{W_{n}^{2}(c)}, n ∈ ℕ.  (13)

Here, we use c = −3/2 and p̂(x) = (x + 3/2)(1 − x)^{1/2}(1 + x)^{−1/2}.

If we write λ_{n} = W_{n}(−3/2) then, using the three-term recurrence relation for W_{n}(x), we have

4λ_{n+1} + 6λ_{n} + λ_{n−1} = 0,

with initial values λ_{0} = 1, λ_{1} = −1.

So, we find

λ_{n} = W_{n}(−3/2) = \frac{(−1)^{n}}{2\sqrt{5} 4^{n}} \{(\sqrt{5} + 1)(3 + \sqrt{5})^{n} + (\sqrt{5} − 1)(3 − \sqrt{5})^{n}\} .

Denoting by

ϕ = \frac{1 + \sqrt{5}}{2},  \overline{ϕ} = \frac{1 − \sqrt{5}}{2}  (14)

the golden section numbers, we can write:

λ_{n} = W_{n}(−3/2) = \frac{(−1)^{n}}{\sqrt{5} 2^{n}} (ϕ^{2n+1} − \overline{ϕ}^{2n+1}) = \frac{(−1)^{n}}{2^{n}} F_{2n+1}.  (15)

In order to simplify further algebraic manipulations we shall use

F_{2n−1}F_{2n+3} = F_{2n+1}^{2} + 1  (16)

This formula is a special case of the identity (Vajda [12]):

G(n + i)H(n + k) − G(n)H(n + i − k) = (−1)^{n}(G(i)H(k) − G(0)H(i + k)) (17)

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 → 2n + 1, i = 2, k = −2.

Now

β̂_{n} = \frac{1}{4} \frac{λ_{n−1}λ_{n+1}}{λ_{n}^{2}} = \frac{1}{4} \frac{F_{2n−1}F_{2n+3}}{F_{2n+1}^{2}}
= \frac{1}{4} \{1 + \frac{1}{F_{2n+1}^{2}} \}  (18)

and

α̂_{n} = −\frac{3}{2} − \frac{λ_{n+1}}{λ_{n}} − \frac{1}{4} \frac{λ_{n}}{λ_{n+1}}
= \frac{−3F_{2n+1}F_{2n+3} + F_{2n+3}^{2} + F_{2n+1}^{2}}{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}} .

If a new weight function p(x) is introduced by

p(x) = p̂(ax + b)

then we have

α_{n} = \frac{α̂_{n} − b}{a}, β_{n} = \frac{β̂_{n}}{a^{2}} (n ≥ 0).

Now, by using x ↦ x/2 − 1, i.e., a = 1/2 and b = −1, we have the wanted weight function

w(x) = p̂(\frac{x}{2} − 1) = \frac{1}{2}(x + 1)\sqrt{\frac{4 − x}{x}}.

Thus

α_{n} = 2 − \frac{5}{(ϕ^{2n+1} − \overline{ϕ}^{2n+1})(ϕ^{2n+3} − \overline{ϕ}^{2n+3})} = 2 − \frac{1}{F_{2n+1}F_{2n+3}}  (19)

and

β_{n} = 1 + \frac{5}{(ϕ^{2n+1} − \overline{ϕ}^{2n+1})^{2}} = 1 + \frac{1}{F_{2n+1}^{2}}  (20)

finishing the proof of (1) .□

3. Layman’s conjecture

By making use of (2) we have that:

h_{n} = a_{0}^{n} (1 + \frac{1}{F_{3}^{2}} )^{n−1} (1 + \frac{1}{F_{5}^{2}} )^{n−2}⋯ (1 + \frac{1}{F_{2n−1}^{2}} )  (21)

Using (16) we can write (21) as:

h_{n} = a_{0}^{n} (\frac{F_{1}F_{5}}{F_{3}^{2}} )^{n−1}(\frac{F_{3}F_{7}}{F_{5}^{2}} )^{n−2}(\frac{F_{5}F_{9}}{F_{7}^{2}} )^{n−3}⋯ \frac{F_{2n−3}F_{2n+1}}{F_{2n−1}^{2}}  (22)

Since a_{0} = 2 = F_{3} the corresponding factors cancel, therefore:

h_{n} = F_{2n+1} (n ≥ 0),

thus proving that Hankel transform of A005807 equals A001519 -sequence of Fibonacci numbers with odd indices.

As we have mentioned in the introduction, Layman observed that the Hankel transform of A005807 equals 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 (17) we take n → 2n. We also use the easily provable fact P_{n}(0) = (−1)^{n}F_{2n+2}/F_{2n+1} (see Example 1).

Finally we mention that, following Layman [5], it is known that the Hankel transform is invariant with the respect to the Binomial and Invert transform, so all the sequences obtained from A005807 using these two transformations have the Hankel transform shown here.

References

[1] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, New York, 1978.

[2] W. Gautschi, Orthogonal polynomials: applications and computations, in Acta Numerica, 1996, Cambridge University Press, 1996, pp. 45–119.

[3] INRIA Algorithms Project, Encyclopedia of Combinatorial Structures, at http://algo.inria.fr/bin/encyclopedia?Search=ESCnb&argseach=431.

[4] C. Krattenthaler, Advanced Determinant Calculus, at http://www.mat.univie.ac.at/People/kratt/artikel/detsurv.html.

[5] J. W. Layman, The Hankel Transform and Some of its Properties, Journal of Integer Sequences, Article 01.1.5, Volume 4, 2001.

[6] P. Peart and W. J. Woan, Generating functions via Hankel and Stieltjes matrices, Journal of Integer Sequences, Article 00.2.1, Issue 2, Volume 3, 2000.

[7] W. J. Woan, Hankel Matrices and Lattice Paths, Journal of Integer Sequences, Article 01.1.2, Volume 4, 2001.

[8] J. P. O. Santos and M. Ivković, Fibonacci numbers and partitions, Fibonacci Quarterly, to appear.

[9] G. Szegö, Orthogonal Polynomials, AMS, 4th. ed., Vol. 23 (Colloquium publications), 1975.

[10] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at http://www.research.att.com/∼njas/sequences/.

[11] R. Tosić, Kombinatorika (in Serbian) Univerzitet u Novom Sadu (1999), Novi Sad.

[12] S. Vajda, Fibonacci and Lucas numbers, and the Golden Section: Theory and Applications, Halsted Press, 1989.

[13] D. Zeilberger and T. Amdeberhan, DODGSON: A Maple package for conjecturing and proving determinant identities by Dodgson’s condensation method, at http://astro.ocis.temple.edu/ doron/programs.html.

(Mentions sequences \underline{A005807} \underline{A001906} \underline{A001519}.)

Received April 8, 2002; revised version received May 14, 2002. Published in Journal of Integer Sequences May 14, 2002.

Return to Journal of Integer Sequences home page