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,
rigorouslyproved EulerAndrews Style formulas, that enables one to generate Eulerstyle "cautionary tales"
about the "danger" of using naive empirical induction. Ironically, the way we prove the Andrewsstyle corrections
is empirical! But in order to turn the empirical proof into a fullfledged rigorous proof, we must
make sure that we check sufficiently many (but still not that many!) special cases.
Maple Package
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 nonq 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
x^{2}+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 nonsymmetric 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), 653669 (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), 653669 (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
Doron Zeilberger's Home Page