
  
%fib.tex: A Fibonacci-Counting Proof Begged by Benjamin and Quinn
%%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 identities
$$
\sum_{i} {{2n} \choose {i}} F_{2i}= 5^n F_{2n}
\quad,\quad
\sum_{i} {{2n} \choose {i}} F_{2i+1}= 5^n F_{2n+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 sides of the identities {\it count} 
$A_\epsilon(n)$ and the right sides count 
$B_\epsilon(n)$, ($\epsilon=1,0$). 
Consider a directed graph with vertices $C_0$ and $C_1$,
where there are ten edges joining $C_0$ to $C_0$,
five edges joining $C_0$ to $C_1$, five edges joining
$C_1$ to $C_0$, and five edges joining $C_1$ to $C_1$.
I claim that both $A_\epsilon(n)$ and 
$B_\epsilon(n)$ are in natural bijection with the set of
$n$-step walks on this
directed graph that start at $C_\epsilon$ ($\epsilon=0,1$).

If $(w,u) \in A_1(n)$, start your journey at vertex $C_1$.
Let $u'$ be the shortest prefix of $u$ such that
$\vert u' \vert \geq 2(w_1+w_2)-1$, and write $u=u'u''$.
Of course $\vert u' \vert=2(w_1+w_2)-1$ or $\vert u' \vert=2(w_1+w_2)$.
There are five possibilities for each of these scenarios,
and once and for all, name the five edges from $C_1$ to $C_0$
and the five edges from $C_1$ to $C_1$ by these possibilities,
respectively,
and follow the appropriate edge, at the same time shrinking
$(w,u)$ by replacing it by $(w',u'')$ where
$w'$ is $w$ with its first two entries chopped.
In the former case $(w',u'')$ belongs to $A_0(n-1)$, and in the latter case to
$A_1(n-1)$. Now continue recursively.

If $(w,u) \in A_0(n)$, start your journey at vertex $C_0$. 
Let $u'$ be the shortest prefix of $u$ such that
$\vert u' \vert \geq 2(w_1+w_2)$, and write $u=u'u''$.
Of course $\vert u' \vert=2(w_1+w_2)$ or $\vert u' \vert=2(w_1+w_2)+1$.
There are ten possibilities for the former scenario
and five possibilities for the latter.
Name, once and for all, the ten edges from $C_0$ to $C_0$,
and the five edges from $C_0$ to $C_1$ by these possibilities,
respectively,
and follow the appropriate edge, at the same time shrinking
$(w,u)$ by replacing it by $(w',u'')$ where
$w'$ is $w$ with its first two entries chopped.
In the former case 
$(w',u'')$ belongs to $A_0(n-1)$, and in the latter case to
$A_1(n-1)$. Now continue recursively.

In the same vein, but much simpler, $B_0(n)$ and $B_1(n)$ correspond
to $n$-step walks staring at $C_0$ and $C_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



