%gea.tex:On Euler's "Misleading Induction", Andrews' "Fix", and How to Fully Automate them
%%a Plain TeX file by Shalosh B. Ekhad and Doron Zeilberger (x pages)
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm \ifodd\pageno \RightHead \else \LeftHead \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
On Euler's ``Misleading Induction", Andrews' ``Fix", and How to Fully Automate them
}
\rm
\bigskip
\centerline{ {\it Shalosh B. EKHAD and
Doron
ZEILBERGER}\footnote{$^1$}
{\eightrm \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/} .
April 3, 2013.
Accompanied by Maple package \hfill \break {\eighttt GEA}
downloadable from Zeilberger's website.
Supported in part by the NSF.
}
}
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
{\it Dedicated to George Andrews on his $(75-\epsilon)^{th}$ birthday}
Recall that the {\it trinomial coefficient}([Wei])
$$
{{n} \choose {j}}_2
$$
is the coefficient of $x^j$ in
$$
(1+x+x^{-1})^n \quad .
$$
In other words,
$$
(1+x+x^{-1})^n=\sum_{j=-n}^{n} {{n} \choose {j}}_2 x^j \quad .
$$
Also recall that the {\it Fibonacci numbers}, $F_n$, are defined by
$F_{-1}=1, F_0=0$, and $F_n=F_{n-1}+F_{n-2}$ for $n>0$.
The fascinating story of how Euler {\it almost} fooled himself into believing that
$$
3{{n+1} \choose {0}}_2 - {{n+2} \choose {0}}_2 = F_{n}(F_{n}+1) \quad,
\eqno(Leonhard)
$$
for {\bf all} $n$ because he checked this for the {\bf nine} values $-1 \leq n \leq 7$, only to find out
that it fails for $n=8$, leading him to record it for {\it posterity} in [E], has been told several times,
including the nice `popular' book by David Wells[Wel], Eric Weisstein's extremely useful Mathworld website[Wei],
and Ed Sandifer's famous on-line MAA column[S].
In the first three sections of George Andrews' important article [An] (that merely serve as
the motivation and background for the remaining sections that talk about deep $q$-analogs),
he describes a brilliant way to `correct' the left side of of $(Leonhard)$ in order to make the identity come true
for {\it all} $n \geq -1$.
First he used the obvious fact that
$$
{{n+2} \choose {0}}_2={{n+1} \choose {-1}}_2+{{n+1} \choose {0}}_2+{{n+1} \choose {1}}_2
$$
(and symmetry) to rewrite Eq. $(Leonhard)$ as:
$$
{{n+1} \choose {0}}_2 - {{n+1} \choose {1}}_2 = \frac{1}{2}F_{n}(F_{n}+1) \quad,
\eqno(Leonhard')
$$
and then went on to prove (using ad-hoc human ways) the identity
$$
\sum_{j=-\infty}^{\infty} {{n+1} \choose {10j}}_2 - \sum_{j=-\infty}^{\infty} {{n+1} \choose {10j+1}}_2 = \frac{1}{2} F_{n}(F_{n}+1) \quad .
\eqno(George)
$$
Note that for $n<8$ the only non-zero summands in $(George)$ are with $j=0$.
[{\eightrm At the risk of giving away the punch-line,
let's remark that once conjectured, a fully rigorous proof of $(George)$ can be obtained by checking it,
\`a la Euler, for (to be safe) $0 \leq n \leq 20$.}]
{\bf Interlude: Even Giants make stupid conjectures}
We are a little surprised that Euler could have believed, {\it even for a second}, that
Eq. $(Leonhard)$ is true for {\it all} $n$. Completely by hand (see [S]) Euler
found a three-term linear recurrence with {\it polynomial} coefficients
for ${{n}\choose {0}}_2$ (that easily implies such a recurrence for $3{{n+1}\choose {0}}_2-{{n+2}\choose {0}}_2$,
both are easily found today with the {\it Almkvist-Zeilberger algorithm} [AlZ]),
so he should have realized that it can't equal $F_n(F_n+1)$ that satisfies a linear recurrence
with {\it constant} coefficients (in other words it is what is called today a $C$-finite sequence, see [Z]).
Another way Euler could have easily realized that $(Leonhard)$ is false is via asymptotics,
even a very crude one. The ratio of consecutive terms on the left side of $(Leonhard)$ obviously tends to $3$ while
the ratios of consecutive terms on the right side tends to $\phi^2=2.61803\dots$.
{\bf The General case}
With Maple (or Sage, or any computer algebra system), it is a piece of cake to generate many Euler-style cautionary tales,
and Andrews-style fixes. Let's summarize our findings by stating a general theorem, whose {\bf proof} also tells you an
{\bf algorithm} how to compute rational generating functions for these sequences. This algorithm has been implemented in
the Maple package {\tt GEA} available from
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/GEA} .
{\bf Theorem}: Let $P(x)$ be any Laurent polynomial, and let
$$
{{n} \choose {j}}_{P}
$$
be the coefficient of $x^j$ in $P(x)^n$.
Let $k$ be a positive integer, and let $a$ be an integer such that $0\leq a