Document Type

Article

Department

Mathematics (HMC)

Publication Date

6-2000

Abstract

Fibonacci numbers arise in the solution of many combinatorial problems. They count the number of binary sequences with no consecutive zeros, the number of sequences of 1's and 2's which sum to a given number, and the number of independent sets of a path graph. Similar interpretations exist for Lucas numbers. Using these interpretations, it is possible to provide combinatorial proofs that shed light on many interesting Fibonacci and Lucas identities (see [1], [3]). In this paper we extend the combinatorial approach to understand relationships among generalized Fibonacci numbers.

Given G0 and G1 a generalized Fibonacci sequence G0, G1, G2,... is defined recursively by Gn = Gn-1 + Gn-2 for n ≥ 2. Two important special cases are the classical Fibonacci sequence Fn (F0 = 0 and F1 = 1) and the Lucas sequence Ln (L0 = 2 and L1 = 1).

These sequences satisfy numerous relationships. Many are documented in Vajda [6], where, they are proved by algebraic means. Our goal is to recount these identities by combinatorial means. We introduce several combinatorial techniques which allow us to provide new proofs of nearly all the identities in [6] involving generalized Fibonacci numbers. We show that in the framework of phased tilings, these identities follow naturally as the tilings are counted, represented, and transformed in clever ways. These techniques are developed in the next several sections. In the final section, we discuss possible extensions.

Comments

First published in The Fibonacci Quarterly, vol. 38, no. 3 (June-July 2000), by The Fibonacci Association.

This article is also available at http://www.fq.math.ca/38-3.html.

Rights Information

© 2000 The Fibonacci Association

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Download

Share

COinS