
  
%fibT.tex: A Fibonacci-Counting Proof Begged by Benjamin and Quinn (Terse)
%%a Plain TeX file by Doron Zeilberger (1 page)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\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}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%end macros
 
\bf
\centerline
{
A Fibonacci-Counting Proof Begged by Benjamin and Quinn
}
\rm
\bigskip
\centerline{ {\it 
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@math.rutgers.edu} , 
%\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/.}
May 24, 2004.
Supported in part by the NSF.
} 
}
Arthur Benjamin and Jennifer Quinn, in their delightful book[1],
asked for {\it proofs that count} of the case $\epsilon=0$ of
$$
\sum_{i} {{2n} \choose {i}} F_{2i+\epsilon}= 5^n F_{2n+\epsilon}
\quad (\epsilon=0,1) \quad .
$$
Here goes. For any vector of integers $u$, let $\vert u \vert$ denote
the sum of its entries. Let, for $\epsilon=1,0 \quad$,
$$
A_\epsilon (n):=\{(w,u) : w \in \{0,1\}^{2n}
\quad , \quad u \in \{1,2\}^{*} \quad , \quad
2 \vert w \vert-\vert u \vert=\epsilon \quad \} \quad ,
$$
$$
B_\epsilon (n):=\{(w,u) : w \in \{1,2,3,4,5\}^{n}
\quad , \quad u \in \{1,2\}^{*} \quad , \quad
\vert u \vert=2n-\epsilon \quad \} \quad .
$$
The left side {\it counts} 
$A_\epsilon(n)$ and the right side counts 
$B_\epsilon(n)$, ($\epsilon=1,0$). 
Consider a directed graph with vertices $A_0$ and $A_1$,
with ten edges from $A_0$ to $A_0$ and five edges each from
$A_0$ to $A_1$, $A_1$ to $A_0$, $A_1$ to $A_1$.
Every pair $(w,u)$ of $A_\epsilon(n)$ corresponds to
an $n$-step walk on this graph that starts at $A_\epsilon$
($\epsilon=0,1$), as follows. 

Indeed, write $w=w'w''$, where $length(w')=2$.
For $(w,u)$ of $A_\epsilon(n)$ ($\epsilon=0,1$),
let $u''$ be the longest suffix of $u$ such that $(w'',u'')$ belongs
to either $A_0(n-1)$ or $A_1(n-1)$, and write $u=u'u''$.
Equivalently, let $u'$ be the shortest prefix such that
$(w',u')$ belongs to $A_0(1)$ or $A_1(1)$.
By inspection, there are 
ten ways of getting from $A_0(n)$ to $A_0(n-1)$ and five 
ways each of getting from
$A_0(n)$ to $A_1(n-1)$, $A_1(n)$ to $A_0(n-1)$, $A_1(n)$ to $A_1(n-1)$.
Thus by repeatedly chopping the first two letter of $w$ and
the appropriate prefix of $u$, and recording the transitions, and
the new `state', each member of $A_0(n)$ or $A_1(n)$ induces
an $n$-step walk on the above directed graph that starts at
$A_0$ or $A_1$, respectively.

In the same vein, but even simpler, $B_0(n)$ and $B_1(n)$ correspond
to $n$-step walks staring at $A_0$ and $A_1$ on that very same
directed graph. The details are left to the reader.

{\bf REFERENCE}

1. A. Benjamin and J. Quinn, ``{\it Proofs that Really Count:
The Art of Combinatorial Proofs}'', The Math. Assoc. of Amer. 2003.

\end



