On Euler's "Misleading Induction", Andrews' "Fix", and How to Fully Automate them

By
Shalosh B. Ekhad and Doron Zeilberger

.pdf   .ps   .tex

Written: April 3, 2013

(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, and arxiv.org)

Dedicated to George Eyre Andrews (b. Dec. 4, 1938), on his (75- ε)-th birthday.

One of the greatest experimental mathematicians of all time was also one of the greatest mathematicians of all time, the great Leonhard Euler. Usually he had an uncanny intuition on how many "special cases" one needs before one can formulate a plausible conjecture, but one time he was "almost fooled", only to find out that his conjecture was premature. See the bottom of Eric Weisstein's beautiful entry on Trinomial Coefficients.

In 1990, George Andrews found a way to "correct" Euler. Here we show how to generate, AUTOMATICALLY, rigorously-proved Euler-Andrews Style formulas, that enables one to generate Euler-style "cautionary tales" about the "danger" of using naive empirical induction. Ironically, the way we prove the Andrews-style corrections is empirical! But in order to turn the empirical proof into a full-fledged rigorous proof, we must make sure that we check sufficiently many (but still not that many!) special cases.

# Sample Output

• To see an article containing rational generating functions for the original Andrews Sums, with Trinomial coefficients and moduli,k, up to 100 (in particular the case k=10, completely does the non-q part of Andrews's paper)
the input file yields the output file.

• To see an article containing rational generating functions for the more difficult polynomial
x2+x+1+ x-1+ x-2
with moduli,k, up to 100
the input file yields the output file.

• To see an article containing rational generating functions for the non-symmetric polynomial
3x+2+5/x
with moduli,k, up to 20
the input file yields the output file.

• To see a completely rigorous proof of Andrews' Theorem 2.1 in his paper J. Amer. Math. Soc. v. 3 (1990), 653-669 (on p. 657)
the input file yields the output file.

• To see a completely rigorous proof of Andrews' Eq. 2.18 in his paper J. Amer. Math. Soc. v. 3 (1990), 653-669 (on p. 659)
the input file yields the output file.

• To get a book of "cautionary tales" warning you against naive empirical induction
the input file yields the output file.

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger