2008/06/26 by Manuel Kauers, Doron Zeilberger, Kauers, Manuel +1
Mathematics · #05A10 #33F10 #Algebraic Geometry and Number Theory #Algebraic structures and combinatorial models #Benford’s Law and Fraud Detection #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A10 #msc:33F10
paper · pdf · doi:10.48550/arxiv.0806.4318
A One-Line Proof of Kreweras' Quarter-Plane Walk Theorem. See: http://www.math.rutgers.edu/~zeilberg/tokhniot/oKreweras
arxiv created 2008/06/26 · openalex publication_date 2008/06/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The great enumerator Germain Kreweras empirically discovered this intriguing fact, and then needed lots of pages[K], and lots of human ingenuity, to prove it. Other great enumerators, for example, Heinrich Niederhausen[N], Ira Gessel[G1], and Mireille Bousquet-Mélou[B], found other ingenious, ``simpler'' proofs. Yet none of them is as simple as ours! Our proof (with the generous help of our faithful computers) is ``ugly'' in the traditional sense, since it would be painful for a lowly human to follow all the steps. But according to our humble aesthetic taste, this proof is much more elegant, since it is (conceptually) one-line. So what if that line is rather long (a huge partial-recurrence equation satisfied by the general counting function), it occupies less storage than a very low-resolution photograph.