# Combinatorial Proofs of Some Identities for Nonregular Continued Fractions

Authors: Oranit Panprasitwech
Journal: International Journal of Combinatorics
 (2012)

---

## Abstract

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.


---

## Body

## 1. Introduction

In the recently popular bookProofs 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(1.1)b0+a1b1+a2b2+⋱+anbn+⋱,,
where for i>0, ai, b0, and bi are positive integers, is called a nonregular continued fraction. It is more convenient to use the notation [b0;a1,b1;a2,b2;…;an,bn;…] for the above continued fraction. If for  every i, ai=1 we denote [b0;b1,b2,…]:=[b0;a1,b1;a2,b2;…] and [b0;b1,b2,…] is said to be regular.Corresponding to each continued fraction[b0;a1,b1;a2,b2;…], two sequences {pn} and {qn} are defined inductively by
(1.2)p0=b0,p1=b1b0+a1,pn=bnpn-1+anpn-2(n≥2),q0=1,q1=b1,qn=bnqn-1+anqn-2(n≥2),pn/qn is called the nth convergent. An importance property of these numerators and denominators of continued fractions is
(1.3)pnqn=[b0;a1,b1;…;an,bn](n≥0).


## 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.LetP(b0;a1,b1;…;an,bn) be the number of ways to tile an (n+1)-board with dominoes and single tiles. All n+1 cells of the (n+1)-board are labeled with 0,1,2,…,n 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)
Alln+1 cells of the (n+1)-board must be covered.(2)
For0≤i≤n, the ith cell can be covered by a stack of as many as bi single tiles.(3)
For1≤i≤n, two consecutive cells i-1 and i can be covered by a stack of as many as ai dominoes.Figure 1
An empty 3-board, a single tile, and a domino.It is obvious thatP(b0)=b0 and by focusing on the last cell covering, it follows that P(b0;a1,b1)=b1b0+a1 and
(2.1)P(b0;a1,b1;…;an,bn)=bnP(b0;a1,b1;…;an-1,bn-1)+anP(b0;a1,b1;…;an-2,bn-2)(n≥2).
Since the sequence {P(b0;a1,b1;…;an,bn)} satisfy the same initial conditions and recurrence relation as the sequence {pn} defined by (1.2),
(2.2)P(b0;a1,b1;…;an,bn)=pn,∀n≥0.Next, we defineQ(b0;a1,b1;…;an,bn)≔P(b1;a2,b2;…;an,bn).Similar to the case of{P(b0;a1,b1;…;an,bn)}, we obtain
(2.3)Q(b0;a1,b1;…;an,bn)=qn,∀n≥0.Equations (1.3), (2.2), and (2.3) yield
(2.4)P(b0;a1,b1;…;an,bn)Q(b0;a1,b1;…;an,bn)=[b0;a1,b1;…;an,bn](n≥0).For example, described by the Figures2 and 3, we get
(2.5)P(1;2,3;4,5)=(1×3×5)+(1×4)+(2×5)=29,Q(1;2,3;4,5)=P(3;4,5)=(3×5)+4=19.
Thus, [1;2,3;4,5]=29/19.Figure 2
The ways to tile a 3-board with the height conditions1;2,3;4,5.Figure 3
The ways to tile a 2-board with the height conditions3;4,5.


## 3. Combinatorial Proofs of Some Identities

In this section, the combinatorial interpretation presented in the previous is adopted to reach combinatorial proofs of some identities for nonregular continued fractions.The reversal identity for the generalization of regular continued fractions recently investigated by Anselm and Weintraub in [6] can easily be verified as Theorem 3.1.Theorem 3.1.
LetN be an arbitrary positive integer and pn/qn the nth convergent of [b0;N,b1;…;N,bn]. Then for all n≥1, one has
(3.1)[bn;N,bn-1;…;N,b0]=pnpn-1.Proof.
This reversal identity follows immediately from (2.2)–(2.4) and the fact that the ways to tile an (n+1)-board with the height conditions bn;N,bn-1;…;N,b0 equals the ways to tile with the height conditions b0;N,b1;…;N,bn, which leads
(3.2)P(bn;N,bn-1;…;N,b0)=P(b0;N,b1;…;N,bn)=pn,
and the fact that the ways to tile an n-board with the height conditions bn-1;N,bn-2;…;N,b0 equals the ways to tile with the height conditions b0;N,b1;…;N,bn-1, which implies
(3.3)Q(bn;N,bn-1;…;N,b0)=P(bn-1;N,bn-2;…;N,b0)=P(b0;N,b1;…;N,bn-1)=pn-1.Theorems3.2 and 3.3 are proved by modifying the proofs of Identity 110 and Identity  111 in [1] for regular continued fractions to nonregular continued fractions.Theorem 3.2.
The difference between consecutive convergents of[b0;a1,b1;…;an,bn] is
(3.4)pnqn-pn-1qn-1=(-1)n-1∏i=1naiqnqn-1(n≥1).
Equivalently, after multiply both sides by qnqn-1, we have
(3.5)pnqn-1-pn-1qn=(-1)n-1∏i=1nai(n≥1).Proof.
Denoteℙn×ℚn-1∶= the set of tiling of two boards, where on the top board has cells 0,1,2,…,n with height conditions b0;a1,b1;…;an,bn, and the bottom board has cells 1,2,…,n-1 with height conditions b1;…;an-1,bn-1 and ℙn-1×ℚn∶= the set of tiling of two boards, where on the top board has cells 0,1,2,…,n-1 with height conditions b0;a1,b1;…;an-1,bn-1, and the bottom board has cells 1,2,…,n with height conditions b1;…;an,bn.
Any element(A,B) in ℙn×ℚn-1 or ℙn-1×ℚn is said to has a fault at cell i≥1, if AandB have tiles that end at i.
It can be seen from the definitions that(1)
|ℙn×ℚn-1|=pnqn-1,(2)
|ℙn-1×ℚn|=pn-1qn,(3)
whenAorB contains a single tile, (A,B) must have a fault.
Next, we consider the numbers of fault-free elements ofℙn×ℚn-1 and ℙn-1×ℚn.Case 1 (n is odd).
There are∏i=1nai fault-free elements of ℙn×ℚn-1 as shown in Figure 4 and no fault-free element of ℙn-1×ℚn, since for all (A,B)∈ℙn-1×ℚn, A and B both cover an odd number of cells that mean A and B must contain a single tile.Figure 4
An illustration of the fault-free elements ofℙn×ℚn-1 for the case n is odd.Case 2 (n is even).
Similar to the case ofn  is odd, there are no fault-free elements of ℙn×ℚn-1 and ∏i=1nai fault-free elements of ℙn-1×ℚn.Finally, let(S,T) be an element in ℙn×ℚn-1 with (S,T) has a fault. If we swap the tails of SandT after the rightmost fault, then we get the element (S',T') in ℙn-1×ℚn that has the same rightmost fault as (S,T). Hence, by using this swapping, a one-to-one correspondence between the set of the elements that has a fault in ℙn×ℚn-1 and the set of the elements that has a fault in ℙn-1×ℚn can be constructed.Therefore,pnqn-1-pn-1qn=|ℙn×ℚn-1|-|ℙn-1×ℚn|=(-1)n-1∏i=1nai.Theorem 3.3.
Forn≥2, let pn/qn be the  nth  convergent of [b0;a1,b1;…;an,bn]. Then
(3.6)pnqn-2-pn-2qn=(-1)nbn∏i=1n-1ai.Proof.
Denoteℙn×ℚn-2∶= the set of tiling of two boards, where on the top board has cells 0,1,2,…,n with height conditions b0;a1,b1;…;an,bn, and the bottom board has cells 1,2,…,n-2 with height conditions b1;…;an-2,bn-2 and ℙn-2×ℚn∶= the set of tiling of two boards, where on the top board has cells 0,1,2,…,n-2 with height conditions b0;a1,b1;…;an-2,bn-2, and the bottom board has cells 1,2,…,n with height conditions b1;…;an,bn.
Hence|ℙn×ℚn-2|=pnqn-2 and |ℙn-2×ℚn|=pn-2qn.
Similar to the proof of Theorem3.2, we can construct a one-to-one correspondence between the set of the elements that has a fault in ℙn×ℚn-2 and the set of the elements that has a fault in ℙn-2×ℚn by swapping the tails after the rightmost fault.
Thus, it suffices to consider the numbers of fault-free elements ofℙn×ℚn-2 and ℙn-2×ℚn.Case 3 (n is odd).
There are no fault-free elements ofℙn×ℚn-2 and bn∏i=1n-1ai fault-free elements of ℙn-2×ℚn, described by the examples illustrated in Figures 5 and 6.Figure 5
There are no fault-free elements ofℙn×ℚn-2 for the case n is odd.Figure 6
An illustration of the fault-free elements ofℙn-2×ℚn for the case n is odd.Case 4 (n is even).
There arebn∏i=1n-1ai fault-free elements of ℙn×ℚn-2 and no fault-free element of ℙn-2×ℚn, see Figures 7 and 8.
Therefore,pnqn-2-pn-2qn=|ℙn×ℚn-2|-|ℙn-2×ℚn|=(-1)nbn∏i=1n-1ai.Figure 7
An illustration of the fault-free elements ofℙn×ℚn-2 for the case n is even.Figure 8
There are no fault-free elements ofℙn-2×ℚn for the case n is even.



---

*Source: 894380-2012-09-29.xml*