\documentclass[12pt,recno]{article}

\usepackage{latexsym}
\usepackage{amsfonts,amsmath,amssymb}
\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{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}}}



\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






\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}








\begin{document}

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




\begin{center}
\vskip 1cm{\LARGE\bf Generating Functions Related to Partition\\
\vskip .15in
Formul\ae{} for Fibonacci Numbers
}
\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}
The generating functions of 2 double schemes of numbers are explicitly computed using the
kernel method, which leads to easy proofs of partition formul\ae{} for Fibonacci numbers.
\end{abstract}



\section{Introduction}
The numbers given by the recursions
\begin{align*}
b_{n+1,k}&=c_{n,k-1}+2c_{n,k}-b_{n,k},\\
c_{n+1,k}&=b_{n+1,k}+2b_{n+1,k+1}-c_{n,k}
\end{align*}
for $n\ge0$, with $b_{0,0}=c_{0,0}=1$, $c_{n,-1}=c_{n,0}$
are used by Fahr and Ringel in \cite{Ringel} to partition the Fibonacci numbers. 
We want to shed new light on these numbers, by computing their
(bivariate) generating functions. These lead then also to straight forward
 proofs of the partition formul\ae{} given by Fahr and Ringel in \cite{Ringel}. Notice, however, that these
 proofs do not provide any \emph{insight}.

\section{The generating functions}


Introducing generating functions
\begin{align*}
B(z,x)&:=\sum_{0\le k\le n}b_{n,k}z^nx^k,\\
C(z,x)&:=\sum_{0\le k\le n}c_{n,k}z^nx^k,
\end{align*}
these recursions translate into
\begin{align*}
B(z,x)&=1+zxC(z,x)+2zC(z,x)-zB(z,x)+zC(z,0),\\
C(z,x)&=B(z,x)+\frac 2x[B(z,x)-B(z,0)]-zC(z,x).
\end{align*}
This leads to
\begin{equation*}
C(z,x)=-{\frac {x+z(x-4)C(z,0)}{z{x}^{2}-{z}^{2}x+2zx-x+4z}}.
\end{equation*}
To solve that, we factor the denominator:
\begin{equation*}
C(z,x)=\frac {-x+z(4-x)C(z,0)}{z(x-r_1(z))(x-r_2(z))}
\end{equation*}
with
\begin{equation*}
r_{1,2}(z)={\frac {(1-z)^{2}\pm (1+z) \sqrt {1-6z+{z}^{2}}}{2z}}.
\end{equation*}
Since $1/(x-r_2(z))$ has no power series expansion in $z$ and $x$, the factor must cancel,
i.e., 
\begin{equation*}
-r_2(z)+z(4-r_2(z))C(z,0)=0,
\end{equation*}
whence
\begin{equation*}
C(z,0)=\frac {-1+4z-{z}^{2}+(1+z)\sqrt {1-6z+{z}^{2}}}{2z ( 1-7z+{z}^{2} ) }.
\end{equation*}
This is the famous \emph{kernel method}, see, e.g., \cite{Prodinger}.

After cancellation, this leads to
\begin{equation*}
C(z,x)=\frac {4r_2(z)}{2z(1-4xr_2(z))}
{\frac {1-10z+{z}^{2}+(1+z)\sqrt {1-6z+{z}^{2}}}{1-7z+{z}^{2}}},
\end{equation*}
and
\begin{equation*}
[x^k]C(z,x)=\frac {(4r_2(z))^{k+1}}{2z}{\frac {1-10z+{z}^{2}+(1+z)\sqrt {1-6z+{z}^{2}}}{1-7z+{z}^{2}}}.
\end{equation*}
From this we get
\begin{equation*}
B(z,x)=\frac{-(1+ z ) ( {z}^{2}x-8xz+4z+x ) + ( -{z}^{2}x+12z+4\,zx-x ) \sqrt {1-6z+{z}^{2}}}
{2( 1-7z+{z}^{2} )  ( -{z}^{2}x+2zx-x+4z+z{x}^{2} )}.
\end{equation*}

The formula
\begin{equation*}
f_{4(n+1)}=3\sum_{k\ge0}4^kc_{n,k},
\end{equation*}
given by Fahr and Ringel in \cite{Ringel}, can now easily be verified, since the generating function of the right-hand side
is
\begin{equation*}
3C(z,4)=\frac{3}{1-7z+z^2},
\end{equation*}
which is also the generating function of the left-hand side, which can be seen for example
from the Binet form of the Fibonacci numbers.

The other formula
\begin{equation*}
f_{4n+2}=b_{n,0}+\frac32\sum_{k\ge1}4^kb_{n,k},
\end{equation*}
follows from the generating function
\begin{equation*}
B(z,0)+\frac32\Big(B(z,4)-B(z,0)\Big)=\frac{1+z}{1-7z+z^2}.
\end{equation*}


\begin{thebibliography}{99}

\bibitem{Ringel} Ph. Fahr and C.-M. Ringel, 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Fahr/ringel44.html}{A partition formula for Fibonacci numbers}, \emph{J. Integer Sequences} \textbf{11} (2008), Article 08.1.4.

\bibitem{Prodinger} H. Prodinger, \href{http://www.mat.univie.ac.at/~slc/wpapers/s50proding.html}{The kernel method: A collection of examples},
\emph{S\'eminaire Lotharingien de Combinatoire}, B50f (2004).



\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B39, Secondary 16G20.

\noindent \emph{Keywords: } 
Fibonacci numbers, generating function, kernel method.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A110122} and \seqnum{A132262}.)

\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received February 28 2008;
revised version received April 21 2008.  
Published in {\it Journal of Integer Sequences}, May 22 2008.
Minor correction, August 12 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}

.