A Fibonacci-Counting Proof Begged by Benjamin and Quinn

Doron ZEILBERGER ^{∗}

Arthur Benjamin and Jennifer Quinn, in their delightful “Proofs that Really Count: The Art of Combinatorial Proof” (MAA, 2003), asked for a bijective proof of (f_{n} := F_{n+1})

∑_{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 ϵ ∈ {0, 1} ,

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). Both sets can be bijectively mapped to the set of n-step walks from A_{ϵ} 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) ∈ A_{ϵ}(n), write w = w′w′′, where length(w′) = 2, and u = u′u′′ where u′ is the shortest head of u such that |u′| = 2|w′| − ϵ or |u′| = 2|w′| − ϵ + 1, which entails (w′′, u′′) ∈ A_{0}(n − 1), (w′′, u′′) ∈ A_{1}(n − 1), respectively. There are ten ^{1} ways of getting from A_{0}(n) to A_{0}(n − 1), five^{2} ways of getting from A_{0}(n) to A_{1}(n − 1), five^{3} ways of getting from A_{1}(n) to A_{0}(n − 1), and five^{4} 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) ∈ B_{ϵ}(n) , write w = w′w′′, where length(w′) = 1, and u = u′u′′ where u′ is the shortest head of u such that |u′| = 2−ϵ or |u′| = 3−ϵ which entails (w′′, u′′) ∈ B_{0}(n−1), (w′′, u′′) ∈ B_{1}(n−1), respectively. There are ten ^{1′} ways of getting from B_{0}(n) to B_{0}(n − 1), five^{2′} ways of getting from B_{0}(n) to B_{1}(n − 1), five^{3′} ways of getting from B_{1}(n) to B_{0}(n − 1), and five^{4′} 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’.

∗ 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/.

First Version: May 24, 2004. This version: May 28, 2004. Supported in part by the NSF.

1 (w′, u′) = (00, ϕ), (01, 11), (01, 2), (10, 11), (10, 2), (11, 1111), (11, 112), (11, 121), (11, 211), (11, 22). 2 (w′, u′) = (01, 12), (10, 12), (11, 1112), (11, 122), (11, 212). 3 (w′, u′) = (01, 1), (10, 1), (11, 111), (11, 12), (11, 21). 4 (w′, u′) = (00, ϕ), (01, 2), (10, 2), (11, 112), (11, 22). 1′ (w′, u′) = (1, 11), (2, 11), (3, 11), (4, 11), (5, 11), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2). 2′ (w′, u′) = (1, 12), (2, 12), (3, 12), (4, 12), (5, 12). 3′ (w′, u′) = (1, 1), (2, 1), (3, 1), (4, 1), (5, 1). 4′ (w′, u′) = (1, 2), (2, 2), (3, 2), (4, 2), (5, 2).