% A Complete Categorization of When Generalized Tribonacci Sequences Can Be
% Avoided by Additive Partitions
%
% Author: Mike Develin
% A LaTeX2e file for a 7 page document
\documentclass[12pt]{article}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{0.0in}
\hoffset= - 0.75 in
\usepackage{amsfonts, amsmath, amssymb, amsthm}
\usepackage{latexsym}
\newtheorem*{defn}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem{claim}{Claim}
\newtheorem{conj}{Conjecture}
\newtheorem{obs}{Observation}
\newtheorem{qn}{Question}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}
\newtheorem{fact}{Fact}
\newcommand{\khalf}{\frac{k}{2}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Zn}{\ZZ/n\ZZ}
\newcommand{\GU}{\mathbf{G_U}}
\newcommand{\Gob}{\mathbf{G_{\{0,b\}}}}
\newcommand{\bin}[2]{
\left(
\begin{array}{@{}c@{}}
#1 \\ #2
\end{array}
\right) }
\DeclareMathOperator{\id}{id}
\begin{document}
\title{A Complete
Categorization of
When Generalized Tribonacci
Sequences Can Be Avoided by Additive Partitions}
\author{Mike Develin\\
Department of Mathematics\\
University of California-Berkeley\\
Berkeley, CA 94720\\
\small{\texttt{develin@math.berkeley.edu}}}
\date{Submitted: June 23, 2000; Accepted: October 9, 2000}
\maketitle
\begin{center}
\noindent\small{\textbf{Keywords:} Avoidable set, additive
partition,
generalized
Tribonacci sequence\\
\textbf{MR Subject Code:} Primary: 05A17, Secondary: 11B37}
\end{center}
\begin{abstract} A set or sequence $U$ in the natural numbers is defined to be
avoidable if
$\NN$ can be partitioned into two sets $A$ and $B$ such that no element of
$U$ is the sum of two distinct elements of $A$ or of two distinct elements
of $B$. In 1980, Hoggatt \cite{Hoggatt} studied the Tribonacci sequence
$T=\{t_n\}$ where $t_1=1$, $t_2=1$, $t_3=2$, and
$t_n=t_{n-1}+t_{n-2}+t_{n-3}$ for $n\ge 4$, and showed that it was
avoidable. Dumitriu \cite{Ioana} continued this research, investigating
Tribonacci sequences with arbitrary initial terms, and achieving partial
results. In this paper we give a complete answer to the question of
when a generalized Tribonacci sequence is avoidable.
\end{abstract}
\maketitle
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000), \#R53\hfill}
\thispagestyle{empty}
\section{Introduction}
A subset $U$ of the natural numbers is defined to be \textbf{avoidable} if there
exists a partition of $\NN$ into two disjoint sets $A$ and $B$
such that no
element of $U$
is the sum of two distinct elements of $A$ or of $B$; the pair $\{A,B\}$
is sometimes referred to as an \textbf{additive partition}.
Avoidable sets in $\NN$ have been studied for many years, yet very few
families of
avoidable sets are known. The concept of avoidable sets was pioneered by
Alladi, Erd\H{o}s, and Hoggatt \cite{Erdos} in 1978. They proved that the
Fibonacci sequence was avoidable, and achieved results for various
special cases of generalized Fibonacci sequences (i.e., sequences
$\{f_n\}$ with $f_1, f_2\in \NN$ and $f_k=f_{k-1}+f_{k-2}$ for $k\ge 3$).
In 1981, Evans \cite{Evans} solved yet more cases of the
generalized Fibonacci sequence; lastly, in 1993, Shan and Zhu
\cite{Shan} solved a large family of two-term recursive sequences,
including generalized Fibonacci sequences. Chow and Long \cite{Chow} also
showed
that a family of sequences arising from continued fractions is avoidable.
Hoggatt \cite{Hoggatt}
showed that the Tribonacci sequence $T=\{t_n\}$ was avoidable, where $t_1=1,
t_2=1, t_3=2$ and we have
\begin{equation}\label{recur}
t_{n}=t_{n-1}+t_{n-2}+t_{n-3}
\end{equation}
for $n\ge 4$. This result suggested that a subfamily of
generalized Tribonacci sequences (sequences satisfying
recursion~(\ref{recur}) with arbitrary initial terms) might be avoidable; in
\cite{Ioana}, Dumitriu
studied generalized Tribonacci sequences and was able to obtain results
when the positive integers $a,b,$ and $c$, the initial terms of the sequence,
satisfy $a\le b\le
c$ with $a+b\ge c$. In this paper we build off Dumitriu's results to
determine when an arbitrary generalized Tribonacci sequence is
avoidable; all Tribonacci sequences in this
paper are assumed to have positive initial terms.
\section{Previous Results}
Dumitriu~\cite{Ioana} achieved two results which form the building blocks
of our proofs. First of all, there is the following important lemma, which
allows us to construct additive partitions of all of $\NN$ from additive
partitions of finite sets.
\begin{lem}[Dumitriu~\cite{Ioana}]\label{extend}
Given a generalized Tribonacci sequence $T=\{t_n\}$ with initial terms
$a\le b\le c$, if there exists an additive partition $\{A,B\}$ of
$\{1, \ldots, c-1\}$ avoiding
$T$, then this partition can be extended to an additive partition of $\NN$
avoiding $T$.
\end{lem}
We extend this lemma to Tribonacci sequences with arbitrarily
ordered initial terms, so that it reads as follows.
\begin{lem}\label{genextend}
Given a generalized Tribonacci sequence $T=\{t_n\}$ with initial terms
$a,b,$ and $c$, if there exists an additive partition $\{A,B\}$ of
$\{1,\ldots, \max(a,b,c)-1\}$ avoiding $T$, then this partition can be
extended to an additive partition of $\NN$ avoiding $T$.
\end{lem}
\begin{proof} Examining Dumitriu's proof, we find that only the assumption
that $c\ge a,b$ is used. Therefore, if we obtain an additive partition of
$\{1,\ldots, a+b+c-1\}$ avoiding $T$, we can then use Lemma~\ref{extend}
to extend this partition to a partition of $\NN$ avoiding the Tribonacci
sequence generated by $b,c,$ and $a+b+c$. As this extended partition will
obviously avoid $a$ (because the original partition did, and $a2d$. In this case, we define:
\begin{eqnarray*}
S_1 &=& \{d,d+1,\ldots,\biggl\lfloor\frac{a+b+c}{2}\biggr\rfloor\} \\
S_2 &=& \{\biggl\lfloor \frac{a+b+c}{2}\biggr\rfloor+1,\ldots,a+b+c-d\} \\
E &=& \{x\mid a+b+c-db+c\ge a+b+c-d$
as $d\ge a$. However, this then implies that $a+b+c-x$ and $a+b+c-y$ are
both in $B$ (respectively $A$), which is impossible
because their sum is $2a+2b+2c-(x+y)=a$ and $\{A,B\}$ avoids
$a$. Therefore $\{C,D\}$ avoids $T$.
\end{proof}
We also note the following easy lemma.
\begin{lem}\label{a2b2c}
If $a>2b+2c$, any partition of the set $A=\{1,\ldots,a-1\}$
avoiding $\{a,b,c,a+b+c\}$ also avoids $a+2b+2c$.
\end{lem}
\begin{proof}
Let $\{E,F\}$ be such a partition of $A$. Without loss of generality,
suppose for purposes of contradiction that
we have $x+y=a+2b+2c$ with $x,y$ distinct elements of $E$. As $\{E,F\}$
avoids $a+b+c$, $a+b+c-x$ and $a+b+c-y$ (which are both in $A$ as
$2b+2c2b+2c$, which is covered by
Lemma~\ref{a2b2c}. We make the following definition.
\begin{defn}
The symmetric Boolean variable $P(a,b,c)$ is defined to be equal to 1 if
there exists a partition of $\{1,\ldots,\max(a,b,c)-1\}$ avoiding
$\{a,b,c,a+b+c\}$, and 0 otherwise.
\end{defn}
Now, Lemma~\ref{genextend} allows us to conclude the following important
equivalence theorem.
\begin{thm}\label{equivalence}
The Tribonacci sequence with initial terms $t_1=a$, $t_2=b$, and $t_3=c$
is avoidable if and only if $P(a,b,c)=1$.
\end{thm}
The importance of this theorem is that it reduces the problem of determining
when a Tribonacci sequence generated by three initial terms is avoidable
to a symmetric one. Because $P(a,b,c)$ is a symmetric function, it
suffices to determine
its values for $a\le b\le c$. We note that if $a$, $b$ and $c$ are all
odd, then we can take as a partition of $\NN$ the sets $A=\{2k\}$,
$B=\{2k+1\}$, so in this case $P(a,b,c)=1$.
Dumitriu also achieved the following result, which we will use as the base
case of our argument.
\begin{thm}[Dumitriu~\cite{Ioana}]\label{abgc}
Say $t_1=a, t_2=b, t_3=c$ with $a,b,c$ not all odd. If $a< b< c< a+b$,
then $P(a,b,c)=1$ if and only if either:
\begin{enumerate}
\item $a$ and $b$ are even, $c$ is odd, and $c\ge a+\frac{b}{2}$, or
\item $b$ and $c$ are even, $a$ is odd, and $a\le \frac{c}{2}$, or
\item $a$ and $c$ are even, $b$ is odd, and either
\begin{itemize}
\item $2b=a+c$, or
\item $c\ge b+\frac{a}{2}$ and $a\le \frac{c}{2}$.
\end{itemize}
\end{enumerate}
\end{thm}
We also need the following supplementary result to cover the special case
where we have equality instead of one of Dumitriu's inequalities.
\begin{lem}\label{weirdequality}
Say $t_1=a, t_2=b, t_3=c$ with $a\le b\le c\le a+b$. If either $a=b$,
$b=c$, or $a+b=c$, then $P(a,b,c)=1$.
\end{lem}
\begin{proof}
We only need to show that there exists an additive partition of
$\{1,\ldots,c-1\}$ avoiding $\{a,b,c\}$, because $a+b+c$ is too large to
be written as the sum of two elements smaller than $c$. If $a=b$ or
$b=c$, then we
need only to find a partition of $\{1,\ldots,c-1\}$ avoiding $\{a,c\}$;
if $a+b=c$, we need to find a partition of $\{1,\ldots,a+b-1\}$ avoiding
$\{a,b,a+b\}$. However, the existence of both partitions is proven by
Shan and Zhu in~\cite{Shan}.
\end{proof}
Using these results as our base case, we will recursively determine whether
a given generalized Tribonacci sequence is avoidable.
\section{Generalized Tribonacci Sequences}
We have already established the value of $P(a,b,c)$ in the case where $a\le
b\le c\le a+b$. In this section, we prove the following complementary
theorem.
\begin{thm}\label{ablc}
If $a\le b\le c$ and $a+b0$ and $w+x=c-a-b$, $c>2b$. Consequently,
we have $x>a,b$, so we need not worry about $x$ summing to $a$ or $b$ or
\textit{a priori} $c$. Therefore, if necessary, we can simply modify our
partition by placing $x$ in whichever of $X\cap A$ and $Y\cap A$
the element $w=c-a-b-x$
is not in.
Conversely, given a partition $\{X,Y\}$ of $A$ avoiding $c-a-b, a, b$, and
$c$, we
can extend this partition to a partition $\{X^{\prime},Y^{\prime}\}$ of
$A\cup B$ by placing each $x\in
B$ in the set opposite to $c-x$ (which is in $A$.) The resulting
partition still avoids $c$ by construction, and still avoids $a$ and $b$
as the elements being added are all at least $(a+b+c+1)/2>a+b$. So we
need only
check that the partition of $A\cup B$ avoids $a+b+c$; however, if without
loss of generality we have
distinct $w,
x\in X^{\prime}$ with $w+x=a+b+c$, then unless $w$ or $x$ is equal to
$c/2$, $c-x$ and $c-w$ are distinct positive
integers in $Y^{\prime}$ whose sum is $c-a-b$. Because $c-a-b\le
(a+b+c)/2$ as $c\le
3(a+b)$, they are therefore both in $A$ and thus in $Y$, contradicting the
fact that $\{X,Y\}$ is a partition of $A$ avoiding $c-a-b$. As before, we
must consider the special case where $x=c/2$. However, as $w2b$, so as before we can modify our partition
if necessary by placing $x$ in the opposite set from $a+b+c-x$.
\end{proof}
Now, to complete the proof of Case 1 of the theorem, we need only prove the
following claim.
\begin{claim}
Let $d=max(c-a-b,b)$. Then a partition of the set $A$ avoiding
$\{c-a-b,a,b,c\}$ exists if and only if
a partition of $\{1,\ldots,d-1\}$ avoiding $\{c-a-b,a,b,c\}$
exists.
\end{claim}
\begin{proof}
Noting that $d-1<\lfloor\frac{a+b+c}{2}\rfloor$, one direction is
trivial: if we
have a partition of
$A$, we can
restrict it to $\{1,\ldots, d-1\}$ and it will still avoid
$\{c-a-b,a,b,c\}$. For the other direction, we can simply take the
partition on $\{1,\ldots,d-1\}$ and extend it by placing $x$
in the opposite set from $c-x$. The partition then obviously avoids $c$;
also, as no number larger than $d-1$
can be added to a natural number to get $a,b,$ or $c-a-b$, this partition
also avoids $a,b,$ and $c-a-b$.
\end{proof}
\textit{Case 2}. $c>3(a+b)$. In this case, we let
$A=\{1,\ldots,c-a-b-1\}$ and $B=\{c-a-b,\ldots,c-1\}$. Again, we claim
that a partition of $A$ avoiding $\{c-a-b, a, b, c\}$ exists if and only
if
a partition of $A\cup B$ avoiding $\{a,b,c,a+b+c\}$ exists.
If we have a partition of $A\cup B$
avoiding $\{a,b,c,a+b+c\}$, we can restrict it to a partition of $A$
avoiding $\{c-a-b,a,b,c\}$; if $x$ and $y$ are in one set of the partition
summing to $c-a-b$, then $c-x$ and $c-y$ must be in the other set of the
partition and $(c-x)+(c-y)=2c-(x+y)=a+b+c$, an impossibility. In the other
direction, we extend the partition $\{X,Y\}$ of $A$ to a partition
$\{X^{\prime},Y^{\prime}\}$ of $A\cup B$ by placing $x\in B$ in the opposite
set from $c-x$. We need only check that the resulting partition avoids
$a+b+c$. Suppose we have distinct $w,x\in X^{\prime}$ (respectively
$Y^\prime$)with $w+x=a+b+c$. Then unless $x$ or $w$ is equal to $c/2$, $c-x$
and $c-w$ are distinct
elements of $Y^{\prime}$ (respectively $X^\prime$) summing to $c-a-b$, and
hence are in $A$; therefore, they are in $Y$ (respectively $X$),
contradicting the fact that $\{X,Y\}$ avoids $c-a-b$. Furthermore, if
$x=c/2$, as in Case 1 we can
modify our partition if necessary by placing $x$ in the opposite set of the
partition from $c+a+b-x$, as again $x>a,b$.
\end{proof}
We can now completely solve the question of when a Tribonacci sequence is
avoidable via a method of descent. Since $P(a,b,c)$ is a symmetric function,
it suffices to establish the answer for $a\le b\le c$. For $a+b\ge c$,
Theorem~\ref{abgc} and Lemma~\ref{weirdequality} establish when
$P(a,b,c)=1$. Meanwhile, if we have $a+b2t_{n-1}-1$
for all $n$ is certainly avoidable by direct construction of the form
outlined in this paper. Therefore, one would expect that the main roadblock
to constructing additive partitions avoiding such a recursive sequence would
lie in the initial terms. Indeed, Theorem~\ref{equivalence} is true for
deeper recursions with an almost identical proof, so, as in the case of
Tribonacci sequences, determining avoidability boils down to determining
whether an appropriate additive partition of a finite set exists.
\section*{Acknowledgements}
This work was done under the supervision of Joseph Gallian at the University of
Minnesota, Duluth, with financial support from the National Science Foundation
(Grant DMS-9531373-001) and the National Security Agency (Grant
MDA-904-98-1-0523). The author wishes to thank Samit Dasgupta for many helpful
suggestions on the preliminary version of this manuscript, and also wishes
to thank the referee for many helpful comments regarding its organization.
\begin{thebibliography}{99} \bibitem{Erdos}
K. Alladi, P. Erd\H{o}s, V.E. Hoggatt, Jr., ``On additive partitions of
integers,'' \textit{Discrete Math.} \textbf{23} (1978), 201-211
\bibitem{Chow}
T.Y. Chow and C.D. Long, ``Additive partitions and continued fractions,''
\textit{Ramanujan J.} \textbf{3} (1999), 55-72
\bibitem{Ioana}
I. Dumitriu, ``On generalized Tribonacci sequences and additive
partitions,'' \textit{Discrete Math.} \textbf{219} (2000), 65-83.
\bibitem{Evans}
R.J. Evans, ``On additive partitions of sets of positive integers,''
\textit{Discrete Math.} \textbf{36} (1981), 239-245
\bibitem{Hoggatt}
V.E. Hoggatt, Jr., ``Additive partitions of the positive integers,''
\textit{Fibonacci Quart.} \textbf{18} (1980), 220-226
\bibitem{Shan}
Z. Shan and P.-T. Zhu, ``On (a,b,k)-partitions of positive integers,''
\textit{Southeast Asian Bull. Math} \textbf{17} (1993), 51-58
\end{thebibliography}
\end{document}