Complementary Equations with Advanced Subscripts

Clark Kimberling Department of Mathematics University of Evansville Evansville, IN 47722 USA

              ck6@evansville.edu

Peter J. C. Moses Engineering Division, Moparmatic Co. Astwood Bank, Nr. Redditch Worcestershire, B96 6DT UK

             moparmatic@gmail.com

Abstract

This paper discusses complementary equations, such as a_{n} = b_{n} + b_{2n}, in which (a_{n}) and (b_{n}) are strictly increasing complementary sequences for which, in addition to the subscript n, at least one subscript in advance of n, such as n + 1 or 2n, occurs. Some of the equations are solved with proofs, and others are presented as conjectures or examples based on Mathematica programs that appear in the final section of the paper.

1 Introduction

Let ℕ = {1, 2, …} and ℕ_{0} = ℕ ∪ {0}. Many sequences (a_{n}) in ℕ are defined by an equation that tells how to determine each term from preceding terms; e.g., the Fibonacci sequence, (F_{n}), arises from the equation F_{n} = F_{n−1} + F_{n−2}, starting with F_{1} = 1 and F_{2} = 1. Less familiar are sequences generated by a complementary equation—that is, an equation that refers to both (a_{n}) and its complement in ℕ.

In this paper, a = (a_{n}) denotes an increasing sequence in ℕ such that the complement in ℕ of the set A = {a_{n} : n ≥ 0} is infinite. We write the complement as B and denote by b = (b_{n}) the sequence of numbers in B in increasing order. A classic example of a complementary equation is

b_{n} = a_{n} + n where a_{1} = 1,

with solution given by

a_{n} = ⌊nτ⌋, b_{n} = n + ⌊nτ⌋,

where τ = (1+\sqrt{5})/2, the golden ratio. The sequences (a_{n}) and (b_{n}) are the lower and upper Wythoff sequences, \underline{A000201} and \underline{A001500} in the On-line Encyclopedia of Integer Sequences [6]; also see [4] and [5].

2 Advanced subscripts

It may seem surprising that complementary equations with advanced subscripts, such as a_{n} = b_{n} + b_{2n}, make sense, since 2n comes after n. The first theorem will show that, with initial value b_{0} = 1, this equation and many others make sense and have unique solutions.

Theorem 1. Suppose that f : ℕ^{2} → ℕ satisfies f(1, 1) ≥ 2 and

f(m + 1, n) ≥ f(m, n) + 1 and f(m, n + 1) ≥ f(m, n) + 1

for all (m, n) ∈ ℕ^{2}. If g, h : ℕ_{0} → ℕ are strictly increasing functions, then the complementary equation

a_{n} = f(b_{g(n)}, b_{h(n)}), with b_{0} = 1,  (1)

has a unique solution.

Proof. We assume that a solution (a, b) = ((a_{n}), (b_{n})) exists and then confirm inductively that it is uniquely determined; that is, a solution is generated inductively by (1), and it is unique. For n ≥ 0,

f(b_{g(n)}, b_{h(n)}) ≥ f(b_{g(n)}, b_{h(n)} − 1) + 1
≥ f(b_{g(n)}, b_{h(n−1)}) + 1
≥ f(b_{g(n)} − 1, b_{h(n−1)}) + 2
≥ f(b_{g(n−1)}, b_{h(n−1)}) + 2,

so that

a_{n} − a_{n−1} ≥ 2.  (2)

Since b_{0} = 1, we have a_{0} = f(b_{0}, b_{0}) = f(1, 1) ≥ 2. Then (2) implies a_{1} ≥ a_{0} + 2, so that by complementation, the numbers b_{i} are uniquely determined as the consecutive integers in [a_{0} + 1, a_{1} − 1], and inductively, the set of b_{i} are uniquely determined as the consecutive integers in [a_{n} + 1, a_{n+1} − 1], for all n ≥ 0.

Following is a list of some complementary equations to which Theorem 1 applies:

a_{n} = 2b_{n},
a_{n} = b_{n} + b_{n+2},
a_{n} = 3b_{n} + 2b_{n+2} − 5,
a_{n} = 2b_{n} + b_{2n} + 1,
a_{n} = b_{n}^{2} + 2b_{n+1},
a_{n} = b_{⌊n/2⌋} + b_{⌊3n/2⌋},
a_{n} = b_{n}b_{n+1} + 1,
a_{n} = b_{n}^{2} + b_{n+1}^{2}.

The method of proof suggests that Theorem 1 could be extended to cover many more types of equations with advanced subscripts, such as these:

a_{n} = a_{n−1} + b_{n+1},
a_{n} = b_{n} + b_{n+1} + b_{n+2},
a_{n} = b_{n+1} + n + 1,
a_{n} = b_{n} + b_{2n} + b_{3n} + b_{4n} − 1.

It appears that for many complementary equations, exact formulas for solutions are elusive and that generating the sequences depends on the mex function (minimal excludant), which has been described as “unwieldy” [3]. Accordingly, aside from multi-case proofs for certain simple-looking equations (in Sections 2 and 4), we rely on Mathematica programs, as shown in Section 7, to generate sequences that reveal both expected and unexpected results, leading to examples and conjectures based on experimentation.

3 The equation a_{n} = b_{2n} + b_{4n}, where b_{0} = 1

In this section, we consider equations a_{n} = b_{hn} + b_{khn}, where h ≥ 2. (A different method applies to the case h = 1, as in Section 5). First, we consider the special case a_{n} = b_{2n} + b_{4n}, and then we state conjectures for general h and k.

Lemma 2. Suppose that a sequence β is given by

β_{n} = r(m(n)) + 21⌊n/18⌋,  (3)

where m(n) = n − 18⌊n/18⌋ and

r(m) = \begin{cases}1, & if m = 0; \\ m + 2, & if 1 ≤ m ≤ 7; \\ m + 3, & if 8 ≤ m ≤ 13; \\ m + 4, & if 14 ≤ m ≤ 17. \end{cases}

Then

β_{2n+2} − β_{2n} = \begin{cases}3, & if n ≡ 0 (mod 3); \\ 2, & if n ≢ 0 (mod 3) \end{cases}

and

β_{4n+4} − β_{4n} = \begin{cases}4 & if n ≡ 2 (mod 3); \\ 5 & if n ≢ 2 (mod 3). \end{cases}

Proof. For 0 ≤ n ≤ 17, we have m(n) = n, and values of r(n) as shown in Table 1.

\begin{matrix}n = m(n) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ r(n) & 1 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 11 & 12 & 13 & 14 & 15 & 16 & 18 & 19 & 20 & 21 \end{matrix}

Table 1: Values of r(n)

By (3) we have

β_{2n+2} − β_{2n} = r(m(2n + 2)) − r(m(2n)) + 21 (⌊\frac{n + 1}{9}⌋ − ⌊\frac{n}{9}⌋) ,

which leads to cases, first for β_{2n+2} − β_{2n} (Cases 1.1 and 1.2), then for β_{4n+4} − β_{4n}. Case 1.1: ⌊\frac{n+1}{9}⌋ − ⌊\frac{n}{9}⌋ = 0. Here, m(2n + 2) − m(2n) = 2, so that

β_{2n+2} − β_{2n} = r(m(2n + 2)) − r(m(2n)),

which, as in Table 1, is 3 if n ≡ 0 (mod 3) and 2 otherwise. Case 1.2: ⌊\frac{n+1}{9}⌋−⌊\frac{n}{9}⌋ = 1. Here, n must be of the form 9j−1, so that m(2n) = m(18j−2) = 16 and m(2n + 2) = m(18j) = 0. Then

β_{2n+2} − β_{2n} = r(0) − r(16) + 21 = 2, as required, since n ≡ 2 (mod 3).

Case 2.1: ⌊\frac{2n+2}{9}⌋ − ⌊\frac{2n}{9}⌋ = 0. Here, m(4n + 4) − m(4n) = 4, so that

β_{4n+4} − β_{4n} = r(m(4n + 4)) − r(m(4n)),

which, as in Table 1, is 4 if n ≡ 2 (mod 3) and 5 otherwise.

Case 2.2: ⌊\frac{2n+2}{9}⌋ − ⌊\frac{2n}{9}⌋ = 1. We recognize two exhaustive subcases:

Subcase 2.2.1: 2n = 7 + 9j for some j, so that 2n + 2 = 9(j + 1). Here, m(4n) = 14 and m(4n + 4) = 0, whence

β_{4n+4} − β_{4n} = r(0) − r(14) + 21 = 1 − 18 + 21 = 4,

as required, since n ≡ 2 (mod 3).

Subcase 2.2.2: 2n = 8 + 9j for some j, so that 2n + 2 = 1 + 9(j + 1). Then m(4n) = 16 and m(4n + 4) = 2, whence

β_{4n+4} − β_{4n} = r(3) − r(16) + 21 = 4 − 20 + 21 = 5,

as required, since n ≡ 1 (mod 3).

We are now ready for the main theorem of this section.

Theorem 3. Let a = (a_{n}) and b = (b_{n}) be the strictly increasing complementary sequences determined by the equation

a_{n} = b_{2n} + b_{4n}, where b_{0} = 1.  (4)

Then

a_{n} = \begin{cases}2 + 21⌊n/3⌋, & if m ≡ 0 (mod 3); \\ 10 + 21⌊n/3⌋, & if m ≡ 1 (mod 3); \\ 17 + 21⌊n/3⌋, & if m ≡ 2 (mod 3). \end{cases}  (5)

Proof. Since b_{0} = 1, we have a_{0} = 2 by (4), and since a and b are strictly increasing and complementary, we have

2 < b_{1} < b_{2} < b_{3} < b_{4},

which implies that b_{i} = 2 + i for i = 1, …, 4. Equation (4) implies a_{1} = b_{2} + b_{4} = 4 + 6 = 10, so that b_{i} = 3 + i for i = 5, 6, 7. Then a_{2} = b_{4} + b_{8} ≥ 6 + 10 = 16, and a_{2} = 6 + 11 = 17. Thus, (5) is established for n = 0, 1, 2. Before assuming (5) as an induction hypothesis, we note that

a_{3} = b_{6} + b_{12} = 8 + 15 = 23

implies b_{13} = 16 and b_{i} = 4 + i for i = 14, …, 17, so that, in regard to the sequence β_{n} in Lemma 2, we have b_{n} = β_{n} for n = 0, …, 17. Moreover, since b is the complement of a, we have, for n = 0, … 17,

b_{n} = r(m(n)) + 21⌊n/18⌋,  (6)

where m(n) = n − 18⌊n/18⌋ and

r(m) = \begin{cases}1, & if m = 0; \\ m + 2, & if 1 ≤ m ≤ 7; \\ m + 3, & if 8 ≤ m ≤ 13; \\ m + 4, & if 14 ≤ m ≤ 17. \end{cases}

For use below, we note that (4) implies

a_{n+1} = a_{n} + b_{4n+4} − b_{4n} + b_{2n+2} − b_{2n}  (7)

for n ≥ 0. Now, as an induction hypothesis, assume that (5) holds for arbitrary n ≥ 2. We have three cases, according as n ≡ 0, 1, 2 (mod 3).

Case 1: n ≡ 0 (mod 3). Here, a_{n} = 2 + 21⌊n/3⌋, and by Lemma 2, b_{2n+2} − b_{2n} = 3 and b_{4n+4} − b_{4n} = 5, so that by (7),

a_{n+1} = a_{n} + 8 = 10 + 21⌊n/3⌋ = 10 + 21⌊(n + 1)/3⌋.

By complementation, we also have (6) for the numbers b_{i} required for the following proof for Case 2.

Case 2: n ≡ 1 (mod 3). Here, b_{2n+2} − b_{2n} = 2 and b_{4n+4} − b_{4n} = 5, so that

a_{n+1} = a_{n} + 7 = 17 + 21⌊n/3⌋ = 17 + 21⌊(n + 1)/3⌋.

By complementation, we also have (6) for the numbers b_{i} required for the following proof for Case 3.

Case 3: n ≡ 2 (mod 3). Here, b_{2n+2} − b_{2n} = 2 and b_{4n+4} − b_{4n} = 4, so that

a_{n+1} = a_{n} + 6 = 23 + 21⌊n/3⌋ = 2 + (21 + 21⌊n/3⌋).

By complementation, we also have (6) for the numbers b_{i} required for the next application of the proof for Case 1, so that by the principle of mathematical induction, (5) holds for all n ≥ 0.

Corollary 4. The sequence (b_{n}) in Theorem 3 is identical to the sequence (β_{n}) in Lemma 2.

Proof. A proof is included in the proof of Theorem 3.

Corollary 5. The sequence a in Theorem 3 satisfies the recurrence

a_{n+4} = a_{n+3} + a_{n+1} − a_{n}.

Proof. We shall make repeated use of Corollary 4. Let

B_{2} = b_{2n+2} − b_{2n}, B_{4} = b_{4n+4} − b_{4n}, B_{8} = b_{2n+8} − b_{2n+6}, B_{16} = b_{4n+16} − b_{4n+12}, so that

a_{n+4} − a_{n+3} = B_{16} + B_{8} and a_{n+1} − a_{n} = B_{4} + B_{2}.

There are three cases: Case 1: n ≡ 0 (mod 3).

B_{16} = vβ_{4m+4} − β_{4m} for m = n + 3, so that m ≡ 0 (mod 3), and B_{16} = 5.
B_{8} = β_{2m+2} − β_{2m} for m = n + 3, so that m ≡ 0 (mod 3), and B_{8} = 3.
B_{4} = β_{2m+4} − β_{4m} for m = n, so that m ≡ 0 (mod 3), and B_{4} = 5.
B_{2} = β_{2m+2} − β_{2m} for m = n, so that m ≡ 0 (mod 3), and B_{2} = 3.

Case 2: n ≡ 1 (mod 3).

B_{16} = β_{4m+4} − β_{4m} for m = n + 3, so that m ≡ 1 (mod 3), and B_{16} = 5.
B_{8} = β_{2m+2} − β_{2m} for m = n + 3, so that m ≡ 1 (mod 3), and B_{8} = 3.
B_{4} = β_{2m+4} − β_{4m} for m = n, so that m ≡ 1 (mod 3), and B_{4} = 5.
B_{2} = β_{2m+2} − β_{2m} for m = n, so that m ≡ 1 (mod 3), and B_{2} = 3.

Case 3: n ≡ 2 (mod 3).

B_{16} = β_{4m+4} − β_{4m} for m = n + 3, so that m ≡ 2 (mod 3), and B_{16} = 4.
B_{8} = β_{2m+2} − β_{2m} for m = n + 3, so that m ≡ 2 (mod 3), and B_{8} = 2.
B_{4} = β_{2m+4} − β_{4m} for m = n, so that m ≡ 2 (mod 3), and B_{4} = 4.
B_{2} = β_{2m+2} − β_{2m} for m = n, so that m ≡ 2 (mod 3), and B_{2} = 2.

In all the cases,

B_{16} + B_{8} = B_{4} + B_{2},

which is equivalent to

a_{n+4} − a_{n+3} = a_{n+1} − a_{n}.

Next, we give a conjecture based on Program 7.1, which was used to generated Table 2.

Conjecture 6. Let a = (a_{n}) and b = (b_{n}) be the strictly increasing complementary sequences determined by the equation

a_{n} = b_{hn} + b_{khn},

where h ≥ 2, k ≥ 2, and b_{0} = 1. Then a is a linear recurrence sequence given by

a_{n} = a_{n−1} + a_{n−k−1} − a_{n−k−2}

with initial terms

a_{0} = 2, a_{1} = h(k + 1) + 4, a_{2} = 2h(k + 1) + 5, …, a_{k} = kh(k + 1) + k + 3.

The sequence a consists of the positive integers congruent modulo (k + 1)(2k + h + 1) to the numbers in {a_{0}, a_{1}, …, a_{k}}, and the sequence b satisfies the linear recurrence

b_{n} = b_{n−1} + b_{n−m} − b_{n−m−1}, where m = (k + 2)hk + h − 5.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ a_{n} = b_{2n} + b_{4n} & 2 & 10 & 17 & 23 & 31 & 38 & 44 & 52 & 59 & 65 & 73 & 80 & 86 & 94 \\ a_{n} = b_{2n} + b_{6n} & 2 & 12 & 21 & 30 & 38 & 48 & 57 & 66 & 74 & 84 & 93 & 102 & 110 & 120 \\ a_{n} = b_{2n} + b_{8n} & 2 & 14 & 25 & 36 & 47 & 57 & 69 & 80 & 91 & 102 & 112 & 124 & 135 & 146 \\ a_{n} = b_{3n} + b_{6n} & 2 & 13 & 23 & 32 & 43 & 53 & 62 & 73 & 83 & 92 & 103 & 113 & 122 & 133 \\ a_{n} = b_{3n} + b_{9n} & 2 & 16 & 29 & 42 & 54 & 68 & 81 & 94 & 106 & 120 & 133 & 146 & 158 & 172 \\ a_{n} = b_{4n} + b_{8n} & 2 & 16 & 29 & 41 & 55 & 68 & 80 & 94 & 107 & 119 & 133 & 146 & 158 & 172 \end{matrix}

Table 2: First fourteen terms, a_{n} = b_{hn} + b_{khn}, b_{0} = 1

In the next section we extend our earlier attention to the special case a_{n} = b_{2n} + b_{4n} by adding a nonzero constant to the right-hand side.

4 The equation a_{n} = b_{2n} + b_{4n} + c, where b_{0} = 1

Theorem 3 gives a precise solution of a_{n} = b_{2n} + b_{4n}, with b_{0} = 1, and Corollary 5 shows that (a_{n}) is more “regular” than might be thought if (5) were the only representations. We shall see, however, that this sort of regularity does not extend to equations of the form a_{n} = b_{2n} + b_{4n} + c when c ≥ 1.

Theorem 7. Let a = (a_{n}) and b = (b_{n}) be the strictly increasing complementary sequences determine by the equation

a_{n} = b_{2n} + b_{4n} + 1, where b_{0} = 1.

Then

a_{n} = 7n + \begin{cases}3, & if n ≡ 0 (mod 3); \\ 3 or 4, & if n ≢ 0 (mod 3). \end{cases}  (8)

Proof. We have [2] inductively

b_{6n+3} ≥ 7n + 5 and b_{6n+1} ≤ 7n + 2,

so that

t + ⌊(t + 3)/6⌋ + 1 ≤ b_{t} ≤ t + ⌈(t − 1)/6⌉ + 1  (9)

for t = 6k + 3, …, 6k + 7. Thus, b_{t} = t + ⌈(t − 1)/6)⌉ + 1 except for

7k + 3 ≤ b_{6k+2} ≤ 7k + 4.

Consequently, 7n + 3 ≤ a_{n} ≤ 7n + 4, as desired.

To illustrate the “irregularity” of (8) when n ≢ 0 (mod 3), let r = (r_{n}) be the increasing sequence of numbers n for which a_{n} = 7n + 4:

r = (1, 5, 7, 10, 13, 14, 17, 19, 23, 25, 28, 32, 34, 37, 41, 44, 46, 47, 49, 50, …).  (10)

Conjecture 8. The sequence r is not linearly recurrent, and

{a_{n} − a_{n−1} : n ≥ 1} = {1, 2, 3, 4, 5}.

The five differences shown in 10 all occur as n ranges from 1 to 28. No other difference occurs as n ranges up to 10000. Similar mysteries are found for other choices of c. Initial terms of (a_{n}) are shown in Table 3, which was used to construct Table 3. Looking ahead, it appears that the sequences (a_{n}) are much more “regular” for c ∈ {2, 3, 5}, than for some other values of c; see Conjectures 14-16.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ a_{n} = b_{2n} + b_{4n} + 0 & 2 & 10 & 17 & 23 & 31 & 38 & 44 & 52 & 59 & 65 & 73 & 80 & 86 & 94 \\ a_{n} = b_{2n} + b_{4n} + 1 & 3 & 11 & 17 & 24 & 31 & 39 & 45 & 53 & 59 & 66 & 74 & 80 & 87 & 95 \\ a_{n} = b_{2n} + b_{4n} + 2 & 4 & 11 & 18 & 25 & 32 & 39 & 46 & 53 & 60 & 67 & 74 & 81 & 88 & 95 \\ a_{n} = b_{2n} + b_{4n} + 3 & 5 & 12 & 19 & 26 & 33 & 40 & 47 & 54 & 61 & 68 & 75 & 82 & 89 & 96 \\ a_{n} = b_{2n} + b_{4n} + 4 & 6 & 12 & 19 & 27 & 34 & 41 & 48 & 54 & 62 & 69 & 75 & 82 & 90 & 96 \\ a_{n} = b_{2n} + b_{4n} + 5 & 7 & 13 & 20 & 28 & 34 & 41 & 49 & 55 & 62 & 70 & 76 & 83 & 91 & 97 \\ a_{n} = b_{2n} + b_{4n} + 6 & 8 & 14 & 21 & 28 & 35 & 42 & 50 & 56 & 63 & 71 & 77 & 84 & 92 & 98 \\ a_{n} = b_{2n} + b_{4n} + 7 & 9 & 15 & 22 & 28 & 36 & 43 & 50 & 57 & 64 & 70 & 78 & 85 & 92 & 99 \\ a_{n} = b_{2n} + b_{4n} + 8 & 10 & 16 & 22 & 29 & 36 & 44 & 50 & 58 & 65 & 71 & 79 & 86 & 92 & 100 \end{matrix}

Table 3: a_{n} = b_{2n} + b_{4n} + c, for c = 0, 1, …, 8

With one exception, the data in Table 3, generated by Program 7.2, show nondecreasing columns. It turns out that this exception is indicative of many others. In order to describe them, we introduce some notation: for each c ≥ 1 and the equations

a_{n} = b_{2n} + b_{4n} + c and a_{n}^{∗} = b_{2n}^{∗} + b_{4n}^{∗} + c + 1, where b_{0} = b_{0}^{∗} = 1,  (11)

throughout this section let

N = an upper bound for n, depending on context;
m(c) = min{a_{n}^{∗} − a_{n}} for 0 ≤ n ≤ N = 5000;
M(c) = max{a_{n}^{∗} − a_{n}} for 0 ≤ n ≤ N = 5000;
T (c, i) = sequence of indices n for which a_{n}^{∗} − a_{n} = i;
Δ(c, i) = set of distinct differences in T (c, i).

The choice of N varies as an experimental upper bound when sampling various (presumably) unbounded sequences.

Note that the sets T (c, i) for i = m(c), …, M(c) partition ℕ_{0}. We shall refer to m, M, T, and Δ in the following examples, which show various sorts of unwieldiness that appear when comparing the sequences (a_{n}) and (a_{n}^{∗}) given by (11).

Example 9. For c = 0, we have m(c) = 0, M(c) = 1, and

T (0, 0) = (2, 4, 8, 11, 16, 20, …); Δ(0, 0) = {1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 13};
T (0, 1) = (0, 1, 3, 5, 6, 7, 9, …); Δ(0, 1) = {1, 2, 3}.

In Example 9, Δ(0, 0) consists of 11 integers in the interval [1, 13], with 6 and 11 missing. Table 4, generated by Program 7.3, shows the frequency of each difference a_{n}^{∗} − a_{n}, for n up to N = 10000.

1 2 3 4 5 6 7 8 9 10 11 12 13
316 581 737 461 188 0 45 129 129 23 0 8 53

Table 4: Frequencies of differences in Δ(0, 0), n = 1, 2, …, N = 10000

Example 10. For c = 1, we have m(c) = 0, M(c) = 1, and

T (1, 0) = (1, 5, 7, 10, 13, 14, 17, 19 …),
Δ(1, 0) = {1, 2, 3, 4, 5};
T (1, 1) = (0, 2, 3, 4, 6, 8, 9, 11, 12 …),
Δ(1, 1) = {1, 2, 3}.

Example 11. For c = 2, we have m(c) = M(c) = 1, so that T (2, 1) = ℕ_{0} and Δ(2, 1) = {1}.

Regarding Example 11, we pose this question: is 2 the only value of c for which m(c) = M(c)? (Program 7.3, with c = 2 in the first instance and c = 3 in the second, confirms that a_{n}^{∗} − a_{n} = 1 for n up to N = 10000).

In connection with Table 4, the difference a_{n}^{∗} − a_{n} is never 6 or 11 for N = 10000, and is 12 relatively rarely; indeed, the least n for which a_{n}^{∗} − a_{n} = 12 is n = 1325.

Example 12. For c = 6, we have m(c) = −1, M(c) = 1, and

T (6, −1) = (9, 18, 24, 27, 36, 45, 48 …),

Δ(6, −1) = {3, 6, 9};

T (6, 0) = (3, 6, 12, 31, 33, 39, 51 …),

Δ(6, 0) (see note below);

T (6, 1) = (0, 1, 2, 4, 5, 7, 8, 10, …),

Δ(6, 1) = {1, 2}.

It appears that Δ(6, 0) is a much larger set, for large n, than all other sampled Δ(c, i). Indeed, it seems possible that if n is not restricted to an upper bound, then Δ(6, 0) is infinite, as suggested by the following data, in which “newcomers” are bolded:

For n = 1, …, N = 6000,
T (6, 0) = {3, 6, 9, 12, 18, 24, 27, 36, 39, 42, 48, 51, 54, 57, 66, 75, 81, 93, 99,
111, 117, 120, 123, 156, 162, 198, 237, 279, 354, 360, 480, 531, 660}.
For n = 1, …, N = 12000,
T (6, 0) = {3, 6, 9, 12, 18, 24, 27, 36, 39, 42, 48, 51, 54, 57, 66, 75, 81, 93, 99,
111, 117, 120, 123, 156, 162, 171, 180, 198, 237, 279, 354, 360, 480,
531, 660, 711, 849, 1065}.
For n = 1, …, N = 16000,
T (6, 0) = {3, 6, 9, 12, 18, 24, 27, 36, 39, 42, 48, 51, 54, 57, 66, 75, 81, 93, 99,
111, 117, 120, 123, 156, 162, 171, 174, 180, 198, 225, 237, 270, 279,
354, 360, 480, 531, 660, 711, 849, 1062, 1065, 1092}.

Example 13. For c = 9, we have m(c) = −1, M(c) = 2, and

T (9, −1) = (6), Δ(9, −1) = (empty);
T (9, 0) = (8, 10, 11, 13, 16, 20, …), Δ(9, 0) = {1, 2, 3, 4, 6, 7};
T (9, 1) = (0, 1, 2, 3, 4, 5, 6, 7, 9, …), Δ(9, 1) = {1, 2, 3};
T (9, 2) = (20), Δ(9, 2) = (empty).

In Example 13, T (9, −1) = (6) comes from a_{6}^{∗} − a_{6} = 44 − 45 = −1, and T (9, 2) = (2, 0) comes from a_{20}^{∗} − a_{20} = 144 − 142 = 2. Otherwise, for 0 ≤ n ≤ N = 5000, we have 0 ≤ a_{n}^{∗} − a_{n} ≤ 1.

For 0 ≤ n ≤ N = 5000, and perhaps for all n > N = 5000,

(m(c), M(c)) = (0, 1) for c = 0, 1, 3, 4, 5, 7, 8, 10, 11, 12, 13, 15, 16, 17, 24, 25,

27, 28, 32, 33, 36, 48, 50, 56, 57;

(m(c), M(c)) = (−1, 1) for c = 6, 14, 18, 19, 20, 21, 23, 26, 34, 37, 39, 40, 44,

45, 47, 55, 58;

(m(c), M(c)) = (−1, 2) for c = 9, 29, 30, 31, 35, 38, 41, 42, 43, 49, 51, 52, 53,

54, 59, 60;
(m(c), M(c)) = (−1, 3) for c = 22, 46.

The next three conjectures, based on N = 10000, suggest that a_{n}^{∗} − a_{n} is “regular” for c = 2, 3, 5, (whereas, it appears, the regularity does not extend to c = 4 or c = 6).

Conjecture 14. Suppose that c ≥ 0, and let (a_{n}) and (â_{n}) be solutions of

a_{n} = b_{2n} + b_{4n} and â_{n} = b̂_{2n} + b̂_{4n} + 2,

respectively. Then

â_{n} − a_{n} = \begin{cases}2, & if n ≡ 0 (mod 3); \\ 1, & if n ≢ 0 (mod 3). \end{cases}

Conjecture 15. Suppose that c ≥ 0, and let (a_{n}) and (â_{n}) be solutions of

a_{n} = b_{2n} + b_{4n} and â_{n} = b̂_{2n} + b̂_{4n} + 3,

respectively. Then

â_{n} − a_{n} = \begin{cases}3, & if n ≡ 0 (mod 3); \\ 2, & if n ≢ 0 (mod 3). \end{cases}

Conjecture 16. Suppose that c ≥ 0, and let (a_{n}) and (â_{n}) be solutions of

a_{n} = b_{2n} + b_{4n} and â_{n} = b̂_{2n} + b̂_{4n} + 5,

respectively. Then

â_{n} − a_{n} = \begin{cases}5, & if n ≡ 0 (mod 3); \\ 3, & if n ≢ 0 (mod 3). \end{cases}

5 The equation a_{n} = b_{n} + b_{2n}

In contrast to results in Section 3, we find less “regularity” in the present section.

Theorem 17. The solution of the complementary equation a_{n} = b_{n} + b_{2n}, with b_{0} = 1, satisfies the following conditions for all n ≥ 0 and i ≥ 0:

4n + 2 ≤ a_{n} ≤ 4n + 3,
b_{3i} = 4i + 1,
4i + 2 ≤ b_{3i+1} ≤ 4i + 3,
b_{3i+2} = 4i + 4.

Proof. We paraphrase a proof given in MathOverflow [1]. Clearly the inequality

4n + 2 ≤ a_{n} ≤ 4n + 3  (12)

holds for n ∈ {0, 1, 2}. We assume (12) as an induction hypothesis for n ≥ 2. For convenience the phrase “is in a” will refer to terms of the sequence a, and likewise for b. We have three cases.

Case 1: n = 3i. By the induction hypothesis,

4i − 2 ≤ a_{i−1} ≤ 4i − 1,  (13)

so that the number of terms a_{m} that are ≤ 4i − 1 is i. (Specifically, these i numbers are a_{0}, a_{1}, …, a_{i−1}.) Since every integer in [1, 4i − 1] is in a or b, the number of terms b_{m} that are ≤ 4i − 1 is (4i − 1)i − i = 3i − 1. By (13), the numbers 4i and 4i + 1 are also in b, so that the number of terms b_{m} in [1, 4i + 1] is 3i + 1. These numbers are b_{0}, b_{1}, …, b_{3i}, so that b_{3i} = 4i + 1.

Case 2: n = 3i + 1. By the induction hypothesis,

4i + 2 ≤ a_{i} ≤ 4i + 3,

and a_{i+1} ≥ 4i + 6, so that there are exactly i + 1 terms a_{m} in [1, 4i + 3]. Therefore, there are exactly 4i + 5 − (i + 1) = 3i + 4 terms b_{m} that are ≤ 4i + 5, specifically, b_{0}, b_{1}, … b_{3i+3}. By the induction hypothesis,

4i + 6 ≤ a_{i+1} ≤ 4i + 7,  (14)

so that there are at most i + 1 terms a_{m} in [1, b_{i+3}]. (Otherwise, a_{i+1} ∈ [1, b_{i+3}], so that a_{i+1} ≤ b_{3i+3}, contrary to the already proved inequality b_{3i+3} ≤ 4i + 5 < a_{i+1}). Since b_{3i+3} ≤ 4i + 5, and since, by (14), 4i + 4 and 4i + 5 are in b, we have b_{3i+2} = 4i + 4 and b_{3i+3} = 4i + 5, so that

b_{3i+1} ≤ 4i + 3.  (15)

We turn now to a proof that b_{3i+1} ≥ 4i + 2. Every integer in [1, 4i] is in a or b, and since (by the induction hypothesis) a_{i−1} ≤ 4i − 1, there are at least i terms a_{m} that are ≤ 4i − 1, hence at most (4i − 1) − i = 3i − 1 terms b_{m} in [1, 4i − 1]. Since

a_{i−1} ≤ 4i − 1 < 4i + 2 ≤ a_{i},

the numbers 4i and 4i+1 are in b. There are, therefore, at most 3i+1 terms b_{m} in [1, 4i+1]. We have

b_{0} < b_{1} < b_{2} < ⋯ b_{3i} ≤ 4i + 1

and b_{3i+1} > 4i + 1. Thus, b_{3i+1} ≥ 4i + 2.

Case 3: n = 3i + 2. By the induction hypothesis, a_{i+1} ≥ 4i + 6, so that, since

4i + 2 ≤ a_{i} ≤ 4i + 3,

the number of terms a_{m} that are ≤ 4i + 3 is i + 1. Since every integer in [1, 4i + 3] is in a or b, the number of terms b_{m} that are ≤ 4i + 3 is 4i + 3 − (i − 1) = 3i + 2. The induction hypothesis implies

a_{i} ≤ 4i + 3 < 4i + 6 < a_{i+1},

so that 4i + 4 is in b. We have thus counted a total of 3i + 3 terms b_{m} in [1, 4i + 4]; they are

b_{0}, b_{1}, …, b_{3i+2},

so that b_{3i+2} = 4i + 4.

We now finish the induction for establishing (12):

4(k + 1) + \frac{10}{3} = \frac{4(k + 1) + 5}{3} + \frac{4(2k + 2) + 5}{3}

≥ b_{k+1} + b_{2k+2}

= a_{k+1}

≥ \frac{4(k + 1) + 2}{3} + \frac{4(2k + 2) + 2}{3}

= 4(k + 1) + \frac{4}{3}.

Since a_{k+1} is an integer, the inequality

4(k + 1) + \frac{10}{3} ≥ a_{k+1} ≥ 4(k + 1) + \frac{4}{3}

implies

4(k + 1) + 2 ≤ a_{k+1} ≤ 4(k + 1) + 3.

The irregular subsequence of the sequence

b = (1, 3, 4, 5, 6, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 22, 24, 25, 27, …

in Theorem 17 is

s(i) := (b_{3i+1}) = (3, 6, 11, 15, 19, 22, 27, 30, 35, 39, 42, 47, 51, 54, 67, …),  (16)

for which 4i + 2 ≤ s(i) ≤ 4i + 3; indeed,

s_{i} = \begin{cases}4i + 2, & if i = 2, 6, 8, 11, 14, 15, 18, 20, 24, 26, 29, 33, 35, 38, 42, … \\ 4i + 3, & if i = 1, 3, 4, 5, 7, 9, 10, 12, 13, 16, 17, 19, 21, 22, 23, 25, …. \end{cases}

Following are two conjectures based on Program 7.4, with n ranging from 1 to 50000.

Conjecture 18. The difference sequence of the above sequence

(2, 6, 8, 11, 14, 15, 18, …)

has only five distinct terms: 1, 2, 3, 4, 5.

The least n for which all five differences occur in Conjecture 18 is 111.

Conjecture 19. The limiting proportion of s_{i}’s of the form 4i + 2 is 2/5.

6 The equation a_{n} = ub_{n} + vb_{n+k} + c

The preceding sections show that some complementary equations with advanced subscripts are easily solved, whereas others involve a multitude of cases and irregularities. Here we consider equations of the form

a_{n} = ub_{n} + vb_{n+k} + c, where b_{0} = 1,  (17)

where u, v, and c are integers satisfying k ≥ 1 and 1 ≤ u ≤ v, and we find the same sort of regularities and irregularities. Let

x = lim_{n→∞} a_{n}/n and y = lim_{n→∞} b_{n}/n.

Then (17) together with 1/x + 1/y = 1, yields

x = u + v + 1 and y = (u + v + 1)/(u + v).

Table 5, generated by Program 7.5, shows in columns 4 and 5 the minimum and maximum values of a_{n}−(u+v+1)n for n = 0, 1, …, 100000. Also, Table 5 indicates that for u = v = 1,

max{a_{n} − 3n} = a_{0} = k + 2,

but that the sequence (m(n)) = (min{a_{n} − 3n}) is not so predictable, as indicated by its first 22 terms:

3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 11, 11, 12, 13, 13, 14, 14, 15, 16.

\begin{matrix}u & v & k & min & max & a_{0} \\ 1 & 1 & 1 & 3 & 3 & 3 \\ 1 & 2 & 1 & −1 & 10 & 5 \\ 1 & 3 & 1 & −3 & 15 & 7 \\ 1 & 4 & 1 & −5 & 18 & 9 \\ 1 & 5 & 1 & −5 & 23 & 11 \\ 2 & 1 & 1 & −1 & 9 & 4 \\ 3 & 1 & 1 & −3 & 13 & 5 \\ 4 & 1 & 1 & −6 & 15 & 6 \\ 5 & 1 & 1 & −6 & 19 & 7 \\ 2 & 3 & 1 & −6 & 17 & 8 \\ 3 & 2 & 1 & −6 & 16 & 7 \\ 2 & 2 & 1 & −3 & 14 & 6 \\ 3 & 3 & 1 & −5 & 21 & 9 \\ 1 & 1 & 2 & 3 & 4 & 4 \\ 1 & 1 & 3 & 4 & 5 & 5 \\ 1 & 1 & 4 & 4 & 6 & 6 \\ 1 & 1 & 5 & 5 & 7 & 7 \\ 1 & 1 & 6 & 6 & 8 & 8 \\ 1 & 1 & 7 & 6 & 9 & 9 \end{matrix}

Table 5: a_{n} = ub_{n} + vb_{n+k}, b_{0} = 1

As already noted, Table 5 and further explorations suggest that if u > 1 or v > 1, then both min and max are unbounded. Taking (u, v, k) = (1, 2, 1) as an example, we have (min, max) = (−1, 10) when N = 100000. The appearance of (N, m, M) in the following list means that as n ranges from 1 to N, the minimal and maximal differences a_{n} − (u + v + 1)n are m and M:

(100, 2, 7), (300, 1, 7), (600, 1, 7), (700, 1, 8),
(1900, 1, 8), (2000, 0, 8), (5000, 0, 8), (6000, 0, 9),
(20000, −1, 9), (10000, −1, 10), (200000, −2, 10)

Theorem 1, with f(x, y) = ux + vy + c, ensures a unique solution of (17) if c ≥ 2 − u − v. This is the case, for example, for the equation a_{n} = b_{n} + 2b_{n+1} + c when c = −1. It is easy to check, however, that this equation also has a unique solution for c = −2, but not for c = −3. This example raises a question to which we respond with another conjecture:

Conjecture 20. The equation (17), where b_{0} = 1, has a unique solution if and only if

c ≥ 2 − u − v + k − vk.

Results shown in Table 5 and experimentation suggest that if (u, v) = (1, 1), then min{a_{n} − (u + v + 1)n} and max{a_{n} − (u + v + 1)n} are as indicated in Table 5 and that otherwise, both are unbounded.

We turn now to equations in which c ≠ 0. Indeed, we take c to be the least value for which the equation (17) has a solution; i.e., c = 2 − u − v + k − vk. Table 6, generated by Program 7.6, shows the minimum and maximum values of a_{n} − (u + v + 1)n for n = 0, 1, …, 100000.

\begin{matrix}u & v & k & c & min & max & a_{0} \\ 1 & 2 & 1 & −2 & −2 & 9 & 3 \\ 1 & 2 & 2 & −3 & −1 & 10 & 4 \\ 1 & 2 & 3 & −4 & 0 & 10 & 5 \\ 2 & 1 & 1 & −1 & −2 & 8 & 3 \\ 2 & 2 & 1 & −3 & −5 & 12 & 3 \\ 2 & 2 & 2 & −4 & 0 & 9 & 4 \\ 2 & 1 & 3 & −1 & 0 & 10 & 5 \\ 3 & 3 & 1 & −6 & −9 & 17 & 3 \\ 3 & 3 & 2 & −8 & −5 & 15 & 4 \\ 3 & 3 & 3 & −10 & −1 & 13 & 5 \end{matrix}

Table 6: a_{n} = ub_{n} + vb_{n+k} + c, b_{0} = 1

As might be expected from the discussion about Table 5, it appears likely that minimum and maximum values represented in columns 5 and 6 of Table 6 are unbounded.

7 Mathematica programs

The examples and conjectures in the preceding sections are based on six Mathematica programs in which the parameters h, k, c, u, v, and z can be varied. Each program depends on the mex function mentioned near the end of Section 2.

7.1 Program for Table 2

The parameters z, c, h, k are set by the first two lines of code. Keep c = 0. Decrease z to 100 for a first run. To see row 4 of Table 2, for example, use h = 3 and k = 6. When experimenting, use larger z for larger h and k.

z = 1000; c = 0;

h = 2; k = 4;
mex[list_, start_] := (NestWhile[# + 1 &, start,
MemberQ[list, #] &]);
a = {}; b = {1}; AppendTo[a, c + mex[Flatten[{a, b}], 1]];
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
  AppendTo[a, c + Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
"Sequence (a(n)), from a(n)=a(h*n)+b(k*n):"
a ; Take[a, 100]

7.2 Program for Table 3

The parameters are set to generate row 7 of Table 3. When experimenting, use larger z for larger h, k, and c.

z = 1000;
h = 2; k = 4; c = 6;
mex[list_, start_] := (NestWhile[# + 1 &, start,
MemberQ[list, #] &]);
a = {}; b = {1}; AppendTo[a, c + mex[Flatten[{a, b}], 1]];
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
  AppendTo[a, c + Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
"Sequence (a^*(n)), from a(n)=a(h*n)+b(k*n)+c, where c = 1:"
a ; Take[a, 100]

Data supporting Conjecture 8 can be obtained by adding the following lines at the end of this program:

r = Select[Range[400], Mod[a[[# + 1]], 7] ==4 &]
(* r is the sequence just before Conjecture 8. *)
d = Differences[s]
Union[d]

7.3 Program for Table 4

The parameters are set to show frequencies 27, 61, 73, …, with z = 1000. The runtime is considerably longer for z = 10000, as in Table 4.

z = 1000; c = 0;
mex[list_, start_] := (NestWhile[# + 1 &, start,
MemberQ[list, #] &]);
h = 2; k = 4; a = {}; b = {1};
AppendTo[a, c + mex[Flatten[{a, b}], 1]];
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];

  AppendTo[a, c + Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
"Sequence (a(n)), from a(n)=a(h*n)+b(k*n)+c, where c = 0:"
a; a1 = a; Take[a, 50]
c = 1; a = {}; b = {1};
AppendTo[a, c + mex[Flatten[{a, b}], 1]]; 90
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
  AppendTo[a, c + Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
"Sequence (a^*(n)), from a(n)=a(h*n)+b(k*n)+c"
a ; Take[a, 50]
"Distinct differences, a(n)^* - a(n):"
Union[a - a1]
p = Differences[Flatten[Position[a - a1, 0]]]; Take[ p, 100]
"Number of occurrences of each difference:"
t = Table[Count[p, k], {k, 1, 13}]

7.4 Program for Conjectures 18 and 19

The parameters are set to output the sequence on Conjecture 18. The code can be easily extended to support Conjecture 19.

mex[list_, start_] := (NestWhile[# + 1 &, start,
MemberQ[list, #] &]);
h = 1; k = 2; a = {}; b = {1}; z = 2000;
AppendTo[a, mex[Flatten[{a, b}], 1]];
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
  AppendTo[a, Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
Take[b, 50]
bb = b; Clear[b];(*next,re-index b with offset 0*)
b[n_] := bb[[n + 1]]; u = Table[b[3 i + 1],
{i, 0, -1 + Length[bb]/3}];
Take[u, 100]
t = Mod[u, 4]; p = Flatten[Position[t, 2]];
Take[p, 100]
d = Differences[p];
Union[d] (* set of distinct differences *)

7.5 Program for Table 5

The parameters u, v, k, c, and z are set to show {0, 9} as minimal and maximal differences; to get {−1, 10},m as in row 2 of Table 5, use z = 100000, and wait.

z = 10000;
mex[list_, start_] := (NestWhile[# + 1 &, start,

MemberQ[list, #] &]);
 {u, v, k, c} = {1, 2, 1, 0}; {a, b} = {{}, {1}};
Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
AppendTo[a, u b[[1]] + v b[[k + 1]] + c];
Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]];
  AppendTo[a, u b[[n]] + v b[[k + n]] + c], {n, 2, z}];
Take[a, 60];
Take[b, 60];
Intersection[a, b];
aa[n_] := a[[n + 1]];
t = Table[aa[n] - (u + v + 1) n, {n, 0, z - 2}];
{Min[t], Max[t]}

7.6 Program for Table 6

The parameters u, v, k, c, and z are set to show {−1, 8} as minimal and maximal differences; to get {−2, 9},m as in row 1 of Table 6, use z = 100000, and wait.

z = 10000;
mex[list_, start_] := (NestWhile[# + 1 &, start,
MemberQ[list, #] &]);
 {u, v, k, c} = {1, 2, 1, -2}; {a, b} = {{}, {1}};
Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}]
AppendTo[a, u b[[1]] + v b[[k + 1]] + c];
Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]];
  AppendTo[a, u b[[n]] + v b[[k + n]] + c], {n, 2, z}];
Take[a, 60]
Take[b, 60]
Intersection[a, b]
aa[n_] := a[[n + 1]];
t = Table[aa[n] - (u + v + 1) n, {n, 0, z - 2}];
{Min[t], Max[t]}
Flatten[Position[t, Min[t]]]
Flatten[Position[t, Max[t]]]

8 Acknowledgments

We thank the referee for their valuable comments and suggestions. We also thank Neil J. A. Sloane and the many contributors to the On-line Encyclopedia of Integer Sequences.

References

[1] Ilya Bogdanov, Answer for “Simple-looking sequences A and B defined by a complementary equation”, 2019. Available at https://tinyurl.com/1j1zv6u5.

[2] Ilya Bogdanov, Answer for “Difference of two integer sequences: all zeros and ones?”,

    2019. Available at https:tinyurl.com/5yu5hddw.

[3] A. Fraenkel and U. Peled, Harnessing the unwieldy MEX function, in Games of No Chance 4, Richard J. Nowakowski, editor, Mathematical Sciences Research Institute Publications 63, Cambridge University Press, 2007, pp. 77–94.

[4] C. Kimberling, Complementary equations, J. Integer Sequences, 10 (2007), Article 07.1.4.

[5] C. Kimberling, Complementary equations and Wythoff sequences, J. Integer Sequences, 11 (2008), Article 08.3.3.

[6] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

    at https://oeis.org/.

2010 Mathematics Subject Classification: Primary 11B37. Keywords: complementary equation, complementary sequence. (Concerned with sequences \underline{A304799}, \underline{A304800}, \underline{A304801}, \underline{A304802}, \underline{A304803}, \underline{A304804}, \underline{A304805}, \underline{A304806}, \underline{A304807}, \underline{A304808}, \underline{A304809}, \underline{A304810}, \underline{A304811}, \underline{A304812}, \underline{A304813}, \underline{A304814}, \underline{A304815}, \underline{A304816}, \underline{A309156}, and \underline{A326661}.)

Received December 2 2020; revised version received February 6 2021. Published in Journal of Integer Sequences, February 6 2021.

Return to Journal of Integer Sequences home page.