A q-Analogue of the Bi-Periodic Fibonacci Sequence

José L. Ramírez Departamento de Matemáticas Universidad Sergio Arboleda Calle 74 No. 14 — 14 Bogotá Colombia

        josel.ramirez@ima.usergioarboleda.edu.co

Víctor F. Sirvent Departamento de Matemáticas Universidad Simón Bolívar Apartado 89000 Caracas 1086-A Venezuela

                    vsirvent@usb.ve

Abstract

The Fibonacci sequence has been generalized in many ways. One of them is defined by the relation t_{n} = at_{n−1} + t_{n−2} if n is even, and t_{n} = bt_{n−1} + t_{n−2} if n is odd, with initial values t_{0} = 0 and t_{1} = 1, where a and b are positive integers. This sequence is called the bi-periodic Fibonacci sequence. In the present article, we introduce a q-analog of the bi-periodic Fibonacci sequence, and prove several identities involving this sequence. We also give a combinatorial interpretation of this q-analog bi-periodic Fibonacci sequence in terms of weighted colored tilings.

1 Introduction

The Fibonacci numbers \underline{A000045} F_{n} are defined by the recurrence relation

F_{0} = 0, F_{1} = 1, F_{n+1} = F_{n} + F_{n−1}, n ≥ 1.

This sequence and its generalizations have many interesting combinatorial properties (cf. [22]). Many kinds of generalizations of Fibonacci numbers have been presented in the literature. In particular, Edson and Yayenie [18] introduced the bi-periodic Fibonacci sequence. For any two positive integers a and b, the bi-periodic Fibonacci sequence, say (t_{n})_{n≥0}, is determined by the following:

t_{0} = 0, t_{1} = 1, t_{n} = \begin{cases}at_{n−1} + t_{n−2}, & if n ≡ 0 (mod 2); \\ bt_{n−1} + t_{n−2}, & if n ≡ 1 (mod 2). \end{cases} n ≥ 2.

The bi-periodic Fibonacci numbers and their generalizations have been studied in several papers; among other references, see [1, 9, 17, 18, 21, 25, 26, 27, 30]. The bi-periodic Fibonacci sequence is a particular case of the continuant polynomials; for more details see [19]. Yayenie [30] found the following explicit formula to bi-periodic Fibonacci numbers

t_{n} = a^{ξ(n−1)} \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{n − i − 1}{i}(ab)^{⌊^{\frac{n−1}{2}}⌋−i},  (1)

where ξ(n) = n − 2⌊n/2⌋, i.e., ξ(n) = 0 when n is even and ξ(n) = 1 when n is odd.

There exist several slightly different q-analogues of the Fibonacci sequence. Among other references, see [3, 5, 6, 11, 12, 13, 14, 15]. In particular, Schur [28] defined the following polynomials:

D_{0}(q) = 0, D_{1}(q) = 1, D_{n}(q) = D_{n−1}(q) + q^{n−2}D_{n−2}(q).  (2)

It is clear that D_{n}(1) = F_{n}. In addition to the recurrence formula (2), D_{n}(q) can be calculated directly by the following analytic formula (cf. [3, 13]):

D_{n}(q) = \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \left[{n − j − 1 \atop j}\right]q^{j^{2}},

where the q-binomial is

\left[{n \atop k}\right] := \frac{(q; q)_{n}}{(q; q)_{k}(q; q)_{n−k}} ,

and

(a; q)_{n} := ∏_{j=0}^{n−1}(1 − aq^{j}).

One of the main applications of the polynomial D_{n}(q) is giving alternative proofs of the Rogers-Ramanujan identities; among other references, see [2, 3, 4, 16, 20].

There is a generalization of the polynomials D_{n}(q) called (Carlitz-) q-Fibonacci polynomials [12]

f_{n}(x, s) = xf_{n−1}(x, s) + q^{n−2}sf_{n−2}(x, s),  (3)

with the initial values f_{0}(x, s) = 0 and f_{1}(x, s) = 1. They can be calculated using the formula

f_{n}(x, s) = \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ l=0 \end{matrix} \left[{n − l − 1 \atop l}\right]q^{l^{2}}s^{l}x^{n−2l−1}.  (4)

A natural question is: What is the q-analogue of the bi-periodic sequence? From (3), we introduce a q-analogue of the bi-periodic Fibonacci sequence as follows:

F_{n}^{(a,b)}(q, s) = χ(n)F_{n−1}^{(a,b)}(q, s) + q^{n−2}sF_{n−2}^{(a,b)}(q, s), n ≥ 2,  (5)

with the initial values F_{0}^{(a,b)}(q, s) = 0 and F_{1}^{(a,b)}(q, s) = 1, where χ(n) is defined by χ(2n) = a and χ(2n + 1) = b. The first few terms are

0, 1, a, ab + sq, a^{2}b + asq + asq^{2}, a^{2}b^{2} + absq + absq^{2} + absq^{3} + s^{2}q^{4}, ….

We call this sequence the q-bi-periodic Fibonacci sequence. It is clear that if a = b = x we obtain the polynomials f_{n}(x, s).

In the present article, we study the q-bi-periodic Fibonacci sequence. We obtain new recurrence relations, new combinatorial identities and the generating function of the q-bi-periodic Fibonacci sequence. Finally, we introduce the tilings weighted by bi-colored squares, then we give several combinatorial proof of some identities.

2 Some basic identities

In this section, we develop several identities of the q-bi-periodic Fibonacci sequence. We give a q-analogue of the identity (1), which is a closed formula to evaluate the q-bi-periodic Fibonacci sequence. Moreover, in Theorem 4 we give a q-analogue of a generalization of Cassini’s identity.

Proposition 1. The following equality holds for any integer n ≥ 2:

F_{n}^{(a,b)}(q, s) = χ(n)F_{n−1}^{(a,b)}(q, qs) + qsF_{n−2}^{(a,b)}(q, q^{2}s).  (6)

Proof. Let G_{n}(q, s) be the right side of (6). This sequence satisfies the recurrence (5) and the same initial values. In fact,

χ(n)G_{n−1}(q, s) + q^{n−2}sG_{n−2}(q, s)

= χ(n) (χ(n − 1)F_{n−2}^{(a,b)}(q, qs) + qsF_{n−3}^{(a,b)}(q, q^{2}s))+q^{n−2}s (χ(n − 2)F_{n−3}^{(a,b)}(q, qs) + qsF_{n−4}^{(a,b)}(q, q^{2}s))

= χ(n) (χ(n − 1)F_{n−2}^{(a,b)}(q, qs) + q^{n−3}(qs)F_{n−3}^{(a,b)}(q, qs))
+ qs (χ(n − 2)F_{n−3}^{(a,b)}(q, q^{2}s) + q^{n−4}(q^{2}s)F_{n−4}^{(a,b)}(q, q^{2}s))
= χ(n)F_{n−1}^{(a,b)}(q, qs) + qsF_{n−2}^{(a,b)}(q, q^{2}s) = G_{n}(q, s).

Then Equation (6) follows.

The following lemma shows how to write the q-bi-periodic Fibonacci sequence in terms of the (Carlitz-) q-Fibonacci polynomials.

Lemma 2. The following equalities hold for any integer n ≥ 0:

F_{2n}^{(a,b)}(q, s) = \sqrt{\frac{a}{b}}f_{2n}(\sqrt{ab}, s),  (7)
F_{2n+1}^{(a,b)}(q, s) = f_{2n+1}(\sqrt{ab}, s).  (8)

Proof. Let a_{n} be the right side of (7), then sequences (a_{n})_{n≥0} and (F_{2n}^{(a,b)}(q, s))_{n≥0} satisfy the same recurrence and the same initial conditions. In fact,

a_{n} = \sqrt{\frac{a}{b}}f_{2n}(\sqrt{ab}, s) = \sqrt{\frac{a}{b}} (\sqrt{ab}f_{2n−1}(\sqrt{ab}, s) + q^{2n−2}sf_{2n−2}(\sqrt{ab}, s))
= af_{2n−1}(\sqrt{ab}, s) + q^{2n−2}sf_{2n−2}(\sqrt{ab}, s).

Similarly, we obtain Equation (8).

Theorem 3. The following equality holds for any integer n ≥ 0:

F_{n}^{(a,b)}(q, s) = a^{ξ(n−1)} \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ l=0 \end{matrix} \left[{n − l − 1 \atop l}\right](ab)^{⌊^{\frac{n−1}{2}}⌋−l}q^{l^{2}}s^{l}.

Proof. If n is even (n = 2k), then from Lemma 2 and Equation (4), we get

F_{2k}^{(a,b)}(q, s) = \sqrt{\frac{a}{b}}f_{2n}(\sqrt{ab}, s) = \sqrt{\frac{a}{b}} ∑_{l=0}^{k−1} \left[{2k − l − 1 \atop l}\right]q^{l^{2}}s^{l}(\sqrt{ab})^{2k−2l−1}

= a ∑_{l=0}^{k−1} \left[{2k − l − 1 \atop l}\right](ab)^{k−l−1}q^{l^{2}}s^{l}.

If n is odd then in analogy way we get

F_{2k+1}^{(a,b)}(q, s) = ∑_{l=0}^{k} \left[{2k − l \atop l}\right](ab)^{k−l}q^{l^{2}}s^{l}.

Note that if we consider the limit when q tends to 1 in the above theorem and s = 1 we obtain the identity (1).

Now, we are going to prove a q-analogue of this Fibonacci identity:

F_{m−1}F_{m+k} − F_{m+k−1}F_{m} = (−1)^{m}F_{k}.

We need the auxiliary sequence F̂_{n}^{(a,b)}(q, s) defined by

F̂_{0}^{(a,b)}(q, s) = 1, F̂_{1}^{(a,b)}(q, s) = 0, F̂_{n}^{(a,b)}(q, s) = χ(n − 1)F̂_{n−1}^{(a,b)}(q, s) + q^{n−2}sF̂_{n−2}^{(a,b)}(q, s),

where n ≥ 2. The first few terms are

1, 0, s, as, abs+q^{2}s^{2}, a^{2}bs+aq^{3}s^{2}+aq^{2}s^{2}, a^{2}b^{2}s+abq^{4}s^{2}+abq^{3}s^{2}+abq^{2}s^{2}+q^{6}s^{3}, …

Note that F̂_{n}^{(a,b)}(q, s) = sF_{n−1}^{(a,b)}(q, qs). Moreover, if a = b = s = 1 we obtain the polynomials E_{n}(q), which satisfy E_{n}(q) = E_{n−1}(q) + q^{n−2}E_{n−2}(q) with initial values E_{0}(q) = 1 and E_{1}(q) = 0. Schur [28] also studied this polynomial sequence.

From identities (7) and (8), and the q-Euler-Cassini formula for the (Carlitz-) q-Fibonacci polynomials (see [14, Corollary 2.2]), we obtain the following identity:

Theorem 4. The following equality holds for integers n ≥ 0 and k ≥ 1:

λ(n, k)F_{n}^{(a,b)}(q, s)F̂_{n+k}^{(a,b)}(q, s) − λ(n + 1, k)F_{n+k}^{(a,b)}(q, s)F̂_{n}^{(a,b)}(q, s) = (−1)^{n+1}q^{\binom{n}{2}}s^{n}F_{k}^{(a,b)}(q, q^{n}s),

where λ(n, k) = \frac{b}{a} if n is even and k is odd and λ(n, k) = 1 else.

Proof. If n and k are even integers, then from Lemma 2 and [14, Corollary 2.2] we get

F_{n−1}^{(a,b)}(q, qs)\sqrt{\frac{b}{a}}F_{n+k}^{(a,b)}(q, s) − \sqrt{\frac{b}{a}}F_{n}^{(a,b)}(q, s)F_{n+k−1}^{(a,b)}(q, qs)

= \sqrt{\frac{b}{a}} \frac{1}{s}F̂_{n}^{(a,b)}(q, s)F_{n+k}^{(a,b)}(q, s) − \sqrt{\frac{b}{a}} \frac{1}{s}F_{n}^{(a,b)}(q, s)F̂_{n+k}^{(a,b)}(q, s)

= (−1)^{n}q^{\binom{n}{2}}s^{n−1}\sqrt{\frac{b}{a}}F_{k}^{(a,b)}(q, q^{n}s),

Then

F_{n}^{(a,b)}(q, s)F̂_{n+k}^{(a,b)}(q, s) − F_{n+k}^{(a,b)}(q, s)F̂_{n}^{(a,b)}(q, s) = (−1)^{n+1}q^{\binom{n}{2}}s^{n}F_{k}^{(a,b)}(q, q^{n}s).

The other cases are analogous.

In particular, if k = 1, then

(\frac{b}{a})^{ξ(n)} F_{n}^{(a,b)}(q, s)F̂_{n+1}^{(a,b)}(q, s) − (\frac{b}{a})^{ξ(n+1)} F_{n+1}^{(a,b)}(q, s)F̂_{n}^{(a,b)}(q, s) = (−1)^{n−1}q^{\binom{n}{2}}.

It is possible give a direct proof of Theorem 4 following the ideas of Andrews et al. [4]. Andrews [3] obtained the following generating function for the q-Fibonacci polynomials:

∑_{n=0}^{∞} D_{n}(q)x^{n} = ∑_{j=0}^{∞} \frac{q^{j^{2}}x^{2j+1}}{(x; q)_{j+1}} .

From (4) it is possible to find the generating function for the (Carlitz-) q-Fibonacci polynomials.

Lemma 5. The generating function for the (Carlitz-) q-Fibonacci polynomials is

Φ(x, z) := ∑_{n=0}^{∞} f_{n}(q, s)z^{n} = ∑_{j=0}^{∞} \frac{q^{j^{2}}s^{j}z^{2j+1}}{(xz; q)_{j+1}} .

Proof. From Equation (4) we get

Φ(x, z) = ∑_{n=0}^{∞} f_{n}(q, s)z^{n} = ∑_{n=0}^{∞} z^{n} ∑_{n−1−k≥0} q^{k^{2}} \left[{n − k − 1 \atop k}\right]s^{k}x^{n−2k−1}

= ∑_{k=0}^{∞} q^{k^{2}}s^{k} ∑_{n−1≥k} q^{k^{2}} \left[{n − k − 1 \atop k}\right]x^{n−2k−1}z^{n} = ∑_{k=0}^{∞} q^{k^{2}}s^{k} ∑_{m=0}^{∞} \left[{m \atop k}\right]x^{m−k}z^{m+k+1}

= ∑_{k=0}^{∞} q^{k^{2}}s^{k}z^{2k+1} ∑_{m=0}^{∞} \left[{m + k \atop k}\right]x^{m}z^{m} = ∑_{k=0}^{∞} \frac{q^{k^{2}}s^{k}z^{2k+1}}{(xz; q)_{k+1}} .

Theorem 6. The generating function for the q-bi-periodic Fibonacci sequence is

W(x) := ∑_{n=0}^{∞} F_{n}^{(a,b)}(q, s)x^{n} = \frac{1}{2} (\sqrt{\frac{a}{b}} + 1) Φ(\sqrt{ab}, x) + \frac{1}{2} (\sqrt{\frac{a}{b}} − 1) Φ(\sqrt{ab}, −x). (9)

Proof. From Identities (7) and (8) we get

F_{n}^{(a,b)}(q, s) = \frac{1}{2} (\sqrt{\frac{a}{b}} + 1) f_{n}(\sqrt{ab}, s) + (−1)^{n} \frac{1}{2} (\sqrt{\frac{a}{b}} − 1) f_{n}(\sqrt{ab}, s).

Then Equation (9) follows.

3 Combinatorial interpretation

The Fibonacci numbers F_{n+1} can be interpreted as the number of tilings of a board of length n (n-board) with cells labelled 1 to n from left to right, using only squares and dominoes (cf. [8]). This interpretation has been used to give a combinatorial interpretation of the q-Fibonacci polynomials and similar recurrent polynomials, see, for instance [7, 10, 23, 24, 29]. In this section, we use tilings weighted by bi-colored squares to give a combinatorial interpretation of the q-bi-periodic Fibonacci sequence. We define a tiling weighted by bicolored squares as a tiling of a n-board by colored squares and non-colored dominoes, such that if the square has an odd position then there are a different colors to choose for the square. If the square has an even position then there are b different colors to choose for the square. Moreover, if a domino covering the i-th boundary receives weight sq^{i} (by ith boundary, we mean the boundary between cells i and i + 1, 1 ⩽ i ⩽ n − 1). Let T_{n} denote the set of all n-tilings, we shall show in Theorem 7 that the bi-periodic Fibonacci sequence (F_{n+1}^{(a,b)}(q, s))_{n≥0} counts the number of tilings weighted by bi-colored squares of a n-board. Specifically, we have

F_{n+1}^{(a,b)}(q, s) = ∑_{T ∈T_{n}} a^{|T |_{a}}b^{|T |_{b}}s^{|T |_{s}}q^{|T |},

where |T |_{a} (|T |_{b}) is the sum of all i such that T has a square in an odd position i (even position i), |T |_{s} is the sum of all dominoes in T and |T | is the sum of all i such that T has a domino in position (i, i + 1).

For example, in Figure 1 we show the different ways to tiling a 4-board. Then it is clear that F_{5}^{(a,b)}(q, s) = a^{2}b^{2} + absq + absq^{2} + absq^{3} + s^{2}q^{4}.

Different ways to tile 4-boards.

Theorem 7. For n ≥ 0, F_{n+1}^{(a,b)}(q, s) counts the number of tilings weighted by bi-colored squares of a n-board.

Proof. Given T ∈ T_{n}. If n is even and T ends with a domino, there are q^{n−1}sF_{n−1}^{(a,b)}(q, s) ways to tile the board, and if T ends with a square, there are bF_{n}^{(a,b)}(q, s) ways to tile the n-board. Analogously, if n is odd we get F_{n+1}^{(a,b)}(q, s) = aF_{n}^{(a,b)}(q, s) + q^{n−1}sF_{n−1}^{(a,b)}(q, s). Moreover, it is clear that the initial values are 1 and a.

Let g(n, k) be the number of tilings weighted by bi-colored squares having n tiles and k dominoes. Then

g(n, k) = q^{n+k−1}sg(n − 1, k − 1) + a^{ξ(n+k)}b^{1−ξ(n+k)}g(n − 1, k).

In fact, if the (n + k)-board ends in a domino, the domino contributes sq^{n+k−1} to the weight. Then, there are q^{n+k−1}sg(n − 1, k − 1) ways to tile the board. If the last tile is a square there are a^{ξ(n+k)}b^{1−ξ(n+k)}g(n − 1, k) ways to tile the board. Let

h(n, k) = a^{ξ(n+k)}q^{k^{2}}s^{k}\left[{n \atop k}\right](ab)^{⌊^{\frac{n−k}{2}}⌋}.

The sequence h(n, k) satisfies the same recurrence of g(n, k). In fact,

q^{n+k−1}sh(n − 1, k − 1) + a^{ξ(n+k)}b^{1−ξ(n+k)}h(n − 1, k)

= q^{n+k−1}s (a^{ξ(n+k)}q^{(k−1)^{2}}s^{k−1}\left[{n − 1 \atop k − 1}\right](ab)^{⌊^{\frac{n−k}{2}}⌋})

+ a^{ξ(n+k)}b^{1−ξ(n+k)}a^{ξ(n+k−1)}q^{k^{2}}s^{k}\left[{n − 1 \atop k}\right](ab)^{⌊^{\frac{n−k−1}{2}}⌋}

= q^{k^{2}+n−k}s^{k}a^{ξ(n+k)}\left[{n − 1 \atop k − 1}\right](ab)^{⌊^{\frac{n−k}{2}}⌋} + a^{ξ(n+k)}q^{k^{2}}s^{k}\left[{n − 1 \atop k}\right](ab)^{⌊^{\frac{n−k}{2}}⌋}

= a^{ξ(n+k)}q^{k^{2}}s^{k} (q^{n−k}\left[{n − 1 \atop k − 1}\right] + \left[{n − 1 \atop k}\right]) (ab)^{⌊^{\frac{n−k}{2}}⌋}

= a^{ξ(n+k)}q^{k^{2}}s^{k}\left[{n \atop k}\right](ab)^{⌊^{\frac{n−k}{2}}⌋} = h(n, k).

Moreover, they satisfy the same initial conditions. Therefore, we have the following lemma.

Lemma 8. The number of tilings weighted by bi-colored squares having n tiles and k dominoes is

a^{ξ(n+k)}q^{k^{2}}s^{k}\left[{n \atop k}\right](ab)^{⌊^{\frac{n−k}{2}}⌋}.

Now, we will give a combinatorial proof of Theorem 3, i.e.,

F_{n+1}^{(a,b)}(q, s) = a^{ξ(n)} \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ l=0 \end{matrix} \left[{n − l \atop l}\right](ab)^{⌊^{\frac{n}{2}}⌋−l}q^{l^{2}}.

Combinatorial Proof of Theorem 3. From Theorem 7, F_{n+1}^{(a,b)}(q, s) counts the number of tilings weighted by bi-colored squares of a n-board. On the other hand, let l be the number of dominoes in the tiling of a n-board. Then there are n − 2l squares. Such a tiling with n − l tiles, exactly l of which are dominoes is

a^{ξ(n)}q^{l^{2}}s^{l}\left[{n − l \atop l}\right](ab)^{⌊^{\frac{n}{2}}⌋−l}.

Summing over all possible l gives the identity.

4 Some additional identities

In this section, we prove several q-analogues of Fibonacci identities using tilings weighted by bi-colored squares.

Theorem 9. The following equality holds for any integer n ≥ 0 :

∑_{k=1}^{n+1} sq^{k}F_{k}^{(a,b)}(q, s)a^{ξ(n)ξ(k)}b^{ξ(k+1)−ξ(n)ξ(k+1)}(ab)^{⌊^{\frac{n−k+1}{2}}⌋} = F_{n+3}^{(a,b)}(q, s) − a^{ξ(n)}(ab)^{⌊^{\frac{n+2}{2}}⌋}. (10)

Proof. There exist F_{n+3}^{(a,b)}(q, s) − a^{ξ(n)}(ab)^{⌊^{\frac{n+2}{2}}⌋} tilings weighted by bi-colored squares of a (n + 2)-board with at least one domino. On the other hand, consider the location of the last domino, say position (k, k + 1). This domino contributes a sq^{k} to the weight, while all tiles to the right are squares and contribute (depending on the parity of the numbers k and n) a^{ξ(n)ξ(k)}b^{ξ(k+1)(1−ξ(n))}(ab)^{⌊^{\frac{n−k+1}{2}}⌋} to the weight. Moreover, there are F_{k}^{(a,b)}(q, s) ways to tile the left side ((k − 1)-board). The equality (10) follows after summing over all possible k.

Note that if we consider the limit when q tends to 1 and s = 1 in above theorem, we obtain the new identity

∑_{k=1}^{n+1} t_{k}a^{ξ(n)ξ(k)}b^{ξ(k+1)−ξ(n)ξ(k+1)}(ab)^{⌊^{\frac{n−k+1}{2}}⌋} = t_{n+3} − a^{ξ(n)}(ab)^{⌊^{\frac{n+2}{2}}⌋}.

Equation (10) is a q-analogue of the following Fibonacci identity [22]:

∑_{k=0}^{n} F_{k} = F_{n+2} − 1.

The following theorem is a q-analogue of the Fibonacci identity [22]:

∑_{k=0}^{n} F_{2k} = F_{2n+1}.

Theorem 10. The following equality holds for any integer n ≥ 0:

a ∑_{k=0}^{n} F_{2k+1}^{(a,b)}(q, s)q^{n^{2}+n−(k^{2}+k)}s^{n−k} = F_{2n+2}^{(a,b)}(q, s).

Proof. There exists F_{2n+2}^{(a,b)}(q, s) tilings weighted by bi-colored squares of a (2n + 1)-board. On the other hand, consider the location of the last square, say position k. Since the length of the board is odd, we know k is odd, and it contributes an a to the weight. The dominoes to the right contribute q^{(k+1)+(k+3)+···+(2n)}s^{n−k} = q^{n^{2}+n−(k^{2}−1)/4}s^{n−k} to the weight. Moreover, there are F_{k}^{(a,b)}(q, s) ways to tile the left side ((k − 1)-board). Summing over all possible odd k gives the identity.

If we consider the limit when q tends to 1 and s = 1 in the above theorem we obtain the expression

a ∑_{k=0}^{n} t_{2k+1} = t_{2n+2}.

We need the following shifted q-bi-periodic Fibonacci sequence:

F_{0}^{(h)}(q, s) = 0, F_{1}^{(h)}(q, s) = 1,

F_{n}^{(h)}(q, s) = \begin{cases}a^{ξ(h+1)}b^{1−ξ(h+1)}F_{n−1}^{(h)}(q, s) + q^{n−2+h}sF_{n−2}^{(h)}(q, s), if n ≡ 0 (mod 2); \\ a^{1−ξ(h+1)}b^{ξ(h+1)}F_{n−1}^{(h)}(q, s) + q^{n−2+h}sF_{n−2}^{(h)}(q, s), if n ≡ 1 (mod 2); \end{cases} n ≥ 2.

A tiling of a n-board is breakable at cell k if the tiling can be decomposed into two tilings, one covering cells 1 through k and the other covering cells k + 1 through n. Moreover, a tiling of a n-board is unbreakable at cell k if a domino occupies cell k and k + 1 (cf. [8]).

It is not difficult to show that F_{n+1}^{(h)}(q, s) counts the latter position of the tilings weighted by bi-colored squares of a (n + h − 1)-board that can be breakable at cell h.

Theorem 11. The following equality holds for any integers n, m ≥ 0:

F_{n+m+1}^{(a,b)}(q, s) = F_{m+1}^{(a,b)}(q, s)F_{n+1}^{(m)}(q, s) + q^{m}sF_{m}^{(a,b)}(q, s)F_{n}^{(m+1)}(q, s).

Proof. There exists F_{n+m+1}^{(a,b)}(q, s) tilings weighted by bi-colored squares of a (n + m)-board. On the other hand, we will consider two cases. If a (n + m)-tiling is breakable at cell m, we have F_{m+1}^{(a,b)}(q, s) ways to tile a m-board (left side) and F_{n+1}^{(m)}(q, s) ways to tile the n-board (right side). If a (n + m)-tiling is unbreakable at cell m then there is a domino in position (m, m + 1). It contributes q^{m}s to the weight. Moreover, there are F_{m}^{(a,b)}(q, s) ways to tile a (m − 1)-board (left side) and F_{n}^{(m+1)}(q, s) ways to tile the (n − 1)-board (right side).

The above theorem is a q-analogue of the Fibonacci identity:

F_{m+n} = F_{m}F_{n} + F_{m−1}F_{n−1}.

The following theorem is a q-analogue of the bi-periodic Fibonacci identity (see [18, Theorem 7]):

∑_{k=0}^{n} \binom{n}{k}a^{ξ(k)}(ab)^{⌊^{\frac{k}{2}}⌋}t_{k} = t_{2n}.

Theorem 12. The following equality holds for any integer n ≥ 0:

F_{2n}^{(a,b)}(q, s) = ∑_{k=1}^{n} a^{ξ(k)}q^{(n−k)^{2}}s^{n−k}\left[{n \atop k}\right](ab)^{⌊^{\frac{k}{2}}⌋}F_{k}^{(2n−k)}(q, s).

Proof. There exists F_{2n}^{(a,b)}(q, s) tilings weighted by bi-colored squares of a (2n−1)-board. On the other hand, note that a (2n − 1)-tiling has to include at least n tiles, and one of them if a square. If a (2n − 1)-tiling has k squares and n − k dominoes among the first n tiles, then by Lemma 8 there are

a^{ξ(2n−k)}q^{(n−k)^{2}}s^{n−k}\left[{n \atop n − k}\right](ab)^{⌊^{\frac{k}{2}}⌋} = a^{ξ(k)}q^{(n−k)^{2}}s^{n−k}\left[{n \atop k}\right](ab)^{⌊^{\frac{k}{2}}⌋}

ways to tile this board. The remaining right board has length k − 1 and can be tiled in F_{k}^{(2n−k)}(q, s) ways.

Theorem 13. The following equality holds for any integer n ≥ 0:

F_{2n+2}^{(a,b)}(q, s) = a ∑_{i=0}^{n} ∑_{j=0}^{n}(ab)^{ξ(n−i−j)}q^{i^{2}+(n+i+j)j}s^{i+j}\left[{n − j \atop i}\right]\left[{n − i \atop j}\right](ab)^{2⌊\frac{n−i−j}{2}⌋}.

Proof. There exist F_{2n+2}^{(a,b)}(q, s) tilings weighted by bi-colored squares of a (2n + 1)-board. On the other hand, note that if a (2n + 1)-tiling has an odd number of squares, then there is a square such that the number of squares to the left side of it is equal to the number of squares of the right side. This square is called median square, and it contributes an a to the weight. We will count the number of tilings containing exactly i dominoes to the left of the median square and exactly j dominoes to the right of the median square. A tiling of a (2n + 1)-board with i + j dominoes has 2n + 1 − 2i − 2j squares, so there are n − i − j squares on each side of the median square. Since the left side has n − j tiles i of which are dominoes, then there are

a^{ξ(n−j+i)}q^{i^{2}}s^{i}\left[{n − j \atop i}\right](ab)^{⌊^{\frac{n−i−j}{2}}⌋}

ways to tile this board. Analogously, the right side can be tiled by

b^{ξ(n−j+i)}q^{(n+i+1)j}s^{j}\left[{n − i \atop j}\right](ab)^{⌊^{\frac{n−i−j}{2}}⌋}

ways.

The above theorem is a q-analogue of the Fibonacci identity (cf. [22]):

∑_{i=0}^{n} ∑_{j=0}^{n} \binom{n − i}{j}\binom{n − j}{i} = F_{2n+1}.

5 Acknowledgments

The authors thank the anonymous referee for his/her comments which helped to improve the article.

References

[1] M. Alp, N. Irmak, and L. Szalay, Two-periodic ternary recurrences and their Binetformula, Acta Math. Univ. Comenianae 2 (2012), 227–232.

[2] G. E. Andrews, A polynomial identity which implies the Rogers-Ramanujan identities, Scr. Math. 28 (1970), 297–305.

[3] G. E. Andrews, Fibonacci numbers and the Rogers-Ramanujan identities, Fibonacci Quart. 42 (2004), 3–19.

[4] G. E. Andrews, A. Knopfmacher, and P. Paule, An infinite family of Engel expansions of Rogers-Ramanujan type, Adv. in Appl. Math. 25 (2000), 2–11.

[5] H. Belbachir and A. Benmezai, An alternative approach to Cigler’s q-Lucas polynomials, Applied. Math. Comp. 226 (2014), 691–698.

[6] H. Belbachir and A. Benmezai, A q analogue for bi^{s}nomial coefficients and generalized Fibonacci sequence, C. R. Math. Acad. Sci. Paris I 352 (2014), 167–171.

[7] A. Benjamin, A. Eustis, and M. Shattuck, Compression theorems for periodic tilings and consequences, J. Integer Sequences 12 (2009), Article 09.6.3.

[8] A. Benjamin and J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Dolciani Mathematical Expositions, Vol. 27, Mathematical Association of America, 2003.

[9] G. Bilgici, Two generalizations of Lucas sequence, Applied. Math. Comp. 245 (2014), 526–538.

[10] K. Briggs, D. Little, and J. Sellers, Combinatorial proofs of various q-Pell identities via tilings, Ann. Comb. 14 (2010), 407–418.

[11] L. Carlitz, Fibonacci notes. III. q-Fibonacci numbers, Fibonacci Quart. 12 (1974), 317– 322.

[12] L. Carlitz, Fibonacci notes. IV. q-Fibonacci polynomials, Fibonacci Quart. 13 (1975), 97–102.

[13] J. Cigler, A new class of q-Fibonacci polynomials, Electron. J. Combin. 10 (2003), 1–15.

[14] J. Cigler, q-Fibonacci polynomials, Fibonacci Quart. 41 (2003), 31–40.

[15] J. Cigler, q-Fibonacci polynomials and the Rogers-Ramanujan identities, Ann. Combin. 8 (2004), 269–285.

[16] H.-C. Chan, On the Andrews-Schur proof of the Rogers-Ramanujan identities, Ramanujan J. 23 (2010), 417–431.

[17] M. Edson, S. Lewis, and O. Yayenie, The k-periodic Fibonacci sequence and extended Binet’s formula, Integers 11 (A32) (2011), 739–751.

[18] M. Edson and O. Yayenie, A new generalization of Fibonacci sequences and extended Binet’s Formula, Integers 9 (A48) (2009), 639–654.

[19] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, Second Edition, 1994.

[20] M. Ismail, H. Prodinger, and D. Stanton, Schur’s determinants and partition theorems, Sém. Lothar. Combin. 44 (B44a) (2000), 1–10.

[21] N. Irmak and L. Szalay, On k-periodic binary recurrences, Ann. Math. Inform. 40 (2012), 25–35.

[22] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, 2001.

[23] K. Garrett, Weighted tilings and q-Fibonacci numbers, preprint, 2004. Available at

    http://www.stolaf.edu/people/garrettk/qFibonacci.pdf.

[24] D. Little and J. Sellers, A tiling approach to eight identities of Rogers, European J. Combin. 31 (2010), 694–709.

[25] D. Panario, M. Sahin, and Q. Wan, A family of Fibonacci-like conditional sequences, Integers 13 (A78) (2013), 1–14.

[26] D. Panario, M. Sahin, Q. Wan, and W. Webb, General conditional recurrences, Applied. Math. Comp. 243 (2014), 220–231.

[27] J. L. Ramírez, Bi-periodic incomplete Fibonacci sequences, Ann. Math. Inform. 42 (2013), 83–92.

[28] I. Schur, Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche, S.-B. Preuss. Akad. Wiss. Phys. Math. Klasse 54 (1917), 302–321.

[29] E. C. Stabel, A combinatorial proof of an identity of Ramanujan using tilings, Bull. Braz. Math. Soc. 42 (2011), 203–212.

[30] O. Yayenie, A note on generalized Fibonacci sequence, Applied. Math. Comp. 217 (2011), 5603–5611.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B65, 05A19. Keywords: q-Fibonacci sequence, q-bi-periodic Fibonacci sequence, bi-periodic Fibonacci sequence, q-analogues, combinatorial identities.

(Concerned with sequence \underline{A000045}.)

Received November 4 2015; revised version received March 30 2016. Published in Journal of Integer Sequences, May 9 2016.

Return to Journal of Integer Sequences home page.