
  
%fib.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}}
\nopagenumbers
%end macros
 
\bf
\centerline
{
A Fibonacci-Counting Proof Begged by Benjamin and Quinn
}
\rm
\bigskip
\centerline{ {\it 
Doron ZEILBERGER
}
\footnote{$^*$}
{\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/.}
First Version: May 24, 2004. This version: May 28, 2004.
Supported in part by the NSF.
} 
}
Arthur Benjamin and Jennifer Quinn, in their delightful 
``{\it Proofs that Really Count:
The Art of Combinatorial Proof}'' (MAA, 2003),
asked for a bijective proof of
($f_n:=F_{n+1}$)
$$
\sum_{i} {{2n} \choose {i}} f_{2i-\epsilon}= 5^n f_{2n-\epsilon}
\quad (\epsilon \in \{0,1\}) \quad .
$$
Here goes. For any vector of integers $u$, let $\vert u \vert$ denote
the sum of its entries. Let, for $\epsilon\in \{0,1\} \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)$.
Both sets can be bijectively mapped to the set of $n$-step walks
from $A_\epsilon$ to $A_0$ in 
a digraph whose vertices are $A_0$ and $A_1$, and
there are 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$.

For $(w,u)\in A_\epsilon(n)$, 
write $w=w'w''$, where $length(w')=2$,
and $u=u'u''$ where $u'$ is the {\bf shortest} head of $u$ such that
$\vert u' \vert=2 \vert w' \vert -\epsilon$ or
$\vert u' \vert=2 \vert w' \vert -\epsilon+1$,
which entails $(w'',u'') \in A_0(n-1)$, $(w'',u'') \in A_1(n-1)$, 
respectively.
There are 
ten
\footnote{$^1$}
{\eightrm  \raggedright
$(w',u')=(00,\phi),(01,11),(01,2),(10,11),(10,2),(11,1111),
(11,112),(11,121),(11,211),(11,22)$.
} ways of getting from $A_0(n)$ to $A_0(n-1)$,
five\footnote{$^2$}
{\eightrm  \raggedright
$(w',u')=(01,12),(10,12),(11,1112),(11,122),(11,212)$.
} ways of getting from $A_0(n)$ to $A_1(n-1)$, 
five\footnote{$^3$}
{\eightrm  \raggedright
$(w',u')=(01,1),(10,1),(11,111),(11,12),(11,21)$.
} ways of getting from $A_1(n)$ to $A_0(n-1)$, 
and five\footnote{$^4$}
{\eightrm  \raggedright
$(w',u')=(00,\phi), (01,2),(10,2),(11,112),(11,22)$.
} ways of getting from $A_1(n)$ to $A_1(n-1)$.
To get the walk, repeat this passage from
$(w,u)$ to $(w'',u'')$,  $n$ times,
recording the transitions, and the `states'. 

For $(w,u)\in B_\epsilon(n)$ ,
write $w=w'w''$, where $length(w')=1$,
and $u=u'u''$ where $u'$ is the {\bf shortest} head of $u$ such that
$\vert u' \vert=2 -\epsilon$ or $\vert u' \vert=3 -\epsilon$
which entails $(w'',u'') \in B_0(n-1)$, $(w'',u'') \in B_1(n-1)$, 
respectively.
There are 
ten
\footnote{$^{1'}$}
{\eightrm  \raggedright
$(w',u')=(1,11),(2,11),(3,11),(4,11),(5,11),
(1,2),(2,2),(3,2),(4,2),(5,2)$.
} ways of getting from $B_0(n)$ to $B_0(n-1)$,
five\footnote{$^{2'}$}
{\eightrm  \raggedright
$(w',u')=(1,12),(2,12),(3,12),(4,12),(5,12)$.
} ways of getting from $B_0(n)$ to $B_1(n-1)$, 
five\footnote{$^{3'}$}
{\eightrm  \raggedright
$(w',u')=(1,1),(2,1),(3,1),(4,1),(5,1)$.
} ways of getting from $B_1(n)$ to $B_0(n-1)$, 
and five\footnote{$^{4'}$}
{\eightrm  \raggedright
$(w',u')=(1,2),(2,2),(3,2),(4,2),(5,2)$.
} ways of getting from $B_1(n)$ to $B_1(n-1)$.
To get the walk, repeat this passage from
$(w,u)$ to $(w'',u'')$,  $n$ times,
recording the transitions, and the `states'. 

 
\end





