<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf On Recurrences of Fahr and Ringel \\
\vskip .1in Arising in Graph Theory
}
\vskip 1cm
\large
Michael D. Hirschhorn \\
School of Mathematics and Statistics \\
UNSW\\
Sydney NSW 2052\\
Australia\\
\href{mailto:m.hirschhorn@unsw.edu.au}{\tt m.hirschhorn@unsw.edu.au} \\
\end{center}

\vskip .2 in
\begin{abstract}
We solve certain recurrences given by Fahr and Ringel, and confirm their
conjecture that two sequences are identical.
\end{abstract}



\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}}

%\usepackage{latexsym,amssymb,amsmath,a4wide,theorem,wasysym,pifont} 

\section{Introduction}
Fahr and Ringel 
%\cite{ref1} 
introduce two tables of numbers, the $b_t[r]$ and $c_t[r]$,
given by

\[ \begin{array}
{ccccccccccccccccc}
 b_t[r]&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;\ \ c_t[r]\\
&amp;&amp;r&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;\ \ r\\
&amp;&amp;0&amp;1&amp;2&amp;3&amp;4&amp;\cdots&amp;&amp;&amp;&amp;0&amp;1&amp;2&amp;3&amp;4&amp;\cdots\\
t&amp;0&amp;1&amp;&amp;&amp;&amp;&amp;&amp;&amp;t&amp;0&amp;1\\
&amp;1&amp;2&amp;1&amp;&amp;&amp;&amp;&amp;&amp;&amp;1&amp;3&amp;1\\
&amp;2&amp;7&amp;4&amp;1&amp;&amp;&amp;&amp;&amp;&amp;2&amp;12&amp;5&amp;1\\
&amp;3&amp;29&amp;18&amp;6&amp;1&amp;&amp;&amp;&amp;&amp;3&amp;53&amp;25&amp;7&amp;1\\
&amp;4&amp;130&amp;85&amp;33&amp;8&amp;1&amp;&amp;&amp;&amp;4&amp;247&amp;126&amp;42&amp;9&amp;1\\
\end{array} \]

and the recurrences
\begin{eqnarray*}
&amp;&amp;b_{t+1}[r]=c_t[r-1]+2c_t[r]-b_t[r],\\
&amp;&amp;c_{t+1}[r]=b_{t+1}[r]+2b_{t+1}[r+1]-c_t[r],\\
\end{eqnarray*}
which hold for $t,r\ge0$, with the understanding that $c_t[-1]=c_t[0]$.

The object of this note is to determine the generating functions of the $b_t[r]$
and $c_t[r]$, and to prove that
$$
F_{4t+2}=b_t[0]+3\sum_{r\ge1}2^{2r-1}b_t[r],
\ \ \ \ F_{4t+4}=3\sum_{r\ge0}2^{2r}c_t[r],
$$
where the $F_t$ are the Fibonacci numbers,
given by $F_0=0,\ F_1=1$ and $F_t=F_{t-1}+F_{t-2}$ for $t\ge2$.

\section{The solution}

Let us define
$$
B_r=B_r(q)=\sum_{t\ge0}b_t[r]q^t,\ \ C_r=C_r(q)=\sum_{t\ge0}c_t[r]q^t.
$$
The first few $B_r$, $C_r$ are
\begin{eqnarray*}
&amp;&amp;B_0=1+2q+7q^2+29q^3+130q^4+\ \cdots\ ,\\
&amp;&amp;B_1=q+4q^2+18q^3+85q^4+\ \cdots\ ,\\
&amp;&amp;B_2=q^2+6q^3+33q^4+\ \cdots\ ,\\
&amp;&amp;C_0=1+3q+12q^2+53q^3+247q^4+\ \cdots\,\\
&amp;&amp;C_1=q+5q^2+25q^3+126q^4+\ \cdots\ ,\\
&amp;&amp;C_2=q^2+7q^3+42q^4+\ \cdots\ .\\
\end{eqnarray*}
Note that for $r\ge0$,
$$
B_r\equiv0\pmod{q^r},\ \ \ \ C_r\equiv0\pmod{q^r}.
$$

From the recurrences given above, we have
$$
B_0=1+3qC_0-qB_0,
$$
or,
$$
B_0=\displaystyle\frac{1+3qC_0}{1+q}.
$$
Also, for $r\ge1$,
$$
B_r=qC_{r-1}+2qC_r-qB_r
$$
and for $r\ge0$,
$$
C_r=B_r+2B_{r+1}-qC_r.
$$
That is, for $r\ge0$,
$$
B_{r+1}=\frac12\left ((1+q)C_r-B_r\right )
$$
and
$$
C_{r+1}=\frac1{2q}\left ((1+q)B_{r+1}-qC_r\right ).
$$
It follows that
\begin{eqnarray*}
&amp;&amp;B_1=\frac12\left ((1+q)C_0-\frac{1+3qC_0}{1+q}\right )
=\frac{(1-q+q^2)C_0-1}{2(1+q)},\\
&amp;&amp;C_1=\frac1{2q}\left ((1+q)\frac{(1-q+q^2)C_0-1}{2(1+q)}-qC_0\right )
=\frac{(1-3q+q^2)C_0-1}{4q},\\
&amp;&amp;B_2=\frac{(1-3q-2q^2-3q^3+q^4)C_o-(1+q^2)}{8q(1+q)},\\
&amp;&amp;C_2=\frac{(1-5q+4q^2-5q^3+q^4)C_0-(1-2q+q^2)}{16q^2},\\
&amp;&amp;B_3=\frac{(1-5q+q^2+2q^3+q^4-5q^5+q^6)C_0-(1-2q-2q^2-2q^3+q^4)}{32q^2(1+q)},\\
&amp;&amp;C_3=\frac{(1-7q+11q^2-6q^3+11q^4-7q^5+q^6)C_0-(1-4q+2q^2-4q^3+q^4)}{64q^3},\\
\end{eqnarray*}
and so on.

It is clear that we can write
\begin{eqnarray*}
&amp;&amp;B_r=\displaystyle\frac{P_rC_0-Q_r}{2^{2r-1}q^{r-1}(1+q)},\\
&amp;&amp;C_r=\displaystyle\frac{S_rC_0-T_r}{2^{2r}q^r},\\
\end{eqnarray*}
where $P_r,\ Q_r,\ S_r,\ T_r$ are polynomials in $q$. The first few are
\begin{eqnarray*}
&amp;&amp;P_1=1-q+q^2,\\
&amp;&amp;P_2=1-3q-2q^2-3q^3+q^4,\\
&amp;&amp;P_3=1-5q+q^2+2q^3+q^4-5q^5+q^6,\\
&amp;&amp;Q_1=1,\\
&amp;&amp;Q_2=1+q^2,\\
&amp;&amp;Q_3=1-2q-2q^2-2q^3+q^4,\\
&amp;&amp;S_1=1-3q+q^2,\\
&amp;&amp;S_2=1-5q+4q^2-5q^3+q^4,\\
&amp;&amp;S_3=1-7q+11q^2-6q^3+11q^4-7q^5+q^6,\\
&amp;&amp;T_1=1,\\
&amp;&amp;T_2=1-2q+q^2,\\
&amp;&amp;T_3=1-4q+2q^2-4q^3+q^4.\\
\end{eqnarray*}

It follows from the recurrences for the $B_r$ and $C_r$ that $P_r,\ Q_r,\ S_r$
and $T_r$ all satisfy the recurrence
$$
X_{r+2}-(1-q)^2X_{r+1}+4q^2X_r=0.
$$

Indeed, in terms of $\alpha$ and $\beta$, the roots of $z^2-(1-q)^2z+4q^2=0$,
\begin{eqnarray*}
&amp;&amp;\alpha=\frac{(1-q)^2+(1+q)\sqrt{1-6q+q^2}}{2}
=1-2q-3q^2-8q^3-28q^4-112q^5-\ \cdots\ ,\\
&amp;&amp;\beta=\frac{(1-q)^2-(1+q)\sqrt{1-6q+q^2}}{2}=4q^2+8q^3+28q^4+112q^5+\ \cdots,\\
\end{eqnarray*}
we have
\begin{eqnarray*}
&amp;&amp;P_r=\left (\frac34+\frac{1+q}{4\sqrt{1-6q+q^2}}\right )\alpha^r
+\left (\frac34-\frac{1+q}{4\sqrt{1-6q+q^2}}\right )\beta^r,\\
&amp;&amp;Q_r=\left (\frac{1+q}{4q\sqrt{1-6q+q^2}}-\frac1{4q}\right )\alpha^r
-\left (\frac{1+q}{4q\sqrt{1-6q+q^2}}+\frac1{4q}\right )\beta^r,\\
&amp;&amp;S_r=\left (\frac12+\frac{1-4q+q^2}{2(1+q)\sqrt{1-6q+q^2}}\right )\alpha^r
+\left (\frac12-\frac{1-4q+q^2}{2(1+q)\sqrt{1-6q+q^2}}\right )\beta^r,\\
&amp;&amp;T_r=\frac1{(1+q)\sqrt{1-6q+q^2}}\,\alpha^r
-\frac1{(1+q)\sqrt{1-6q+q^2}}\,\beta^r.\\
\end{eqnarray*}
It follows that
\begin{eqnarray*}
&amp;&amp;2^{2r-1}q^{r-1}(1+q)B_r=P_rC_0-Q_r\\
&amp;&amp;=\left (\left (\frac34+\frac{1+q}{4\sqrt{1-6q+q^2}}\right )C_0
-\left (\frac{1+q}{4q\sqrt{1-6q+q^2}}-\frac1{4q}\right )\right )\alpha^r\\
&amp;&amp;+\left (\left (\frac34-\frac{1+q}{4\sqrt{1-6q+q^2}}\right )C_0
+\left (\frac{1+q}{4q\sqrt{1-6q+q^2}}+\frac1{4q}\right )\right )\beta^r\\
\end{eqnarray*}
and
\begin{eqnarray*}
&amp;&amp;2^{2r}q^rC_r
=\left (\left (\frac12+\frac{1-4q+q^2}{2(1+q)\sqrt{1-6q+q^2}}\right )C_0
-\frac1{(1+q)\sqrt{1-6q+q^2}}\right )\alpha^r\\
&amp;&amp;+\left (\left (\frac12-\frac{1-4q+q^2}{2(1+q)\sqrt{1-6q+q^2}}\right )C_0
+\frac1{(1+q)\sqrt{1-6q+q^2}}\right )\beta^r.\\
\end{eqnarray*}

Since the left--hand--sides of the above two equations are congruent to 0 modulo $q^{2r-1}$, we deduce that
$$
\left (\frac34+\frac{1+q}{4\sqrt{1-6q+q^2}}\right )C_0
-\left (\frac{1+q}{4q\sqrt{1-6q+q^2}}-\frac1{4q}\right )=0,
$$
alternatively that
$$
\left (\frac12+\frac{1-4q+q^2}{2(1+q)\sqrt{1-6q+q^2}}\right )C_0
-\frac1{(1+q)\sqrt{1-6q+q^2}}=0.
$$

It follows that
$$
C_0=\frac{(1+q)\sqrt{1-6q+q^2}-(1-4q+q^2)}{2q(1-7q+q^2)}
$$
(this confirms the conjecture of Fahr and Ringel \cite{ref1} that
$\{c_t[0]\},\ t=0,1,2,\ \ldots\ $ is \seqnum{A110122} in the  On-Line
Encyclopedia of Integer Sequences \cite{ref2}),

that
$$
B_0=\frac{3\sqrt{1-6q+q^2}-(1+q)}{2(1-7q+q^2)},
$$
(this is the generating function for \seqnum{A132262} in the On-Line Encyclopedia
of Integer Sequences \cite{ref2}),

and with some work we find that for $r\ge1$,
\begin{eqnarray*}
&amp;&amp;B_r=B_0\left (\frac{\beta}{4q}\right )^r
=B_0\left (\frac{(1-q)^2-(1+q)\sqrt{1-6q+q^2}}{8q}\right )^r,\\
&amp;&amp;C_r=C_0\left (\frac{\beta}{4q}\right )^r
=C_0\left (\frac{(1-q)^2-(1+q)\sqrt{1-6q+q^2}}{8q}\right )^r.\\
\end{eqnarray*}
Also, we can confirm the following result of Fahr and Ringel.


\begin{theorem}
$$
b_t[0]+3\sum_{r=1}^t2^{2r-1}b_t[r]=F_{4t+2},\ \ \ 3\sum_{r=0}^t2^{2r}c_r[r]=F_{4t+4},
$$
where the $F_t$ are the Fibonacci numbers,
given by $F_0=0,\ F_1=1$ and $F_t=F_{t-1}+F_{t-2}$ for $t\ge2$.
\end{theorem}

\begin{proof}
We have
\begin{eqnarray*}
B_0+3\sum_{r\ge1}2^{2r-1}B_r
&amp;=&amp;B_0\left (1+6\left (\frac{\beta}{4q}\right )
+24\left (\frac{\beta}{4q}\right )^2+\ \cdots\ \right )\\
&amp;=&amp;B_0\left (1+\frac{6\beta}{4q(1-\frac{\beta}{q})}\right )\\
&amp;=&amp;\frac{1+q}{1-7q+q^2}\\
&amp;=&amp;\sum_{t\ge0}F_{4t+2}\,q^t\\
\end{eqnarray*}
and
\begin{eqnarray*}
3\sum_{r\ge0}2^{2r}C_r
&amp;=&amp;3C_0\left (1+4\left (\frac{\beta}{4q}\right )
+16\left (\frac{\beta}{4q}\right )^2+\ \cdots\ \right )\\
&amp;=&amp;3C_0\left (1+\frac{\beta}{q(1-\frac{\beta}{q})}\right )\\
&amp;=&amp;\frac{3}{1-7q+q^2}\\
&amp;=&amp;\sum_{t\ge0}F_{4t+4}\,q^t.\\
\end{eqnarray*}
\end{proof}


\begin{thebibliography}{2}

\bibitem{ref1} P. Fahr and C. M. Ringel,
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Fahr/ringel44.html}{A partition formula for Fibonacci numbers},
{\it J. Integer Sequences}, {\bf 11} (2008), Paper 08.1.4.

\bibitem{ref2} N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences},
available electronically at 
\href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\char'176njas/sequences/}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } Partition formula, Fibonacci numbers, recurrences.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 3 2009;
revised version received  October 2 2009.
Published in {\it Journal of Integer Sequences}, October 2 2009.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

</pre></body></html>