\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \usepackage{caption} \captionsetup[figure]{labelformat=empty} \def\divides{\, | \,} \newcommand{\N}{{\mathbb N}} \newcommand{\W}{{\mathcal W}} \newcommand{\T}{{\mathcal T}} \def\modd#1 #2{#1\ ({\rm mod}\ #2)} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A $q$-Analogue of the Bi-Periodic \\ \vskip .1in Fibonacci Sequence } \vskip 1cm \large Jos\'e L. Ram\'irez \\ Departamento de Matem\'aticas\\ Universidad Sergio Arboleda \\ Calle 74 No.~14 --- 14 \\ Bogot\'a \\ Colombia \\ \href{mailto:josel.ramirez@ima.usergioarboleda.edu.co}{\tt josel.ramirez@ima.usergioarboleda.edu.co} \\ \ \\ V\'{\i}ctor F. Sirvent \\ Departamento de Matem\'aticas\\ Universidad Sim\'{o}n Bol\'{i}var\\ Apartado 89000 \\ Caracas 1086-A \\ Venezuela \\ \href{mailto:vsirvent@usb.ve}{\tt vsirvent@usb.ve} \end{center} \vskip .2 in \begin{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. \end{abstract} \section{Introduction} The Fibonacci numbers \seqnum{A000045} $F_n$ are defined by the recurrence relation \begin{align*} F_{0}=0, \quad F_{1}=1, \quad F_{n+1}=F_{n}+F_{n-1}, \ \ n\geq 1. \end{align*} This sequence and its generalizations have many interesting combinatorial properties (cf.\ \cite{koshy}). Many kinds of generalizations of Fibonacci numbers have been presented in the literature. In particular, Edson and Yayenie \cite{edson1} introduced the bi-periodic Fibonacci sequence. For any two positive integers $a$ and $b$, the \emph{bi-periodic Fibonacci sequence}, say $(t_{n})_{n \geq 0}$, is determined by the following: \begin{align*} t_{0}=0, \ \ t_{1}=1, \ \ t_{n}= \begin{cases} at_{n-1} + t_{n-2}, & \text{if} \ n\equiv \modd{0} {2};\\ bt_{n-1} + t_{n-2}, & \text{if} \ n\equiv \modd{1} {2}. \end{cases} \ \ \ n\geq 2. \end{align*} The bi-periodic Fibonacci numbers and their generalizations have been studied in several papers; among other references, see \cite{ALP, Bil, edson3, edson1, NURE, Panario, Panario2, Ram, edson2}. The bi-periodic Fibonacci sequence is a particular case of the continuant polynomials; for more details see \cite{Graham}. Yayenie \cite{edson2} found the following explicit formula to bi-periodic Fibonacci numbers \begin{align} t_{n}=a^{\xi(n-1)}\sum_{i=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{n-i-1}{i}(ab)^{\left\lfloor\frac{n-1}{2}\right\rfloor-i}, \label{ec20} \end{align} where $\xi(n)=n-2\lfloor n/2 \rfloor$, i.e., $\xi(n)=0$ when $n$ is even and $\xi(n)=1$ when $n$ is odd. There exist several slightly different $q$-analogues of the Fibonacci sequence. Among other references, see \cite{Andrews2, Bel, Bel2, Carlitz, Carlitz2, Cigler, Cigler2, Cigler4}. In particular, Schur \cite{Schur} defined the following polynomials: \begin{align} D_0(q)=0, \quad D_1(q)=1, \quad D_n(q)=D_{n-1}(q)+q^{n-2}D_{n-2}(q). \label{shurpa} \end{align} It is clear that $D_n(1)=F_n$. In addition to the recurrence formula (\ref{shurpa}), $D_n(q)$ can be calculated directly by the following analytic formula (cf.\ \cite{Andrews2, Cigler}): \begin{align*} D_n(q)=\sum_{j=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}{n - j -1 \brack j}q^{j^2}, \end{align*} where the $q$-binomial is $${n \brack k}:=\frac{(q;q)_n}{(q;q)_k(q;q)_{n-k}},$$ and $$(a;q)_n:=\prod_{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 \cite{Andrews4, Andrews2, Andrews, Chan, Prodinger}. There is a generalization of the polynomials $D_n(q)$ called (Carlitz-) $q$-Fibonacci polynomials \cite{Carlitz2} \begin{align} f_n(x,s)=xf_{n-1}(x,s)+q^{n-2}sf_{n-2}(x,s), \label{shurp} \end{align} with the initial values $f_0(x,s)=0$ and $f_1(x,s)=1$. They can be calculated using the formula \begin{align} \label{calfibo} f_n(x,s)=\sum_{l=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}{n-l-1 \brack l}q^{l^2}s^lx^{n-2l-1}. \end{align} A natural question is: What is the $q$-analogue of the bi-periodic sequence? From (\ref{shurp}), we introduce a $q$-analogue of the bi-periodic Fibonacci sequence as follows: \begin{align} F_{n}^{(a,b)}(q,s)&= \chi(n)F_{n-1}^{(a,b)}(q,s) + q^{n-2}sF_{n-2}^{(a,b)}(q,s), \ \ \ n\geq 2, \label{eqq11} \end{align} with the initial values $F_{0}^{(a,b)}(q,s)=0$ and $F_{1}^{(a,b)}(q,s)=1$, where $\chi(n)$ is defined by $\chi(2n)=a$ and $\chi(2n+1)=b$. The first few terms are $$0, \quad 1, \quad a, \quad a b + sq, \quad a^2 b + asq + asq^2, \quad a^2 b^2 + absq + absq^2 + absq^3 + s^2q^4, \dots.$$ We call this sequence the \emph{$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. \section{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 (\ref{ec20}), which is a closed formula to evaluate the $q$-bi-periodic Fibonacci sequence. Moreover, in Theorem \ref{theo4} we give a $q$-analogue of a generalization of Cassini's identity. \begin{proposition}\label{prop:1} The following equality holds for any integer $n\geq 2$: \begin{align} F_n^{(a,b)}(q,s)=\chi(n)F_{n-1}^{(a,b)}(q,qs)+qsF_{n-2}^{(a,b)}(q,q^2s). \label{refer1} \end{align} \end{proposition} \begin{proof} Let $G_n(q,s)$ be the right side of (\ref{refer1}). This sequence satisfies the recurrence (\ref{eqq11}) and the same initial values. In fact, \begin{multline*} \chi(n)G_{n-1}(q,s) + q^{n-2}sG_{n-2}(q,s)\\=\chi(n)\left(\chi(n-1)F^{(a,b)}_{n-2}(q,qs)+qsF^{(a,b)}_{n-3}(q,q^2s)\right) + q^{n-2}s\left(\chi(n-2)F^{(a,b)}_{n-3}(q,qs)+qsF^{(a,b)}_{n-4}(q,q^2s) \right)\\ =\chi(n)\left(\chi(n-1)F^{(a,b)}_{n-2}(q,qs)+q^{n-3}(qs)F^{(a,b)}_{n-3}(q,qs)\right) \\ + qs\left(\chi(n-2)F^{(a,b)}_{n-3}(q,q^2s)+q^{n-4}(q^2s)F^{(a,b)}_{n-4}(q,q^2s) \right)\\ =\chi(n)F^{(a,b)}_{n-1}(q,qs)+qsF^{(a,b)}_{n-2}(q,q^2s)=G_n(q,s). \end{multline*} Then Equation (\ref{refer1}) follows. \end{proof} The following lemma shows how to write the $q$-bi-periodic Fibonacci sequence in terms of the (Carlitz-) $q$-Fibonacci polynomials. \begin{lemma}\label{mlemma} The following equalities hold for any integer $n\geq 0$: \begin{align} F_{2n}^{(a,b)}(q,s)&=\sqrt{\frac{a}{b}}f_{2n}(\sqrt{ab},s), \label{eq12c} \\ F_{2n+1}^{(a,b)}(q,s)&=f_{2n+1}(\sqrt{ab},s). \label{eq2c} \end{align} \end{lemma} \begin{proof} Let $a_n$ be the right side of (\ref{eq12c}), then sequences $(a_n)_{n\geq 0}$ and $(F^{(a,b)}_{2n}(q,s))_{n\geq 0}$ satisfy the same recurrence and the same initial conditions. In fact, \begin{align*} a_n&=\sqrt{\frac ab} f_{2n}(\sqrt{ab},s)=\sqrt{\frac ab}\left(\sqrt{ab} f_{2n-1}(\sqrt{ab},s)+q^{2n-2}sf_{2n-2}(\sqrt{ab},s)\right)\\ &=af_{2n-1}(\sqrt{ab},s)+q^{2n-2}sf_{2n-2}(\sqrt{ab},s). \end{align*} Similarly, we obtain Equation (\ref{eq2c}). \end{proof} \begin{theorem}\label{Theo1} The following equality holds for any integer $n\geq 0$: \begin{align*} F_n^{(a,b)}(q,s)=a^{\xi(n-1)}\sum_{l=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}{n-l-1 \brack l}(ab)^{\left\lfloor\frac{n-1}{2}\right\rfloor-l}q^{l^2}s^l. \end{align*} \end{theorem} \begin{proof} If $n$ is even ($n=2k$), then from Lemma \ref{mlemma} and Equation (\ref{calfibo}), we get \begin{align*} F_{2k}^{(a,b)}(q,s)&=\sqrt{\frac{a}{b}} f_{2n}(\sqrt{ab},s)=\sqrt{\frac{a}{b}} \sum_{l=0}^{k-1}{2k-l-1 \brack l}q^{l^2}s^l(\sqrt{ab})^{2k-2l-1}\\ &=a\sum_{l=0}^{k-1}{2k-l-1 \brack l}(ab)^{k-l-1}q^{l^2}s^l. \end{align*} If $n$ is odd then in analogy way we get \begin{align*} F_{2k+1}^{(a,b)}(q,s)&=\sum_{l=0}^{k}{2k-l \brack l}(ab)^{k-l}q^{l^2}s^l. \end{align*} \end{proof} Note that if we consider the limit when $q$ tends to $1$ in the above theorem and $s=1$ we obtain the identity (\ref{ec20}). 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)^mF_k.$$ We need the auxiliary sequence $\widehat{F}^{(a,b)}_{n}(q,s)$ defined by \begin{align*} \widehat{F}_{0}^{(a,b)}(q,s)=1, \ \ \widehat{F}_{1}^{(a,b)}(q,s)=0, \ \ \widehat{F}_{n}^{(a,b)}(q,s)=\chi(n-1)\widehat{F}_{n-1}^{(a,b)}(q,s) + q^{n-2}s\widehat{F}_{n-2}^{(a,b)}(q,s), \end{align*} where $n\geq 2$. The first few terms are $$1, \quad 0, \quad s, \quad as, \quad abs + q^2s^2, \quad a^2 b s+aq^3s^2+a q^2 s^2, \quad a^2 b^2 s+a b q^4s^2+a b q^3 s^2+a b q^2 s^2+q^6s^3, \dots$$ Note that $\widehat{F}_{n}^{(a,b)}(q,s)=sF^{(a,b)}_{n-1}(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 \cite{Schur} also studied this polynomial sequence. From identities (\ref{eq12c}) and (\ref{eq2c}), and the $q$-Euler-Cassini formula for the (Carlitz-) $q$-Fibonacci polynomials (see \cite[Corollary 2.2]{Cigler2}), we obtain the following identity: \begin{theorem} \label{theo4} The following equality holds for integers $n\geq 0$ and $k\geq 1$: \begin{align*} \lambda(n,k) F^{(a,b)}_{n}(q,s)\widehat{F}^{(a,b)}_{n+k}(q,s)- \lambda(n+1,k) F^{(a,b)}_{n+k}(q,s)\widehat{F}^{(a,b)}_{n}(q,s)=(-1)^{n+1}q^{\binom n2}s^{n} F^{(a,b)}_k(q,q^ns), \end{align*} where $\lambda(n,k)=\frac{b}{a}$ if $n$ is even and $k$ is odd and $\lambda(n,k)=1$ else. \end{theorem} \begin{proof} If $n$ and $k$ are even integers, then from Lemma \ref{mlemma} and \cite[Corollary 2.2]{Cigler2} we get \begin{multline*} F_{n-1}^{(a,b)}(q,qs)\sqrt{\frac ba}F_{n+k}^{(a,b)}(q,s) - \sqrt{\frac ba}F_{n}^{(a,b)}(q,s)F_{n+k-1}^{(a,b)}(q,qs)\\ =\sqrt{\frac ba}\frac{1}{s}\widehat{F}_{n}^{(a,b)}(q,s)F_{n+k}^{(a,b)}(q,s) - \sqrt{\frac ba}\frac{1}{s}F_{n}^{(a,b)}(q,s)\widehat{F}_{n+k}^{(a,b)}(q,s)\\ =(-1)^{n}q^{\binom n2}s^{n-1} \sqrt{\frac ba} F_k^{(a,b)}(q,q^ns), \end{multline*} Then \begin{align*} F_{n}^{(a,b)}(q,s)\widehat{F}_{n+k}^{(a,b)}(q,s)-F_{n+k}^{(a,b)}(q,s)\widehat{F}_{n}^{(a,b)}(q,s)=(-1)^{n+1}q^{\binom n2}s^{n} F_k^{(a,b)}(q,q^ns). \end{align*} The other cases are analogous. \end{proof} In particular, if $k=1$, then \begin{align*} \left(\frac{b}{a}\right)^{\xi(n)}F^{(a,b)}_n(q,s)\widehat{F}^{(a,b)}_{n+1}(q,s)-\left(\frac{b}{a}\right)^{\xi(n+1)}F^{(a,b)}_{n+1}(q,s)\widehat{F}^{(a,b)}_{n}(q,s)=(-1)^{n-1}q^{\binom n2}. \end{align*} It is possible give a direct proof of Theorem \ref{theo4} following the ideas of Andrews et al.\ \cite{Andrews}. Andrews \cite{Andrews2} obtained the following generating function for the $q$-Fibonacci polynomials: \begin{align*} \sum_{n=0}^{\infty}D_n(q)x^n=\sum_{j=0}^{\infty}\frac{q^{j^2}x^{2j+1}}{(x;q)_{j+1}}. \end{align*} From (\ref{calfibo}) it is possible to find the generating function for the (Carlitz-) $q$-Fibonacci polynomials. \begin{lemma} The generating function for the (Carlitz-) $q$-Fibonacci polynomials is \begin{align*} \Phi(x,z):=\sum_{n=0}^{\infty}f_n(q,s)z^n=\sum_{j=0}^{\infty}\frac{q^{j^2}s^jz^{2j+1}}{(xz;q)_{j+1}}. \end{align*} \end{lemma} \begin{proof} From Equation (\ref{calfibo}) we get \begin{align*} \Phi(x,z)&=\sum_{n=0}^{\infty}f_n(q,s)z^n=\sum_{n=0}^\infty z^n \sum_{n-1-k\geq 0}q^{k^2} {n-k-1 \brack k} s^kx^{n-2k-1}\\ &=\sum_{k=0}^\infty q^{k^2}s^k \sum_{n-1\geq k}q^{k^2} {n-k-1 \brack k} x^{n-2k-1}z^n=\sum_{k=0}^\infty q^{k^2}s^k \sum_{m=0}^\infty {m \brack k} x^{m-k}z^{m+k+1}\\ &=\sum_{k=0}^\infty q^{k^2}s^k z^{2k+1}\sum_{m=0}^\infty {m + k \brack k} x^{m}z^{m} =\sum_{k=0}^{\infty}\frac{q^{k^2}s^kz^{2k+1}}{(xz;q)_{k+1}}. \end{align*} \end{proof} \begin{theorem}\label{thm:15} The generating function for the $q$-bi-periodic Fibonacci sequence is \begin{align} \W(x):=\sum_{n=0}^{\infty}F_n^{(a,b)}(q,s)x^n=\frac{1}{2}\left(\sqrt{\frac{a}{b}}+1\right)\Phi(\sqrt{ab},x) + \frac{1}{2}\left(\sqrt{\frac{a}{b}}-1\right)\Phi(\sqrt{ab},-x). \label{genfun1r} \end{align} \end{theorem} \begin{proof} From Identities (\ref{eq12c}) and (\ref{eq2c}) we get \begin{align*} F_n^{(a,b)}(q,s)=\frac{1}{2}\left(\sqrt{\frac ab} + 1\right)f_n(\sqrt{ab},s) + (-1)^n\frac{1}{2}\left(\sqrt{\frac ab} - 1\right)f_n(\sqrt{ab},s). \end{align*} Then Equation (\ref{genfun1r}) follows. \end{proof} \section{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.\ \cite{Benja}). This interpretation has been used to give a combinatorial interpretation of the $q$-Fibonacci polynomials and similar recurrent polynomials, see, for instance \cite{Shatu, Briggs, Kris, Little, Stabel}. 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 \emph{tiling weighted by bi-colored 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 $i$th boundary, we mean the boundary between cells $i$ and $i+1$, $1\leqslant i \leqslant n-1$). Let $\T_n$ denote the set of all $n$-tilings, we shall show in Theorem \ref{theocount} that the bi-periodic Fibonacci sequence $(F^{(a,b)}_{n+1}(q,s))_{n\geq 0}$ counts the number of tilings weighted by bi-colored squares of a $n$-board. Specifically, we have $$F^{(a,b)}_{n+1}(q,s)=\sum_{T\in\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 \ref{tile} we show the different ways to tiling a $4$-board. Then it is clear that $F_5^{(a,b)}(q,s)=a^2b^2+absq+absq^2+absq^3+s^2q^4.$ \begin{figure}[h] \centering \includegraphics[scale=1]{tile.eps} \caption{Different ways to tile $4$-boards.} \label{tile} \end{figure} \begin{theorem} \label{theocount} For $n\geq 0$, $F_{n+1}^{(a,b)}(q,s)$ counts the number of tilings weighted by bi-colored squares of a $n$-board. \end{theorem} \begin{proof} Given $T\in\T_n$. If $n$ is even and $T$ ends with a domino, there are $q^{n-1}sF^{(a,b)}_{n-1}(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$. \end{proof} 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^{\xi(n+k)}b^{1-\xi(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^{\xi(n+k)}b^{1-\xi(n+k)}g(n-1,k)$ ways to tile the board. Let $$h(n,k)=a^{\xi(n+k)}q^{k^2}s^k{n\brack k}(ab)^{\left\lfloor \frac{n-k}{2}\right\rfloor}.$$ The sequence $h(n,k)$ satisfies the same recurrence of $g(n,k)$. In fact, \begin{align*} q^{n+k-1}s&h(n-1,k-1) + a^{\xi(n+k)}b^{1-\xi(n+k)}h(n-1,k)\\ &=q^{n+k-1}s\left(a^{\xi(n+k)}q^{(k-1)^2}s^{k-1}{n-1\brack k-1}(ab)^{\left\lfloor \frac{n-k}{2}\right\rfloor}\right)\\ & \ + a^{\xi(n+k)}b^{1-\xi(n+k)}a^{\xi(n+k-1)}q^{k^2}s^k{n-1\brack k}(ab)^{\left\lfloor \frac{n-k-1}{2}\right\rfloor}\\ &=q^{k^2+n-k}s^ka^{\xi(n+k)}{n-1\brack k-1}(ab)^{\left\lfloor \frac{n-k}{2}\right\rfloor} + a^{\xi(n+k)}q^{k^2}s^k{n-1\brack k}(ab)^{\left\lfloor \frac{n-k}{2}\right\rfloor }\\ &=a^{\xi(n+k)}q^{k^2}s^k\left(q^{n-k}{n-1\brack k-1}+{n-1\brack k}\right)(ab)^{\left\lfloor \frac{n-k}{2}\right\rfloor}\\ &=a^{\xi(n+k)}q^{k^2}s^k{n\brack k}(ab)^{\left\lfloor \frac{n-k}{2}\right\rfloor}=h(n,k). \end{align*} Moreover, they satisfy the same initial conditions. Therefore, we have the following lemma. \begin{lemma}\label{lema} The number of tilings weighted by bi-colored squares having $n$ tiles and $k$ dominoes is $$a^{\xi(n+k)}q^{k^2}s^k{n\brack k}(ab)^{\left\lfloor \frac{n-k}{2}\right\rfloor}.$$ \end{lemma} Now, we will give a combinatorial proof of Theorem \ref{Theo1}, i.e., \begin{align*} F_{n+1}^{(a,b)}(q,s)=a^{\xi(n)}\sum_{l=0}^{\left\lfloor\frac{n}{2}\right\rfloor}{n-l \brack l}(ab)^{\left\lfloor\frac{n}{2}\right\rfloor-l}q^{l^2}. \end{align*} \textit{Combinatorial Proof of Theorem \ref{Theo1}}. From Theorem \ref{theocount}, $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^{\xi(n)}q^{l^2}s^l{n-l\brack l}(ab)^{\left\lfloor \frac{n}{2}\right\rfloor-l}.$$ Summing over all possible $l$ gives the identity. \qedhere \section{Some additional identities} In this section, we prove several $q$-analogues of Fibonacci identities using tilings weighted by bi-colored squares. \begin{theorem} The following equality holds for any integer $n\geq 0:$ \begin{align} \sum_{k=1}^{n+1}sq^kF_k^{(a,b)}(q,s)a^{\xi(n)\xi(k)}b^{\xi(k+1)-\xi(n)\xi(k+1)}(ab)^{\left\lfloor\frac{n-k+1}{2}\right\rfloor}=F_{n+3}^{(a,b)}(q,s)-a^{\xi(n)}(ab)^{\left\lfloor\frac{n+2}{2}\right\rfloor}. \label{id1} \end{align} \end{theorem} \begin{proof} There exist $F_{n+3}^{(a,b)}(q,s)-a^{\xi(n)}(ab)^{\left\lfloor\frac{n+2}{2}\right\rfloor}$ 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^{\xi(n)\xi(k)}b^{\xi(k+1)(1-\xi(n))}(ab)^{\left\lfloor\frac{n-k+1}{2}\right\rfloor}$ to the weight. Moreover, there are $F_k^{(a,b)}(q,s)$ ways to tile the left side ($(k-1)$-board). The equality~(\ref{id1}) follows after summing over all possible $k$. \end{proof} Note that if we consider the limit when $q$ tends to $1$ and $s=1$ in above theorem, we obtain the new identity $$\sum_{k=1}^{n+1}t_ka^{\xi(n)\xi(k)}b^{\xi(k+1)-\xi(n)\xi(k+1)}(ab)^{\left\lfloor\frac{n-k+1}{2}\right\rfloor}=t_{n+3}-a^{\xi(n)}(ab)^{\left\lfloor\frac{n+2}{2}\right\rfloor}.$$ Equation (\ref{id1}) is a $q$-analogue of the following Fibonacci identity \cite{koshy}: $$ \sum_{k=0}^{n}F_k=F_{n+2}-1. $$ The following theorem is a $q$-analogue of the Fibonacci identity \cite{koshy}: $$\sum_{k=0}^{n}F_{2k}=F_{2n+1}.$$ \begin{theorem} The following equality holds for any integer $n\geq 0$: \begin{align*} a\sum_{k=0}^{n}F^{(a,b)}_{2k+1}(q,s)q^{n^2+n-(k^2+k)}s^{n-k}=F^{(a,b)}_{2n+2}(q,s). \end{align*} \end{theorem} \begin{proof} There exists $F^{(a,b)}_{2n+2}(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)+\cdots+(2n)}s^{n-k}=q^{n^2+n-(k^2-1)/4}s^{n-k}$ to the weight. Moreover, there are $F^{(a,b)}_k(q,s)$ ways to tile the left side ($(k-1)$-board). Summing over all possible odd $k$ gives the identity. \end{proof} If we consider the limit when $q$ tends to $1$ and $s=1$ in the above theorem we obtain the expression $$a\sum_{k=0}^{n}t_{2k+1}=t_{2n+2}.$$ We need the following shifted $q$-bi-periodic Fibonacci sequence: \begin{align*} &F^{(h)}_{0}(q,s)=0, \quad F^{(h)}_{1}(q,s)=1, \quad \\ &F^{(h)}_{n}(q,s)=\begin{cases} a^{\xi(h+1)}b^{1-\xi(h+1)}F^{(h)}_{n-1}(q,s) + q^{n-2+h}sF^{(h)}_{n-2}(q,s), \ \text{if} \ n\equiv 0 \pmod 2;\\ a^{1-\xi(h+1)}b^{\xi(h+1)}F^{(h)}_{n-1}(q,s) + q^{n-2+h}sF^{(h)}_{n-2}(q,s), \ \text{if} \ n\equiv 1\pmod 2; \end{cases} \ n\geq 2. \label{eqq1} \end{align*} A tiling of a $n$-board is \emph{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 \emph{unbreakable} at cell $k$ if a domino occupies cell $k$ and $k+1$ (cf.\ \cite{Benja}). It is not difficult to show that $F^{(h)}_{n+1}(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$. \begin{theorem} The following equality holds for any integers $n, m \geq 0$: \begin{align*} F_{n+m+1}^{(a,b)}(q,s)=F_{m+1}^{(a,b)}(q,s)F_{n+1}^{(m)}(q,s) + q^msF_{m}^{(a,b)}(q,s)F_{n}^{(m+1)}(q,s). \end{align*} \end{theorem} \begin{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). \end{proof} The above theorem is a $q$-analogue of the Fibonacci identity: $$F_{m+n}=F_mF_n+F_{m-1}F_{n-1}.$$ The following theorem is a $q$-analogue of the bi-periodic Fibonacci identity (see \cite[Theorem 7]{edson1}): $$\sum_{k=0}^n\binom nk a^{\xi(k)}(ab)^{\left\lfloor \frac k2 \right\rfloor}t_k=t_{2n}.$$ \begin{theorem} The following equality holds for any integer $n\geq 0$: \begin{align*} F_{2n}^{(a,b)}(q,s)=\sum_{k=1}^na^{\xi(k)}q^{(n-k)^2}s^{n-k} {n\brack k}(ab)^{\left\lfloor \frac k2 \right\rfloor} F_{k}^{(2n-k)}(q,s). \end{align*} \end{theorem} \begin{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 \ref{lema} there are $$a^{\xi(2n-k)}q^{(n-k)^2}s^{n-k}{n\brack n-k}(ab)^{\left\lfloor \frac{k}{2}\right\rfloor}=a^{\xi(k)}q^{(n-k)^2}s^{n-k}{n\brack k}(ab)^{\left\lfloor \frac{k}{2}\right\rfloor}$$ 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. \end{proof} \begin{theorem} The following equality holds for any integer $n\geq 0$: \begin{align*} F_{2n+2}^{(a,b)}(q,s)=a\sum_{i=0}^n\sum_{j=0}^n(ab)^{\xi(n-i-j)}q^{i^2+(n+i+j)j}s^{i+j}{n-j\brack i}{n-i\brack j}(ab)^{2\left\lfloor \frac{n-i-j}{2} \right\rfloor}. \end{align*} \end{theorem} \begin{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^{\xi(n-j+i)}q^{i^2}s^i{n-j\brack i}(ab)^{\left\lfloor \frac{n-i-j}{2}\right\rfloor}$$ ways to tile this board. Analogously, the right side can be tiled by $$b^{\xi(n-j+i)}q^{(n+i+1)j}s^j{n-i\brack j}(ab)^{\left\lfloor \frac{n-i-j}{2}\right\rfloor}$$ ways. \end{proof} The above theorem is a $q$-analogue of the Fibonacci identity (cf.\ \cite{koshy}): $$\sum_{i=0}^n\sum_{j=0}^n\binom{n-i}{j}\binom{n-j}{i}=F_{2n+1}.$$ \section{Acknowledgments} The authors thank the anonymous referee for his/her comments which helped to improve the article. \begin{thebibliography}{12} \bibitem{ALP} M. Alp, N. Irmak, and L. Szalay, Two-periodic ternary recurrences and their Binet-formula, \emph {Acta Math. Univ. Comenianae} {\bf {2}} (2012), 227--232. \bibitem{Andrews4} G. E. Andrews, A polynomial identity which implies the Rogers-Ramanujan identities, \emph{Scr. Math.} \textbf{28} (1970), 297--305. \bibitem{Andrews2} G. E. Andrews, Fibonacci numbers and the Rogers-Ramanujan identities, \emph{Fibonacci Quart.} \textbf{42} (2004), 3--19. \bibitem{Andrews} G. E. Andrews, A. Knopfmacher, and P. Paule, An infinite family of Engel expansions of Rogers-Ramanujan type, \emph{Adv. in Appl. Math.} \textbf{25} (2000), 2--11. \bibitem{Bel} H. Belbachir and A. Benmezai, An alternative approach to Cigler's $q$-Lucas polynomials, \emph{Applied. Math. Comp.} \textbf{226} (2014), 691--698. \bibitem{Bel2} H. Belbachir and A. Benmezai, A $q$ analogue for bi$^s$nomial coefficients and generalized Fibonacci sequence, \emph{C. R. Math. Acad. Sci. Paris I} \textbf{352} (2014), 167--171. \bibitem{Shatu} A. Benjamin, A. Eustis, and M. Shattuck, Compression theorems for periodic tilings and consequences, \emph{J. Integer Sequences} \textbf{12} (2009), \href{https://cs.uwaterloo.ca/journals/JIS/VOL12/Shattuck/shattuck20.html}{Article 09.6.3}. \bibitem{Benja} A. Benjamin and J. Quinn, \emph{Proofs that Really Count: The Art of Combinatorial Proof}, Dolciani Mathematical Expositions, Vol.~27, Mathematical Association of America, 2003. \bibitem{Bil} G. Bilgici, Two generalizations of Lucas sequence, \emph{Applied. Math. Comp.} \textbf{245} (2014), 526--538. \bibitem{Briggs} K. Briggs, D. Little, and J. Sellers, Combinatorial proofs of various $q$-Pell identities via tilings, \emph{Ann. Comb.} \textbf{14} (2010), 407--418. \bibitem{Carlitz} L. Carlitz, Fibonacci notes. III. $q$-Fibonacci numbers, \emph{Fibonacci Quart.} \textbf{12} (1974), 317--322. \bibitem{Carlitz2} L. Carlitz, Fibonacci notes. IV. $q$-Fibonacci polynomials, \emph{Fibonacci Quart.} \textbf{13} (1975), 97--102. \bibitem{Cigler} J. Cigler, A new class of $q$-Fibonacci polynomials, \emph{Electron. J. Combin.} \textbf{10} (2003), 1--15. \bibitem{Cigler2} J. Cigler, $q$-Fibonacci polynomials, \emph{Fibonacci Quart.} \textbf{41} (2003), 31--40. \bibitem{Cigler4} J. Cigler, $q$-Fibonacci polynomials and the Rogers-Ramanujan identities, \emph{ Ann. Combin.} \textbf{8} (2004), 269--285. \bibitem{Chan} H.-C. Chan, On the Andrews-Schur proof of the Rogers-Ramanujan identities, \emph{Ramanujan J.} \textbf{23} (2010), 417--431. \bibitem{edson3} M. Edson, S. Lewis, and O. Yayenie, The $k$-periodic Fibonacci sequence and extended Binet's formula, \emph{Integers} \textbf{11} (A32) (2011), 739--751. \bibitem{edson1} M. Edson and O. Yayenie, A new generalization of Fibonacci sequences and extended Binet's Formula, \emph{Integers} \textbf{9} (A48) (2009), 639--654. \bibitem{Graham} R. Graham, D. Knuth, and O. Patashnik, \emph{Concrete Mathematics}, Addison-Wesley, Second Edition, 1994. \bibitem{Prodinger} M. Ismail, H. Prodinger, and D. Stanton, Schur's determinants and partition theorems, \emph{S\'em. Lothar. Combin.} \textbf{44} (B44a) (2000), 1--10. \bibitem{NURE} N. Irmak and L. Szalay, On $k$-periodic binary recurrences, \emph{Ann. Math. Inform.} \textbf{40} (2012), 25--35. \bibitem{koshy} T. Koshy, \emph{Fibonacci and Lucas Numbers with Applications}, Wiley-Interscience, 2001. \bibitem{Kris} K. Garrett, Weighted tilings and $q$-Fibonacci numbers, preprint, 2004. Available at \url{http://www.stolaf.edu/people/garrettk/qFibonacci.pdf}. \bibitem{Little} D. Little and J. Sellers, A tiling approach to eight identities of Rogers, \emph{European J. Combin.} \textbf{31} (2010), 694--709. \bibitem{Panario} D. Panario, M. Sahin, and Q. Wan, A family of Fibonacci-like conditional sequences, \emph{Integers} \textbf{13} (A78) (2013), 1--14. \bibitem{Panario2} D. Panario, M. Sahin, Q. Wan, and W. Webb, General conditional recurrences, \emph{Applied. Math. Comp}. \textbf{243} (2014), 220--231. \bibitem{Ram} J. L. Ram\'irez, Bi-periodic incomplete Fibonacci sequences, \emph{Ann. Math. Inform.} \textbf{42} (2013), 83--92. \bibitem{Schur} I. Schur, Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbr\"uche, \emph{S.-B. Preuss. Akad. Wiss. Phys. Math. Klasse} \textbf{54} (1917), 302--321. \bibitem{Stabel} E. C. Stabel, A combinatorial proof of an identity of Ramanujan using tilings, \emph{Bull. Braz. Math. Soc.} \textbf{42} (2011), 203--212. \bibitem{edson2} O. Yayenie, A note on generalized Fibonacci sequence, \emph{Applied. Math. Comp.} \textbf{217} (2011), 5603--5611. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B39; Secondary 11B65, 05A19. \noindent \emph{Keywords: } $q$-Fibonacci sequence, $q$-bi-periodic Fibonacci sequence, bi-periodic Fibonacci sequence, $q$-analogues, combinatorial identities. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A000045}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 4 2015; revised version received March 30 2016. Published in {\it Journal of Integer Sequences}, May 9 2016. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}