\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}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

\newcommand{\T}[1]{\qquad\mbox{#1}\qquad}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\dimv}{\textbf{dim}}
\newcommand{\MATRIX}[4]{\left[\begin{array}{cc} #1 & #2 \\#3 & #4 \end{array}\right]} % 2x2 matrix

\def\al{\alpha}
\def\a{\alpha}
\def\b{\beta}
\newcommand{\gauss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}

\def\q#1{[#1]_q}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}


\begin{center}
\vskip 1cm{\LARGE\bf On the Expansion of Fibonacci and Lucas \\
\vskip .1in
Polynomials}
\vskip 1cm
\large
Helmut Prodinger\\ 
Department of Mathematics\\
University of Stellenbosch\\
7602 Stellenbosch\\
South Africa\\
\href{mailto:hproding@sun.ac.za}{\tt hproding@sun.ac.za} \\
\end{center}

\vskip .2 in

\begin{abstract}
Recently, Belbachir and Bencherif have expanded Fibonacci
and Lucas polynomials using bases of Fibonacci- and Lucas-like
polynomials. Here, we provide simplified proofs for the expansion
formul\ae that in essence a computer can do.
Furthermore, for 2 of the 5 instances, we find $q$-analogues.
\end{abstract}

\section{Introduction}

In \cite{algier}, Belbachir and Bencherif studied the
Fibonacci and Lucas polynomials:
\begin{gather*}
U_0=0,\ U_1=1,\ U_n=xU_{n-1}+yU_{n-2},\\
V_0=2,\ V_1=x,\ V_n=xV_{n-1}+yV_{n-2}.
\end{gather*}
We prefer the modified polynomials
\begin{gather*}
u_0=0,\ u_1=1,\ u_n=u_{n-1}+zu_{n-2},\\
v_0=2,\ v_1=1,\ v_n=v_{n-1}+zv_{n-2},
\end{gather*}
so that
\begin{equation*}
U_n(x,y)=x^{n-1}u_n\Bigl(\frac{y}{x^2}\Bigr),\quad
V_n(x,y)=x^nv_n\Bigl(\frac{y}{x^2}\Bigr).
\end{equation*}
Then, with 
\begin{equation*}
\lambda_{1,2}=\frac{1\pm\sqrt{1+4z}}{2},
\end{equation*}
\begin{equation*}
u_n=\frac1{\sqrt{1+4z}}(\lambda_1^n-\lambda_2^n),\qquad
v_n=\lambda_1^n+\lambda_2^n.
\end{equation*}
Substituting $z=t/(1-t)^2$, these formul\ae{} become particularly nice:
\begin{equation*}
u_n=\frac{1-(-t)^n}{(1+t)(1-t)^{n-1}},\qquad
v_n=\frac{1+(-t)^n}{(1-t)^{n}}.
\end{equation*}
The main result of \cite{algier} are the following 5 formul\ae:
\begin{equation}\label{eq-A}
2u_{2n+1}=\sum_{k=0}^na_{n,k}v_{2n-k},\qquad
a_{n,k}=2\sum_{j=0}^n(-1)^{j+k}\binom jk-(-1)^{n+k}\binom nk.
\end{equation}
\begin{equation}\label{eq-B}
u_{2n}=\sum_{k=1}^nb_{n,k}u_{2n-k},\qquad
b_{n,k}=(-1)^{k+1}\binom nk.
\end{equation}
\begin{equation}\label{eq-C}
v_{2n-1}=\sum_{k=1}^nc_{n,k}u_{2n-k},\qquad
c_{n,k}=2(-1)^{k+1}\binom nk-[k=1].
\end{equation}
\begin{equation}\label{eq-D}
2v_{2n-1}=\sum_{k=1}^nd_{n,k}v_{2n-1-k},\qquad
d_{n,k}=(-1)^{k+1}\frac{2n-k}{n}\binom nk.
\end{equation}
\begin{align}\label{eq-E}
2u_{2n}&=\sum_{k=1}^ne_{n,k}v_{2n-1-k},\\
e_{n,k}&=(-1)^{k+1}\frac{2n-k}{2n}\binom nk+
\sum_{j=0}^{n-1}(-1)^{j+k-1}\binom j{k-1} -\frac12(-1)^{n+k}\binom{n-1}{k-1}.\nonumber
\end{align}
But the proofs of all these, using the simple forms for $u_n$ and $v_n$, can be done by a computer! To give the reader an idea, let us do the last one, which seems to be the most complicated:
\begin{align*}
\sum_{k=1}^ne_{n,k}v_{2n-1-k}
&=\sum_{k=1}^n(-1)^{k+1}\frac{2n-k}{2n}\binom nkv_{2n-1-k}
\\&
+\sum_{j=0}^{n-1}\sum_{k=1}^{j+1}(-1)^{j+k-1}\binom j{k-1}v_{2n-1-k}
-\sum_{k=1}^n\frac12(-1)^{n+k}\binom{n-1}{k-1}v_{2n-1-k}\\
&=\frac{1-t^{2n-1}}{(1-t)^{2n-1}}+\frac{1+t^{2n-1}}{(1-t)^{2n-2}(1+t)}-
\frac{(-1)^nt^{n-1}}{(1-t)^{2n-2}}+\frac{(-1)^nt^{n-1}}{(1-t)^{2n-2}}\\
&=\frac{2(1-t^{2n})}{(1-t)^{2n-1}(1+t)}=2u_{2n}.
\end{align*}
The other proofs are similar/easier:
\begin{align*}
\sum_{k=0}^na_{n,k}v_{2n-k}&=\frac{2[(-t)^n(1+t)+1+t^{2n+1}]}{(1-t)^{2n}(1+t)}-
\frac{2(-t)^n}{(1-t)^{2n}}\\
&=\frac{2[1+t^{2n+1}]}{(1-t)^{2n}(1+t)}=2u_{2n+1}.
\end{align*}
\begin{align*}
\sum_{k=1}^nc_{n,k}u_{2n-k}&=\frac{2(1-t^{2n})}{(1-t)^{2n-1}(1+t)}-
\frac{1+t^{2n-1}}{(1+t)(1-t)^{2n-2}}\\&
=\frac{1-t^{2n-1}}{(1-t)^{2n-1}}=v_{2n-1}.
\end{align*}

\begin{remark}
The polynomials $u_n(x)$ and $v_n(x)$ are essentially Chebyshev polynomials.
The authors of \cite{algier} have also published a companion
paper~\cite{algier2}; according to a remark in  \cite{algier}, the
results in \cite{algier} are more general than the ones in
\cite{algier2}.
\end{remark}

\section{$\boldsymbol{q}$-analogues}

Now we are interested in $q$-analogues. For this, we replace $u_n$ by
\begin{equation*}
\text{Fib}_n=\sum_{0\le k\le \frac{n-1}{2}}q^{\binom{k+1}2}\gauss{n-k-1}{k}z^k
\end{equation*}
and $v_n$ by
\begin{equation*}
\text{Luc}_n=\sum_{0\le k\le \frac{n}{2}}q^{\binom{k}2}\gauss{n-k}{k}\frac{\q{n}}{\q{n-k}}z^k,
\end{equation*}
as suggested by Cigler~\cite{Cigler2003}. We use standard $q$-notation here:
\begin{align*}
[n]_q:=1+q+\cdots+q^{n-1},\quad [n]_q!:=[1]_q[2]_q\dots[n]_q, \quad \gauss{n}{k}
:=\frac{[n]_q!}{[k]_q![n-k]_q!},
\end{align*}
compare \cite{AAR}; the notions of the Introduction are the special instance $q=1$.

\begin{theorem}
\begin{equation*}
\text{\rm Luc}_{2n-1}=\sum_{k=1}^nd_{n,k}\text{\rm Luc}_{2n-1-k},
\end{equation*}
with
\begin{equation*}
d_{n,k}=(-1)^{k-1}\frac{q^{\binom k2}}{1+q^{n-1}}
\bigg(\gauss{n-1}k+q^{n-1}\gauss{n}{k}\bigg).
\end{equation*}
\end{theorem}
\begin{proof}
We must prove that
\begin{multline*}
\sum_{0\le k\le n-1}q^{\binom{k}2}\gauss{2n-1-k}{k}\frac{\q{2n-1}}{\q{2n-1-k}}z^k\\
=\sum_{j=1}^{n}(-1)^{j-1}\frac{q^{\binom j2}}{1+q^{n-1}}
\bigg(\gauss{n-1}j+q^{n-1}\gauss{n}{j}\bigg)\\
\hspace*{4cm}\times\sum_{0\le k\le \frac{2n-j-1}{2}}q^{\binom{k}2}\gauss{2n-j-1-k}{k}\frac{\q{2n-j-1}}{\q{2n-j-1-k}}z^k.
\end{multline*}
Comparing coefficients, we have to  prove that
\begin{align*}
&q^{\binom{k}2}\gauss{2n-1-k}{k}\frac{\q{2n-1}}{\q{2n-1-k}}\\
&=\sum_{j=1}^{n}(-1)^{j-1}\frac{q^{\binom j2}}{1+q^{n-1}}
\bigg(\gauss{n-1}j+q^{n-1}\gauss{n}{j}\bigg)q^{\binom{k}2}\gauss{2n-j-1-k}{k}\frac{\q{2n-j-1}}{\q{2n-j-1-k}}.
\end{align*}
Simplifying, we must prove that
\begin{align*}
\sum_{j=0}^{n}(-1)^{j}q^{\binom j2}
\bigg(\gauss{n-1}j+q^{n-1}\gauss{n}{j}\bigg)\gauss{2n-j-2-k}{k-1}\q{2n-j-1}=0.
\end{align*}
Another form of this is
\begin{align*}
\sum_{j=0}^{n}(-1)^{j}q^{\binom j2}\Big(1-q^{2n-1}-q^{n-j}+q^{n-1}\Big)
\Big(1-q^{2n-j-1}\Big)\gauss{n}{j}
\gauss{2n-j-2-k}{k-1}=0.
\end{align*}
Notice that
\begin{align*}
\sum_{j=0}^{n}(-1)^{j}q^{\binom j2}\gauss{n}{j}q^{-aj}=0
\end{align*}
for $0\le a\le n-1$. This follows from \emph{Rothe's} formula~\cite[p.~490]{AAR}
\begin{equation*}
\sum_{j=0}^{n}(-1)^{j}q^{\binom j2}\gauss{n}{j}x^{j}=(1-x)(1-xq)\dots(1-q^{n-1}).
\end{equation*}
We write the desired identity as
\begin{align*}
\sum_{j=0}^{n}(-1)^{j}q^{\binom j2}\Big(A+Bq^{-j}+Cq^{-2j}\Big)\gauss{n}{j}
\Big(D_0q^{-0}+\cdots+D_{k-1}q^{-j(k-1)}\Big)=0.
\end{align*}
Therefore, for  $k\le n-2$, the identity holds. For $k=n-1$, 
\begin{align*}
\sum_{j=0}^{1}(-1)^{j}q^{\binom j2}\Big(1-q^{2n-1}-q^{n-j}+q^{n-1}\Big)
\Big(1-q^{2n-j-1}\Big)\gauss{n}{j}
\gauss{n-j-1}{n-2}=0
\end{align*}
can be shown by inspection, and for $k=n$, the identity holds, since the sum is empty.
\end{proof}

\begin{theorem}
\begin{equation*}
\text{\rm Fib}_{2n}=\sum_{k=1}^nb_{n,k}\text{\rm Fib}_{2n-k}
\end{equation*}
with
\begin{equation*}
b_{n,k}=(-1)^{k-1}q^{\binom k2}\gauss{n}{k}.
\end{equation*}
\end{theorem}
\begin{proof}
We must prove that
\begin{multline*}
\sum_{0\le k\le n-1}q^{\binom{k+1}2}\gauss{2n-k-1}{k}z^k\\=\sum_{j=1}^n(-1)^{j-1}q^{\binom j2}\gauss{n}{j}
\sum_{0\le k\le \frac{2n-j-1}{2}}q^{\binom{k+1}2}\gauss{2n-j-k-1}{k}z^k.
\end{multline*}
Comparing coefficients, this means
\begin{align*}
\sum_{j=0}^n(-1)^{j}q^{\binom j2}\gauss{n}{j}\gauss{2n-j-k-1}{k}=0,
\end{align*}
which follows by a similar but simpler argument than before.
\end{proof}

\section{Conclusion} We found 2 $q$-analogues; for the remaining 3 instances we were not
successful and leave this as a challenge for anybody who is interested.

\begin{thebibliography}{10}

\bibitem{AAR}
G.~E.~Andrews, R.~Askey and R.~Roy, {\it Special Functions},
Cambridge University Press, 2000.

\bibitem{algier}
H.~Belbachir and F.~Bencherif, 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Belbachir/belbachir13.html}{On some properties of bivariate {F}ibonacci and {L}ucas} polynomials, {\it
J. Integer Sequences} {\bf 11} (2008), Article 08.2.6.

\bibitem{algier2}
H.~Belbachir and F.~Bencherif,
On some properties of {C}hebyshev polynomials,
{\it Discuss. Math. Gen. Algebra Appl.} {\bf 28} (2008), 121--133.

\bibitem{Cigler2003}
{\sc J.~Cigler},
A new class of $q$-{F}ibonacci polynomials,
{\it Electronic J. Combinatorics}
{\bf 10} (2003), Article R19.  Text available at  \hfill\\
\href{http://www.combinatorics.org/Volume_10/Abstracts/v10i1r19.html}{\tt http://www.combinatorics.org/Volume\_10/Abstracts/v10i1r19.html}.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 11B37.

\noindent \emph{Keywords: } 
Fibonacci polynomials, Lucas polynomials, generating functions, $q$-analogues.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A007318}, \seqnum{A029653} and \seqnum{A112468}.)

\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received October 6 2008;
revised version received December 15 2008.  
Published in {\it Journal of Integer Sequences}, December 17 2008.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}