Combinatorial Proofs of Some Identities for Nonregular Continued Fractions

A combinatorial interpretation of nonregular continued fractions is studied. Using a modification of a tiling technique due to Benjamin and Quinn, combinatorial proofs of some identities for nonregular continued fractions are obtained. 1. Introduction In the recently popular book Proofs that Really Count [1], many identities involving linear recurrences were proved by using beautiful tiling interpretations. Many researches provided tiling proofs for a variety of identities. See, for example, [2–4]. By making use of the combinatorial interpretation of continued fractions presented by Benjamin and Quinn in [1], Benjamin and Zeilberger [5] introduced a combinatorial proof of the statement related to prime numbers. In this research, a combinatorial interpretation of nonregular continued fractions is investigated. The major part of this work is devoted to establishing combinatorial proofs of some identities for nonregular continued fractions. A continued fraction of the form where for , , , and are positive integers, is called a nonregular continued fraction. It is more convenient to use the notation for the above continued fraction. If for？？every , we denote and is said to be regular. Corresponding to each continued fraction , two sequences and are defined inductively by is called the th convergent. An importance property of these numerators and denominators of continued fractions is 2. Combinatorial Interpretation of Nonregular Continued Fractions As mentioned by Benjamin and Quinn in [1], a simple combinatorial interpretation of nonregular continued fractions can be realized. Let be the number of ways to tile an with dominoes and single tiles. All cells of the are labeled with from left to right, respectively. Figure 1 illustrates a 3-board, a single tile and a domino. Tiling must satisfy the following three conditions.(1)All cells of the must be covered.(2)For , the cell can be covered by a stack of as many as single tiles.(3)For , two consecutive cells and can be covered by a stack of as many as dominoes. Figure 1: An empty 3-board, a single tile, and a domino. It is obvious that and by focusing on the last cell covering, it follows that and Since the sequence satisfy the same initial conditions and recurrence relation as the sequence defined by (1.2), Next, we define . Similar to the case of , we obtain Equations (1.3), (2.2), and (2.3) yield For example, described by the Figures 2 and 3, we get Thus, . Figure 2: The ways to tile a 3-board with the height conditions . Figure 3: The ways to tile a 2-board with the height conditions . 3. Combinatorial