A Fibonacci-Counting Proof Begged by Benjamin and Quinn

Doron ZEILBERGER ^{1}

Arthur Benjamin and Jennifer Quinn, in their delightful book[1], asked for proofs that count of the case ϵ = 0 of

∑_{i} \binom{2n}{i}F_{2i+ϵ} = 5^{n}F_{2n+ϵ} (ϵ = 0, 1) .

Here goes. For any vector of integers u, let |u| denote the sum of its entries. Let, for ϵ = 1, 0 ,

A_{ϵ}(n) := {(w, u) : w ∈ {0, 1}^{2n} , u ∈ {1, 2}^{∗} , 2|w| − |u| = ϵ } ,
B_{ϵ}(n) := {(w, u) : w ∈ {1, 2, 3, 4, 5}^{n} , u ∈ {1, 2}^{∗} , |u| = 2n − ϵ } .

The left side counts A_{ϵ}(n) and the right side counts B_{ϵ}(n), (ϵ = 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_{ϵ}(n) corresponds to an n-step walk on this graph that starts at A_{ϵ} (ϵ = 0, 1), as follows.

Indeed, write w = w′w′′, where length(w′) = 2. For (w, u) of A_{ϵ}(n) (ϵ = 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.

REFERENCE

1. A. Benjamin and J. Quinn, “Proofs that Really Count: The Art of Combinatorial Proofs”, The Math. Assoc. of Amer. 2003.

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg@math.rutgers.edu , http://www.math.rutgers.edu/~zeilberg/.

May 24, 2004. Supported in part by the NSF.