Bounds for the Kolakoski Sequence

Olivier Bordellès 2 allée de la Combe 43000 Aiguilhe France

                  borde43@wanadoo.fr

Benoit Cloitre 19 rue Louise Michel 92300 Levallois-Perret France

                 benoit7848c@yahoo.fr

Abstract

The Kolakoski sequence (K_{n}) is perhaps one of the most famous examples of selfdescribing sequences for which some problems are still open. In particular, one does not know yet whether the density of 1’s in this sequence is equal to \frac{1}{2}. This work, which does not answer this question, provides explicit bounds for the main sequences related to (K_{n}). The proofs rest on a new identity involving the partial sums of (K_{n}) and on Dirichlet’s pigeonhole principle which allows us to improve notably on the error-term.

1 Introduction

In 1965, Kolakoski [7] introduced an example of a self-generating sequence by creating the sequence defined in the following way.

Definition 1.

⋆ We call block all sets of one or more identical digits. The number of digits in a block is the length of the block.

⋆ The Kolakoski sequence is the sequence (K_{n}) of blocks of 1’s or 2’s defined by

\{ \begin{matrix}K_{1} & = & 1 \\ K_{n} & = & length of the n-th block. \end{matrix}

⋆ We also define the partial sums

S_{n} = ∑_{j=1}^{n} K_{j}.

⋆ The three following sequences (k_{n}), (o_{n}) and (t_{n}) are related to (K_{n}) and defined by

\{ \begin{matrix}k_{0} & = & 0 \\ k_{n} & = & min_{1≤j≤n}\{j : S_{j} ≥ n\} (n ≥ 1) \end{matrix}

and

o_{n} := |{1 ≤ j ≤ n : K_{j} = 1}| and t_{n} := |{1 ≤ j ≤ n : K_{j} = 2}|

where |E| means the number of elements of the finite set E. Remark 2. We have o_{n} + t_{n} = n and since

S_{n} = ∑_{j=1}^{n} K_{j} = ∑_{\begin{matrix}j=1 \\ K_{j}=1 \end{matrix}}^{n} 1 + 2 ∑_{\begin{matrix}j=1 \\ K_{j}=2 \end{matrix}}^{n} 1 = o_{n} + 2t_{n}

we infer S_{n} = 2n − o_{n} = n + t_{n}, o_{n+1} − o_{n} = 2 − K_{n+1} and t_{n+1} − t_{n} = K_{n+1} − 1. The following table shows the first terms of the sequences defined above.

n  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
K_{n}  1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1
n-th block 1 2  3 4 5  6  7  8  9  10 11
k_{n}  1 2  3 4 5  6  7  8  9  10 11
S_{n}  1 3 5 6 7 9 10 12 14 15 17 19 20 21 23 24 25
o_{n}  1 1 1 2 3 3 4 4 4 5 5 5 6 7 7 8 9
t_{n}  0 1 2 2 2 3 3 4 5 5 6 7 7 7 8 8 8

This sequence, which belongs to the online Encyclopedia of Integer Sequences [10], has been studied by many authors (see [2, 3, 4, 5, 11] for instance), and some conjectures have been made. In particular, no one knows yet whether the density of the 1’s is equal to \frac{1}{2}, e.g.

lim_{n→∞} \frac{o_{n}}{n} = \frac{1}{2}.  (1)

This problem seems to be very tricky. It is equivalent to proving that

S_{n} = \frac{3n}{2} + o(n) or k_{n} = \frac{2n}{3} + o(n) (n ⟶ ∞).  (2)

These estimates come from the asymptotic formula

∑_{j=1}^{n}(−1)^{k_{j}} = o(n) (n ⟶ ∞)  (3)

that we conjecture (See Corollary 10). Such sums are frequent in number theory. For instance, the Mertens function M(n) = ∑_{j=1}^{n} μ(j), where μ is the Möbius function, or the summatory function L(n) = ∑_{j=1}^{n} λ(j) of the Liouville λ-function, are strongly related to the prime number theorem. Another interesting example can be found in the paper [9] in which an “almost alternating” sum, related to the Beatty’s sequences, is investigated. We did not manage to prove one or the other estimates (1), (2) or (3). The sequence (k_{n}), with its fractal behavior, seems to prevent the use of ordinary tools to treat such sums (generating functions, convolution identities, periodicity, discrepance theory, specific arithmetic properties, etc). From then on, it could be interesting to provide unconditional effective bounds for the sequences (k_{n}), (S_{n}), (t_{n}) and (o_{n}). The following estimates, valid for all positive integers n, are obvious (see Lemma 6 for (k_{n})).

\begin{matrix}n ≤ S_{n} < 2n & and & \frac{n}{2} < k_{n} ≤ n \\ 0 ≤ t_{n} < n & and & 0 < o_{n} ≤ n. \end{matrix}

The aim of this work is to give better bounds than the above trivial inequalities. More precisely, we will first prove the following result.

Theorem 3. For all positive integers n, we have

\begin{matrix}\frac{4n}{3} − 1 ≤ S_{n} ≤ \frac{5n}{3} & and & \frac{3n}{5} ≤ k_{n} ≤ \frac{3n}{4} + \frac{3}{2}. \\ \frac{n}{3} − 1 ≤ t_{n} ≤ \frac{2n}{3} & and & \frac{n}{3} ≤ o_{n} ≤ \frac{2n}{3} + 1. \end{matrix}

In a second step, we use Dirichlet’s pigeonhole principle to estimate the remainder term in a more subtle way. We will establish the following improvement.

Theorem 4. Let α ≐ 0, 6764 … be the unique root of the polynomial P = X^{3} − 26X^{2} + 26X − 6 in the interval (\frac{1}{2}, 1) and we set

β := \frac{α^{2} + α − 1}{6(3α − 1)} ≐ 0.021703504 …

For all positive integers n, we have

\begin{matrix}(\frac{3}{2} − β) n − 6 ≤ S_{n} ≤ (\frac{3}{2} + β) n + 6 & and & (\frac{α}{3α − 1}) n − 4 ≤ k_{n} ≤ αn + 5. \\ (\frac{1}{2} − β) n − 6 ≤ t_{n} ≤ (\frac{1}{2} + β) n + 6 & and & (\frac{1}{2} − β) n − 6 ≤ o_{n} ≤ (\frac{1}{2} + β) n + 6. \end{matrix}

Thus we have unconditionally

|\frac{o_{n}}{n} − \frac{1}{2}| ≤ 0.021703504 … + \frac{6}{n}.

Although these bounds are still far from (2), they improve on the results established in [8] if n is sufficiently large, where it is proven that, if the limit lim_{n→∞}(o_{n}/n) exists, then

| lim_{n→∞} \frac{o_{n}}{n} − \frac{1}{2}| ≤ \frac{17}{762} ≐ 0.0223097 …

and our bounds are even slightly better than their “semi-rigorous” bound

| lim_{n→∞} \frac{o_{n}}{n} − \frac{1}{2}| ≤ \frac{1}{46} ≐ 0.02173913 …

Nevertheless, it should be mentioned that Theorem 4 does not improve on Chvátal’s results (see [4]). The sketch of the proof is the following one.

⋆ We first establish Proposition 12 which prompts to introduce the set E_{n} of indexes j ∈ {1, …, n} such that K_{j} = 2 and shows it is sufficient to prove that there are more or less as many even integers as odd integers.

⋆ Since we did not manage to prove this assertion, we studied the gaps between consecutive elements of E_{n} and showed that it is sufficient to establish that there are almost as many even integers as odd integers in the subset E_{n}(2) of E_{n} made up of integers e ∈ E_{n} such that e + 2 ∈ E_{n} (Lemma 17).

⋆ Then we studied the gaps between consecutive elements of E_{n}(2) (Lemmas 15 and 18) and defined two subsets A_{n} and B_{n} of E_{n}(2) (Lemmas 20 and 22) to refine the estimates.

Although they are getting smaller and smaller, the subsets become gradually harder and harder to handle, for they require the knowledge of longer and longer runs of the sequence (K_{n}) (Lemma 21). The proofs, using disjunction arguments, become also longer and longer, since the number of cases gradually increases. Finally, we use Dirichlet’s pigeonhole principle applied to the sets A_{n} and B_{n} (Lemma 22) to accurately estimate the remainder term. However, such a strategy does not seem to prove estimates of the form ≪ n^{θ} with 0 ≤ θ < 1. Finally, it should be mentioned that all the numeric computations have been made using PARI/GP system [12].

2 Some properties of the sequence (k_{n})

Steinsky [11] proved the following results.

Lemma 5. Let n ≥ 2 be an integer. Then we have

(i) S_{k_{n−1}} ∈ {n − 1, n} and k_{n} = k_{n−1} + n − S_{k_{n−1}}.

(ii) k_{n} − k_{n−1} = |K_{n} − K_{n−1}|.

(iii) k_{n} = n − t_{k_{n−1}}.

We deduce the following consequences.

Lemma 6. The sequence (k_{n}) is non-decreasing and, for all positive integers n, we have

\frac{n + 1}{2} ≤ k_{n} ≤ n.

Proof. Using Lemma 5 (ii), we get k_{n} − k_{n−1} = |K_{n} − K_{n−1}| ≥ 0. The inequality k_{n} ≤ n comes from Lemma 5 (iii). Moreover, we also have S_{k_{n}} ∈ {n, n + 1} by Lemma 5, so that 2k_{n} > S_{k_{n}} ≥ n and hence k_{n} > n/2. Since k_{n} is an integer, we get the desired lower bound.

Lemma 7. For all integers n ≥ 2, the number of blocks of length equal to 2 between the letters K_{1} and K_{n} is given by n − k_{n}.

Proof. Using Lemma 5 (ii), for all integers j ≥ 2, we have

(K_{j−1}, K_{j}) = (1, 1) or (2, 2) ⟺ k_{j−1} = k_{j}

so that the number in question is

∑_{\begin{matrix}j=2 \\ k_{j−1}=k_{j} \end{matrix}}^{n} 1 = ∑_{j=2}^{n} 1 − ∑_{\begin{matrix}j=2 \\ k_{j−1}≠k_{j} \end{matrix}}^{n} 1 = n − 1 − ∑_{j=2}^{n} (k_{j} − k_{j−1}) = n − k_{n}.

This proves Lemma 7.

3 Some properties of the sequence (K_{n})

In what follows, we list some situations which cannot appear in the sequence (K_{n}). We will call run any (finite or not) subsequence of the sequence (K_{n}). The next lemma lists some of the avoided runs. The easy proof of this fact, left to the reader (see [2, 3] for instance), is based upon the property that the sequence does not contain cubes, that is, runs of the form xxx.

Lemma 8. The following runs cannot appear in the sequence (K_{n}).

(i) (1, 1, 1, …) and (2, 2, 2, …).

(ii) (1, 2, 1, 2, 1) , (2, 1, 2, 1, 2), (1, 1, 2, 2, 1, 1) and (2, 2, 1, 1, 2, 2).

(iii) (1, 1, 2, 1, 1, 2, 1, 1, 2) , (2, 2, 1, 2, 2, 1, 2, 2, 1), (1, 2, 2, 1, 2, 2, 1, 2, 2) and (2, 1, 1, 2, 1, 1, 2, 1, 1).

(iv) (2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2) and (2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2).

(v) (2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2) and (2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2).

(vi) (2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2) and (2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2).

(vii) (2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2).

Proposition 9. For all positive integers n, we have

K_{S_{n}} = \frac{3 + (−1)^{n}}{2} and K_{1+S_{n}} = \frac{3 + (−1)^{n+1}}{2} .

Proof. We first notice that, since the first block is {1} and the other blocks alternate between 1’s and 2’s, then the n-th block is either {1} or {1, 1} (resp., either {2} or {2, 2}) if n is odd (resp., even). The next step is the proof by induction of the following assertion.

For all positive integers n, S_{n} is the index of the last element of the n-th block. (4)

The assertion (4) is clearly true for n = 1. Assume it is true for some n ≥ 1. By induction hypothesis, we get

S_{n+1} = S_{n} + K_{n+1} = \{ \begin{matrix}S_{n} + 1 \\ or \\ S_{n} + 2 \end{matrix} = \{ \begin{matrix}index of the unique element of the (n + 1)-th block \\ or \\ index of the last element of the (n + 1)-th block \end{matrix}

since, if K_{n+1} = 1 (resp., K_{n+1} = 2), then the length of the (n + 1)-th block is equal to 1 (resp., 2) and there is only one element (resp., two elements) in this block. This proves (4).

Now we can prove Proposition 9. Indeed, K_{S_{n}} is the value in the sequence (K_{n}) of the index of the last element of the n-th block, which is equal to 2 if n is even and to 1 if n is odd, and the asserted result for K_{S_{n}} follows. We get the formula for K_{1+S_{n}} in a similar way, since S_{n} +1 is the index of the first element of the (n+1)-th block. This proves Proposition 9.

Corollary 10. For all positive integers n, we have

K_{n} = \frac{3 + (−1)^{k_{n}}}{2} .

Proof. By Lemma 5, we have

S_{k_{n}} = \begin{cases}n, & if k_{n} ≠ k_{n+1}; \\ n + 1, & if k_{n} = k_{n+1}; \end{cases}

so that

K_{n} = K_{S_{kn}} = \frac{3 + (−1)^{k_{n}}}{2} if k_{n} ≠ k_{n+1}

and

K_{n+1} = K_{S_{kn}} = \frac{3 + (−1)^{k_{n}}}{2} = \frac{3 + (−1)^{k_{n+1}}}{2} if k_{n} = k_{n+1}

which completes the proof.

Corollary 11. For all positive integers n, we have

∑_{j=1}^{n}(−1)^{j}K_{j} = 2S_{S_{n}} − 3S_{n}.

Proof. By induction, the case n = 1 being obvious. Assume the equality is true for some positive integer n. Noticing that [S_{n} + 1, S_{n+1}] ∩ ℤ = {S_{n} + 1} or {S_{n} + 1, S_{n+1}} according to K_{n+1} = 1 or 2 and using Proposition 9 and the induction hypothesis, we get

2S_{S_{n+1}} − 3S_{n+1} = \begin{cases}2S_{S_{n}} − 3S_{n} + 2K_{S_{n}+1} − 3, & if K_{n+1} = 1; \\ 2S_{S_{n}} − 3S_{n} + 2K_{S_{n}+1} − 3 + 2K_{S_{n+1}} − 3, & if K_{n+1} = 2; \end{cases}

= \begin{cases}2S_{S_{n}} − 3S_{n} + (−1)^{n+1}, & if K_{n+1} = 1; \\ 2S_{S_{n}} − 3S_{n} + 2(−1)^{n+1}, & if K_{n+1} = 2; \end{cases}

= 2S_{S_{n}} − 3S_{n} + (−1)^{n+1}K_{n+1}

= ∑_{j=1}^{n}(−1)^{j}K_{j} + (−1)^{n+1}K_{n+1} = ∑_{j=1}^{n+1}(−1)^{j}K_{j}

as required. The proof is complete.

4 A useful identity

In what follows, ⌊x⌋ is the integer part of x ∈ ℝ. Proposition 12. For all positive integers n, we have

S_{n} = \frac{3n}{2} + \frac{1}{2} ( ∑_{\begin{matrix}j=1 \\ K_{2j}=2 \end{matrix}}^{⌊k_{n}/2⌋} 1 − ∑_{\begin{matrix}j=1 \\ K_{2j+1}=2 \end{matrix}}^{⌊(k_{n}−1)/2⌋} 1) + \frac{(−1)^{k_{n}} − 1}{4} − \frac{(−1)^{k_{n}}c_{n}}{2}

where c_{n} = \begin{cases}1, & if K_{n} = K_{n+1}; \\ 0, & if K_{n} ≠ K_{n+1}. \end{cases}.

Proof. Using Corollary 11 with k_{n} instead of n, we get

∑_{j=1}^{k_{n}}(−1)^{j}K_{j} = 2S_{S_{kn}} − 3S_{k_{n}}

= \begin{cases}2S_{n+1} − 3n − 3, & if K_{n} = K_{n+1}; \\ 2S_{n} − 3n, & if K_{n} ≠ K_{n+1}; \end{cases}

= \begin{cases}2S_{n} − 3n + 2K_{n+1} − 3, & if K_{n} = K_{n+1}; \\ 2S_{n} − 3n, & if K_{n} ≠ K_{n+1}; \end{cases}

= 2S_{n} − 3n + (−1)^{k_{n}}c_{n},

where we used Corollary 10. Besides, by Abel summation, we have for all m ≥ 1

\begin{aligned}∑_{j=1}^{m}(−1)^{j}K_{j} & = (−1)^{m} ∑_{j=1}^{m} K_{j} − ∑_{j=1}^{m−1} \{(−1)^{j+1} − (−1)^{j}\} ∑_{h=1}^{j} K_{h} \\ & = (−1)^{m}S_{m} + 2 ∑_{j=1}^{m−1}(−1)^{j}S_{j} = 2 ∑_{j=1}^{m}(−1)^{j}S_{j} − (−1)^{m}S_{m} \end{aligned}

so that

S_{n} = \frac{3n}{2} + ∑_{j=1}^{k_{n}}(−1)^{j}S_{j} − \frac{(−1)^{k_{n}}}{2} (S_{k_{n}} + c_{n})

The relation S_{j} = j + t_{j} implies

S_{n} = \frac{3n}{2} − \frac{(−1)^{k_{n}}t_{k_{n}}}{2} + ∑_{j=1}^{k_{n}}(−1)^{j}t_{j} + \frac{(−1)^{k_{n}} − 1}{4} − \frac{(−1)^{k_{n}}c_{n}}{2} .

We conclude the proof by using the identity

∑_{j=1}^{m}(−1)^{j}a_{j} = \frac{(−1)^{m}a_{m} − a_{1}}{2} + \frac{1}{2} ∑_{j=2}^{m}(−1)^{j} (a_{j} − a_{j−1})  (5)

which can be viewed as a discrete analogue of Boole’s summation formula of order 1 (see [1, 6] for instance) and which implies here that

∑_{j=1}^{k_{n}}(−1)^{j}t_{j} = \frac{(−1)^{k_{n}}t_{k_{n}}}{2} + \frac{1}{2} ∑_{j=2}^{k_{n}}(−1)^{j} (K_{j} − 1)

= \frac{(−1)^{k_{n}}t_{k_{n}}}{2} + \frac{1}{2} ∑_{\begin{matrix}j=2 \\ K_{j}=2 \end{matrix}}^{k_{n}}(−1)^{j}

= \frac{(−1)^{k_{n}}t_{k_{n}}}{2} + \frac{1}{2} ( ∑_{\begin{matrix}j=1 \\ K_{2j}=2 \end{matrix}}^{⌊k_{n}/2⌋} 1 − ∑_{\begin{matrix}j=1 \\ K_{2j+1}=2 \end{matrix}}^{⌊(k_{n}−1)/2⌋} 1) ,

which concludes the proof.

5 Proof of Theorem 3

We are now in a position to prove Theorem 3, for which one may suppose n ≥ 4 and whose results come from trivial estimates of the sums of Proposition 12. Considering the four cases (K_{n}, K_{n+1}) = (1, 1), (2, 2), (1, 2) and (2, 1), the trivial estimate

| ∑_{\begin{matrix}j=1 \\ K_{2j}=2 \end{matrix}}^{⌊n/2⌋} 1 − ∑_{\begin{matrix}j=1 \\ K_{2j+1}=2 \end{matrix}}^{⌊(n−1)/2⌋} 1| ≤ t_{n} − 1  (6)

applied to Proposition 12 allows us to get the inequalities

n + \frac{k_{n}}{2} − \frac{1}{2} ≤ S_{n} ≤ 2n − \frac{k_{n}}{2} .  (7)

On the other hand, the inequality

∑_{\begin{matrix}j=1 \\ K_{2j}=2 \end{matrix}}^{⌊n/2⌋} 1 ≤ \frac{n}{2}

used in Proposition 12 implies that

S_{n} ≤ \frac{3n}{2} + \frac{k_{n}}{4}

and the use of (7) rewritten as k_{n} ≤ 4n − 2S_{n} gives

2S_{n} ≤ 5n − S_{n}

which implies the asserted upper bound for S_{n}. The lower bound for k_{n} comes from the inequality S_{k_{n}} ≥ n and from the upper bound S_{n} formerly established. We get the upper bound for t_{n} and the lower bound for o_{n} with the help of the relations t_{n} = S_{n} − n and o_{n} = n−t_{n}. To prove the lower bound for t_{n}, we introduce the set E_{n} := {j ∈ {1, …, n} : K_{j} = 2} and show that the gaps between two consecutive elements of E_{n} can only be equal to 1, 2 or 3. Indeed, suppose there exists e ∈ E_{n} such that e and e + a are consecutive in E_{n} with a ≥ 4. Then we have K_{e+1} = K_{e+2} = K_{e+3} = 1 which is impossible by Lemma 8 (i). We infer that E_{n} is a subset of {1, …, n} whose gaps between two consecutive elements are at most 3, so that

n ≤ 3 (|E_{n}| + 1) = 3 (t_{n} + 1)

which implies the asserted lower bound. The relation S_{n} = n + t_{n} gives the lower bound for S_{n}, the relation o_{n} = n − t_{n} gives the upper bound for o_{n} and the inequality k_{n} ≤ n + 1 − t_{k_{n}} gives the upper bound for k_{n}. Theorem 3 is completely proven.

6 Proof of Theorem 4

The proof of Theorem 3 shows that we may take advantage of the specificities of the sequence (K_{n}). In this section, we study these specificities in a more accurate way. We first check the validity of the inequalities for all n ∈ {1, …, 99}, and we may suppose n ≥ 100. We use the set E_{n} introduced in the proof of Theorem 3 and define the two following subsets.

\begin{aligned}F_{n} & := \{2j : 1 ≤ j ≤ ⌊n/2⌋ and K_{2j} = 2\} \\ G_{n} & := \{2j + 1 : 1 ≤ j ≤ ⌊(n − 1)/2⌋ and K_{2j+1} = 2\} \end{aligned}

and, for all sets of integers E and all positive integers a and b, we set

E (a) := {e ∈ E : e and e + a are consecutive in E} and E(a, b) := (E(a))(b).

It is obvious that the elements of F_{n} (resp., F_{n}(2)) are the even indexes of E_{n} (resp., E_{n}(2)), and the elements of G_{n} (resp., G_{n}(2)) are the odd indexes of E_{n} (resp., E_{n}(2)).

Example 13. Here are the main sets used in the proof (n = 100).

⋆ E_{100} = {2, 3, 6, 8, 9, 11, 12, 15, 18, 19, 21, 24, 26, 27, 30, 33, 35, 36, 38, 39, 42, 44, 45, 47, 50, 53, 54,

56, 57, 60, 62, 63, 65, 66, 69, 72, 74, 75, 77, 80, 81, 83, 84, 87, 89, 90, 92, 93, 96, 99, 100} .

⋆ F_{100} = {2, 6, 8, 12, 18, 24, 26, 30, 36, 38, 42, 44, 50, 54, 56, 60, 62, 66, 72, 74, 80, 84, 90, 92, 96, 100} .
⋆ G_{100} = {3, 9, 11, 15, 19, 21, 27, 33, 35, 39, 45, 47, 53, 57, 63, 65, 69, 75, 77, 81, 83, 87, 89, 93, 99} .
⋆ E_{100}(1) ∪ E_{100}(3) = {2, 3, 8, 11, 12, 15, 18, 21, 26, 27, 30, 35, 38, 39, 44, 47, 50, 53, 56, 57, 62, 65,

66, 69, 74, 77, 80, 83, 84, 89, 92, 93, 96, 99} .

⋆ E_{100}(2) = {6, 9, 19, 24, 33, 36, 42, 45, 54, 60, 63, 72, 75, 81, 87, 90} .
⋆ F_{100}(2) = {6, 24, 36, 42, 54, 60, 72, 90} and G_{100}(2) = {9, 19, 33, 45, 63, 75, 81, 87} .
⋆ A_{100} = {9, 36, 54, 75, 81} and B_{100} = {6, 19, 24, 33, 42, 45, 60, 63, 72, 87} .

Set  E_{100}  F_{100} G_{100} E_{100}(1) ∪ E_{100}(3) E_{100}(2) F_{100}(2) G_{100}(2) A_{100} B_{100}

Cardinal t_{100} = 51 26 25 100 − k_{100} = 34  16  8  8  5  10

The main purpose of this section is to provide better estimates of ||F_{n}| − |G_{n}|| than the trivial bound (6) used in the proof of Theorem 3. To this end, we first study some properties of the sets E_{n}(1) ∪ E_{n}(3) and E_{n}(2).

Lemma 14. We have |E_{n}(1) ∪ E_{n}(3)| = n − k_{n} + ε_{n} where ε_{n} ∈ {−1, 0, 1}.

Proof. It has been seen above that the gaps between consecutive elements of E_{n} are at most equal to 3. In particular, we get

\begin{matrix}e ∈ E_{n}(1) ⟺ K_{e} = K_{e+1} = 2. \\ e ∈ E_{n}(3) ⟺ K_{e} = K_{e+3} = 2 and K_{e+1} = K_{e+2} = 1. \end{matrix}

We infer that |E_{n}(1) ∪ E_{n}(3)| counts the number of blocks of length 2 between K_{1} and K_{n}, possibly plus or minus 1 block, so that

|E_{n}(1) ∪ E_{n}(3)| = n − k_{n} + ε_{n}

by Lemma 7.

Lemma 15. The gaps between two consecutive elements of E_{n}(2) can only be equal to 3, 5, 6, 9 or 10.

Proof.

1. We first prove that, in E_{n}(2), there do not exist consecutive elements with gaps equal to 1, 2, 4, 7 or 8. Indeed, if a gap between two consecutive elements of E_{n}(2) is :

⋆ equal to 1, then there exists e ∈ E_{n} such that e, e + 1, e + 2, e + 3 ∈ E_{n} and therefore

we have

(K_{e}, …, K_{e+3}) = (2, 2, 2, 2)

which is impossible by Lemma 8 (i).

⋆ equal to 2, then there exists e ∈ E_{n} such that e, e + 2, e + 4 ∈ E_{n} and we have

(K_{e}, …, K_{e+4}) = (2, 1, 2, 1, 2)

which is impossible by Lemma 8 (ii).

⋆ equal to 4, then there exists e ∈ E_{n} such that e, e + 2, e + 4, e + 6 ∈ E_{n} and we have

(K_{e}, …, K_{e+6}) = (2, 1, 2, 1, 2, 1, 2)

which is impossible by Lemma 8 (ii).

⋆ equal to 7, then there exists e ∈ E_{n} such that

(K_{e+4}, …, K_{e+8}) = (1, 2, 1, 2, 1) .

Indeed, we have K_{e+2} = K_{e+7} = 2 by hypothesis, and K_{e+4} = K_{e+6} = 1 otherwise we have e + 2, e + 4 ∈ E_{n}(2). We infer that K_{e+5} = 2, otherwise (K_{e+4}, K_{e+5}, K_{e+6}) = (1, 1, 1) and K_{e+8} = 1, for K_{e+9} = 2. This run is impossible by Lemma 8 (ii).

⋆ equal to 8, then there exists e ∈ E_{n} such that

(K_{e}, …, K_{e+10}) = (2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2) .

Indeed, we have K_{e} = K_{e+2} = K_{e+8} = K_{e+10} = 2, hence K_{e+1} = K_{e+9} = 1, but also K_{e+4} = 1 otherwise e + 2 ∈ E_{n}(2), and similarly K_{e+6} = 1 otherwise e + 4 ∈ E_{n}(2), and therefore K_{e+5} = 2 otherwise there exist three consecutive 1’s, and hence K_{e+3} = K_{e+7} = 1 otherwise e + 3, e + 5 ∈ E_{n}(2). This run is impossible by Lemma 8 (iv).

2. Now it only remains to be shown that gaps between two consecutive elements of E_{n}(2) are at most equal to 10. Suppose that e and e + a are consecutive in E_{n}(2) with a ≥ 11. We then have

K_{e} = K_{e+2} = 2 and K_{e+1} = K_{e+4} = 1

for if K_{e+4} = 2, then e + 2 ∈ E_{n}(2) contrary to the hypothesis. Let us treat two cases.

⋆ 1^{st} case : K_{e+3} = 1. Then K_{e+5} = 2.

(i) If K_{e+6} = 1, then we have

(K_{e}, …, K_{e+10}) = (2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1).

Indeed, if K_{e+7} = 2, then we have e + 5 ∈ E_{n}(2). We infer that K_{e+8} = 2. Moreover, we have K_{e+9} = 2, otherwise we get a run (1, 1, 2, 1, 1, 2, 1, 1) which is impossible. Also, K_{e+10} = 1, otherwise e + 8 ∈ E_{n}(2).

We then observe in this case that K_{e+11} can neither be equal to 1, otherwise we have three consecutive blocks of length 2, nor be equal to 2, otherwise e + 9 ∈ E_{n}(2). This case is then impossible.

(ii) If K_{e+6} = 2, then we have

(K_{e}, …, K_{e+10}) = (2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1).

Indeed, K_{e+8} = 1 otherwise e + 6 ∈ E_{n}(2), and K_{e+10} = 1 otherwise we have three consecutive blocks of length 2. Such a run is impossible, since it has three consecutive blocks of length 2.

⋆ 2^{nd} case : K_{e+3} = 2. Then K_{e+5} = 1 otherwise e + 3 ∈ E_{n}(2). We also have

(K_{e}, …, K_{e+10}) = (2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1 or 2).

Indeed, in view of K_{e+4} and K_{e+5}, we must have K_{e+6} = 2, hence K_{e+7} = 1 otherwise we have three consecutive blocks of length 2, and K_{e+8} = 1 otherwise e + 6 ∈ E_{n}(2), and then K_{e+9} = 2.

(i) If K_{e+10} = 1, then K_{e+11} can neither be equal to 1, otherwise we have a run (1, 1, 2, 1, 1, 2, 1, 1) which is impossible by Lemma 8 (iii), nor be equal to 2 otherwise e + 9 ∈ E_{n}(2).

(ii) If K_{e+10} = 2, then we have K_{e+11} = 1, and K_{e+12} can neither be equal to 1, otherwise we have three consecutive blocks of length 2, nor be equal to 2 otherwise e + 10 ∈ E_{n}(2).

The proof is complete.

Lemma 16. The gaps between two consecutive elements of E_{n}(1) ∪ E_{n}(3) can only be equal to 1, 3 or 5.

Proof. They cannot be equal to 2 for, if e and e + 2 are consecutive in E_{n}(1) ∪ E_{n}(3), then we have e ∈ E_{n}(2). They cannot be equal to 4 either, for if e and e + 4 are consecutive E_{n}(1) ∪ E_{n}(3), then e can neither belong to E_{n}(1) otherwise e + 1 ∈ E_{n}(3) and then e and e + 1 are consecutive in E_{n}(1) ∪ E_{n}(3), nor belong to E_{n}(3) otherwise e + 3 ∈ E_{n}(1) and then e and e + 3 are consecutive in E_{n}(1) ∪ E_{n}(3), which is a contradiction. Now it only remains to be shown that gaps between two consecutive elements of E_{n}(1) ∪ E_{n}(3) are at most equal to 5. Suppose that e and e + a are consecutive in E_{n}(1) ∪ E_{n}(3) with a ≥ 6.

⋆ If e ∈ E_{n}(1), then K_{e+2} = 1. Moreover, K_{e+4} = 1 otherwise e + 1 ∈ E_{n}(3). Hence K_{e+3} = 2. Similarly, K_{e+6} = 1 otherwise e + 3 ∈ E_{n}(3). Therefore K_{e+5} = 2. Hence we have

(K_{e+2}, …, K_{e+6}) = (1, 2, 1, 2, 1)

which is impossible by Lemma 8 (ii).

⋆ If e ∈ E_{n}(3), then K_{e+1} = K_{e+2} = 1 and K_{e+4} = 1 otherwise e + 3 ∈ E_{n}(1). Similarly, K_{e+6} = 1 otherwise e + 3 ∈ E_{n}(3). Hence K_{e+5} = 2 and we have

(K_{e+2}, …, K_{e+6}) = (1, 2, 1, 2, 1)

which is impossible by Lemma 8 (ii).

The proof is complete.

Lemma 17. We have

||F_{n}| − |G_{n}|| ≤ ||F_{n}(2)| − |G_{n}(2)|| + 3.

Proof. By Lemma 16, the set E_{n}(1)∪E_{n}(3) is alternatively made up of even and odd numbers, and since 2 is the first element of this set, the difference between the number of even and odd integers of E_{n}(1) ∪ E_{n}(3) is equal to 0 or 1, i.e.

|F_{n} ∩ (E_{n}(1) ∪ E_{n}(3))| = |G_{n} ∩ (E_{n}(1) ∪ E_{n}(3))| + 0 or 1

and therefore

|F_{n}| ≤ |F_{n} ∩ E_{n}(2)| + |F_{n} ∩ (E_{n}(1) ∪ E_{n}(3))| + 1
= |F_{n}(2)| + |F_{n} ∩ (E_{n}(1) ∪ E_{n}(3))| + 1
≤ |F_{n}(2)| + |G_{n} ∩ (E_{n}(1) ∪ E_{n}(3))| + 2
≤ |G_{n}| + |F_{n}(2)| − |G_{n}(2)| + 3

and similarly we have |G_{n}| ≤ |F_{n}| + |G_{n}(2)| − |F_{n}(2)| + 3 which completes the proof of Lemma 17.

Lemma 18. There do not exist four consecutive numbers with the same parity in E_{n}(2).

Proof. 1. If e and e + 6 are consecutive in E_{n}(2), then we have

(K_{e}, …, K_{e+6}) = \{ \begin{matrix}(2, 1, 2, 2, 1, 1, 2) & if e + 2 ∈ E_{n}(1); \\ (2, 1, 2, 1, 1, 2, 2) & if e + 2 ∈ E_{n}(3). \end{matrix}  (8)

Indeed, suppose e + 2 ∈ E_{n}(1). Then (K_{e}, …, K_{e+3}) = (2, 1, 2, 2), and hence K_{e+4} = 1, and K_{e+5} = 1 otherwise either e + 3 ∈ E_{n}(2) or e + 2 ∈ E_{n}(3). A similar argument applies if e + 2 ∈ E_{n}(3).

If e and e + 10 are consecutive in E_{n}(2), then if e + 2 ∈ E_{n}(1), a similar argument as above proves that

(K_{e}, …, K_{e+10}) = (2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2).

Besides, we have e + 2 ∉ E_{n}(3). Indeed, if e + 2 ∈ E_{n}(3), then we get

(K_{e}, …, K_{e+10}) = (2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2) or (2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2)

and these two runs are impossible by Lemma 8 (iv).

2. Now let us prove that, if three consecutive numbers have the same parity in E_{n}(2), then the gap between the first two and between the last two can only be equal to 6.

⋆ 1^{st} case : Suppose that e, e + 6 and e + 16 are consecutive in E_{n}(2). By the arguments above, we have

(K_{e}, …, K_{e+16}) = (2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2)

or

(K_{e}, …, K_{e+16}) = (2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2)

and these two runs are impossible by Lemma 8 (v).

⋆ 2^{nd} case : Suppose that e, e+10 and e+16 are consecutive in E_{n}(2). By the arguments above, we have

(K_{e}, …, K_{e+16}) = (2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2)

or

(K_{e}, …, K_{e+16}) = (2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2)

and these two runs are impossible by Lemma 8 (vi).

⋆ 3^{rd} case : Suppose that e, e+10 and e+20 are consecutive in E_{n}(2). By the arguments above, we have

(K_{e}, …, K_{e+20}) = (2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2)

and this run is impossible by Lemma 8 (vii).

Since the numbers have the same parity and they are consecutive in E_{n}(2), there is no other possibility according to Lemma 15.

3. We are now able to prove Lemma 18. According to the above arguments, if four numbers with the same parity are consecutive in E_{n}(2), one can only have e, e + 6, e + 12, e + 18 consecutive in E_{n}(2). The (tedious) examination of the eight possibilities induced by (8) shows that each case leads to a run appearing in Lemma 8 (ii), which concludes the proof.

Remark 19. The result of Lemma 18 is optimal since, for instance, the numbers 75, 81 and 87 are consecutive in E_{n}(2) for all integers n ≥ 90 (see Example 13).

In what follows, we introduce the following subsets of E_{n}(2).

A_{n} := E_{n}(2, 6) ∪ E_{n}(2, 10)

and

B_{n} := E_{n}(2, 3) ∪ E_{n}(2, 5) ∪ E_{n}(2, 9).

Lemma 20. We have |F_{n}(2) ∩ B_{n}| = |G_{n}(2) ∩ B_{n}| + 0 or 1.

Proof. The proof rests on the following assertion.

The gap between two consecutive elements of B_{n} is odd.  (9)

Indeed, if statement (9) is true, then the elements of B_{n} are alternatively even and odd, and the result follows by noticing that 6 is the first element of this set.

The rest of the text is devoted to the proof of (9). Let e ∈ B_{n}.

1. If e, e + a and e + a + b are consecutive in E_{n}(2) with (a, b) ∈ {3, 5, 9}^{2}, then e and e + a are consecutive in B_{n} with a odd.

2. If e, e + a and e + a + b are consecutive in E_{n}(2) with (a, b) ∈ {3, 5, 9} × {6, 10}, then e + a ∈ A_{n}. Let e + a + b + c be the successor of e + a + b in E_{n}(2).

(i) If c ∈ {3, 5, 9}, then e and e + a + b are consecutive in B_{n} with a + b odd.

(ii) If c = 6, then e + a + b ∈ A_{n}. Let e + a + b + 6 + d be the successor of e + a + b + 6 in E_{n}(2).

⋆ If d ∈ {3, 5, 9}, then e and e + a + b + 6 are consecutive in B_{n} with a + b + 6 odd.

⋆ If d = 6, then e + a + b + 6 ∈ A_{n}. By Lemmas 15 and 18, the successor of e+a+b+12 in E_{n}(2) can only be the number e+a+b+12+f with f ∈ {3, 5, 9}, so that e and e + a + b + 12 are consecutive in B_{n} with a + b + 12 odd.

(iii) If c = 10, then e + a + b ∈ A_{n}. Let e + a + b + 10 + g be the successor of e + a + b + 10 in E_{n}(2). Again, By Lemmas 15 and 18, we have g ∈ {3, 5, 9}, so that e and e+a+b+10 are consecutive in B_{n} with a + b + 10 odd.

There is no other possibility by Lemmas 15 and 18, which completes the proof.

Lemma 21. If (e, e + 6) ∈ (E_{n}(2, 6))^{2}, then (K_{e}, …, K_{e+27}) has a configuration of the form

\{ \begin{matrix}(2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2), & if e + 25 ∉ E_{n}; \\ (2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2), & if e + 25 ∈ E_{n}. \end{matrix}

Proof.

1. We first notice that, according to (8), if (e, e + 6) ∈ (E_{n}(2, 6))^{2}, one can only have e + 2 ∈ E_{n}(3) and e + 8 ∈ E_{n}(1). We infer that

(e, e + 6) ∈ (E_{n}(2, 6))^{2} ⟺ (K_{e}, …, K_{e+14}) = (2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2).

2. We then examine all the possibilities offered by the sequence (K_{n}).

⋆ Let us show that e + 15 ∈ E_{n}(2). Indeed, we necessarily have e + 15 ∈ E_{n}, otherwise (K_{e+11}, …, K_{e+15}) = (1, 2, 1, 2, 1) which is impossible by Lemma 8 (ii). We deduce that K_{e+16} = 1. If e + 15 ∉ E_{n}(2), then K_{e+17} = 1 and we have

(K_{e+8}, …, K_{e+17}) = (2, 2, 1, 1, 2, 1, 2, 2, 1, 1)

and the lengths give the run (2, 2, 1, 1, 2, 2), which is impossible by Lemma 8 (ii).

⋆ Thus, e + 15 ∈ E_{n}(2), hence K_{e+17} = 2 and K_{e+19} = 1 otherwise e + 15 and e + 17 are consecutive in E_{n}(2) which is impossible by Lemma 15.

⋆ We also have e + 18 ∉ E_{n}(2) otherwise the lengths of the run (K_{e+13}, …, K_{e+19}) generate the run (1, 2, 1, 2, 1). Similarly, we necessarily have e + 18 ∈ E_{n} otherwise the lengths of the run (K_{e+1}, …, K_{e+20}) give the sequence (1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2) which is impossible.

⋆ We infer that K_{e+21} = 2 otherwise (K_{e+19}, …, K_{e+21}) = (1, 1, 1). One can also prove that e + 21 ∉ E_{n}(2) otherwise the lengths of the run (K_{e+8}, …, K_{e+22}) give (2, 2, 1, 1, 2, 1, 2, 2, 1, 1) which is impossible.

⋆ We have K_{e+22} = 1 otherwise (K_{e+17}, …, K_{e+22}) = (2, 2, 1, 1, 2, 2), which is impossible by Lemma 8 (ii).

⋆ We have K_{e+23} = 1 for e+21 ∉ E_{n}(2). Thus K_{e+24} = 2 otherwise (K_{e+22}, …, K_{e+24}) = (1, 1, 1).

⋆ K_{e+25} = 1 or 2.

If K_{e+25} = 1, then K_{e+26} = 2 otherwise (K_{e+19} …, K_{e+26}) = (1, 1, 2, 1, 1, 2, 1, 1). In particular, we have e + 24 ∈ E_{n}(2). Moreover, we then have K_{e+27} = 2 otherwise (K_{e+23}, …, K_{e+27}) = (1, 2, 1, 2, 1).

If K_{e+25} = 2, then K_{e+26} = 1 otherwise (K_{e+24}, …, K_{e+26}) = (2, 2, 2), and K_{e+27} = 2 otherwise (K_{e+22}, …, K_{e+27}) = (1, 1, 2, 2, 1, 1), which is impossible by Lemma 8 (ii), so that e + 25 ∈ E_{n}(2).

The proof is complete.

Lemma 22. We have |F_{n}(2) ∩ A_{n}| ≤ |F_{n}(2) ∩ B_{n}| and |G_{n}(2) ∩ A_{n}| ≤ |G_{n}(2) ∩ B_{n}|.

Proof. By definition of A_{n} and Lemmas 15 and 18, between two consecutive elements e and e′ of A_{n}, there is always at least an element of B_{n} having the same parity as e in the following cases

⋆ e ∈ E_{n}(2, 10), for then e + 10 ∈ B_{n} by Lemma 18.

⋆ e ∈ E_{n}(2, 6) and e + 6 ∈ B_{n}.

It remains to be studied the case where e, e + 6, e + 12 are consecutive in E_{n}(2), for then e and e + 6 are consecutive in E_{n}(2, 6).

In what follows, we consider two pairs (e, e+6) and (e+a, e+6+a) consecutive in (E_{n}(2, 6))^{2} where a is a positive integer. By Dirichlet’s pigeonhole principle, Lemma 22 follows if we show that between these two pairs, there is always at least two elements of B_{n} having the same parity as e. To prove that, we will use the configurations of Lemma 21.

1. By Lemma 18, we have e + 12 ∈ B_{n}.

2. By Lemma 21, if e + 25 ∉ E_{n}, then a ≥ 27

3. Let us show that, if e + 25 ∈ E_{n}, then a ≥ 33.

If e + 25 ∈ E_{n}, then K_{e+29} = 1 otherwise e + 25 and e + 27 are consecutive in E_{n}(2) which is impossible by Lemma 15. If e+28 ∈ E_{n}, then the lengths of the sequence (K_{e+14}, …, K_{e+28}) generate the run (2, 1, 2, 2, 1, 2, 2, 1, 2) whose lengths give the run (1, 2, 1, 2, 1) which is impossible by Lemma 8 (ii). Thus, we have K_{e+28} = 1 and hence K_{e+30} = 2. We notice that e + 30 ∉ E_{n}(2, 6) otherwise (K_{e+29}, …, K_{e+33}) = (1, 2, 1, 2, 1). We also have K_{e+31} = 1 otherwise the lengths of the sequence (K_{e+22}, …, K_{e+31}) give the impossible run (2, 2, 1, 1, 2, 2). Finally, we have K_{e+32} = 2 otherwise K_{e+33} = 2 and the lengths of the sequence (K_{e+26}, …, K_{e+33}) then give the impossible run (1, 2, 1, 2, 1). But we also have e + 32 ∉ E_{n}(2, 6) otherwise (K_{e+31}, …, K_{e+35}) = (1, 2, 1, 2, 1).

4. Now we are in a position to conclude the proof of Lemma 22.

Let (e, e + 6) and (e + a, e + 6 + a) be two consecutive pairs of (E_{n}(2, 6))^{2}. According to the above arguments, we have

⋆ If e + 25 ∉ E_{n}, then e + 12 and e + 24 are two elements of B_{n} comprised between these two pairs.

⋆ If e + 25 ∈ E_{n}, then e + 12 and e + 30 are two elements of B_{n} comprised between these two pairs.

The proof is complete.

Lemma 23. We have

||F_{n}(2)| − |G_{n}(2)|| ≤ \frac{t_{n} + k_{n} − n + 7}{3}.

Proof. By Lemmas 20 and 22, we have

|F_{n}(2)| ≤ |F_{n}(2) ∩ A_{n}| + |F_{n}(2) ∩ B_{n}| + 1
≤ 2|F_{n}(2) ∩ B_{n}| + 1
≤ 2|G_{n}(2) ∩ B_{n}| + 3
≤ 2|G_{n}(2)| + 3,

and similarly we get |G_{n}(2)| ≤ 2|F_{n}(2)| + 3. The relation |E_{n}(2)| = |F_{n}(2)| + |G_{n}(2)| implies that

\frac{|E_{n}(2)|}{3} − 1 ≤ |F_{n}(2)| ≤ \frac{2|E_{n}(2)|}{3} + 1

and similar inequalities for |G_{n}(2)| so that

||F_{n}(2)| − |G_{n}(2)|| ≤ \frac{|E_{n}(2)|}{3} + 2

and we conclude the proof by using Lemma 14.

Lemmas 17 and 23, used in Proposition 12, give at once the following estimate. Corollary 24. We have

|S_{n} − \frac{3n}{2}| ≤ \frac{t_{k_{n}} + k_{k_{n}} − k_{n}}{6} + 4.

We now are able to prove Theorem 4. Proof of Theorem 4. Using Corollary 24 and the inequalities t_{k_{n}} ≤ n + 1 − k_{n} from Lemma 5 and k_{k_{n}} ≤ 3k_{n}/4 + 3/2 from Theorem 3, we get

S_{n} ≤ \frac{3n}{2} + \frac{t_{k_{n}} + k_{k_{n}} − k_{n}}{6} + 4 ≤ \frac{5n}{3} − \frac{5k_{n}}{24} + \frac{53}{12}

and the lower bound k_{n} ≥ 3n/5 from Theorem 3 implies that

S_{n} ≤ \frac{37n}{24} + \frac{53}{12},

and since S_{k_{n}} ≥ n, we infer

k_{n} ≥ \frac{24n}{37} − 3.

The same method, now using the lower bound

S_{n} ≥ \frac{3n}{2} − \frac{t_{k_{n}} + k_{k_{n}} − k_{n}}{6} − 4 ≥ \frac{4n}{3} + \frac{5k_{n}}{24} − \frac{53}{12}

and the inequality S_{k_{n}} ≤ n + 1, leads to

k_{n} ≤ \frac{24n}{35} + 4.

At the end of this first step, we then have

\frac{24n}{37} − 3 ≤ k_{n} ≤ \frac{24n}{35} + 4 (n ≥ 1).  (10)

We repeat this process by defining the sequences (u_{m})_{m≥1} and (v_{m})_{m≥1} by

\{ \begin{matrix}u_{1} & = & \frac{24}{35} \\ u_{m+1} & = & \frac{6(1 − 3u_{m})}{u_{m}^{2} − 26u_{m} + 8} \end{matrix} and v_{m} = \frac{u_{m}}{3u_{m} − 1}.

It is easy to check that, for all positive integers m, we have \frac{1}{2} < u_{m} < 1 and \frac{1}{2} < v_{m} < 1 so that these two sequences are well-defined. Let us show by induction that, for all positive integers m, we have

nv_{m} − 4 ≤ k_{n} ≤ nu_{m} + 5 (n ≥ 1)  (11)

the case m = 1 being a consequence of (10). Assume estimate (11) is true for some m. Then, using induction hypothesis rewritten in the form k_{k_{n}} ≤ k_{n}u_{m} + 5, we get

S_{n} ≤ \frac{3n}{2} + \frac{t_{k_{n}} + k_{k_{n}} − k_{n}}{6} + 4 ≤ \frac{5n}{3} − \frac{k_{n} (2 − u_{m})}{6} + 5

and induction hypothesis used in the form k_{n} ≥ nv_{m} − 4 implies that

S_{n} ≤ \frac{n}{6} (u_{m}v_{m} − 2v_{m} + 10)−\frac{2u_{m} − 19}{3} = \frac{n (u_{m}^{2} + 28u_{m} − 10)}{6 (3u_{m} − 1)}−\frac{2u_{m} − 19}{3} = \frac{n}{v_{m+1}} −\frac{2u_{m} − 19}{3}

and the lower bound S_{k_{n}} ≥ n gives

k_{n} ≥ nv_{m+1} + \frac{v_{m+1} (2u_{m} − 19)}{3} = nv_{m+1} − \frac{2 (19 − 2u_{m}) (3u_{m} − 1)}{u_{m}^{2} + 28u_{m} − 10} ≥ nv_{m+1} − 4.

Similarly, the lower bound

S_{n} ≥ \frac{3n}{2} − \frac{t_{k_{n}} + k_{k_{n}} − k_{n}}{6} − 4 ≥ \frac{4n}{3} + \frac{k_{n} (2 − u_{m})}{6} − 5

and the inequality S_{k_{n}} ≤ n + 1, lead to

k_{n} ≤ nu_{m+1} + \frac{2u_{m+1} (11 − u_{m})}{3} = nu_{m+1} + \frac{4(11 − u_{m})(3u_{m} − 1)}{u_{m}^{2} − 26u_{m} + 8} ≤ nu_{m+1} + 5

which completes the proof of (11). We conclude by noticing that the sequence (u_{m}) converges to α.

Finally, estimates for t_{n} and o_{n} follow from relations t_{n} = S_{n} − n and o_{n} = n − t_{n}. The proof is complete.

7 Concluding remarks

Remark 25. There exist other identites analogue to Proposition 12. For instance, we were able to prove the following results.

(i) For all positive integers n, we have

k_{n} = \frac{2}{3} (n + ∑_{\begin{matrix}j=1 \\ (K_{2j−1},K_{2j})=(1,1) \end{matrix}}^{⌊k_{n}/2⌋} 1 − ∑_{\begin{matrix}j=1 \\ (K_{2j−1},K_{2j})=(2,2) \end{matrix}}^{⌊k_{n}/2⌋} 1) + r_{n}

where r_{1} = 1/3 and, for all integers n ≥ 2,

r_{n} = \begin{cases}−1/3, & if (K_{n−1}, K_{n}, K_{n+1}) = (1, 1, 2); \\ 0, & if (K_{n}, K_{n+1}) = (2, 1) \\ 1/3, & if (K_{n}, K_{n+1}) = (1, 1) or (K_{n−1}, K_{n}, K_{n+1}) = (2, 1, 2) \\ 2/3, & if (K_{n}, K_{n+1}) = (2, 2). \end{cases}

(ii) For all positive integers n, we have

t_{n} = \frac{k_{n}}{2} + ∑_{\begin{matrix}j=2 \\ (K_{j−1},K_{j})=(2,2) \end{matrix}}^{n} 1 + \frac{K_{n}}{2} − 1.

Although these identities are equivalent to Proposition 12, they seemed to be less handy to get fine estimates of the remainder term. Remark 26. Like the continuous case and the usual summation formulas (Euler, Euler– MacLaurin, Boole, etc), it might be useful to derive an identity of order two or more to improve on the error-term. In the discrete case, if we treat the sum in (5) by Abel summation, we get

∑_{j=1}^{m}(−1)^{j}a_{j} = \frac{(−1)^{m}a_{m} − a_{1}}{2} + \frac{(−1)^{m} (a_{m} − a_{m−1})}{4} + \frac{a_{2} − a_{1}}{4} − \frac{1}{4} ∑_{j=2}^{m−1}(−1)^{j}Δ^{2}a_{j}

where we set Δ^{2}a_{j} := a_{j+1} − 2a_{j} + a_{j−1} (j ≥ 2). Applied to the sequence (t_{j}) noticing that Δ^{2}t_{j} = K_{j+1} − K_{j}, this gives

∑_{j=1}^{k_{n}}(−1)^{j}t_{j} = \frac{(−1)^{k_{n}}t_{k_{n}}}{2} + \frac{(−1)^{k_{n}} (K_{k_{n}} − 1)}{4} + \frac{1}{4} − \frac{1}{4} ∑_{j=2}^{k_{n}−1}(−1)^{j} (K_{j+1} − K_{j})

for all integers n ⩾ 2 and, following the proof of Proposition 12, we infer that

S_{n} = \frac{3n}{2} − \frac{1}{4} ∑_{j=2}^{k_{n}−1}(−1)^{j} (K_{j+1} − K_{j}) + \frac{(−1)^{k_{n}}}{4} (K_{k_{n}} − 2c_{n})

where c_{n} is defined in Proposition 12. The trivial estimate of the sum gives

|∑_{j=2}^{k_{n}−1}(−1)^{j} (K_{j+1} − K_{j})| ≤ ∑_{j=2}^{k_{n}−1} |K_{j+1} − K_{j}| = ∑_{j=2}^{k_{n}−1} (k_{j+1} − k_{j}) = k_{k_{n}} − 2

where we used Lemma 5. Compared to (6), the saving is not significant.

8 Acknowledgments

We express our gratitude to the referee for his careful reading of the manuscript and the many valuable suggestions he provided.

References

[1] B. C. Berndt and L. Schoenfeld, Periodic analogues of the Euler–MacLaurin and Poisson summation formulas with applications to number theory, Acta Arith. 28 (1975), 23–68.

[2] S. Brlek, S. Dulucq, A. Ladouceur, and L. Vuillon, Combinatorial properties of smooth infinite words, Theor. Comp. Sci. 352 (2006), 306–317.

[3] A. Carpi, On repeated factors in C^{∞}-words, Inf. Process. Lett. 52 (1994), 289–294.

[4] V. Chvátal, Notes on the Kolakoski sequence, DIMACS Technical report, 1993.

[5] F. M. Dekking, What is the long range order in the Kolakoski sequence?, The Mathematics of Long–range Aperiodic Order, NATO Adv. Sci. Inst. Ser. C Maths. Phys. Sci., 489, Kluwer Acad. Publ., Dordrecht (1997), 115–125.

[6] R. Johnsonbaugh, Summing an alternating series, Amer. Math. Monthly 86 (1979), 637– 648.

[7] W. Kolakoski, Problem 5304: self generating runs, Amer. Math. Monthly 72 (1965), 674.

[8] E. J. Kupin and E. S. Rowland, Bounds on the frequency of 1 in the Kolakoski word, preprint (2008).

[9] K. O’Bryant, B. Reznick, and M. Serbinowska, Almost alternating sums, Amer. Math. Monthly 113 (2006), 673–688.

[10] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, published electronically

   at http://oeis.org.

[11] B. Steinsky, A recursive formula for the Kolakoski sequence, J. Integer Seq. 9 (2006), Article 06.3.7.

[12] PARI/GP, available at ftp://megrez.math.u-bordeaux.fr/pub/pari.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 11B83, 11B85. Keywords: Kolakoski sequence, Dirichlet’s pigeonhole principle.

(Concerned with sequence \underline{A000002}.)

Received November 7 2010; revised version received January 28 2011. Published in Journal of Integer Sequences, February 9 2011.

Return to Journal of Integer Sequences home page.