\documentclass[12pt]{article}
\usepackage{amsfonts}
\textwidth14.8cm
\textheight22.8cm
\title{Recurrences and Legendre Transform}
\author{Volker Strehl \\
Institut f\"ur Mathematische Maschinen und Datenverarbeitung\\
(Informatik I)\\
Universit\"at Erlangen-N\"urnberg, Germany}
\date{}
\newtheorem{prop}{Proposition}
\newtheorem{thm}[prop]{Theorem}
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{cor}[prop]{Corollary}
%\thispagestyle{titlepage}
\begin{document}
\bibliographystyle{plain}
\maketitle
\begin{abstract}
A binomial identity ((\ref{A}) below), which relates the
famous Ap\'ery numbers and the sums of cubes of binomial
coefficients (for which Franel has established a recurrence
relation almost 100 years ago), can be seen as a particular
instance of a Legendre transform between sequences.
A proof of this identity can be based on the more general
fact that the Ap\'ery and Franel recurrence relations
themselves are conjugate via Legendre transform.
This motivates a closer look at conjugacy of sequences
satisfying linear recurrence relations with polynomial
coefficients. The r\^ole of computer-aided proof and
verification in the study of binomial identities and recurrence
relations is illustrated, and potential applications of conjugacy
in diophantine approximation are mentioned.
\newline
This article is an expanded version of a talk given at the
29. meeting of the {\em S\'eminaire Lothringien de
Combinatoire}, Thurnau, september 1992.
\end{abstract}
\section{Introduction}
In this article I will discuss some general aspects related to
the following beautiful binomial identity:
\begin{equation}\label{A}
\sum_{k=0}^n
{n \choose k}^2
{n+k \choose k}^2
=
\sum_{k=0}^n
{n \choose k}
{n+k \choose k}
\sum_{j=0}^k
{k \choose j}^3~~~(n \geq 0)
\end{equation}
An interesting aspect of this identity is the fact that it
relates the famous {\em Ap\'ery numbers}
$a_n := \sum_k {n \choose k}^2 {n+k \choose k}^2$,
which played an important r\^ole in R. Ap\'ery's
original proof of the irrationality of $\zeta (3)$ (see
the entertaining and instructive article \cite{vdpoorten:78}
by A. v.d. Poorten for an account
of this), with the sums of cubes of binomial coefficients
$f_n := \sum_k {n \choose k}^3$,
for which J. Franel had found recurrences long ago
( \cite{franel:94}, see \cite{comtet:74},
\cite{gould:72}, \cite{perlstadt:87}, \cite{cusick:89} ),
and which for that reason will be called {\em Franel numbers}
in this article.
This identity was brought to my attention early in 1992
as a conjecture by my colleague B. Voigt from Bielefeld.
The origin of it lies in the following question put forward
by A. L. Schmidt from Copenhagen:
\begin{quote}
\em
Let numbers $c_k ~(k \geq 0)$, independent of $n$,
be defined by
\[
\sum_{k=0}^n
{n \choose k}^2
{n+k \choose k}^2
=
\sum_{k=0}^n
{n \choose k}
{n+k \choose k}
\,c_k~~~(n \geq 0)
\]
{\rm [It is easy to see (by induction) that these rational numbers
are uniquely determined.]}
\newline
Is it then true that these numbers
are always integers?
\newline
{\rm [This is not obvious
from the definition, but an evaluation of the first few
hundred values clearly suggests that.]}
\end{quote}
It was soon observed by W. Deuber, W. Thumser and B. Voigt that the
beginning of the sequence
\[
\left( c_k \right)_{k \geq 0} =
(\,1\,,\, 2\,,\, 10\,,\, 56\,,\, 346\,,
\,2252\,,\, 15184\,,\, 104960\,,\, 739162, \ldots\,)
\]
is the same as the beginning of
the sequence of the Franel numbers $f_k = \sum_{j=0}^k {k \choose j}^3$.
From this observation the above conjecture (\ref{A}) was formulated.
Since I could not spot the conjectured identity
in the relevant literature (e.g. \cite{riordan:68}, \cite{gould:72}),
I tried to find a proof
for myself. In fact, there are now several different proofs
available, none of them really "trivial",
and I will briefly mention below these diverse approaches
that I worked out. The ordering corresponds to
the chronological ordering in which these proofs
were discovered.
A detailed discussion of this affair
will be given in \cite{strehl:92}.
\begin{enumerate}
\item
Identity (\ref{A}) is hidden in a classical result, due to W.N. Bailey,
from the theory of hypergeometric functions. In fact, it can be
pulled out of Bailey's bilinear generating function for the
Jacobi polynomials (\cite{bailey:38}, \cite{stanton:80},
\cite{strehl:90}) via a kind of diagonalization. The special case
where the Jacobi polynomials degenerate into Legendre polynomials
is sufficient for our identity, but the same trick can be played
in the general situation, so that (\ref{A}) turns out to be a degenerate
case belonging to a family of binomial identities with two
free parameters.
\item
As has been shown by myself in \cite{strehl:90},
Bailey's bilinear generating function
can be proved from a suitable combinatorial interpretation.
This is somewhat involved, and on the way of proving the full
bilinear generating function I established a certain family of binomial
identities. It turned out that these already include (\ref{A})
(up to routine transformations) and its
generalization mentioned before. This answers positively the question
about a possible combinatorial proof of (\ref{A}),
but such a proof is more complicated than the rather simple
appearance of this identity might suggest.
\item
By using the method of Legendre inverse pairs, as exposed in Riordan's
book \cite{riordan:68}, the problem can be transformed into
an equivalent one to which
D. Zeilberger's method of constructing recurrence operators for
definite hypergeometric sums (in the case of single sums)
can be applied. This gives a "computer-supported"
proof, which can be turned into a "conventional" one - once the operators
are known.
\item
The desired result can be obtained by a series of applications
of hypergeometric transforms (D. Stanton, Ch. Krattenthaler and
G. Andrews have provided comments on that approach). Once found, such
a proof is routine to check - finding the right track is the problem!
\item
The Wilf-Zeilberger-method (see remarks below)
for multiple hypergeometric sums can be applied
directly to the identity. Doron Zeilberger provided such a completely
"machine-made" proof in june 1992.
\item
Using the known recurrences for the Ap\'ery numbers
$a_n = \sum_k{n\choose k}^2{n+k \choose k}^2$
and the Franel numbers
$f_n = \sum_k{n \choose k}^3$
one can give a short (partially computer supported) proof of (\ref{A}),
using no sophisticated algorithms, but only standard simplification
capabilities of any reasonable computer algebra program.
Such a proof is outlined in the next section, and indeed, this kind
of proof was the motivation for writing the present note.
Let me remark that a proof similar to this one was found independently
by A. L. Schmidt.
\end{enumerate}
The following sections are organized as follows.
After illustrating the use (neither the principles, nor the theory
behind) of available implementations of algorithms for a computer-aided
treatment of binomial sums and sequences satisfying linear recurrence
relations with polynomial coefficients,
I will present a short proof of (\ref{A}) which is based on
the (known) recurrence relations of the Ap\'ery and Franel numbers.
The crucial fact is this: identity (\ref{A}) claims that
Franel's and Ap\'ery's sequences are related via {\em Legendre transform}.
This concept has been used, with number-theoretic applications in mind,
by A. L. Schmidt,
see \cite{schmidt:90}, \cite{schmidt:91}, \cite{schmidt:92},
and, in particular, his most recent
article is closely related to the present one, and some of his
results will be mentioned below. This turns out to be an immediate
consequence of the stronger fact that the linear recurrences
(of second order, with polynomial coefficients) generating those sequences
are themselves {\em conjugates} via Legendre transform in a
sense to be made precise below. Once guessed correctly, a proof
of this conjugacy relation is remarkably simple (relative
to a routine use of a machine-based simplification procedure).
In section 3 some notation will be developed in order to
deal with this approach
from a more general perspective.
The situation of (reduced) Legendre transform is then studied
in some detail in section 4, and the question under which condition
(and if so: how) recurrence relations are transformed into
recurrence relations via conjugation is answered completely
in a particular case.
It should become clear, however, that similar results could be
obtained by the same approach in related and more general
situations. Thus these results should be taken as exemplary -
no complete treatment was intended here, just an outline of how one may
proceed.
In the final section I present some consequences
in the field of diophantine approximation which are directly related
to identity (\ref{A}) and the conjugacy relation behind it.
These results are taken from A. L. Schmidt's recent article
\cite{schmidt:92} mentioned
above - here they should be taken as a motivation showing
that the study of binomial (or hypergeometric) identities
and recurrences related to them might lead to interesting
applications in number theory.
\section{A short proof of identity (1)}
Two basic facts are used for a proof of (\ref{A}) as presented here:
\begin{itemize}
\item{}[Franel, 1895]
The Franel numbers
$f_n = \sum_k {n \choose k}^3$
satify the following second-order recurrence
with polynomial coefficients
\footnote{
Franel has also found a similar recurrence
for $\sum_{k=0}^n {n \choose k}^4$. It took
quite a while until corresponding recurrence relations
for higher exponents were found,
see the recent articles by Perlstadt \cite{perlstadt:87}
and Cusick \cite{cusick:89}.}
\begin{equation}\label{B}
(n+1)^2 f_{n+1} - (7 n^2 + 7 n +2) f_{n} - 8 n^2 f_{n-1} = 0
~~~(n \geq 0)
\end{equation}
\item{}[Ap\'ery, 1978]
The Ap\'ery numbers
$f_n = \sum_k {n \choose k}^2{n+k \choose k}^2$
satify the following second-order recurrence
with polynomial coefficients\footnote{
Ap\'ery has also found a similar recurrence
for $\sum_{k=0}^n {n \choose k}^2{n+k \choose k}$. See the article
by van der Poorten \cite{vdpoorten:78} and an article
\cite{askeywil:84} by R. Askey and J. Wilson
for illuminating remarks from the hypergeometric viewpoint
and a generalization.}
\begin{equation}
\label{C}
(n+1)^3 a_{n+1} - \left( (n+1)^3+n^3+4(2n+1)^3 \right) a_{n}
+ n^3 a_{n-1} = 0
~~~(n \geq 0)
\end{equation}
\end{itemize}
Note that even if one {\em knows} the recurrences beforehand, it can be
rather tedious to {\em verify} them. To illustrate this situation,
let me cite (with a slight change in notation)\footnote{
Actually, v.d. Poorten writes about two solutions of the
recurrence, the other one, call it $\{\,b_n\,\}$ specified by initial values
$b_0=0$ and $b_1=6$. This second solution will only appear in
the last section of this article. Note that the r\^ole of
$a$ and $b$ has been interchanged w.r.t. \cite{vdpoorten:78}.}
from A. v.d. Poorten's article \cite{vdpoorten:78}:
\begin{quote}
\em
... To convince ourselves of the validity
of Ap\'ery's proof we need only complete
the following exercise: \newline
Let $a_n = \sum_k {n \choose k}^2{n+k \choose k}^2$,
then $a_0=1$, $a_1=5$ and the sequence $\{\,a_n \,\}$ satisfies
the recurrence (\ref{C}).
\newline
... Neither Cohen nor I had been able to prove this in the
intervening two months ...
\end{quote}
Then v.d. Poorten mentions that D. Zagier was able to provide
a solution to this problem {\em with irritating speed} by virtue
of a technique called {\em creative telescoping}. Actually, this
technique, combined with the powerful algorithm for indefinite
hypergeometric summation due to W. Gosper \cite{gosper:78},
is at the heart of D. Zeilberger's method.
Today, finding (and proving!) recurrences like (\ref{B}) and (\ref{C}) is
a routine application of Zeilberger's algorithm for simple
terminating hypergeometric sums, in fact a matter
of very few seconds (in these cases! In a case like the one
mentioned above in 5., i.e. directly verifying that the right
hand side of (\ref{A}) satisfies the same recurrence as
the Ap\'ery numbers do,
application of Zeilberger's algorithm for
{\em hypergeometric multisums} leads to nonnegligible computing time,
even on fast machines\footnote{
D. Zeilberger's first direct verification of (\ref{A}) took about 1500 sec.}.
To illustrate this, I include
input and output from an implementation of Zeilberger's algorithm
which was programmed by J. Hornegger \cite{hornegger:92}
in the context of the AXIOM\footnote{
{\em AXIOM} is a trademark of NAG, Numerical Algoriths Group Ltd.,Oxford, England.}
computer algebra system.\newline
\newline\noindent
Recurrences for $\sum_{k=0}^n {n \choose k}^e~~(e=1,2,3)$
\footnotesize
\begin{verbatim}
k1 : Symbol := k
p1 : SMP(FRAC INT, Symbol) := n
p2 : SMP(FRAC INT, Symbol) := k
arg: FRAC SMP(FRAC INT, Symbol) := 1
\end{verbatim}
\normalsize
Exponent $e=1$:
\footnotesize
\begin{verbatim}
(69) r1:= findrec(bin(p1, p2, n1, k1, 1), 1, arg, 1, n1, k1)
(69) - B + 2, 1
Type: Union(List FRAC SMP(FRAC INT,Symbol),...)
Time: 0.08 (IN) + 0.13 (EV) + 0.04 (OT) = 0.25 sec
\end{verbatim}
\normalsize
The result consists of the recurrence operator (written as
a polynomial in the shift operator $B$ and $n$) and the
{\em certificate} provided by the method (plus informations
about typing and timing).\newline
\ \newline
\noindent
Exponent $e=2$:
\footnotesize
\begin{verbatim}
(71) r2:= findrec(bin(p1, p2, n1, k1, 2), 1, arg, 1, n1, k1)
(71) (B - 4)n + B - 2, - 3n + 2k - 1
Type: ...
Time: 0.08 (IN) + 0.31 (EV) + 0.05 (OT) = 0.44 sec
\end{verbatim}
\normalsize
This result expresses the fact that
$\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}$, because both sides
are annihilated by the recurrence operator.
\newline
\ \newline
Exponent $e=3$:
\footnotesize
\begin{verbatim}
(72) r3:= findrec(bin(p1, p2, n1, k1, 3), 1, arg, 1, n1, k1)
(72)
2 2 2 2
(B - 7 B - 8)n + (4 B - 21 B - 16)n + 4 B - 16 B - 8,
5 4 2 3
- 14n + (27k - 75)n + (- 18k + 111k - 161)n
+
3 2 2 3 2
(4k - 54k + 171k - 173)n + (8k - 54k + 117k - 93)n
+
3 2
4k - 18k + 30k - 20
/
3 2 2 3 2
n + (- 3k + 3)n + (3k - 6k + 3)n - k + 3k - 3k + 1
Type: ...
Time: 0.08 (IN) + 13.30 (EV) + 0.38 (OT) +4.15 (GC) = 17.91 sec
(73) factorCoefficients r3.1
2 2 2 16 2
(73) (n + 2) B - 7(n + 3n + --)B - 8(n + 1)
7
Type: SUP Factored SMP(FRAC INT,Symbol)
Time: 0.01 (IN) + 0.11 (EV) + 0.09 (OT) = 0.21 sec
\end{verbatim}
\normalsize
This is Franel's recurence. The certificate in factorized form:
\footnotesize
\begin{verbatim}
(74) factorCertifyingFunction r3.2
(74)
2
- 14(n + 1)
*
3 27 47 2 9 2 57 53 2 3 9 2 15 10
(n + (- -- k + --)n + (- k - -- k + --)n - - k + - k - -- k + --)
14 14 7 14 14 7 7 7 7
/
3
(n - k + 1)
Type: FRAC Factored SMP(FRAC INT,Symbol)
Time: 0.04 (IN) + 0.78 (EV) + 0.48 (OT) + 1.50 (GC) = 2.80 sec
\end{verbatim}
\normalsize
Now for Ap\'ery's recurrence (omitting the certificate):
\footnotesize
\begin{verbatim}
a1: SMP(FRAC INT, Symbol):= n
a2: SMP(FRAC INT, Symbol):= k
a3: SMP(FRAC INT, Symbol):= a1 + a2
r:= recurrence findrec(bin(a1, a2, n1, k1, 2),
bin(a3, a2, n1, k1, 2), 1, 2, n1, k1)
3 2 2 3 2
(n + 6n + 12n + 8)B + (- 34n - 153n - 231n - 117)B +
3 2
n + 3n + 3n + 1
Type: SUP SMP(FRAC INT, Symbol)
Time: 0.20 (IN) + 13.71 (EV) + 0.23 (OT) = 14.14 sec
\end{verbatim}
\normalsize
Here I will not give any further explanations w.r.t. Zeilberger's method.
The interested reader may look into the numerous articles
available (e.g.
\cite{zeilberger:90b},
\cite{zeilberger:91a},
\cite{wilfzeil:90a},
\cite{wilfzeil:90b},
\cite{wilfzeil:92a},
\cite{wilfzeil:92b},
\cite{cartier:91}),
\cite{koornwinder:92},
\cite{hornegger:92}) describing the method, the algorithms,
and their applications.
As a side remark: I would like to take the occasion to point
out another approach, experimental in character, which can
be helpful in situations similar to the one discussed here.
There is now a nice set of tools available with which
given the first few coefficients of a generatin function,
one may {\em cleverly guess} the generating function (if it
has a "nice" closed form), or a linear differential
equation satisfied by it, or a linear recurrence relation
satisfied by its coefficients.
The mathematical model behind it is that of {\em holonomic}
functions of one variable (or equivalently: D-finite power series,
or P-recursive sequences), with important special cases such
as rational and algebraic generating functions. Even if these
tools only provide {\em guesses} and not {\em proofs} in the strict sense,
they often can be used to obtain enough information about a problem
so that a strict solution becomes feasible. These tools,
written by B. Salvy and P. Zimmerman (INRIA, Paris)
are available under the
Maple\footnote{{\em Maple} is a trademark of Waterloo Maple Software,
Waterloo, Canada.}
computer algebra system as a package named {\em gfun}
in the Maple share library \footnote{The
Maple share library
be accessed using anonymous ftp
from {\tt daisy.uwaterloo.ca} in Waterloo (Canada) or
{\tt neptune.inf.ethz.ch} in Zurich (Switzerland).}.
A rather comprehensive description \cite{salvyzim:92} will soon be available
from the authors.
As an illustration,
let us {\em guess} the recurrences (\ref{B}) and (\ref{C}) using {\em gfun}:
\footnotesize
\begin{verbatim}
|\^/| MAPLE V
._|\| |/|_. Copyright (c) 1981-1990 by the University of Waterloo.
\ MAPLE / All rights reserved. MAPLE is a registered trademark of
<____ ____> Waterloo Maple Software.
| Type ? for help.
> readlib(gfun):with(gfun):
\end{verbatim}
\normalsize
The Ap\'ery numbers are defined:
\footnotesize
\[
a := \left \langle
n \mapsto
\sum _{k=0}^{n}{n\choose k}^{2}{n+k\choose k}^{2}
\right \rangle
\]
\normalsize
A list of the first few values:
\footnotesize
\begin{verbatim}
> [a(i)$i=0..10];
[1, 5, 73, 1445, 33001, 819005, 21460825, 584307365,
16367912425, 468690849005, 13657436403073]
\end{verbatim}
\normalsize
{\em gfun} does not find a "nice" generating function:
\footnotesize
\begin{verbatim}
> guessgf([a(i)$i=0..15],t);
FAIL
\end{verbatim}
\normalsize
Eleven initial values are not sufficient for the recurrence:
\footnotesize
\begin{verbatim}
> listtorec([a(i)$i=0..10],A(n));
FAIL
\end{verbatim}
\normalsize
but sixteen initial values are:
\footnotesize
\begin{verbatim}
> listtorec([a(i)$i=0..15],A(n));
\end{verbatim}
\begin{eqnarray*}
[~\big\{n^{3}A(n)&+&\left (-5-27\,n-51\,n^{2}-34\,n^{3}\right )A(n+1)\\
&+&\left (1+3\,n+3\,n^{2}+n^{3}\right )A(n+2), A(1)=1,A(2)=5\big\}~,~
{\it ogf}~]
\end{eqnarray*}
\normalsize
We can get a differential equation from the recurrence:
\footnotesize
\begin{verbatim}
> rectodiffeq("[1],A(n),aa(z));
\end{verbatim}
\begin{eqnarray*}
&[&{\mbox {D}({\it aa})}(0)=1,
{{D}^{\left (2\right )}({\it aa})}(0)=10,\\
&&\left (3\,z^{4}-51\,z^{3}\right ){\frac {d^{2}}{dz^{2}}}{\it aa}(z)+
\left (z+z^{3}-10\,z^{2}\right ){\frac {d}{dz}}{\it aa}(z)+\left (5\,z
-1\right ){\it aa}(z)\\
&&-5\,A(0)z+
A(0)+z^{5}{\frac {d^{3}}{dz^{3}}}{\it
aa}(z)+\left ({\frac {d^{3}}{dz^{3}}}{\it aa}(z)\right )z^{3}-34\,
\left ({\frac {d^{3}}{dz^{3}}}{\it aa}(z)\right )z^{4}~,~{\it ogf}~]
\end{eqnarray*}
\normalsize
\noindent
Now we consider sums of cubes of binomial coefficients:
\footnotesize
\[
f := \left \langle n \mapsto \sum _{k=0}^{n}{n\choose k}^{3}\right
\rangle
\]
\begin{verbatim}
> [f(i)$i=0..10];
[1, 2, 10, 56, 346, 2252, 15184, 104960, 739162, 5280932, 38165260]
\end{verbatim}
\normalsize
Too few initial values will not lead to a differential equation:
\footnotesize
\begin{verbatim}
> listtodiffeq([f(i)$i=0..10],F(z));
FAIL
> listtodiffeq([f(i)$i=0..15],F(z));
\end{verbatim}
\begin{eqnarray*}
&&\big\{~\left (-2-8\,z\right )F(z)+\left (1-14\,z-24\,z^{2}\right ){
\frac {d}{dz}}F(z)+\left (z-7\,z^{2}-8\,z^{3}\right ){\frac {d^{2}}{dz
^{2}}}F(z),\\
&&{\mbox {D}(F)}(0)=2,F(0)=1~\big\}
\end{eqnarray*}
\normalsize
From the differential equation we get the Franel recurrence:
\begin{verbatim}
> diffeqtorec(",F(z),ff(n));
\end{verbatim}
\begin{eqnarray*}
&&\big\{~\left(-7n-2-7 n^2 \right)
{\it ff}(n) + \left( n^2+2n+1 \right) {\it ff}(n+1) -
8 {\it ff}(n-1) n^2 , \\
&&{\it ff}(0)=1 , {\it ff}(1)=2 ~\big\}
\end{eqnarray*}
\normalsize
\bigskip
Let us now return to the proposed proof of (\ref{A}).
It will be presented in matrix form.
To begin with, let us define a doubly infinite
tridiagonal matrix ${\bf F} = \left( f_{i,j} \right)_{i,j \geq 0}$
representing the difference operator of the Franel recurrence (\ref{B}) :
\[
f_{i,j} = f_{i-j}(i) ~~{\rm where}~~
f_k(z) := \cases{
(z+1)^2 & if $k=-1$ \cr
-(7z^2+7z+2) & if $k=0$ \cr
-8z^2 & if $k=1$ \cr
0 & if $|k|> 1$}
\]
so that
\[
{\bf F} =
\pmatrix{
f_0(0) & f_{-1}(0) & f_{-2}(0) & \ldots \cr
f_1(1) & f_0(1) & f_{-1}(1) & \ldots \cr
f_2(2) & f_1(2) & f_{0}(2) & \ldots \cr
\vdots & \vdots & \vdots & \ddots}
=
\pmatrix{
-2 & 1 & 0 & 0 & \ldots \cr
-8 & -16 & 4 & 0 & \ldots \cr
0 & -32 & -44 & 9 & \ldots \cr
0 & 0 & -72 & -86 & \ldots \cr
\vdots & \vdots & \vdots & \vdots & \ddots}
\]
If we denote by ${\bf f} = (f_n)_{n \geq 0}$ the infinite column
vector with the Franel numbers $f_n = \sum_k {n \choose k}^3$
as entries, then Franel's result (\ref{B}) is equivalent to
\[
{\bf F} \cdot {\bf f} = {\bf 0}
\]
where ${\bf 0}$ denotes the zero column vector.
Similarly, the difference operator occuring in
the Ap\'ery recurrence (\ref{C}) has matrix form
\[
{\bf A} =
\pmatrix{
a_0(0) & a_{-1}(0) & a_{-2}(0) & \ldots \cr
a_1(1) & a_0(1) & a_{-1}(1) & \ldots \cr
a_2(2) & a_1(2) & a_{0}(2) & \ldots \cr
\vdots & \vdots & \vdots & \ddots}
=
\pmatrix{
-5 & 1 & 0 & 0 & \ldots \cr
1 & -117 & 8 & 0 & \ldots \cr
0 & 8 &-535 & 27 & \ldots \cr
0 & 0 & 27 & -1463 & \ldots \cr
\vdots & \vdots & \vdots & \vdots & \ddots}
\]
where
\[
a_{i,j} = a_{i-j}(i) ~~{\rm where}~~
a_k(z) := \cases{
(z+1)^3 & if $k=-1$ \cr
- (z+1)^3 - z^3 - 4(2z+1)^3 & if $k=0$ \cr
z^3 & if $k=1$ \cr
0 & if $|k|> 1$}
\]
Then Ap\'ery's recurrence can be written as
\[
{\bf A} \cdot {\bf a} = {\bf 0}
\]
where ${\bf a} = ( a_n )_{n \geq 0}$
is the vector of the Ap\'ery numbers,
$a_n = \sum_k{n \choose k}^2{n+k \choose k}^2$.
Finally we introduce the doubly infinite, lower triangular
matrix ${\bf P} = \left( p_{i,j} \right)_{i,j \geq 0}$
of the {\em Legendre transform}:
\[
{\bf P} =
\left( {i \choose j}{i+j \choose j} \right)_{i,j \geq 0}
=
\pmatrix{
1 & 0 & 0 & 0 & \ldots \cr
1 & 2 & 0 & 0 & \ldots \cr
1 & 6 & 6 & 0 & \ldots \cr
1 & 12 & 30 & 20 & \ldots \cr
\vdots & \vdots & \vdots & \vdots & \ddots}
\]
Note that the $n$-th row of this matrix contains the coefficients
of the Legendre polynomials $P_n$, if written as
\[
P_n(z) = \sum_{k=0}^n {n \choose k}{n+k \choose k}
\left({z-1 \over 2}\right)^k
\]
Using this notation, it becomes clear that A.L. Schmidt's question
mentioned in the beginning asks for the inverse image of the
sequence of Ap\'ery's numbers under the Legendre transform,
and that the conjectured identity (\ref{A}) claims that Ap\'ery's
sequence $\bf a$ is the image of Franel's sequence $\bf f$
under the Legendre transform, i.e.
${\bf a} = {\bf P}\cdot {\bf f}$.
Put into matrix terms, what we would like to show is that
\[
{\bf A} \cdot {\bf P}\cdot {\bf f} = {\bf 0}
\]
Obviously, we would be done if we could exhibit a matrix $\bf X$ such that
\[
{\bf A} \cdot {\bf P } = {\bf X } \cdot {\bf F}
\]
Computing initial segments of this unknown (infinite) matrix
$\bf X$ leads to the following (surprising?) {\em guess}:
\begin{equation}\label{D}
{\bf X} = {\bf D} \cdot {\bf P}~~~
{\rm and~hence}~~~
{\bf A} = {\bf D} \cdot {\bf P} \cdot {\bf F} \cdot {\bf P}^{-1}
\end{equation}
where ${\bf D} = \left( d_{i,j} \right)_{i,j \geq 0}$
is a diagonal matrix given by $d_{i,i} = 4i+2~(i \geq 0)$.
\medskip
It remains to {\em prove} this claim which not only says that
the Franel and the Ap\'ery sequences are related
via the Legendre transform, but also that the associated difference operators
are related in the sense of {\em conjugation}
via Legendre transform (up to multiplication
with a diagonal matrix). Interestingly, even though we have
to deal with infinite matrices containing binomial coefficients,
i.e. nonrational terms, the proof can be established by rational
arithmetic alone. For this to see, let us write the assertion (\ref{D})
to be proved in the form:
\[
{\bf A} \cdot {\bf P} = {\bf D} \cdot {\bf P} \cdot {\bf F}
\]
Consider the $(i,j)$-entry on both sides of this equation.
Since both ${\bf A}$ and $\bf F$ are {\em tridiagonal} matrices,
every such term involves three summands only.
Write this as
\begin{eqnarray*}
lhs &=& a_{1}(i) \, p_{i-1,j} + a_0(i) \,
p_{i,j} + a_{-1}(i) \, p_{i+1,j} \cr
rhs &=& (4i+2)\left[p_{i,j-1} \, f_{-1}(j-1) + p_{i,j} \,
f_0(j) + p_{i,j+1} \, f_1(j+1) \right]
\end{eqnarray*}
where now $i$ and $j$ are treated as {\em variables}. Now ask
for simplification of $lhs - rhs$. The Maple command
\begin{quote}
\tt
expand(lhs - rhs)
\end{quote}
gives back an expression of considerable size. Of course, simplification
{\rm could} be done by hand, but this tedious task is better accomplished by
your computer algebra system\footnote{
The subtle point here is this: the simplification algorithm
must recognize the fact that even though there are binomial
coefficients with symbolic entries around, the problem is
essentially one of rational arithmetic because of the {\em hypergeometric}
nature of binomial coefficients: walking along rows and columns
in the Pascal triangle can locally be performed via multiplication
with suitable rational functions of the locations, hence rational
normalization is possible as soon as only bounded neighbourhoods have
to be taken into account. Here the tridiagonal structure of the
matrices ${\bf A}$ and ${\bf F}$ is important.}:
\begin{quote}
\tt
simplify(expand(lhs - rhs))
\begin{center}
0
\end{center}
\end{quote}
To conclude this section, let us summarize the above discussion
\begin{thm}
The Franel recurrence operator $\bf F$
and the Ap\'ery recurrence operator $\bf A$
are Legendre conjugates in the following sense:
\[
{\bf A} = {\bf D} \cdot {\bf P} \cdot {\bf F} \cdot {\bf P}^{-1}
\]
with ${\bf A},{\bf F},{\bf D},{\bf P}$ as above.
\end{thm}
The binomial identity (\ref{A}) we started with is just one of the
consequences of this general fact - perhaps the most
interesting one. In section 5 it will be shown how this conjugacy relation
can be further exploited.
Note that in the proof of the theorem we essentially used the fact
that the matrices $\bf A$ and $\bf F$ are tridiagonal matrices
with "polynomial values along the diagonals", and that the
matrix of the Legendre transform $\bf P$ has a similar structure\footnote{
No quite, actually: the values "along the diagonals" are no longer
polynomial, but still hypergeometric. That is why in section 4 we will pass
to a related transform, called {\em reduced} Legendre transform, which
is polynomial and thus behaves a bit nicer.}.
It is therefore natural to ask under which conditions a conjugation
operation (with a nonsingular, lower triangular matrix such as $\bf P$)
will transform matrices representing linear recurrence operators
with polynomial coefficients into matrices of the same kind.
I will not try to give a definitive answer to this question in generality.
Instead, I will look into the case of the (reduced) Legendre transform
and show how, at least for recurrence operators of low order and
with low degree polynomial coefficients, such a question can be
attacked.
\section{Notation and some generalities}
Let $\Phi = \left( \phi_i(z) \right)_{i \in {\bf Z}}$
be a family of functions defined on the integers.
With this family we will associate a doubly-infinite matrix
$D_{\Phi}
= \left( d_{i,j} \right)_{i,j \geq 0}
= \left( \phi_{i-j}(i) \right)_{i,j \geq 0}$, i.e.
\[
D_{\Phi} =
\pmatrix{
\phi_0(0) & \phi_{-1}(0) & \phi_{-2}(0) & \ldots \cr
\phi_1(1) & \phi_0(1) & \phi_{-1}(1) & \ldots \cr
\phi_2(2) & \phi_{1}(2) & \phi_{0}(2) & \ldots \cr
\vdots & \vdots & \vdots & \ddots }
\]
In the previous section, we have seen the matrices $\bf A$ and $\bf F$
belonging to the Ap\'ery and the Franel recurrence, respectively,
when written in this form, are defined by {\em polynomial}
families $\left( a_i(z) \right)_{i \in {\bf Z}}$
and $\left( f_i(z) \right)_{i \in {\bf Z}}$ (with three nonzero members
in each case). The matrix $\bf P$ of the Legendre transform does not
belong to a polynomial family,
simply because $i \mapsto {2i \choose i}$ does not grow polynomially.
(One might use the $\Gamma$-function
in order to represent the matrix by a family of analytic functions.
Instead, we will pass to a related polynomial family below).
In particular, if $\Phi= \left( t_i(z) \right)_{i \in {\bf Z}}$
is such that $t_i= 0$ for $i < 0$ and $t_0(j) \neq 0$ for all
$ j \in {\bf N}$, i.e. $D_{\Phi}$ is an invertible lower triangular
triangular matrix, then its inverse matrix $(D_{\Phi})^{-1}$ can
be written as $D_{\Psi}$ where the family
$\Psi = \left( {t}_i'(z) \right)_{i \in {\bf Z}}$ is given by
${t}_i'(z) = 0$ for $i < 0$,
${t}'_0(j) = 1 / t_0(j)$ for all $j \in {\bf N}$, and
for $i > 0$, $(-1)^i {t}_i'(z)$ is given by:
\[
{\det
\pmatrix{
t_1(z-i+1) & t_0(z-i+1) & 0 & 0 & \ldots & 0 \cr
t_2(z-i+2) & t_1(z-i+2) & t_0(z-i+2) & 0 & \ldots & 0 \cr
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \cr
t_{i-1}(z-1)& t_{i-2}(z-1) & \ldots & \ldots & \ldots & t_0(z-1) \cr
t_i(z) & t_{i-1}(z) & t_{i-2}(z) & t_{i-3}(z) & \ldots & t_1(z)}
\over t_0(z-i) \cdot \ldots \cdot t_0(z)}
\]
This shows in particular: if $\Phi$ is a {\em polynomial} family
in the sense that all $t_i(z)$ are polynomials, and if in addition
$t_0(z)$ is a non-vanishing constant, then the inverse family
$\Psi$ is of the same kind. Moreover, if $\deg t_i(z) \leq i$
for all $i \geq 0$, then
expansion of the determinant shows that ${t}_i'(z)$ is
a sum of terms of degree $\leq i$, hence $\deg {t}_i'(z) \leq i$
for $i \geq 0$.
Now take a function $g(z)$ and $\delta \in {\bf Z}$. The singleton family
$\Gamma_{g,\delta} = \left( g_i(z) \right)_{i \in {\bf Z}}$
is given by $g_{\delta}(z) = g(z)$ and $g_i(z) = 0$ for $i \neq \delta$.
Then consider the family $\Lambda = \left( h_d(z) \right)_{d \in {\bf Z}}$
given by conjugation
\[
D_{\Phi} \cdot D_{\Gamma} \cdot \left( D_{\Phi} \right)^{-1}
= D_{\Lambda}
\]
with a `triangular' family $\Phi= \left( t_i(z) \right)_{i \in {\bf Z}}$
as before. It is easy to see that $h_d(z) = 0$ for $d < \delta$,
and that for $d \geq \delta$ one gets
\begin{equation}\label{E}
h_d(z) =
\sum_{0 \leq k \leq d - \delta}
t_k(z) \cdot g(z-k) \cdot{t}_{d-\delta-k}'(z-k-\delta)
\end{equation}
which can be written in determinantal form (and thus avoiding explicit
reference to the inverse family ${t}_i'(z)$) as
\[
h_d(z) =
{\det M(\Phi,g,\delta,d) \over t_0(z-d) \cdot \ldots \cdot t_0(z-\delta)}
\]
where the square matrix $ M(\Phi,g,\delta,d)$ of size $d - \delta +1$
is given by
\[
\pmatrix{
t_{d-\delta}(z)\cdot g(z-d+\delta) &
t_{d-\delta-1}(z)\cdot g(z-d+\delta+1) &
\ldots &
t_0(z)\cdot g(z) \cr
t_1(z-d+1) & t_0(z-d+1) & \ldots & 0 \cr
t_2(z-d+2) & t_1(z-d+2) & \ldots & 0 \cr
\vdots & \vdots & \ddots & \vdots \cr
t_{d-\delta}(z-\delta) &
t_{d-\delta-1}(z-\delta) &
\ldots & t_0(z-\delta)}
\]
Either of these presentations shows that for a polynomial $g(z)$
and $\delta \in {\bf Z}$ the family
$\Lambda = \left( h_i(z) \right)_{i \in {\bf Z}}$
obtained via conjugation with a polynomial family
$\Phi = \left( t_i(z) \right)_{i \in {\bf Z}}$
is again polynomial (and vanishes for indices $d < \delta$).
By superposition and linearity, if
$\Gamma = \left( g_i(z) \right)_{i \in {\bf Z}}$
is a family of polynomials such that $g_i(z) = 0$ for
all $i$ less than some integer $K$, and if $\Phi$
is as before, than conjugation
\[
D_{\Phi} \cdot D_{\Gamma} \cdot \left( D_{\Phi} \right)^{-1}
\]
is well-defined and gives a family of polynomials
$\Lambda = \left( h_d(z) \right)_{d \in {\bf Z}}$
which vanishes for $d < K$, and for $d \geq K$ its members are given by
\[
h_d(z) =
\sum_{K \leq \delta \leq d}
\sum_{0 \leq k \leq d - \delta}
t_k(z) \cdot g_{\delta}(z-k) \cdot{t}_{d-\delta-k}'(z-k-\delta)
\]
In general, if the family
$\Gamma = \left( g_i(z) \right)_{i \in {\bf Z}}$ has a finite
number of nonzero terms - and hence corresponds to a linear
difference operator with polynomial coefficients - the same
will not be true for the members of the conjugate family
$\Lambda = \left( h_i(z) \right)_{i \in {\bf Z}}$,
as the case of a singleton family $\Gamma_{g,\delta}$
clearly shows. We also expect the degree of the
conjugate polynomials $h_i(z)$ to be higher
than the degrees of the $g_j(z)$. Thus it will come rather as an
exception if the conjugate under $\Phi$-transform of a finite
polynomial family $\Gamma$ (in the above sense) is again of the
same type.
In the next section we will study this situation with respect to
a variant of the Legendre transform.
\section{(Reduced) Legendre transform preserves degrees}
We consider now the matrix ${\bf P} = (p_{i,j})_{i,j \geq 0}$
belonging to the Legendre transform, i.e.
\[
p_{i,j} = {i \choose j}{i+j \choose j} = {2j \choose j} {i+j \choose i-j}
\]
which corresponds to a family
$\Pi = \left( p_k(z) \right)_{k \in {\bf Z}}$
whose members do not behave polynomially.
Since it is slightly more convenient to work with polynomials only,
we will write
\[
{\bf P} = {\bf Q} \cdot {\bf \Delta}
\]
where
\begin{equation}\label{F}
{\bf Q} = (q_{i,j})_{i,j \geq 0}~~{\rm with}~~
q_{i,j} = {i+j \choose i-j}~~{\rm and}~~
{\bf \Delta} = {\rm diag} \left( {2i \choose i} \right)_{i \geq 0}
\end{equation}
The matrix ${\bf Q}$ belongs to the polynomial family
$\Phi = \left( q_k(z) \right)_{k \in {\bf Z}}$
where
$q_k(z) = {2z -k \choose k}~(k \geq 0)$. Note that the
family $\Phi' = \left( q_k'(z) \right)_{k \in {\bf Z}}$
belonging to the inverse matrix ${\bf Q}^{-1}$
is given by
\begin{equation}\label{G}
q_k'(z) = (-1)^k
\left[
{2z \choose k}-{2z \choose k-1}
\right] =
(-1)^k {2z \choose k} {2z-2k+1 \over 2z-k+1}
\end{equation}
so that
$q_0(z) = q_0'(z) =1$ and $\deg q_k(z) = \deg q_k'(z) = k~(k \geq 0)$.
The transformation provided by the matrix ${\bf Q}$ and its inverse
will be called {\em reduced Legendre transform}. Since it differs
from the Legendre transform just by multiplication with the diagonal
matrix $\Delta$, it will be easy to carry over results from one
situation to the other.
Let us now take singleton families $\Gamma_{g,\delta}$ as above,
with polynomial $g(z)$ and $\delta \in {\bf Z}$, and study their
reduced Legendre transform. Let
$\Lambda = \left( h_d(z) \right)_{d \in {\bf Z}}$
be the conjugate family obtained from (reduced)
Legendre transform, i.e.
\[
D_{\Lambda} = D_{\Phi}
\cdot D_{\Gamma_{g,\delta}}
\cdot \left( D_{\Phi} \right)^{-1}
\]
Below I will sketch a proof of
\begin{prop}
With the notions introduced, one has $\deg h_d(z) \leq \deg g(z)$
for all $d \geq \delta$, and hence the same result holds
by linearity for any (summable) combination of such singleton families
\end{prop}
The proof will only given as a sketch, technical details will be
left out. Note that the assertion is robust under linear transformations
of the $z$-variable, so free use can be made of this fact.
From (\ref{E}),(\ref{F}), and (\ref{G}) we know that we have to evaluate
\[
h_d(z) =
\sum_{k=0}^n
g(z-k) {2z-k \choose k}
(-1)^{n-k}
{2(z-k-\delta) \choose n-k}
{2(z-\delta-n)+1 \over 2(z-\delta)-n-k+1}
\]
where $n = d - \delta \geq 0$.
By expanding and linear transformation it turns out that it is
sufficient to show that for $t \geq 0$ a sum like
\[
\sum_{k=0}^n
(-1)^{n-k} \, k^t \,
{z+d-k \choose k}{z-2k \choose n-k}
{z-2n+1 \over z-n-k+1}
\]
is a polynomial of degree $\leq \min (n,t)$ in $z$.
Now, this follows from
\begin{lemma}
For each integer $t \geq 0$
\[
r_{n,t}(z,d) =
\sum_{k=0}^n
(-1)^{n-k}
k(k-1)\ldots (k-t+1)
{z+d-k \choose k}{z-2k \choose n-k}
{z-2n+1 \over z-n-k+1}
\]
is a polynomial in $z$ and $d$ with:
\begin{enumerate}
\item
$r_{n,t}(z,d) = 0$ for $0 \leq n < t~~$(trivially);
\item
for $n \geq t$, $r_{n,t}(z,d)$ is a polynomial of total degree $n$, and
its terms of highest degree are given by
\[
{1 \over (n-t)!} (z+d)^t \cdot d^{n-t}
\]
\item
the degree in $z$ of $r_{n,t}(z,d)$ is always $\leq t$, and in
particular
\[
r_{n,0}(z,d) = {n+d-1 \choose n}
\]
\end{enumerate}
\end{lemma}
For our purposes, we are only interested in the assertion
about the $z$-degree. The proof of this lemma can be reduced to
the proof of a similar assertion for sums like
\[
\sum_{k=0}^n
(-1)^k \, k^t \,
{z+d-k \choose k}
{z-2k \choose n-k}
\]
or
\[
\sum_{k=0}^n
(-1)^k
{k \choose t}
{z+d-k \choose k}
{z-2k \choose n-k}
\]
for nonnegative integer values of $t$.
Let us now consider a bit more generally sums like
\begin{equation}\label{G1}
\sum_{k=0}^n
(-1)^k
{k \choose t}
{x+\lambda\, k \choose k}
{y + \mu \,(n-k) \choose n-k}
\end{equation}
Note that the above sums show up when specializing:
\[
x = z+d ~,~y = z-2n ~,~\lambda=-1~,~\mu = 2
\]
For $t > n$ it is clear, that the sum vanishes, since every
summand equals zero.
\newline
For $0 < t < n$, the first $t$ terms of (\ref{G1}) vanish, and
this together with rewriting of binomial coefficients
and linear transformation of the variables makes it
possible to replace the sum by a similar one in which
the range $0 \ldots n$ has been replaced by $0 \ldots n-t$.
(Some care has to be taken to see that the inductive argument
goes through in this situation).
\newline
The critical case which remains to be treated and which can
be eventually be made responsible for the cancellation
phenomenon is then the case $t=0$.
Here we can use:
\begin{lemma}
\[
\sum_{k=0}^n
(-1)^k
{x+\lambda k \choose k}
{y + \mu (n-k) \choose n-k}
\]
can be written as a polynomial in $(x-y)$, provided
$\lambda + \mu = 1$.
\end{lemma}
In particular, if we replace $x$ by $z+a$ and similarly
$y$ by $z+b$, for some $a,b$ independent of $z$ and $k$, the
the sum is a constant w.r.t. $z$.
\bigskip
Let us now take a tridiagonal matrix ${\bf G}$ associated
with polynomials of second degree, i.e.
${\bf G} =D_{\Gamma}$ where
$\Gamma = \left( g_i(z) \right)_{i \in {\bf Z}}$ s. th.
\parbox{11cm}{
\begin{eqnarray*}
g_{-1}(z) &=& a_0 + a_1\,z + a_2\,z^2 \\
g_0(z) &=& b_0 + b_1\,z + b_2\,z^2 \\
g_1(z) &=& c_0 + c_1\,z + c_2\,z^2 \\
g_k(z) &=& 0 ~~{\rm if}~~|k| > 1
\end{eqnarray*}}
\hfill
\parbox{1cm}{\begin{eqnarray}\label{H}\end{eqnarray}}
Let $\Lambda = \left( h_d(z) \right)_{d \in {\bf Z}}$ be
the conjugate family obtained from $\Gamma$ via reduced
Legendre transform. We know from the above considerations,
that for $d \geq -1$ the polynomials $h_d(z)$ are polynomials of degree
$2$ if we take the coefficients $a_0, \ldots , c_2$ as indeterminates.
What we are interested in is the question:
{\em under which conditions will the matrix $D_{\Lambda}$
again be a tridiagonal matrix,
(i.e. $h_d(z) = 0$ for $|d| > 1$) ?} It should be clear that the
occurence of this phenomenon is expressible as a linear condition
in the indeterminates. So let us use the above formulas and calculate
the first few values of
$h_d(z) = \lambda_{d,0} + \lambda_{d,1} \, z + \lambda_{d,2} \, z^2$
\[
\begin{array}{rrrr}
d & \lambda_{d,0} & \lambda_{d,1} & \lambda_{d,2} \\
-1& a_0 & a_1 & a_2 \\
0 & -2 a_0 +a_1 - a_2 & -4 a_1 + 4 a_2 + b_1 & -6a_2+b_2 \\
1 & a_0 -5 a_1 +11 a_2 & 7 a_1 - 26 a_2 & 17 a_2 - 4 b_2 + c_2 \\
& +b_1 - b_2 + c_0 & -2 b_1 + 4 b_2 + c_1 & \\
2 & 12 a_1 - 54 a_2 &-8 a_1 + 48 a_2 & -32 a_2 + 8 b_2 - 2 c_2 \\
& -3 b_1 + 9 b_2 &+2 b_1 - 18 b_2 & \\
&2 c_0 + c_1 - c_2 & + 4 c_2 & \\
3 & -20 a_1 +170 a_2 & 8 a_1 - 188 a_2 & 48 a_2 - 12 b_2 + 3 c_2 \\
& + 5 b_1 - 35 b_2 & - 2 b_1 + 44 b_2 & \\
& + 3 c_0 - c_1 + 7 c_2 & c_1 - 10 c_2 & \\
4 & 28 a_1 - 406 a_2 & - 8 a_1 + 340 a_2 & -64 a_2 + 16 b_2 - 4 c_2 \\
& -7 b_1 + 91 b_2 & +2 b_1 - 82 b_2 & \\
& +4 c_0 + 2 c_1 - 20 c_2 & + 20 c_2 & \\
5 & -36 a_1 + 810 a_2 & 8 a_1 - 540 a_2 & 80 a_2 -20 b_2 + 5 c_2 \\
& + 9 b_1 - 189 b_2 & -2 b_1 + 132 b_2 & \\
& +5 c_0 - 2 c_1 &c_1 - 32 c_2 &
\end{array}
\]
Either via manipulation of formulas (tedious) or interpolation
from the first few values we can find the following explicit
general form for the polynomials $h_d(z)$ as functions of
the indeterminates $a_0, \ldots , c_2$:
\begin{eqnarray*}
h_d(z) & = & (-1)^d \left\{
\left[ -16 a_2 + 4 b_2 - c_2 \right] d \, z^2 +
+ \left[ 24 a_2 - 6 b_2 + {3 \over 2} c_2 \right] d^2 \, z \right.\\
&&
+ \left[ -16 a_2 + 4 b_2 - c_2 \right] d \, z
+ \left[ -8 a_1 + 20 a_2 + 2 b_1 - 2 b_2 \right] z \\
&&
+ \left[ -8 a_2 + 2 b_2 - {1 \over 2} c_2 \right] d^3
+ \left[ 12 a_2 - 3 b_2 + {4 \over 2} c_2 \right] d^2 \\
&&
+ \left[ 8 a_1 - 24 a_2 - 2 b_1 + 3 b_2 + (-1)^d c_0
+ {1 \over 2} c_1 \right] d
\\
&&
\left.
+ \left[ -4 a_1 + 10 a_2 + b_1 - b_2 \right] \right\}+ {1- (-1)^d \over 2}
\left[ c_1 + {1 \over 2} c_2 \right]\,(z - {1 \over 2})
\end{eqnarray*}
From this we conclude that for $h(d)$ to vanish identically for $d \geq 2$
it is necessary and sufficient to have
\parbox{11cm}{
\begin{eqnarray*}
c_2 &=& -16 a_2 + 4 b_2\\
c_1 &=&-{1 \over 2} c_2 = 8 a_2 - 2 b_2\\
c_0 &=& 0 \\
b_1 &=& 4 a_1 + 10 a_2 + b_2
\end{eqnarray*}}
\hfill
\parbox{1cm}{\begin{eqnarray}\label{I}\end{eqnarray}}
and the parameters $a_0,a_1,a_2,b_0,b_2$ may be chosen independently.
(Actually, rank consideration show that the vanishing of
$h_2(z)$ and $h_3(z)$ is sufficient to impose these conditions,
whereas vanishing of $h_2(z)$ or $h_3(z)$ alone is not).
Let us note that under the mentioned conditions the polynomials
$h_{-1}(z)$, $h_0(z)$ and $h_1(z)$
turn out to be:
\parbox{11cm}{
\begin{eqnarray*}
h_{-1}(z) &=& g_{-1}(z) = a_1 + a_1 \, z + a_2 \, z^2 \\
h_0(z) &=&
(-6 a_2 + b_2) z^2 + (-6 a_2 + b_2) z - 2 a_0 + a_1 + a_2 + b_0 \\
&=&
(-6 a_2)z^2 + (4 a_2 - 4 a_1)z - 2 a_0 + a_1 - a_2 + g_0(z) \\
h_1(z) &=&
a_2 \, z^2 + (2 a_2 - a_1)z + a_0 - a_1 + a_2 \\
&=&
a_2(z+1)^2 - a_1(z+1)+a_0 = g_1(-z-1)
\end{eqnarray*}}\hfill
\parbox{1cm}{\begin{eqnarray}\label{J}\end{eqnarray}}
Thus we have shown:
\begin{thm}
For any tridiagonal matrix ${\bf G} = D_{\Gamma}$ as specified
in (\ref{H}), the matrix ${\bf H} = D_{\Lambda}$ obtained via
reduced Legendre transform, i.e.
\[
{\bf H} = {\bf Q} \cdot {\bf G} \cdot {\bf Q}^{-1}
\]
is again tridiagonal if and only if the conditions in (\ref{I}) are
satisfied.
\newline
In this case, the family $\Lambda$ is given by (\ref{J}).
\end{thm}
Note that a {\em verification} of the if-part of this result is just as
easy as the verificational proof of identity (\ref{D}). Again, we can verify
\[
{\bf H} \cdot {\bf Q} = {\bf Q} \cdot {\bf G}
\]
by comparing the $(i,j)$-entries of the matrices
on both sides with $i$ and $j$ as indeterminates.
The same remarks as made at the end of section 3 apply.
The result of theorem 5
can be rephrased in terms of the original Legendre
transform. Let
\[
{\bf \tilde{G}} = {\bf \Delta}^{-1} \cdot {\bf G} \cdot {\bf \Delta}
\]
with ${\bf \Delta} = diag\left( {2k \choose k} \right)_{k \geq 0}$.
Then ${\bf \tilde{G}} = D_{\tilde{\Gamma}}$ where
$\tilde{\Gamma} = \left( \tilde{g}_k(z) \right)_{k \in {\bf Z}}$
is given by
\[
\tilde{g}_k(z)
=
\cases{
{4z+2 \over z+1}\,g_{-1}(z) & if $k = -1$ \cr
g_0(z) & if $k=0$ \cr
{z \over 4z-2}\, g_1(z) & if $k=1$ \cr
0 & else}
\]
If we impose conditions (\ref{I}) and furthermore
require that $z+1 \, | \, g_{-1}(z)$ (which
introduces a further linear constraint: $a_0 = a_1 - a_2$),
then we find:
\begin{cor}
Legendre transform
\[
{\bf H } = {\bf P } \cdot {\bf \tilde {G}} \cdot {\bf P}^{-1}
\]
maps the polynomials
\begin{eqnarray*}
\tilde{g}_{-1}(z) &=& A \, z^2 + B \, z + C \\
\tilde{g}_0(z) &=& (A+D)\,z^2 +(-A+B+D) \, z + E \\
\tilde{g}_1(z) &=& D \, z^2
\end{eqnarray*}
onto
\begin{eqnarray*}
h_{-1}(z) &=& {z+1 \over 4z+2} \left( A \, z^2 + B \, z + c \right) \\
h_{0}(z) &=& {1 \over 2} \left[ (2D-A)\,z(z+1) + 2E - C \right] \\
h_1(z) &=& {z \over 4z+2} \left[ A \, z^2 + (2A -B)\,z + (A-B+C)\right]
\end{eqnarray*}
\end{cor}
Note that the translation is given by
$A=4a_2$, $B=-2a_2+4a_1$, $C=2(a_1-a_2)$, $D = c_2/4$ and $E = b_0$.
This is essentially the contents\footnote{
The equivalence is not complete, because the additional
linear relation introduced here reduces the number of
free parameters by one. But this is a technical matter that
can be dealt with.} of theorem 1 in \cite{schmidt:92}, where
a rather different proof using {\em creative telescoping}
is given. Note that the situation of the Franel-Ap\'ery conjugacy
is given by the particular values $A=C=1, B=2, D=-8,E=2$.
Schmidt's article contains a number of further examples
illustrating this transformation.
\section{A brief look at diophantine approximation}
In this final section I would like to draw attention to
an application of the foregoing to diophantine approximation.
The results mentioned here are adapted from \cite{schmidt:92}.
As mentioned in the beginning, Ap\'ery's surprising proof
of the irrationality of $\zeta (3)$ is
based on the recurrence relation for the Ap\'ery numbers.
In a few words, his idea of proof goes as follows (see \cite{vdpoorten:78}):
Consider the two sequences
\begin{eqnarray*}
\left( a_n \right)_{n \geq 0}
&=& (\,1\,,\,5\,,\,73\,,\,1445\,,\,33001\,,\, \ldots\, ) \\
\left( b_n \right)_{n \geq 0}
&=& (\,0\,,\,6\,,\,\frac{351}{4}\,,\,\frac{62531}{36}\,,\,
\frac{11424695}{288}\,,\,\ldots\,)
\end{eqnarray*}
satisfying both Ap\'ery's linear recurrence relation
\begin{equation}\label{K}
n^3\,u_n -(34\,n^3-51\,n^2+27\,n-5)\,u_{n-1}+(n-1)^3u_{n-2} = 0
\end{equation}
The surprising fact about $\left( a_n \right)_{n \geq 0}$ is
that all its terms are {\em integers}, which is contained in (\ref{C}),
but by no means obvious from (\ref{K}) alone. The terms of
$ \left( b_n \right)_{n \geq 0}$ are rational numbers, where
the denominator of $b_n$ divides $2 \,{\rm lcm} (1,2,\ldots ,n)^3$.
This follows from
\[
b_n = \sum_{k=0}^n {n \choose k}^2 {n+k \choose k}^2\,c_{n,k}
\]
where\[
c_{n,k} = \sum_{m=1}^n \frac{1}{m^3}
+ \sum_{m=1}^k \frac{(-1)^{m-1}}{2\,m^3 {n \choose m}{n+m \choose m}}
\]
and this also shows that
\[
\lim_{n \rightarrow \infty}
\frac{b_n}{a_n} = \zeta(3)
\]
The joint recurrence (\ref{K}) for numerator and denominator of
this recurrence allows for an estimate of the rate of convergence:
\[
\zeta(3) - \frac{b_n}{a_n} =
\sum_{k=n+1}^{\infty}
\frac{a_k\,b_{k+1} - a_{k+1} \, b_k}{a_k\,a_{k+1}}
= O\left( \frac{1}{a_n^2} \right)
\]
since
\[
a_{n-1}\,b_n - a_n \, b_{n-1} =
\frac{a_0 \,b_1 - a_1\,b_0}{n^3} = \frac{6}{n^3}
\]
The sequences $\left( p_n \right)_{n \geq 0}$ and
$\left( q_n \right)_{n \geq 0}$ with
\[
p_n = 2\,{\rm lcm}(1,2, \ldots,n)^3\,b_n~~~{\rm and}~~~
q_n = 2\,{\rm lcm}(1,2, \ldots,n)^3\,a_n~~(n \geq 0)
\]
respectively, are {\em integer} sequences with
\[
\lim \frac{p_n}{q_n} = \lim \frac{b_n}{a_n} = \zeta(3)
\]
and from an estimate of the growth rate of $\left( a_n \right)_{n \geq 0}$
(which is obtained from coefficients of the recurrence (\ref{K})) one can show
that the convergence of $\left( \frac{p_n}{q_n}\right)_{n \geq 0}$ towards
$\zeta(3)$ is rapidly enough (in terms of the growth of the $q_n$)
so as to establish non-rationality of the limit.
In terms of our matrix notation, writing ${\bf A}$ for the matrix
representing the Ap\'ery recurrence, $\bf a$ for the (column)-vector of the
$a_n~(n\geq 0)$ and similarly for $\bf b$, we have
\[
{\bf A} \cdot {\bf a} = {\bf 0}
~~~{\rm and}~~~
{\bf A} \cdot {\bf b} =
\left[
{6 \atop {\bf 0} } \right]
\]
where on the right we have a vector with a $0$ in all positions, except
a $6$ in the top position.
As to the Franel recurrence, it has been remarked by Cusick (see a
footnote in \cite{vdpoorten:78}) that both sequences
\begin{eqnarray*}
\left( f_n \right)_{n \geq 0} &=&
(1,2,10,56,346,\ldots) \\
\left( g_n \right)_{n \geq 0} &=&
(0,3,12,\frac{208}{3},\frac{1280}{3},\ldots)
\end{eqnarray*}
satisfying the Franel recurrence, which we may write as
\[
{\bf F} \cdot {\bf f} = {\bf 0}
~~~{\rm and}~~~
{\bf F} \cdot {\bf g} = \left[ {3 \atop {\bf 0}} \right]
\]
lead to a diophantine approximation:
\begin{equation}
\lim \frac{g_n}{f_n} = \frac {\pi^2}{8}
\end{equation}
We have seen above that the equation
\[
{\bf A} \cdot {\bf a} = {\bf 0}
~~~{\rm and}~~~
{\bf F} \cdot {\bf f} = {\bf 0}
\]
are related via Legendre conjugacy. Now conjugacy provides us
with a solution of an inhomogeneous Franel recurrence
associated to the second solution $\bf b$ of the (homogeneous)
Ap\'ery recurrence:
\[
{\bf A} \cdot {\bf b} =
\left[ {6 \atop {\bf 0}} \right]
~~~{\rm vs.}~~~
{\bf F} \cdot {\bf h} = {\bf k}
\]
where $\bf h$ and $\bf k$ are vectors belonging to the sequences
\begin{eqnarray*}
\left( h_n \right)_{n \geq 0}
&=&
(\,0\,,\,3\,,\,\frac{93}{8}\,,\,\frac{1217}{18}\,,\,
\frac{239429}{576}\,,\,\ldots\,) \\
\left( k_n \right)_{n \geq 0}
&=&
(\,3\,,\,-\frac{3}{2}\,,\,1\,,\,-\frac{4}{3}\,,\,
\ldots\,,\,(-1)^n \frac{3}{n+1}\,,\,\ldots\,)
\end{eqnarray*}
Similarly, the second solution $\bf g$ of the (homogeneous)
Franel recurrence provides us with a solution of an inhomogeneous
Ap\'ery recurrence:
\[
{\bf F} \cdot {\bf g} =
\left[ {3 \atop {\bf 0}} \right]
~~~{\rm vs.}~~~
{\bf A} \cdot {\bf c} = {\bf d}
\]
where $\bf c$ and $\bf d$ are vectors belonging to the sequences
\begin{eqnarray*}
\left( c_n \right)_{n \geq 0}
&=&
(\,0\,,\,6\,,\,90\,,\,\frac{5348}{3}\,,\,\frac{122140}{3}\ldots) \\
\left( d_n \right)_{n \geq 0}
&=&
(\,6\,,\,18\,,\,30\,,\,\ldots\,,\,3\,(4n+2)\,,\,\ldots\,)
\end{eqnarray*}
As a result, we get the approximations
\[
\lim_{n \rightarrow \infty} \frac{h_n}{f_n} = \zeta(3)
~~~{\rm and}~~\lim_{n \rightarrow \infty}
\frac{c_n}{a_n} = \frac{\pi^2}{8}
\]
i.e. one approximation of $\zeta (3)$ in terms of Franel-recursive
sequences, and one of $\pi^2/8$ in terms of Ap\'ery-recursive
sequences. From this, one may hope for a proof of independence
of $\{\,1\,,\pi^2/8\,,\,\zeta(3)\,\}$ over the rationals.
\begin{thebibliography}{10}
\bibitem{askeywil:84}
R.~Askey and J.~A. Wilson.
\newblock A recurrence relation generalizing those of {A}p\'ery.
\newblock {\em J. Austral. Math. Soc. (Series A)}, 36:267--278, 1984.
\bibitem{bailey:38}
W.~N. Bailey.
\newblock The generating function for {J}acobi polynomials.
\newblock {\em J. London Math. Soc.}, 13:243--246, 1938.
\bibitem{cartier:91}
P.~Cartier.
\newblock D\'emonstration "automatique" d'identit\'es et fonctions
hyperg\'eometriques [d'apr\`es {D}. {Z}eilberger].
\newblock In {\em S\'eminaire Bourbaki}, volume 746, 1991.
\bibitem{comtet:74}
L.~Comtet.
\newblock {\em Advanced Combinatorics}.
\newblock Reidel, Dordrecht, 1974.
\bibitem{cusick:89}
T.~Cusick.
\newblock Recurrences for sums of powers of binomial coefficients.
\newblock {\em J. Comb. Theory (A)}, 52:77--83, 1989.
\bibitem{franel:94}
J.~Franel.
\newblock notes published in: {\em L'Interm\'ediaire des Math\'ematiciens},
vol. 1 (1894), 45-47, and vol. 2 (1895), 33-35.
\bibitem{gosper:78}
R.~W. Gosper.
\newblock Decision procedure for indefinite hypergeometric summation.
\newblock {\em Proc. Nat. Acad. Sci. USA}, 75:40--42, 1978.
\bibitem{gould:72}
H.~W. Gould.
\newblock {\em Combinatorial Identities: A Standardized Set of Tables Listing
500 Binomial Coefficient Identities} (rev. ed.).
\newblock Morgantown, W. VA., 1972.
\bibitem{hornegger:92}
J.~Hornegger.
\newblock {\em Hypergeometrische {S}ummation und polynomiale {R}ekursion}.
\newblock Diplomarbeit, IMMD-I, Erlangen, 1992.
\bibitem{koornwinder:92}
T.~H. Koornwinder.
\newblock On {Z}eilberger's algorithm and its $q$-analogue: a rigorous
description.
\newblock Technical Report AM-R9207, Centre for Mathematics and Computer
Science, Amsterdam, 1992.
\bibitem{perlstadt:87}
M.~A. Perlstadt.
\newblock Some recurrences for sums of powers of binomial coefficients.
\newblock {\em J. Number Theory}, 27:304--309, 1987.
\bibitem{riordan:68}
J.~Riordan.
\newblock {\em Combinatorial Identities}.
\newblock John Wiley \& Sons, Inc., New York-London-Sidney, 1968.
\bibitem{salvyzim:92}
B.~Salvy and P.~Zimmerman.
\newblock {\sc Gfun}: a {M}aple package for the manipulation of generating and
holonomic functions in one variable.
\newblock preprint, October 1992.
\bibitem{schmidt:90}
A.~L. Schmidt.
\newblock Generalized {L}egendre polynomials.
\newblock {\em J. Reine Angew. Math.}, 404:192--202, 1990.
\bibitem{schmidt:91}
A.~L. Schmidt.
\newblock Generalized {L}egendre and q-{L}egendre polynomials.
\newblock In {\em VII Simposium sobre polinomios ortogonales y applicaciones,
Granada 1991}, 1991.
\newblock (to appear in: J. Comp. Appl. Math.).
\bibitem{schmidt:92}
A.~L. Schmidt.
\newblock {L}egendre transforms and {A}p\'ery's sequences.
\newblock preprint series~14, Matematisk Institut, University of Copenhagen,
August 1992.
\bibitem{stanton:80}
D.~Stanton.
\newblock A short proof of a generating function for the {J}acobi polynomials.
\newblock {\em Proc. Amer. Math. Soc.}, 80:398--400, 1980.
\bibitem{strehl:92}
V.~Strehl.
\newblock Binomial identities: combinatorial and algorithmic aspects.
\newblock (in preparation).
\bibitem{strehl:90}
V.~Strehl.
\newblock {\em Zykel-{E}numeration bei lokal-strukturierten {F}unktionen}.
\newblock Habilitationsschrift, Erlangen, 1990.
\bibitem{vdpoorten:78}
A.~J. van~der Poorten.
\newblock A proof that {E}uler missed ... {A}p\'ery's proof of the
irrationality of $\zeta(3)$.
\newblock {\em Math. Intelligencer}, 1:195--203, 1978.
\bibitem{wilfzeil:90a}
H.~S. Wilf and D.~Zeilberger.
\newblock Rational functions certify combinatorial identities.
\newblock {\em J. Amer. Math. Soc.}, 3:147--158, 1990.
\bibitem{wilfzeil:90b}
H.~S. Wilf and D.~Zeilberger.
\newblock Towards computerized proofs of combinatorial identities.
\newblock {\em Bull. Amer. Math. Soc. (New Series)}, pages 77--83, 1990.
\bibitem{wilfzeil:92b}
H.~S. Wilf and D.~Zeilberger.
\newblock An algorithmic proof theory for hypergeometric (ordinary and "q")
multisum/integral identities.
\newblock {\em Invent. Math.}, 108:575--633, 1992.
\bibitem{wilfzeil:92a}
H.~S. Wilf and D.~Zeilberger.
\newblock Rational function certification of multisum/integral/"q" identites.
\newblock {\em Bull. Amer. Math. Soc. (New Series)}, 27:148--153, 1992.
\bibitem{zeilberger:90b}
D.~Zeilberger.
\newblock A fast algorithm for proving terminating hypergeometric identities.
\newblock {\em Discrete Mathematics}, 80:207--211, 1990.
\bibitem{zeilberger:91a}
D.~Zeilberger.
\newblock The method of creative telescoping.
\newblock {\em J. Symb. Comp.}, 11:195--205, 1991.
\end{thebibliography}
\end{document}