A Complete Categorization of When Generalized Tribonacci Sequences Can Be Avoided by Additive

Partitions

Mike Develin Department of Mathematics University of California-Berkeley Berkeley, CA 94720

                     develin@math.berkeley.edu

Submitted: June 23, 2000; Accepted: October 9, 2000

Keywords: Avoidable set, additive partition, generalized Tribonacci sequence MR Subject Code: Primary: 05A17, Secondary: 11B37

Abstract

A set or sequence U in the natural numbers is defined to be avoidable if ℕ 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 [5] 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 ≥ 4, and showed that it was avoidable. Dumitriu [3] 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.

1 Introduction

A subset U of the natural numbers is defined to be avoidable if there exists a partition of ℕ 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 additive partition. Avoidable sets in ℕ 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ős, and Hoggatt [1] 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} ∈ ℕ and f_{k} = f_{k−1} +f_{k−2} for k ≥ 3). In 1981, Evans [4] solved yet more cases of the generalized Fibonacci sequence; lastly, in 1993, Shan and Zhu [6] solved a large family of two-term recursive sequences, including generalized Fibonacci sequences. Chow and Long [2] also showed that a family of sequences arising from continued fractions is avoidable.

Hoggatt [5] showed that the Tribonacci sequence T = {t_{n}} was avoidable, where t_{1} = 1, t_{2} = 1, t_{3} = 2 and we have

t_{n} = t_{n−1} + t_{n−2} + t_{n−3}  (1)

for n ≥ 4. This result suggested that a subfamily of generalized Tribonacci sequences (sequences satisfying recursion (1) with arbitrary initial terms) might be avoidable; in [3], 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 ≤ b ≤ c with a + b ≥ 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.

2 Previous Results

Dumitriu [3] 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 ℕ from additive partitions of finite sets.

Lemma 1 (Dumitriu [3]). Given a generalized Tribonacci sequence T = {t_{n}} with initial terms a ≤ b ≤ c, if there exists an additive partition {A, B} of {1, …, c − 1} avoiding T, then this partition can be extended to an additive partition of ℕ avoiding T.

We extend this lemma to Tribonacci sequences with arbitrarily ordered initial terms, so that it reads as follows.

Lemma 2. 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, …, max(a, b, c) − 1} avoiding T, then this partition can be extended to an additive partition of ℕ avoiding T.

Proof. Examining Dumitriu’s proof, we find that only the assumption that c ≥ a, b is used. Therefore, if we obtain an additive partition of {1, …, a + b + c − 1} avoiding T, we can then use Lemma 1 to extend this partition to a partition of ℕ 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 a < a + b + c), we will in fact have generated a partition of ℕ avoiding T.

Let d = max(a, b, c). We proceed as follows:

Case 1. a + b + c ≤ 2d. In this case, we extend the partition {A, B} of {1, …, d − 1} avoiding T to one of {1, …, a + b + c − 1} by, for d ≤ x < a + b + c, placing x in the opposite set from a + b + c − x (which is in A or B unless a + b + c = 2d and x = d, in which case we can place x in either set.) Clearly, the resulting partition {C, D} will avoid a, b, c, and a + b + c; also, t_{6} = 2a + 3b + 4c is too large to be expressed as the sum of two terms in {1, …, a + b + c − 1}. Therefore, we need only check that {C, D} avoids t_{5} = a + 2b + 2c. Suppose not; then without loss of generality, we have y, z ∈ C with y + z = a + 2b + 2c. Then unless y or z is equal to (a + b + c)/2, a + b + c − y and a + b + c − z are both in D, yet their sum is equal to 2a + 2b + 2c − (y + z) = a, contradicting the fact that D avoids a. If y = (a + b + c)/2, a + b + c is even and z = (a + 3b + 3c)/2. However, since in this case we must have a ≤ b + c, we conclude that z ≥ a + b + c, a contradiction. Therefore, {C, D} avoids T as desired.

Case 2. a + b + c > 2d. In this case, we define:

S_{1} = \{d, d + 1, …, ⌊\frac{a + b + c}{2}⌋\}
S_{2} = \{⌊\frac{a + b + c}{2}⌋ + 1, …, a + b + c − d\}
E = {x | a + b + c − d < x < a + b + c, a + b + c − x ∈ B}
F = {x | a + b + c − d < x < a + b + c, a + b + c − x ∈ A}

We then let C = A ∪ S_{1} ∪ E and D = B ∪ S_{2} ∪ F. Clearly as before {C, D} avoids a, b, c, and a + b + c, and t_{6} = 2a + 3b + 4c is too large to be expressed as the sum of two elements of C or D. Suppose we had two elements x, y ∈ C (respectively D) with x + y = t_{5} = a + 2b + 2c. Then x and y must both be in E (respectively F) , for as x < a + b + c, we have y > b + c ≥ a + b + c − d as d ≥ 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.

We also note the following easy lemma.

Lemma 3. If a > 2b+2c, any partition of the set A = {1, …, a−1} avoiding {a, b, c, a+ b + c} also avoids a + 2b + 2c.

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 + 2c < x, y < a) are distinct elements of F. However, their sum is then equal to 2a + 2b + 2c − (x + y) = a, contrary to the assumption that {E, F } avoids a.

Therefore, any partition of A = {1, …, max(a, b, c) − 1} avoiding {a, b, c, a + b + c} in fact avoids all of T, as t_{n} is too large to be expressed as the sum of two elements of A for n ≥ 6, and t_{5} = a + 2b + 2c is too large except in the case a > 2b + 2c, which is covered by Lemma 3. We make the following definition.

Definition. The symmetric Boolean variable P (a, b, c) is defined to be equal to 1 if there exists a partition of {1, …, max(a, b, c)−1} avoiding {a, b, c, a+b+c}, and 0 otherwise.

Now, Lemma 2 allows us to conclude the following important equivalence theorem.

Theorem 1. 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.

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 ≤ b ≤ c. We note that if a, b and c are all odd, then we can take as a partition of ℕ 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.

Theorem 2 (Dumitriu [3]). 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:

1. a and b are even, c is odd, and c ≥ a + \frac{b}{2}, or

2. b and c are even, a is odd, and a ≤ \frac{c}{2}, or

3. a and c are even, b is odd, and either

• 2b = a + c, or

• c ≥ b + \frac{a}{2} and a ≤ \frac{c}{2}.

We also need the following supplementary result to cover the special case where we have equality instead of one of Dumitriu’s inequalities.

Lemma 4. Say t_{1} = a, t_{2} = b, t_{3} = c with a ≤ b ≤ c ≤ a + b. If either a = b, b = c, or a + b = c, then P (a, b, c) = 1.

Proof. We only need to show that there exists an additive partition of {1, …, 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, …, c − 1} avoiding {a, c}; if a + b = c, we need to find a partition of {1, …, a + b − 1} avoiding {a, b, a + b}. However, the existence of both partitions is proven by Shan and Zhu in [6].

Using these results as our base case, we will recursively determine whether a given generalized Tribonacci sequence is avoidable.

3 Generalized Tribonacci Sequences

We have already established the value of P (a, b, c) in the case where a ≤ b ≤ c ≤ a + b. In this section, we prove the following complementary theorem.

Theorem 3. If a ≤ b ≤ c and a + b < c, then a partition of {1, …, c − 1} avoiding a, b, c and a + b + c exists if and only if a partition of {1, …, max(c − a − b, b) − 1} avoiding c − a − b, a, b and c exists.

Proof. We have two cases to consider:

Case 1. c ≤ 3(a + b). In this case, let A = \{1, …, ⌊\frac{a+b+c}{2}⌋\}, and B = \{⌊\frac{a+b+c}{2}⌋ + 1, …, c − 1}.

Claim 1. A partition of A∪B avoiding {a, b, c, a+b+c} exists if and only if a partition of A avoiding {c − a − b, a, b, c} exists.

Proof. Given such a partition {X, Y } of A ∪ B, we create a partition of A by restricting the partition of A ∪ B. The only thing remaining to check is that no two elements in the same set of the partition {X ∩ A, Y ∩ A} sum to c − a − b. Without loss of generality, suppose there exist distinct elements w, x ∈ X ∩ A with w + x = c − a − b. Because {X, Y } avoids c, unless x or w is equal to c/2, it follows that c − x and c − w (which lie in A ∪ B) must be in Y, but then (c − x) + (c − w) = a + b + c, contrary to the assumption that {X, Y } avoids a + b + c. Now, consider the case where, without loss of generality, x = c/2. In this case, we note that since w > 0 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 a priori c. Therefore, if necessary, we can simply modify our partition by placing x in whichever of X ∩ A and Y ∩ 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′, Y′} of A ∪ B by placing each x ∈ 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 ∪ B avoids a + b + c; however, if without loss of generality we have distinct w, x ∈ X′ 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′ whose sum is c − a − b. Because c − a − b ≤ (a + b + c)/2 as c ≤ 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 w < c, it follows that c > 2b, so as before we can modify our partition if necessary by placing x in the opposite set from a + b + c − x.

Now, to complete the proof of Case 1 of the theorem, we need only prove the following claim.

Claim 2. 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, …, d − 1} avoiding {c − a − b, a, b, c} exists.

Proof. Noting that d − 1 < ⌊\frac{a+b+c}{2}⌋, one direction is trivial: if we have a partition of A, we can restrict it to {1, …, 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, …, 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.

Case 2. c > 3(a + b). In this case, we let A = {1, …, c − a − b − 1} and B = {c − a − b, …, 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 ∪ B avoiding {a, b, c, a + b + c} exists.

If we have a partition of A ∪ 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′, Y′} of A∪B by placing x ∈ 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 ∈ X′ (respectively Y′)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′ (respectively X′) 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.

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 ≤ b ≤ c. For a + b ≥ c, Theorem 2 and Lemma 4 establish when P (a, b, c) = 1. Meanwhile, if we have a + b < c, Theorem 3 states that P (a, b, c) = P (a, b, c − a − b); note that a, b, and c − a − b are all odd if and only if a, b, and c are. Then, using this recursion as well as the symmetry of P, for any triple (a, b, c) not all odd, we can reduce P (a, b, c) to a case covered in Theorem 2 or Lemma 4. And, as stated before, if a, b, and c are all odd, P (a, b, c) = 1.

4 Open Questions

The author would like to thank the referee for suggesting the following two questions.

Question 1. In this paper, we have only considered Tribonacci sequences with positive initial terms. One can ask the same question for initial terms not all positive; in this case, the negative terms of the Tribonacci sequence place no constraint on a potential additive partition {A, B} of ℕ. Which such Tribonacci sequences are avoidable?

Question 2. Given the recursion outlined in this paper, is there a simple non-recursive way to categorize avoidable Tribonacci sequences?

In addition, one can proceed to the next case, that of sequences satisfying t_{n} = t_{n−1} + t_{n−2} + t_{n−3} + t_{n−4} for n ≥ 5, and beyond. It is worth noting that as the depth of the recursion increases, the ratio between the terms approaches 2; furthermore, any sequence satisfying t_{n} > 2t_{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 1 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.

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.

References

[1] K. Alladi, P. Erdős, V.E. Hoggatt, Jr., “On additive partitions of integers,” Discrete Math. 23 (1978), 201-211

[2] T.Y. Chow and C.D. Long, “Additive partitions and continued fractions,” Ramanujan J. 3 (1999), 55-72

[3] I. Dumitriu, “On generalized Tribonacci sequences and additive partitions,” Discrete Math. 219 (2000), 65-83.

[4] R.J. Evans, “On additive partitions of sets of positive integers,” Discrete Math. 36 (1981), 239-245

[5] V.E. Hoggatt, Jr., “Additive partitions of the positive integers,” Fibonacci Quart. 18 (1980), 220-226

[6] Z. Shan and P.-T. Zhu, “On (a,b,k)-partitions of positive integers,” Southeast Asian Bull. Math 17 (1993), 51-58