An Empirical Method for Solving (rigorously!) Algebraic Functional Equations Of the Form F(P(x,t), P(x,1),x,t)=0

Ira M. Gessel and Doron Zeilberger

.pdf   .ps   .tex  

First Posted: Dec. 28, 2014; Last update (of this page, not the article): Feb. 15, 2015.

[Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, Ira Gessel's website, and]

Added Jan. 2, 2019: Colin R. Defant, from Princeton University correctly pointed out that there is an issue with the current version. There is a hidden assumption that the functional equation in question should be solvable in the ring of formal power series. I believe that once this hidden assumption is made explicit, then everything will work out.

CNRS Silver-medalist, Mireille Bousquet-Mélou, in a recent talk, lamented `Adieu l'élégance'. The proofs produced by the Maple package described in this article are indeed far from `elegant', for most humans, but the method sure is meta-elegant, since it is so simple!

This is a long overdue fullfilment of a promise made in 1991, where it was referenced in this article, labeled "in planning". But it was good that it took so long, since now computers are so much faster, and we are much better programmers.

Added Feb. 13 and Feb. 15, 2015: Mireille Bousquet-Mélou beat us in our game! She sent us a `one-line' maple code (that for some cases needs to be adjusted to a few more lines, to get rid of extraneous factors) that finds algebraic equations without any guessing! See her email messages.

While Mireille won this battle, and in this case, our guessing approach was not necessary, and human cleverness won (of course, still with the assistance of computers!), the main point of our article was methodological, and in the long run, we will win the "war", and our empirical and naive approach would rule. Better still, both sides will be winners, and collaborate!

Maple Package

Some Input and Output files for the Maple package FunEq

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Doron Zeilberger's Home Page