tailieunhanh - Báo cáo tin học: "The 99th Fibonacci Identity"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The 99th Fibonacci Identity. | The 99th Fibonacci Identity Arthur T. Benjamin Alex K. Eustis and Sean S. Plott Department of Mathematics Harvey Mudd College Claremont CA USA benjamin@ Submitted Feb 7 2007 Accepted Jan 30 2008 Published Feb 25 2008 Mathematics Subject Classification 05A19 11B39 Abstract We provide elementary combinatorial proofs of several Fibonacci and Lucas number 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 offer several new identities as well. Among these we prove pk 0 n G2k 5nG2n and pk 0 n Gqk Fq 2 k Fq ỴG2n. In the book Proofs that Really Count 1 the authors use combinatorial arguments to prove many identities involving Fibonacci numbers Lucas numbers and their generalizations. 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 define terminology and illustrate our approach. Identity 1. For n 0 xinh F2n kf k 0 v 7 Here the Fibonacci numbers Fn have initial conditions F0 0 F1 1 and this identity has an elementary algebraic proof using Binet s formula and the binomial theorem but it also has a completely transparent proof using the combinatorially defined Fibonacci number fn Fn 1. It is easy to show as in 1 that fn counts the ways to tile a one-dimensional board of length n using squares of length one and dominoes of length two. We refer to such tilings THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R34 1 as n-tilings and express these tilings .