The Quasi-Holonomic Ansatz and Restricted Lattice Walks

By Manuel Kauers and Doron Zeilberger

.pdf   .ps   .tex  
[Appeared in J. Difference Equations and Applications 14 (2008) , 1119 - 1126 (Special issue in honor of Gerry Ladas' 70th Birthday)]
Written: Dec. 5, 2007.
Dedicated to Gerry Ladas, on his 70th Birthday

We have a marvelous proof of Gessel's lattice-walk conjecture, but the margins (we mean our computers) are not wide (we mean large) enough to contain it. Let's hope that we won't need to wait 350 years for another "proof".

Note added June 30, 2008: We only had to wait 6 months! See the exciting new paper, coauthored by Christoph Koutschan and the authors of the present paper.

Mathematica Packages

This article is accompanied by the following Mathematica packages (written by Manuel Kauers):

Maple Packages

This article is accompanied by the following Maple packages (written by Doron Zeilberger):

Sample Input and Output

  • To get a completely computer-generated (and rigorous (of course!)) proof of Kreweras' famous theorem, using the quasi-holonomic ansatz of our paper
    the input produces the output
    (Note: Kreweras' problem does belong to the (fully) holonomic ansatz, but the (pure) recurrence, in n, is much larger. See the pure recurrence equation (in n) .)
  • To get a completely computer-generated (and rigorous (of course!)) proof of Marni Mishna's Second Class of Walks,
    the input produces the output
  • To get a completely computer-generated (and rigorous (of course!)) proof of Marni Mishna's Fourth Class of Walks,
    the input produces the output
  • To get a completely computer-generated (and rigorous (of course!)) proof of Marni Mishna's Fifth Class of Walks,
    the input produces the output
  • To get a completely computer-generated (and rigorous (of course!)) proof of Marni Mishna's Sixth Class of Walks,
    the input produces the output
  • To get a completely computer-generated (and rigorous (of course!)) proof of Marni Mishna's Seventh Class of Walks, the input produces the output
  • To get a completely computer-generated (and rigorous (of course!)) proof of Marni Mishna's Eighth Class of Walks,
    the input produces the output
  • To get a completely computer-generated (and rigorous (of course!)) proof of Marni Mishna's Ninth Class of Walks,
    the input produces the output
Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page