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 identities

∑_{i} \binom{2n}{i}F_{2i} = 5^{n}F_{2n} , ∑_{i} \binom{2n}{i}F_{2i+1} = 5^{n}F_{2n+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 sides of the identities count A_{ϵ}(n) and the right sides count B_{ϵ}(n), (ϵ = 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_{ϵ}(n) and B_{ϵ}(n) are in natural bijection with the set of n-step walks on this directed graph that start at C_{ϵ} (ϵ = 0, 1).

If (w, u) ∈ A_{1}(n), start your journey at vertex C_{1}. Let u′ be the shortest prefix of u such that |u′| ≥ 2(w_{1} + w_{2}) − 1, and write u = u′u′′. Of course |u′| = 2(w_{1} + w_{2}) − 1 or |u′| = 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) ∈ A_{0}(n), start your journey at vertex C_{0}. Let u′ be the shortest prefix of u such that |u′| ≥ 2(w_{1} + w_{2}), and write u = u′u′′. Of course |u′| = 2(w_{1} + w_{2}) or |u′| = 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.

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.