The 99th Fibonacci Identity
First published in the Electronic Journal of Combinatorics, vol. 15, no. 1 (February 2008), by the Mathematical Assocation of America.
We provide elementary combinatorial proofs of several Fibonacci and Lucas num- ber identities left open in the book Proofs That Really Count (1), and generalize these to Gibonacci sequences Gn that satisfy the Fibonacci recurrence, but with arbitrary real initial conditions. We oer several new identities as well. Among these, we prove P k 0 n k G2k = 5nG2n and P k 0 n k Gqk(Fq 2)n k = (Fq)nG2n. In the book Proofs that Really Count (1), the authors use combinatorial arguments to prove many identities involving Fibonacci numbers, Lucas numbers, and their generaliza- tions. Among these, they derive 91 of the 118 identities mentioned in Vajda's book (2), leaving 27 identities unaccounted. Eight of these identities, presented later in this paper, have such a similar appearance, the authors remark (on page 144) that \one good idea might solve them all." In this paper, we provide elegant combinatorial proofs of these Fibonacci and Lucas identities along with generalizations to arbitrary initial conditions. Before examining these new identities, we warm up with the following well known identity, which will allow us to dene terminology and illustrate our approach. Identity 1. For n 0; X k 0 n k Fk = F2n;