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