%mathar.tex: %%a Plain TeX file by Shalosh B. Ekhad and Mingjia Yang (6 pages) %begin macros \def\L{{\cal L}} \baselineskip=14pt \parskip=10pt \def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule height0.15cm width 0.01cm}} \font\eightrm=cmr8 \font\sixrm=cmr6 \font\eighttt=cmtt8 \magnification=\magstephalf \def\P{{\cal P}} \def\Q{{\cal Q}} \def\1{{\overline{1}}} \def\2{{\overline{2}}} \parindent=0pt \overfullrule=0in \def\Tilde{\char126\relax} \def\frac#1#2{{#1 \over #2}} %\headline={\rm \ifodd\pageno \RightHead \else \LeftHead \fi} %\def\RightHead{\centerline{ %Title %}} %\def\LeftHead{ \centerline{Doron Zeilberger}} %end macros \centerline {\bf Automated Proofs of Many Conjectured Recurrences in the OEIS made by R.J. Mathar } \bigskip \centerline {\it Shalosh B. EKHAD, Mingjia YANG and Doron Zeilberger} The On-Line Encyclopedia Of Integer Sequence (OEIS) ([Sl]), that wonderful resource that most combinatorialists, and many other mathematicians and scientists, use at least once a day, is a treasure trove of mathematical information, and one of its charms is that it contains many intriguing conjectures. But one should be on one's guard, because some of the conjectures are either already theorems, or can be routinely proved. As pointed out in [Z1], all identities involving sequences that belong to the {\bf $C$-finite ansatz} can be proved by checking sufficiently many initial special cases, and the number of such checks is usually very small, and the number of initial values needed to make the ``empirical" proof rigorous can be easily found. Recall that a sequence is $C$-finite if it satisfies a homogeneous linear recurrence equation with {\bf constant} coefficients, the most famous members being sequence $A000079$ \hfill\break ({\tt https://oeis.org/A000079}), namely $a(n)=2^n$, satisfying the recurrence $a(n)-2a(n-1)=0$ and sequence $A000045$ ({\tt https://oeis.org/A000045}), satisfying the recurrence $F(n)-F(n-1)-F(n-2)=0$. Things are not so simple with the $P$-recursive ansatz (see [Z2]), the class of sequences satisfying a homogeneous linear recurrence equation with {\bf polynomial} coefficients, the most famous one being sequences A000142 ({\tt https://oeis.org/A000142}), $n!$, satisfying the recurrence $a(n)\, - \, n\, a(n-1)=0$. Many sequences can be shown, by purely theoretical {\it a priori} arguments, to be $P$-recursive, so it seems that in order to prove that two differently defined $P$-recursive sequences $a(n)$ and $b(n)$ are actually equal, it should suffice to check sufficiently many initial values. Alas, while it is true that the sequence $c(n):=a(n)-b(n)$ is also $P$-recursive, if you don't know the explicit recurrence that it satisfies, it is conceivable (albeit extremely unlikely) that even if it satisfies a low-order, say, second-order, recurrence, it is something like $$ ( \, n-10^{1000000} \, )\, a(n) \, + \, (n+1) a(n-1) \, + \, (n-3) \, (n-2)=0 \quad , $$ in other words it has a `singularity' at a very large positive integer, and the `finitely many' values one has to check is $10^{1000000}+2$ rather than $2$. In such cases, to be completely rigorous, one has to actually find the recurrences, and check that they do not have such singularities, or if they do, find the largest positive integer that is a singularity. One case where it is relatively painless (for the computer) to explicitly find a recurrence for a sequence, is the case of what is called the {\bf Sch\"utzenberger ansatz} in [Z2], i.e. sequences $\{a(n)\}_0^{\infty}$ whose {\bf ordinary generating functions} $$ f(x) = \sum_{n=0}^{\infty} a(n)\,x^n \quad , $$ satisfy equations of the form $P(f(x),x)=0$, where $P$ is a polynomial of two variables. More explicitly, there exists a positive integer $A$, and polynomials $p_i(x)$, $i=0,1,\dots, A$, such that $$ \sum_{i=0}^A p_i(x) f(x)^i \, = \, 0 \quad . $$ These are discussed in the Flajolet-Sedgewick {\bf bible}, [FS]. By a well-known algorithm (that by today's standards is fairly straightforward), that goes back to the 19th century, and is implemented, {\it inter alia}, in Bruno Salvy and Paul Zimmermann's Maple package {\tt gfun}, as function {\tt algtodiffeq}, every algebraic formal power series satisfies a {\bf linear differential equation} with {\bf polynomial coefficients} $$ \sum_{i=0}^L q_i(x) \frac{d^i}{dx^i} f(x) \, = \, 0 \quad , $$ that immediately translates (by writing $f(x)=\sum_{n=0}^{\infty} a(n)x^n$, substituting into the above differential equation, and setting the coefficient of $x^n$ to $0$), to a {\bf linear recurrence equation with polynomial coefficients}, satisfied by the sequence $a(n)$ $$ \sum_{i=0}^{M} c_i(n) a(n-i) \, = \, 0 \quad . $$ This is implemented in the function {\tt diffeqtorec} in {\tt gfun}. {\bf Mathar's conjectures} When we searched the OEIS, on July 7, 2017, for {\tt Conjecture AND recurrence AND Mathar }, we got $450$ hits. Many of them concern the sequences of coefficients of generating functions given in terms of radicals. While Abel, Galois, and Ruffini famously proved that not every algebraic function can be expressed in terms of radicals, the converse is trivially true. Let's take for example, sequence $A004148$ ({\tt https://oeis.org/A004148}), where a generating function (conjectured by Michael Somos) is given $$ f(x)= {\frac {1-x+{x}^{2}-\sqrt {1-2\,x-{x}^{2}-2\,{x}^{3}+{x}^{4}}}{2 \, {x}^{2}}} \quad. $$ Obviously this is an algebraic formal power series, and the algebraic equation satisfied by $f(x)$ may be routinely obtained by clearing radicals. Alas, one often gets a higher order recurrence than the one conjectured. To prove that the simpler conjectured recurrence also satisfies this sequence one proceeds as follows. {\bf Proving that a Lower-Order Recurrence is Equivalent to a Higher-Order Recurrence} Let $N$ be the forward shift operator: $$ Na(n):=a(n+1) \quad , $$ then the fact that the sequence $\{a(n)\}_0^{\infty}$ satisfies a recurrence $$ \sum_{i=0}^{M} c_i(n) a(n-i) \, = \, 0 \quad , $$ is equivalent to the fact that $$ \left ( \sum_{i=0}^{M} c_i(n)N^{-i} \right ) a(n) \, \equiv \, 0 \quad . $$ Calling the operator on the left $C(n,N)$, we have $$ C(n,N) a(n) \, \equiv \, 0 \quad . $$ The class of linear recurrence operators with polynomial coefficients is a {\bf non-commutative} algebra, where everything commutes {\bf except} $n$ and $N$, where the commutation relation between $n$ and $N$ is $N n \,- \, n N \, = \, N$. See [Z3] for a primer. We say that the sequence $a(n)$ is {\it annihilated} by the operator $C(n,N)$. Of course, any {\bf left-multiple} of an annihilator is yet-another annihilator. For example, since $$ (N-1)(N^2-N-1)=N^3- 2N^2+1 \quad, $$ the Fibonacci numbers {\it can} be also defined by the recurrence, and initial conditions $$ F_{n+3}=2F_{n+2}-F_n \quad ; \quad F_{0}=0 \, , \, F_1=1 \, , \, F_2=1 \quad , $$ but it would not make William of Ockham happy. The Euclidean division algorithm for the commutative case is easily generalized to the case of the non-commutative algebra of linear recurrence operators with rational-function coefficients. If $A(n,N)$ is such a (monic) operator of order $d_1$ and $B(n,N)$ is such a (monic) operator of order $d_2$, with $d_1>d_2$ then there exist operators $Q(n,N)$ (the {\it quotient}), of order $d_1 -d_2$, and $R(n,N)$ (of order $