\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]&&&&&&&&&\ \ c_t[r]\\ &&r&&&&&&&&&\ \ r\\ &&0&1&2&3&4&\cdots&&&&0&1&2&3&4&\cdots\\ t&0&1&&&&&&&t&0&1\\ &1&2&1&&&&&&&1&3&1\\ &2&7&4&1&&&&&&2&12&5&1\\ &3&29&18&6&1&&&&&3&53&25&7&1\\ &4&130&85&33&8&1&&&&4&247&126&42&9&1\\ \end{array} \] and the recurrences \begin{eqnarray*} &&b_{t+1}[r]=c_t[r-1]+2c_t[r]-b_t[r],\\ &&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*} &&B_0=1+2q+7q^2+29q^3+130q^4+\ \cdots\ ,\\ &&B_1=q+4q^2+18q^3+85q^4+\ \cdots\ ,\\ &&B_2=q^2+6q^3+33q^4+\ \cdots\ ,\\ &&C_0=1+3q+12q^2+53q^3+247q^4+\ \cdots\,\\ &&C_1=q+5q^2+25q^3+126q^4+\ \cdots\ ,\\ &&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*} &&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)},\\ &&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},\\ &&B_2=\frac{(1-3q-2q^2-3q^3+q^4)C_o-(1+q^2)}{8q(1+q)},\\ &&C_2=\frac{(1-5q+4q^2-5q^3+q^4)C_0-(1-2q+q^2)}{16q^2},\\ &&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)},\\ &&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*} &&B_r=\displaystyle\frac{P_rC_0-Q_r}{2^{2r-1}q^{r-1}(1+q)},\\ &&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*} &&P_1=1-q+q^2,\\ &&P_2=1-3q-2q^2-3q^3+q^4,\\ &&P_3=1-5q+q^2+2q^3+q^4-5q^5+q^6,\\ &&Q_1=1,\\ &&Q_2=1+q^2,\\ &&Q_3=1-2q-2q^2-2q^3+q^4,\\ &&S_1=1-3q+q^2,\\ &&S_2=1-5q+4q^2-5q^3+q^4,\\ &&S_3=1-7q+11q^2-6q^3+11q^4-7q^5+q^6,\\ &&T_1=1,\\ &&T_2=1-2q+q^2,\\ &&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*} &&\alpha=\frac{(1-q)^2+(1+q)\sqrt{1-6q+q^2}}{2} =1-2q-3q^2-8q^3-28q^4-112q^5-\ \cdots\ ,\\ &&\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*} &&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,\\ &&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,\\ &&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,\\ &&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*} &&2^{2r-1}q^{r-1}(1+q)B_r=P_rC_0-Q_r\\ &&=\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\\ &&+\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*} &&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\\ &&+\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*} &&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,\\ &&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 &=&B_0\left (1+6\left (\frac{\beta}{4q}\right ) +24\left (\frac{\beta}{4q}\right )^2+\ \cdots\ \right )\\ &=&B_0\left (1+\frac{6\beta}{4q(1-\frac{\beta}{q})}\right )\\ &=&\frac{1+q}{1-7q+q^2}\\ &=&\sum_{t\ge0}F_{4t+2}\,q^t\\ \end{eqnarray*} and \begin{eqnarray*} 3\sum_{r\ge0}2^{2r}C_r &=&3C_0\left (1+4\left (\frac{\beta}{4q}\right ) +16\left (\frac{\beta}{4q}\right )^2+\ \cdots\ \right )\\ &=&3C_0\left (1+\frac{\beta}{q(1-\frac{\beta}{q})}\right )\\ &=&\frac{3}{1-7q+q^2}\\ &=&\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}