\documentclass[12pt]{article} \def\boxit{$\sqcap\kern-8pt\sqcup$} \def\littbox{\hfill{\boxit{}}\vskip .2cm} \font\subld=cmbx7 \newtheorem{teo}{Theorem}[section] \newtheorem{lem}[teo]{Lemma} \newtheorem{cor}[teo]{Corollary} \newtheorem{pro}[teo]{Proposition} \newtheorem{cla}[teo]{Claim} \newtheorem{rem}[teo]{Remark} \newtheorem{ques}[teo]{Question} \newtheorem{ex}[teo]{Example} \newtheorem{prob}[teo]{Problem} \newtheorem{con}[teo]{Conjecture} \newcommand{\pepe}{{\rm I}\!{\rm P}} \newcommand{\rere}{{\rm I}\!{\rm R}} \newcommand{\nene}{{\rm I}\!{\rm N}} \newcommand{\zeze}{{\rm Z}\hskip-0.30em{\rm Z}} %\lineskip = 25pt %\input epsf \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \makeatletter %% this should really go into a style file! \renewcommand\section{\@startsection {section}{1}{\z@}% % {-3.5ex \@plus -1ex \@minus -.2ex}% % here is your vskip of 30pt: {-30pt \@plus -1ex \@minus -.2ex}% {2.3ex \@plus.2ex}% {\normalfont\normalsize\bfseries}} \renewcommand\subsection{\@startsection{subsection}{2}{\z@}% {-3.25ex\@plus -1ex \@minus -.2ex}% {1.5ex \@plus .2ex}% {\normalfont\normalsize\bfseries}} % add a point after section numbers: \renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad} \makeatother \begin{document} \vspace*{-40pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A14} \vskip 40pt \begin{center} {\bf ON THE FROBENIUS NUMBER OF FIBONACCI NUMERICAL SEMIGROUPS} \vskip 20pt {\bf J.M. Mar\'{\i}n}\\ {\smallit Dept. Matem\'{a}tica Aplicada I. Universidad deSevilla. Avda. Reina Mercedes s/n. 41012 Sevilla, Spain }\\ {\tt jmarin@us.es}\\ \vskip 10pt {\bf J. L. Ram\'{\i}rez Alfons\'{\i}n}\\ {\smallit Combinatoire et Optimisation, Universit\'{e}Pierre et Marie Curie (Paris 6), France }\\ {\tt ramirez@math.jussieu.fr}\\ \vskip 10pt {\bf M.P. Revuelta}\\ {\smallit Dept. Matem\'{a}tica Aplicada I. Universidad deSevilla. Avda. Reina Mercedes s/n. 41012 Sevilla, Spain }\\ {\tt pastora@us.es}\\ \end{center} \vskip 20pt \centerline{\smallit Received: 8/29/06, Revised: 3/9/07, Accepted: 3/14/07, Published: 3/26/07} \vskip 20pt \centerline{\bf Abstract} \noindent In this note we investigate the Frobenius number of {\em Fibonacci numerical semigroups}, that is, numerical semigroups generated by a set of Fibonacci numbers. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A14\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} \vspace*{-10pt} Let $s_1,s_2,\dots ,s_n$ be positive integers such that their greatest common divisor is one. Let $S=$ be the numerical semigroup\footnote{Recall that a {\em semigroup } $(S,*)$ consists of a nonempty set $S$ and an associative binary operation $*$ on $S$. If, in addition, there exists an element, which is usually denoted by $0$, in $S$ such that $a+0=0+a=a$ for all $a\in S$, we say that $(S,*)$ is a {\em monoid}. A {\em numerical semigroup} is a submonoid of $\nene$ such that the greatest common divisor of its elements is equal to one.} generated by $s_1,\dots ,s_n$. A {\em Fibonacci numerical semigroup} is a numerical semigroup generated by a set of Fibonacci numbers $F_{i_1},\dots ,F_{i_r}$, for some integers $3\le {i_1}<\cdots <{i_r}$ where $\gcd(F_{i_1},\dots ,F_{i_r})=1$. The so-called {\em Frobenius number}, denoted by $g(s_1,\dots ,s_n)$, is defined as the largest integer not belonging to $S$, that is, the largest integer that is not representable as a nonnegative integer combination of $s_1,\dots ,s_n$. It is well known that $g(s_1,s_2)=s_1s_2-s_1-s_2$. In general, finding $g(S)$ is a difficult problem and so formulas and upper bounds for particular sequences are of interest. For instance, it is known [3] $g(S)$ when $S$ is an arithmetical sequence \begin{equation}\label{arit} g(a,a+d,\dots ,a+kd)=a\left(\left\lfloor{{a-2}\over {k}}\right\rfloor\right)+d(a-1) \end{equation} We refer the reader to [2] where a complete account on the Frobenius problem can be found. In this note, we investigate the value of $g(F_i,F_j,F_l)$ for some triples $3\le i$ and $$ generate the same set of elements and thus they have the same Frobenius number. Let us consider then $g(F_i,F_{i+2},F_{l})$ with $l\ge i+3$. We notice that the case when $l=i+3$ is a consequence of equation (\ref{arit}) since the triple $\{F_i,F_{i+2},F_{i+3}\}=\{F_i,F_i+F_{i+1},F_i+2F_{i+1}\}$ form an arithmetical sequence. However, it can be checked that $\{F_i,F_{i+2},F_{i+k}\}$ do not form an arithmetical sequence when $k\ge 3$ and the calculation of $g(F_i,F_{i+2},F_{i+k})$ is more complicated. We state our main result. \noindent {\bf Theorem 1.} {\em Let $i,k\ge 3$ be integers and let $r=\lfloor{{F_i-1}\over {F_k}}\rfloor$. Then, $$g(F_{i},F_{i+2},F_{i+k})=\left\{\begin{array}{ll} (F_i-1)F_{i+2}-F_i(rF_{k-2}+1)& \hbox{if $r=0$ or $r\ge 1$ and}\\ & \hbox{$F_{k-2}F_i<(F_i-rF_k)F_{i+2}$,}\\ \\ (rF_k-1)F_{i+2}-F_i((r-1)F_{k-2}+1)& \hbox{otherwise.}\\ \end{array}\right.$$} Let $N(a_1,\dots ,a_n)$ be the number of positive integers with no representation by a nonnegative integer combination of $a_1,\dots ,a_n$. Theorem 1 yields to the following result. \noindent {\bf Corollary 2.} {\em Let $i,k\ge 3$ be integers and let $r=\lfloor{{F_i-1}\over {F_k}}\rfloor$.Then, $$N(F_{i},F_{i+2},F_{i+k})={{(F_i-1)(F_{i+2}-1)-rF_{k-2}(2F_i-F_k(1+r))} \over {2}}\cdot$$} \vspace*{-10pt} \section*{\normalsize 2. Fibonacci semigroups} \vspace*{-10pt} In order to prove Theorem 1 we need the following result due to Brauer and Shockley [1]. \noindent {\bf Lemma 3.} {\em Let $1t_{x,y}$.} \noindent {\it Proof.} We first notice that the set $S$ can be written as follows $$\begin{array}{ccccccccccc} \{s_0,& \dots &,s_{F_k-1},&s_{F_k},&\dots &,s_{2F_k-1},&\dots &,s_{rF_k},&\dots &,s_{rF_k+l}=s_{F_i-1},\\ s_{F_i},& \dots &,s_{F_i+F_k-1},&s_{F_i+F_k},&\dots &,s_{F_i+2F_k-1},&\dots &,s_{F_i+rF_k},&\dots &,s_{2F_i-1},\\ s_{2F_i},& \dots &,s_{2F_i+F_k-1},&s_{2F_i+F_k},&\dots &,s_{2F_i+2F_k-1},&\dots &,s_{2F_i+rF_k},&\dots &,s_{3F_i-1},\dots\}\\ \end{array}$$ where $S'=\{s_0,\dots ,s_{F_k-1},s_{F_k},\dots ,s_{2F_k-1},\dots ,s_{rF_k},\dots ,s_{F_i-1}\}$. We have two cases. \vskip .3cm \noindent {\tt Case A.} Suppose that $t_{u,v}\in S\setminus S'$. Then $t_{u,v}$ is of the form $s_{pF_i+g}$ for some integers $p\ge 1$ and $0\le g\le F_i-1$. It is clear that, $$s_g=gF_{i+2}-\left\lfloor{g\over {F_k}}\right\rfloor F_iF_{k-2}\equiv (pF_i+g)F_{i+2}-\left\lfloor{{pF_i+g}\over {F_k}}\right\rfloor F_iF_{k-2}=g_{pF_i+g}(\bmod \, F_i.)$$ We will show that $s_{pF_i+g}>s_g$. To this end, it suffices to prove that $s_{F_i+g}>s_g$ (since $s_{pF_i+g}\ge s_{F_i+g}$). Recall that $r=\lfloor{{F_i-1}\over {F_k}}\rfloor$ and that $F_i-1=rF_k+l$ for some integer $0\le l\le F_k-1$. We have two subcases. {\tt Subcase a.} If $r=0$ then $F_k\ge F_i$. If $F_k=F_i$ then $s_{F_i+g}=t_{g,1}$ and, by Remark 4(c), $t_{g,0}F_i$ then $s_{F_i+g}=t_{q,0}$ for some integer $q\ge F_i$ and, by Remark 4(c), $t_{g,0}s_g$ holds if and only if $$(F_i+g)F_{i+2}-\left\lfloor{{F_i+g}\over {F_k}}\right\rfloor F_iF_{k-2}>gF_{i+2}-\left\lfloor{g\over {F_k}}\right\rfloor F_iF_{k-2}$$ or equivalently if and only if $$F_{i+2}>F_{k-2}\left( \left\lfloor{{F_i+g}\over {F_k}}\right\rfloor - \left\lfloor{g\over {F_k}}\right\rfloor\right)\cdot$$ Let $g=mF_k+n$ with $0\le n\le F_k-1$. Since $F_i-1=rF_k+l$ with $0\le l\le F_k-1$, then $$\left\lfloor{{F_i-1+g+1}\over {F_k}}\right\rfloor=\left\lfloor{{rF_k+l+mF_k+n+1}\over {F_k}}\right\rfloor\le r+m+1$$ and thus $$\left\lfloor{{F_i+g}\over {F_k}}\right\rfloor - \left\lfloor{g\over {F_k}}\right\rfloor\le r+m+1-m=r+1.$$ So, it is enough to show that $F_{i+2}>(r+1)F_{k-2}$ or equivalently to show that $F_i+F_{i+1}>(r+1)F_{k-2}$. Since $F_i=rF_k+l+1$ then the latter inequality holds if and only if $rF_k+l+1+F_{i+1}>rF_{k-2}+F_{k-2}$, that is, if and only if $$r(F_k-F_{k-2})+l+1+F_{i+1}=r(F_{k-1})+l+1+F_{i+1}>F_{k-2}$$ which is true since $r\ge 1$. \noindent {\tt Case B.} Suppose that $t_{u,v}\not\in S$. Then we have that $0\le x\le F_k-1-yF_{k-2}F_i$. So, combining the last two inequalities we have that $$t_{u,v}=(u+vF_k)F_{i+2}-vF_{k-2}F_i> (x+yF_k)F_{i+2}-yF_{k-2}F_i=t_{x,y}.$$ \littbox We may now prove Theorem 1. \noindent {\it Proof of Theorem 1.} Let $T^*=\{t^*_0,\dots ,t^*_{F_i-1}\}$ where $t^*_l$ is the smallest positive integer congruent to $l$ modulo $F_i$, that is representable as a nonnegative integer combination of $F_{i+2}$ and $F_{i+k}$. Let $s_{x}=xF_{i+2}-\lfloor {x\over {F_k}} \rfloor F_{k-2}F_{i}$ for $x=0,1,\dots$. By Lemma 5, we have that for each $x=0,\dots ,F_i-1$, $s_x$ is the smallest positive integer congruent to $l$ modulo $F_i$, for some integer $0\le l\le F_i-1$, that is representable as a nonnegative integer combination of $F_{i+2}$ and $F_{i+k}$, that is, $S'=T^*$ where $S'=\{s_0,\dots ,s_{F_k-1},s_{F_k},\dots ,s_{2F_k-1},\dots ,s_{rF_k},\dots ,s_{F_i-1}\}$. Now, by Remark 4(c), if $r\ge 1$ then $$\hbox{ $\ \ t_{F_k-1,i}=\max\limits_{0\le x\le F_k-1}\{t_{x,i} | t_{x,i}\in S'\}$ for each $i=0,\dots ,r-1$,}$$ $$t_{F_k-1,r-1}=\max\limits_{0\le i\le r-1}\{t_{F_k-1,i} | t_{F_k-1,i}\in S'\},$$ and $$t_{l,r}=\max\limits_{0\le x\le l}\{t_{x,r} | t_{x,r}\in S'\}.$$ Thus, $$\max\{s | s\in S'\}=\left\{\begin{array}{ll} t_{l,r}& \hbox{if $r=0$,}\\ \max\{t_{F_k-1,r-1},t_{l,r}\}&\hbox{otherwise.} \end{array}\right.$$ The result follows since $t_{l,r}>t_{F_k-1,r-1}$ if and only if $$(rF_k+l)F_{i+2}-rF_{k-2}F_i=(F_i-1)F_{i+2}-rF_{k-2}F_i>(rF_k-1)F_{i+2}-(r-1)F_{k-2}F_i$$ or equivalently, if and only if $F_{i+2}(F_i-rF_k)>F_{k-2}F_i$. \littbox We will use the following result due to Selmer [4] to show Corollary 2. \noindent {\bf Lemma 6.} {\em Let $1