\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Bounds for the Kolakoski Sequence } \vskip 1cm \large Olivier Bordell\`es\\ 2 all\'{e}e de la Combe\\ 43000 Aiguilhe\\ France\\ \href{mailto:borde43@wanadoo.fr}{\tt borde43@wanadoo.fr} \ \\ \vskip .2in \ \\ Benoit Cloitre\\ 19 rue Louise Michel\\ 92300 Levallois-Perret\\ France\\ \href{mailto:benoit7848c@yahoo.fr}{\tt benoit7848c@yahoo.fr} \end{center} \vskip .2 in \theoremstyle{definition} \newtheorem{definition}{Definition} \newtheorem{example}[definition]{Example} \newtheorem{conjecture}[definition]{Conjecture} \theoremstyle{plain} \newtheorem{theorem}[definition]{Theorem} \newtheorem{corollary}[definition]{Corollary} \newtheorem{lemma}[definition]{Lemma} \newtheorem{proposition}[definition]{Proposition} \theoremstyle{remark} \newtheorem{remark}[definition]{Remark} \newcommand{\N}{\mathbb {N}} \newcommand{\Z}{\mathbb {Z}} \newcommand{\Q}{\mathbb {Q}} \newcommand{\R}{\mathbb {R}} \newcommand{\C}{\mathbb {C}} \newcommand{\K}{\mathbb {K}} \begin{abstract} The Kolakoski sequence $(K_n)$ is perhaps one of the most famous examples of self-describing 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 $1\over 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. \end{abstract} \section{Introduction} \label{s1} In 1965, Kolakoski \cite{kol} introduced an example of a self-generating sequence by creating the sequence defined in the following way. \begin{definition} \begin{itemize} \item[] \item[$\star$] We call {\it block} all sets of one or more identical digits. The number of digits in a block is the {\it length} of the block. \item[$\star$] The {\it Kolakoski sequence} is the sequence $(K_n)$ of blocks of $1$'s or $2$'s defined by $$\left\lbrace \begin{array}{rcl} K_1 &=& 1 \\ K_n & = & \text{{\rm length of the\ }} n\text{{\rm-th block}}. \end{array}\right. $$ \item[$\star$] We also define the partial sums $$S_n = \sum_{j=1}^{n} K_j.$$ \item[$\star$] The three following sequences $(k_n)$, $(o_n)$ and $(t_n)$ are related to $(K_n)$ and defined by $$\left\lbrace \begin{array}{rcl} k_0 &=& 0 \\ k_n &=& \underset{1 \leq j \leq n}{\min} \{j:S_j \geq n\} \quad (n \geq 1) \end{array} \right.$$ and $$o_n := \left | \{ 1 \leq j \leq n : K_j = 1 \} \right | \quad \text{and} \quad t_n := \left | \{ 1 \leq j \leq n : K_j = 2 \} \right |$$ where $|E|$ means the number of elements of the finite set $E$. \end{itemize} \end{definition} \begin{remark} \label{re1} We have $o_n+t_n=n$ and since $$S_n = \sum_{j=1}^{n} K_j = \sum_{\substack{j=1 \\ K_j = 1}}^{n} 1 + 2 \sum_{\substack{j=1 \\ K_j = 2}}^{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$. \end{remark} The following table shows the first terms of the sequences defined above. \begin{center} \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & & & & & & & & & & & & & & & & & \\ $n$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $12$ & $13$ & $14$ & $15$ & $16$ & $17$ \\ & & & & & & & & & & & & & & & & & \\ \hline & & & & & & & & & & & & & & & & & \\ $K_n$ & $1$ & $2$ & $2$ & $1$ & $1$ & $2$ & $1$ & $2$ & $2$ & $1$ & $2$ & $2$ & $1$ & $1$ & $2$ & $1$ & $1$ \\ & & & & & & & & & & & & & & & & & \\ \hline & & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} & & & \multicolumn{2}{c|}{} & & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} & & \multicolumn{2}{c|}{} \\ $n$-th block & $1$ & \multicolumn{2}{c|}{$2$} & \multicolumn{2}{c|}{$3$} & $4$ & $5$ & \multicolumn{2}{c|}{$6$} & $7$ & \multicolumn{2}{c|}{$8$} & \multicolumn{2}{c|}{$9$} & $10$ & \multicolumn{2}{c|}{$11$} \\ & & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} & & & \multicolumn{2}{c|}{} & & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} & & \multicolumn{2}{c|}{} \\ \hline & & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} & & & \multicolumn{2}{c|}{} & & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} & & \multicolumn{2}{c|}{} \\ $k_n$& $1$ & \multicolumn{2}{c|}{$2$} & \multicolumn{2}{c|}{$3$} & $4$ & $5$ & \multicolumn{2}{c|}{$6$} & $7$ & \multicolumn{2}{c|}{$8$} & \multicolumn{2}{c|}{$9$} & $10$ & \multicolumn{2}{c|}{$11$} \\ & & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} & & & \multicolumn{2}{c|}{} & & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{} & & \multicolumn{2}{c|}{} \\ \hline & & & & & & & & & & & & & & & & & \\ $S_n$ & $1$ & $3$ & $5$ & $6$ & $7$ & $9$ & $10$ & $12$ & $14$ & $15$ & $17$ & $19$ & $20$ & $21$ & $23$ & $24$ & $25$ \\ & & & & & & & & & & & & & & & & & \\ \hline & & & & & & & & & & & & & & & & & \\ $o_n$ & $1$ & $1$ & $1$ & $2$ & $3$ & $3$ & $4$ & $4$ & $4$ & $5$ & $5$ & $5$ & $6$ & $7$ & $7$ & $8$ & $9$ \\ & & & & & & & & & & & & & & & & & \\ \hline & & & & & & & & & & & & & & & & & \\ $t_n$ & $0$ & $1$ & $2$ & $2$ & $2$ & $3$ & $3$ & $4$ & $5$ & $5$ & $6$ & $7$ & $7$ & $7$ & $8$ & $8$ & $8$ \\ & & & & & & & & & & & & & & & & & \\ \hline \end{tabular} \end{center} This sequence, which belongs to the online Encyclopedia of Integer Sequences \cite{slo}, has been studied by many authors (see \cite{brl,car,chv,dek,ste} for instance), and some conjectures have been made. In particular, no one knows yet whether the density of the $1$'s is equal to $1\over 2$, e.g. \begin{alignat}{1} \underset{n \rightarrow \infty}{\lim} \frac{o_n}{n} = \dfrac{1}{2}. \label{e1} \end{alignat} This problem seems to be very tricky. It is equivalent to proving that \begin{alignat}{1} S_n = \frac{3n}{2} + o(n) \quad \text{or} \quad k_n = \frac{2n}{3}+ o(n) \quad {\rm (} n \longrightarrow \infty {\rm )}. \label{e2} \end{alignat} These estimates come from the asymptotic formula \begin{alignat}{1} \sum_{j=1}^{n} (-1)^{k_j} = o(n) \quad {\rm (} n \longrightarrow \infty {\rm )} \label{e3} \end{alignat} that we conjecture (See Corollary~\ref{cor1}). Such sums are frequent in number theory. For instance, the Mertens function $M(n) = \sum_{j=1}^{n} \mu(j)$, where $\mu$ is the M\"{o}bius function, or the summatory function $L(n) = \sum_{j=1}^{n} \lambda(j)$ of the Liouville $\lambda$-function, are strongly related to the prime number theorem. Another interesting example can be found in the paper \cite{bry} 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 (\ref{e1}), (\ref{e2}) or (\ref{e3}). 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~\ref{le2} for $(k_n)$). $$\begin{array}{lcl} n \leq S_n < 2n & \text{and} & \dfrac{n}{2} < k_n \leq n \\ & \\ 0 \leq t_n < n & \text{and} & 0 < o_n \leq n. \end{array}$$ The aim of this work is to give better bounds than the above trivial inequalities. More precisely, we will first prove the following result. \begin{theorem} \label{t0} For all positive integers $n$, we have $$\begin{array}{lcl} \dfrac{4n}{3} - 1 \leq S_n \leq \dfrac{5n}{3} & \text{and} & \dfrac{3n}{5} \leq k_n \leq \dfrac{3n}{4} + \dfrac{3}{2}. \\ & & \\ \dfrac{n}{3} - 1 \leq t_n \leq \dfrac{2n}{3} & \text{and} & \dfrac{n}{3} \leq o_n \leq \dfrac{2n}{3} + 1. \end{array}$$ \end{theorem} 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. \begin{theorem} \label{t05} Let $\alpha \doteq 0,6764 \dotsc$ be the unique root of the polynomial $P = X^3 - 26X^2+26X-6$ in the interval $\left( {1 \over 2},1 \right)$ and we set $$\beta := \frac{\alpha^2 + \alpha -1}{6(3\alpha - 1)} \doteq 0.021703504 \dotsc$$ For all positive integers $n$, we have $$\begin{array}{lcl} \left( \dfrac{3}{2} - \beta \right) n - 6 \leq S_n \leq \left( \dfrac{3}{2} + \beta \right) n + 6 & \text{and} & \left( \dfrac{\alpha}{3 \alpha -1} \right) n - 4 \leq k_n \leq \alpha n + 5. \\ & & \\ \left( \dfrac{1}{2} - \beta \right) n - 6 \leq t_n \leq \left( \dfrac{1}{2} + \beta \right) n + 6 & \text{and} & \left( \dfrac{1}{2} - \beta \right) n - 6 \leq o_n \leq \left( \dfrac{1}{2} + \beta \right) n + 6. \end{array}$$ \end{theorem} Thus we have unconditionally $$\left | \frac{o_n}{n} - \frac{1}{2} \right | \leq 0.021703504 \dotsc + \frac{6}{n}.$$ Although these bounds are still far from (\ref{e2}), they improve on the results established in \cite{kup} if $n$ is sufficiently large, where it is proven that, if the limit $\underset{n\rightarrow \infty}{\lim} (o_n/n)$ exists, then $$\left | \lim_{n \rightarrow \infty} \frac{o_n}{n} - \frac{1}{2} \right | \leq \frac{17}{762} \doteq 0.0223097 \dotsc$$ and our bounds are even slightly better than their ``semi-rigorous" bound $$\left | \lim_{n \rightarrow \infty} \frac{o_n}{n} - \frac{1}{2} \right | \leq \frac{1}{46} \doteq 0.02173913 \dotsc$$ Nevertheless, it should be mentioned that Theorem~\ref{t05} does not improve on Chv\'{a}tal's results (see \cite{chv}). The sketch of the proof is the following one. \begin{itemize} \item[$\star$] We first establish Proposition~\ref{pro2} which prompts to introduce the set $E_n$ of indexes $j \in \left\lbrace 1, \dotsc,n \right\rbrace $ 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. \item[$\star$] 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 \in E_n$ such that $e+2 \in E_n$ (Lemma~\ref{le356}). \item[$\star$] Then we studied the gaps between consecutive elements of $E_n(2)$ (Lemmas~\ref{le341} and \ref{le36}) and defined two subsets $A_n$ and $B_n$ of $E_n(2)$ (Lemmas~\ref{le10} and~\ref{le11}) to refine the estimates. \end{itemize} 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~\ref{le105}). 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~\ref{le11}) to accurately estimate the remainder term. However, such a strategy does not seem to prove estimates of the form $\ll n^{\theta}$ with $0 \leq \theta < 1$. Finally, it should be mentioned that all the numeric computations have been made using PARI/GP system \cite{par}. \section{Some properties of the sequence $(k_n)$} \label{s2} Steinsky \cite{ste} proved the following results. \begin{lemma} \label{le1} Let $n \geq 2$ be an integer. Then we have \begin{enumerate} \item[\rm{(i)}] $S_{k_{n-1}} \in \left\lbrace n-1,n \right\rbrace \ $ {\rm and} $ \ k_n = k_{n-1} + n - S_{k_{n-1}}$. \item[\rm{(ii)}] $k_n - k_{n-1} = \left | K_n - K_{n-1} \right |$. \item[\rm{(iii)}] $k_n = n - t_{k_{n-1}}$. \end{enumerate} \end{lemma} We deduce the following consequences. \begin{lemma} \label{le2} The sequence $(k_n)$ is non-decreasing and, for all positive integers $n$, we have $$\frac{n+1}{2} \leq k_n \leq n.$$ \end{lemma} \begin{proof} Using Lemma~\ref{le1} (ii), we get $k_n - k_{n-1} = \left | K_n - K_{n-1} \right | \geq 0$. The inequality $k_n \leq n$ comes from Lemma~\ref{le1} (iii). Moreover, we also have $S_{k_n} \in \{n, n+1 \}$ by Lemma~\ref{le1}, so that $2k_n > S_{k_n} \geq n$ and hence $k_n > n/2$. Since $k_n$ is an integer, we get the desired lower bound. \end{proof} \begin{lemma} \label{le33} For all integers $n \geq 2$, the number of blocks of length equal to $2$ between the letters $K_1$ and $K_n$ is given by $n-k_n$. \end{lemma} \begin{proof} Using Lemma~\ref{le1} (ii), for all integers $j \geq 2$, we have $$\left( K_{j-1},K_j \right) = (1,1) \ \text{or } (2,2) \Longleftrightarrow k_{j-1} = k_j$$ so that the number in question is $$\sum_{\substack{j=2 \\ k_{j-1} = k_j}}^{n} 1 = \sum_{j=2}^{n} 1 - \sum_{\substack{j=2 \\ k_{j-1} \not = k_j}}^{n} 1 = n-1 - \sum_{j=2}^{n} \left( k_j - k_{j-1} \right) = n-k_n.$$ This proves Lemma~\ref{le33}. \end{proof} \section{Some properties of the sequence $(K_n)$} \label{s3} In what follows, we list some situations which cannot appear in the sequence $(K_n)$. We will call {\it 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 \cite{brl,car} for instance), is based upon the property that the sequence does not contain cubes, that is, runs of the form $xxx$. \begin{lemma} \label{le0} The following runs cannot appear in the sequence $(K_n)$. \begin{enumerate} \item[{\rm (i)}] $(1,1,1,\dotsc) \ $ {\rm and} $ \ (2,2,2,\dotsc)$. \item[{\rm (ii)}] $(1,2,1,2,1) \ $, $ \ (2,1,2,1,2)$, $ \ (1,1,2,2,1,1) \ $ {\rm and} $ \ (2,2,1,1,2,2)$. \item[{\rm (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) \ $ {\rm and} $\ (2,1,1,2,1,1,2,1,1)$. \item[{\rm (iv)}] $(2,1,2,1,1,2,1,1,2,1,2) \ $ {\rm and} $ \ (2,1,2,1,1,2,2,1,2,1,2).$ \item[{\rm (v)}] $(2,1,2,2,1,1,2,1,2,2,1,1,2,1,1,2,2) \ $ {\rm and} $ \ (2,1,2,1,1,2,2,1,2,2,1,1,2,1,1,2,2)$. \item[{\rm (vi)}] $(2,1,2,2,1,1,2,1,1,2,2,1,2,2,1,1,2) \ $ {\rm and} $ \ (2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,2)$. \item[{\rm (vii)}] $(2,1,2,2,1,1,2,1,1,2,2,1,2,2,1,1,2,1,1,2,2)$. \end{enumerate} \end{lemma} \begin{proposition} \label{t1} For all positive integers $n$, we have $$K_{S_n} = \frac{3+(-1)^n}{2} \quad \text{and} \quad K_{1+S_n} = \frac{3+(-1)^{n+1}}{2}.$$ \end{proposition} \begin{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. \begin{alignat}{1} \text{{\it For all positive integers}\ } n, \ S_n \ \text{{\it is the index of the last element of the\ }} n\text{{\it-th block}}. \label{e4} \end{alignat} The assertion (\ref{e4}) is clearly true for $n=1$. Assume it is true for some $n \geq 1$. By induction hypothesis, we get $$S_{n+1} = S_n + K_{n+1} = \left\lbrace \begin{array}{c} S_n + 1 \\ \text{or} \\ S_n +2 \end{array} \right. = \ \left\lbrace \begin{array}{l} \text{index of the unique element of the } (n+1)\text{{\rm-th block}} \\ \text{or} \\ \text{index of the last element of the } (n+1)\text{{\rm-th block}} \end{array} \right. $$ 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 (\ref{e4}). \item[] Now we can prove Proposition~\ref{t1}. 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~\ref{t1}. \end{proof} \begin{corollary} \label{cor1} For all positive integers $n$, we have $$K_n = \dfrac{3+(-1)^{k_n}}{2}.$$ \end{corollary} \begin{proof} By Lemma~\ref{le1}, we have $$S_{k_n} = \begin{cases} n, & \text{if } k_n \not = k_{n+1}; \\ n+1, & \text{if } k_n = k_{n+1}; \end{cases} $$ so that $$K_n = K_{S_{k_n}} = \frac{ 3+(-1)^{k_n}}{2} \quad \text{if } \ k_n \not = k_{n+1}$$ and $$K_{n+1} = K_{S_{k_n}} = \frac{ 3+(-1)^{k_n}}{2} = \frac{ 3+(-1)^{k_{n+1}}}{2} \quad \text{if } \ k_n = k_{n+1}$$ which completes the proof. \end{proof} \begin{corollary} \label{cor3} For all positive integers $n$, we have $$\sum_{j=1}^{n} (-1)^j K_j = 2S_{S_n} - 3 S_n.$$ \end{corollary} \begin{proof} By induction, the case $n=1$ being obvious. Assume the equality is true for some positive integer $n$. Noticing that $\left [ S_n+1, S_{n+1} \right ] \cap \Z = \left \{ S_n + 1 \right \}$ or $\left \{ S_n + 1, S_{n+1} \right \}$ according to $K_{n+1} = 1$ or $2$ and using Proposition~\ref{t1} and the induction hypothesis, we get \begin{equation*} \begin{split} 2S_{S_{n+1}} - 3 S_{n+1} &= \begin{cases} 2S_{S_n} - 3 S_n + 2K_{S_n+1} -3, & \text{if } K_{n+1} = 1; \\ & \\ 2S_{S_n} - 3 S_n + 2K_{S_n+1} -3 + 2K_{S_{n+1}} - 3, & \text{if } K_{n+1} = 2; \end{cases} \\ & \\ &= \begin{cases} 2S_{S_n} - 3 S_n + (-1)^{n+1}, & \text{if } K_{n+1} = 1; \\ & \\ 2S_{S_n} - 3 S_n + 2(-1)^{n+1}, & \text{if } K_{n+1} = 2; \end{cases} \\ & \\ &= 2S_{S_n} - 3 S_n + (-1)^{n+1}K_{n+1} \\ & \\ &= \sum_{j=1}^{n} (-1)^j K_j + (-1)^{n+1}K_{n+1} = \sum_{j=1}^{n+1} (-1)^j K_j \\ \end{split} \end{equation*} as required. The proof is complete. \end{proof} \section{A useful identity} \label{s4} In what follows, $\lfloor x \rfloor$ is the integer part of $x \in \R$. \begin{proposition} \label{pro2} For all positive integers $n$, we have $$S_n = \frac{3n}{2} + \frac{1}{2} \left( \sum_{\substack{j=1 \\ K_{2j} = 2}}^{\lfloor k_n/2 \rfloor} 1 - \sum_{\substack{j=1 \\ K_{2j+1} = 2}}^{\lfloor(k_n-1)/2 \rfloor} 1 \right) + \frac{(-1)^{k_n} - 1}{4} - \frac{(-1)^{k_n} c_n}{2}$$ where $c_n = \begin{cases} 1, & \text{if } K_n = K_{n+1}; \\ 0, & \text{if } K_n \not = K_{n+1}. \end{cases}$. \end{proposition} \begin{proof} Using Corollary~\ref{cor3} with $k_n$ instead of $n$, we get \begin{equation*} \begin{split} \sum_{j=1}^{k_n} (-1)^j K_j &= 2S_{S_{k_n}} - 3 S_{k_n} \\ &= \begin{cases} 2S_{n+1} - 3n-3, & \text{if } K_n = K_{n+1}; \\ 2S_n - 3n, & \text{if } K_n \not = K_{n+1}; \\ \end{cases} \\ & \\ &= \begin{cases} 2S_{n} - 3n + 2K_{n+1} -3, & \text{if } K_n = K_{n+1}; \\ 2S_n - 3n, & \text{if } K_n \not = K_{n+1}; \\ \end{cases} \\ & \\ &= 2S_n - 3n + (-1)^{k_n} c_n, \end{split} \end{equation*} where we used Corollary~\ref{cor1}. Besides, by Abel summation, we have for all $m \geq 1$ \begin{equation*} \begin{split} \sum_{j=1}^{m} (-1)^j K_j &= (-1)^m \sum_{j=1}^{m} K_j - \sum_{j=1}^{m-1} \left\lbrace (-1)^{j+1} - (-1)^j \right\rbrace \sum_{h=1}^{j} K_h \\ &= (-1)^m S_m + 2 \sum_{j=1}^{m-1} (-1)^j S_j = 2 \sum_{j=1}^{m} (-1)^j S_j - (-1)^{m} S_m \\ \end{split} \end{equation*} so that $$S_n = \frac{3n}{2} + \sum_{j=1}^{k_n} (-1)^{j} S_j - \frac{(-1)^{k_n}}{2} \left( S_{k_n} + c_n \right)$$ The relation $S_j = j + t_j$ implies $$S_n = \frac{3n}{2} - \frac{(-1)^{k_n} t_{k_n}}{2} + \sum_{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 \begin{alignat}{1} \sum_{j=1}^{m} (-1)^j a_j = \frac{(-1)^m a_m - a_1}{2} + \frac{1}{2} \sum_{j=2}^{m} (-1)^j \left( a_j - a_{j-1} \right) \label{e5} \end{alignat} which can be viewed as a discrete analogue of Boole's summation formula of order $1$ (see \cite{ber, joh} for instance) and which implies here that \begin{equation*} \begin{split} \sum_{j=1}^{k_n} (-1)^j t_j &= \frac{(-1)^{k_n} t_{k_n}}{2} + \frac{1}{2} \sum_{j=2}^{k_n} (-1)^j \left( K_{j} - 1 \right) \\ & = \frac{(-1)^{k_n} t_{k_n}}{2} + \frac{1}{2} \sum_{\substack{j=2 \\ K_j = 2}}^{k_n} (-1)^j \\ &= \frac{(-1)^{k_n} t_{k_n}}{2} + \frac{1}{2} \left( \sum_{\substack{j=1 \\ K_{2j} = 2}}^{\lfloor k_n/2 \rfloor} 1 - \sum_{\substack{j=1 \\ K_{2j+1} = 2}}^{\lfloor (k_n-1)/2 \rfloor} 1 \right), \\ \end{split} \end{equation*} which concludes the proof. \end{proof} \section{Proof of Theorem~\ref{t0}} \label{s5} We are now in a position to prove Theorem~\ref{t0}, for which one may suppose $n \geq 4$ and whose results come from trivial estimates of the sums of Proposition~\ref{pro2}. Considering the four cases $\left( K_n,K_{n+1} \right) = (1,1), \ (2,2), \ (1,2)$ and $(2,1)$, the trivial estimate \begin{alignat}{1} \left | \sum_{\substack{j=1 \\ K_{2j} = 2}}^{\lfloor n/2 \rfloor} 1 - \sum_{\substack{j=1 \\ K_{2j+1} = 2}}^{\lfloor (n-1)/2 \rfloor} 1 \right | \leq t_n -1 \label{e6} \end{alignat} applied to Proposition~\ref{pro2} allows us to get the inequalities \begin{alignat}{1} n+\frac{k_n}{2} - \frac{1}{2} \leq S_n \leq 2n - \frac{k_n}{2}. \label{e7} \end{alignat} On the other hand, the inequality $$\sum_{\substack{j=1 \\ K_{2j} = 2}}^{\lfloor n/2 \rfloor} 1 \leq \frac{n}{2}$$ used in Proposition~\ref{pro2} implies that $$S_n \leq \frac{3n}{2} + \frac{k_n}{4}$$ and the use of (\ref{e7}) rewritten as $k_n \leq 4n - 2S_n$ gives $$2S_n \leq 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} \geq 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 := \left\lbrace j \in \left\lbrace 1, \dotsc,n \right\rbrace : K_j = 2\right\rbrace$ 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 \in E_n$ such that $e$ and $e+a$ are consecutive in $E_n$ with $a \geq 4$. Then we have $K_{e+1} = K_{e+2} = K_{e+3} = 1$ which is impossible by Lemma~\ref{le0} (i). We infer that $E_n$ is a subset of $\left\lbrace 1, \dotsc, n \right\rbrace$ whose gaps between two consecutive elements are at most $3$, so that $$n \leq 3 \left( |E_n|+1 \right) = 3 \left( t_n+1 \right)$$ 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 \leq n+1-t_{k_n}$ gives the upper bound for $k_n$. Theorem~\ref{t0} is completely proven. \qed \section{Proof of Theorem~\ref{t05}} \label{s6} The proof of Theorem~\ref{t0} 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 \in \left\lbrace 1,\dotsc,99\right\rbrace$, and we may suppose $n \geq 100$. We use the set $E_n$ introduced in the proof of Theorem~\ref{t0} and define the two following subsets. \begin{equation*} \begin{split} F_n & := \left\lbrace 2j : 1 \leq j \leq \lfloor n/2 \rfloor \ \text{and} \ K_{2j} = 2\right\rbrace \\ & \\ G_n & := \left\lbrace 2j+1 : 1 \leq j \leq \lfloor (n-1)/2 \rfloor \ \text{and} \ K_{2j+1} = 2 \right\rbrace \\ \end{split} \end{equation*} and, for all sets of integers $E$ and all positive integers $a$ and $b$, we set $$E \left( a \right) := \left\lbrace e \in E : e \ \text{and} \ e+a \ \text{{\rm are consecutive in\ }} E \right\rbrace \quad \text{and} \quad 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)$). \begin{example} \label{ex1} Here are the main sets used in the proof ($n=100$). \begin{equation*} \begin{split} \star \; & E_{100} = \left\lbrace 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, \right. \\ & \left. 56,57,60,62,63,65,66,69,72,74,75,77,80,81,83,84,87,89,90,92,93,96,99,100 \right\rbrace. \\ & \\ \star \; & F_{100} = \left\lbrace 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 \right\rbrace. \\ & \\ \star \; & G_{100} = \left\lbrace 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\right\rbrace. \\ & \\ \star \; & E_{100}(1) \cup E_{100}(3) = \left\lbrace 2,3,8,11,12,15,18,21,26,27,30,35,38,39,44,47,50,53,56,57,62,65, \right. \\ & \left. 66,69,74,77,80,83,84,89,92,93,96,99 \right\rbrace. \\ & \\ \star \; & E_{100}(2) = \left\lbrace 6,9,19,24,33,36,42,45,54,60,63,72,75,81,87,90 \right\rbrace. \\ & \\ \star \; & F_{100}(2) = \left\lbrace 6,24,36,42,54,60,72,90 \right\rbrace \quad \text{and} \quad G_{100}(2) = \left\lbrace 9,19,33,45,63,75,81,87 \right\rbrace. \\ & \\ \star \; & A_{100} = \left\lbrace 9,36,54,75,81 \right\rbrace \quad \text{and} \quad B_{100} = \left\lbrace 6,19,24,33,42,45,60,63,72,87 \right\rbrace. \\ \end{split} \end{equation*} \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline & & & & & & & & & \\ {\bf Set} & $E_{100}$ & $F_{100}$ & $G_{100}$ & $E_{100}(1) \cup E_{100}(3)$ & $E_{100}(2)$ & $F_{100}(2)$ & $G_{100}(2)$ & $A_{100}$ & $B_{100}$ \\ & & & & & & & & & \\ \hline & & & & & & & & & \\ {\bf Cardinal} & $t_{100} = 51$ & $26$ & $25$ & $100-k_{100} = 34$ & $16$ & $8$ & $8$ & $5$ & $10$ \\ & & & & & & & & & \\ \hline \end{tabular} \end{center} \end{example} The main purpose of this section is to provide better estimates of $\Bigl | |F_n| - |G_n| \Bigr |$ than the trivial bound (\ref{e6}) used in the proof of Theorem~\ref{t0}. To this end, we first study some properties of the sets $E_n(1) \cup E_n(3)$ and $E_n(2)$. \begin{lemma} \label{le5} We have $|E_n(1) \cup E_n(3)| = n-k_n + \varepsilon_n \ $ where $ \ \varepsilon_n \in \left\lbrace -1,0,1 \right\rbrace$. \end{lemma} \begin{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{equation*} \begin{split} & e \in E_n(1) \Longleftrightarrow K_e = K_{e+1} = 2. \\ & e \in E_n(3) \Longleftrightarrow K_{e} = K_{e+3} = 2 \ \text{and\ } K_{e+1} = K_{e+2} = 1. \\ \end{split} \end{equation*} We infer that $|E_n(1) \cup 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) \cup E_n(3)| = n-k_n + \varepsilon_n $$ by Lemma~\ref{le33}. \end{proof} \begin{lemma} \label{le341} The gaps between two consecutive elements of $E_n(2)$ can only be equal to $3, \ 5, \ 6, \ 9 \ \text{or} \ 10.$ \end{lemma} \begin{proof} \item[] 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 : \begin{itemize} \item[$\star$] equal to $1$, then there exists $e \in E_n$ such that $e,e+1,e+2,e+3 \in E_n$ and therefore we have $$\left( K_e,\dotsc,K_{e+3} \right) = \left( 2,2,2,2 \right)$$ which is impossible by Lemma~\ref{le0} (i). \item[$\star$] equal to $2$, then there exists $e \in E_n$ such that $e,e+2,e+4 \in E_n$ and we have $$\left( K_e,\dotsc,K_{e+4} \right) = \left( 2,1,2,1,2 \right)$$ which is impossible by Lemma~\ref{le0} (ii). \item[$\star$] equal to $4$, then there exists $e \in E_n$ such that $e,e+2,e+4,e+6 \in E_n$ and we have $$\left( K_e,\dotsc,K_{e+6} \right) = \left( 2,1,2,1,2,1,2 \right)$$ which is impossible by Lemma~\ref{le0} (ii). \item[$\star$] equal to $7$, then there exists $e \in E_n$ such that $$\left( K_{e+4},\dotsc,K_{e+8} \right) = \left( 1,2,1,2,1 \right).$$ 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 \in E_n(2)$. We infer that $K_{e+5} = 2$, otherwise $\left( K_{e+4},K_{e+5},K_{e+6} \right) = (1,1,1)$ and $K_{e+8} = 1$, for $K_{e+9} = 2$. This run is impossible by Lemma~\ref{le0} (ii). \item[$\star$] equal to $8$, then there exists $e \in E_n$ such that $$\left( K_e,\dotsc,K_{e+10} \right) = \left( 2,1,2,1,1,2,1,1,2,1,2 \right).$$ 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 \in E_n(2)$, and similarly $K_{e+6} = 1$ otherwise $e+4 \in 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 \in E_n(2)$. This run is impossible by Lemma~\ref{le0} (iv). \end{itemize} 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 \geq 11$. We then have $$K_e = K_{e+2} = 2 \quad \text{and} \quad K_{e+1} = K_{e+4} = 1$$ for if $K_{e+4} = 2$, then $e+2 \in E_n(2)$ contrary to the hypothesis. Let us treat two cases. \begin{itemize} \item[$\star$] $\mathbf{1}^{\text{st}}$ {\bf case} : $K_{e+3} = 1$. Then $K_{e+5} = 2$. \begin{enumerate} \item[{\rm (i)}] If $K_{e+6} = 1$, then we have $$\left( K_e, \dotsc,K_{e+10} \right) = (2,1,2,1,1,2,1,1,2,2,1).$$ Indeed, if $K_{e+7} = 2$, then we have $e+5 \in 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 \in E_n(2)$. \item[] 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 \in E_n(2)$. This case is then impossible. \item[{\rm (ii)}] If $K_{e+6} = 2$, then we have $$\left( K_e, \dotsc,K_{e+10} \right) = (2,1,2,1,1,2,2,1,1,2,1).$$ Indeed, $K_{e+8} = 1$ otherwise $e+6 \in 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$. \end{enumerate} \item[$\star$] $\mathbf{2}^{\text{nd}}$ {\bf case} : $K_{e+3} = 2$. Then $K_{e+5} = 1$ otherwise $e+3 \in E_n(2)$. We also have $$\left( K_e, \dotsc,K_{e+10} \right) = (2,1,2,2,1,1,2,1,1,2,1 \ \text{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 \in E_n(2)$, and then $K_{e+9} = 2$. \begin{enumerate} \item[{\rm (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~\ref{le0} (iii), nor be equal to $2$ otherwise $e+9 \in E_n(2)$. \item[{\rm (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 \in E_n(2)$. \end{enumerate} \end{itemize} The proof is complete. \end{proof} \begin{lemma} \label{le342} The gaps between two consecutive elements of $E_n(1) \cup E_n(3)$ can only be equal to $1, \ 3 \ \text{or} \ 5.$ \end{lemma} \begin{proof} They cannot be equal to $2$ for, if $e$ and $e+2$ are consecutive in $E_n(1) \cup E_n(3)$, then we have $e \in E_n(2)$. They cannot be equal to $4$ either, for if $e$ and $e+4$ are consecutive $E_n(1) \cup E_n(3)$, then $e$ can neither belong to $E_n(1)$ otherwise $e+1 \in E_n(3)$ and then $e$ and $e+1$ are consecutive in $E_n(1) \cup E_n(3)$, nor belong to $E_n(3)$ otherwise $e+3 \in E_n(1)$ and then $e$ and $e+3$ are consecutive in $E_n(1) \cup E_n(3)$, which is a contradiction. Now it only remains to be shown that gaps between two consecutive elements of $E_n(1) \cup E_n(3)$ are at most equal to $5$. Suppose that $e$ and $e+a$ are consecutive in $E_n(1) \cup E_n(3)$ with $a \geq 6$. \begin{itemize} \item[$\star$] If $e \in E_n(1)$, then $K_{e+2} = 1$. Moreover, $K_{e+4} = 1$ otherwise $e+1 \in E_n(3)$. Hence $K_{e+3} = 2$. Similarly, $K_{e+6} = 1$ otherwise $e+3 \in E_n(3)$. Therefore $K_{e+5} = 2$. Hence we have $$\left( K_{e+2}, \dotsc,K_{e+6} \right) = \left( 1,2,1,2,1 \right)$$ which is impossible by Lemma~\ref{le0} (ii). \item[$\star$] If $e \in E_n(3)$, then $K_{e+1} = K_{e+2} = 1$ and $K_{e+4} = 1$ otherwise $e+3 \in E_n(1)$. Similarly, $K_{e+6} = 1$ otherwise $e+3 \in E_n(3)$. Hence $K_{e+5} = 2$ and we have $$\left( K_{e+2}, \dotsc,K_{e+6} \right) = \left( 1,2,1,2,1 \right)$$ which is impossible by Lemma~\ref{le0} (ii). \end{itemize} The proof is complete. \end{proof} \begin{lemma} \label{le356} We have $$\Bigl | |F_n| - |G_n| \Bigr | \leq \Bigl | |F_n(2)| - |G_n(2)| \Bigr | + 3.$$ \end{lemma} \begin{proof} By Lemma~\ref{le342}, the set $E_n(1) \cup 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) \cup E_n(3)$ is equal to $0$ or $1$, i.e. $$\left | F_n \cap \left( E_n(1) \cup E_n(3) \right) \right | = \left | G_n \cap \left( E_n(1) \cup E_n(3) \right) \right | + 0 \ \text{or } 1$$ and therefore \begin{equation*} \begin{split} |F_n| & \leq |F_n \cap E_n(2)| + \left | F_n \cap \left( E_n(1) \cup E_n(3) \right) \right | + 1 \\ &= |F_n(2)| + \left | F_n \cap \left( E_n(1) \cup E_n(3) \right) \right | + 1 \\ & \leq |F_n(2)| + \left | G_n \cap \left( E_n(1) \cup E_n(3) \right) \right | + 2 \\ & \leq |G_n| + |F_n(2)| - |G_n(2)| + 3 \\ \end{split} \end{equation*} and similarly we have $|G_n| \leq |F_n| + |G_n(2)| - |F_n(2)| + 3$ which completes the proof of Lemma~\ref{le356}. \end{proof} \begin{lemma} \label{le36} There do not exist four consecutive numbers with the same parity in $E_n(2)$. \end{lemma} \begin{proof} 1. If $e$ and $e+6$ are consecutive in $E_n(2)$, then we have \begin{alignat}{1} \left( K_e,\dotsc,K_{e+6} \right) = \left\lbrace \begin{array}{rl} (2,1,2,2,1,1,2) & \text{if } e+2 \in E_n(1); \\ & \\ (2,1,2,1,1,2,2) & \text{if } e+2 \in E_n(3). \end{array} \right. \label{e8} \end{alignat} Indeed, suppose $e+2 \in E_n(1)$. Then $\left( K_e,\dotsc,K_{e+3} \right) = (2,1,2,2)$, and hence $K_{e+4} = 1$, and $K_{e+5} =1$ otherwise either $e+3 \in E_n(2)$ or $e+2 \in E_n(3)$. A similar argument applies if $e+2 \in E_n(3)$. \item[] If $e$ and $e+10$ are consecutive in $E_n(2)$, then if $e+2 \in E_n(1)$, a similar argument as above proves that $$\left( K_e,\dotsc,K_{e+10} \right) = (2,1,2,2,1,1,2,1,1,2,2).$$ Besides, we have $e+2 \not \in E_n(3)$. Indeed, if $e+2 \in E_n(3)$, then we get $$\left( K_e,\dotsc,K_{e+10} \right) = (2,1,2,1,1,2,1,1,2,1,2) \quad \text{or} \quad (2,1,2,1,1,2,2,1,2,1,2)$$ and these two runs are impossible by Lemma~\ref{le0} (iv). \item[] 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$. \begin{itemize} \item[$\star$] $\mathbf{1}^{\text{st}}$ {\bf case} : Suppose that $e$, $e+6$ and $e+16$ are consecutive in $E_n(2)$. By the arguments above, we have $$\left( K_e,\dotsc,K_{e+16} \right) = (2,1,2,2,1,1,2,1,2,2,1,1,2,1,1,2,2)$$ or $$\left( K_e,\dotsc,K_{e+16} \right) = (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~\ref{le0} (v). \item[$\star$] $\mathbf{2}^{\text{nd}}$ {\bf case} : Suppose that $e$, $e+10$ and $e+16$ are consecutive in $E_n(2)$. By the arguments above, we have $$\left( K_e,\dotsc,K_{e+16} \right) = (2,1,2,2,1,1,2,1,1,2,2,1,2,2,1,1,2)$$ or $$\left( K_e,\dotsc,K_{e+16} \right) = (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~\ref{le0} (vi). \item[$\star$] $\mathbf{3}^{\text{rd}}$ {\bf case} : Suppose that $e$, $e+10$ and $e+20$ are consecutive in $E_n(2)$. By the arguments above, we have $$\left( K_e,\dotsc,K_{e+20} \right) = (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~\ref{le0} (vii). \end{itemize} Since the numbers have the same parity and they are consecutive in $E_n(2)$, there is no other possibility according to Lemma~\ref{le341}. \item[] 3. We are now able to prove Lemma~\ref{le36}. 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 (\ref{e8}) shows that each case leads to a run appearing in Lemma~\ref{le0} (ii), which concludes the proof. \end{proof} \begin{remark} \label{re2} The result of Lemma~\ref{le36} is optimal since, for instance, the numbers $75$, $81$ and $87$ are consecutive in $E_n(2)$ for all integers $n \geq 90$ (see Example~\ref{ex1}). \end{remark} In what follows, we introduce the following subsets of $E_n(2)$. \begin{equation*} \begin{split} A_n & := E_n(2,6) \cup E_n(2,10) \\ & \text{and} \\ B_n & := E_n(2,3) \cup E_n(2,5) \cup E_n(2,9). \\ \end{split} \end{equation*} \begin{lemma} \label{le10} We have $ \ |F_n(2) \cap B_n| = |G_n(2) \cap B_n| + 0 \ \text{or\ } 1$. \end{lemma} \begin{proof} The proof rests on the following assertion. \begin{alignat}{1} \text{{\it The gap between two consecutive elements of}\ } B_n \ \text{{\it is odd}}. \label{e9} \end{alignat} Indeed, if statement (\ref{e9}) 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. \item[] The rest of the text is devoted to the proof of (\ref{e9}). Let $e \in B_n$. \item[] 1. If $e$, $e+a$ and $e+a+b$ are consecutive in $E_n(2)$ with $(a,b) \in \left\lbrace 3,5,9 \right\rbrace^2$, then $e$ and $e+a$ are consecutive in $B_n$ with $a$ odd. \item[] 2. If $e$, $e+a$ and $e+a+b$ are consecutive in $E_n(2)$ with $(a,b) \in \left\lbrace 3,5,9 \right\rbrace \times \left\lbrace 6,10 \right\rbrace$, then $e+a \in A_n$. Let $e+a+b+c$ be the successor of $e+a+b$ in $E_n(2)$. \begin{itemize} \item[(i)] If $c \in \left\lbrace 3,5,9 \right\rbrace$, then $e$ and $e+a+b$ are consecutive in $B_n$ with $a+b$ odd. \item[(ii)] If $c=6$, then $e+a+b \in A_n$. Let $e+a+b+6+d$ be the successor of $e+a+b+6$ in $E_n(2)$. \begin{itemize} \item[$\star$] If $d \in \left\lbrace 3,5,9 \right\rbrace$, then $e$ and $e+a+b+6$ are consecutive in $B_n$ with $a+b+6$ odd. \item[$\star$] If $d=6$, then $e+a+b+6 \in A_n$. By Lemmas~\ref{le341} and~\ref{le36}, the successor of $e+a+b+12$ in $E_n(2)$ can only be the number $e+a+b+12+f$ with $f \in \left\lbrace 3,5,9 \right\rbrace$, so that $e$ and $e+a+b+12$ are consecutive in $B_n$ with $a+b+12$ odd. \end{itemize} \item[(iii)] If $c=10$, then $e+a+b \in A_n$. Let $e+a+b+10+g$ be the successor of $e+a+b+10$ in $E_n(2)$. Again, By Lemmas~\ref{le341} and~\ref{le36}, we have $g \in \left\lbrace 3,5,9 \right\rbrace$, so that $e$ and $e+a+b+10$ are consecutive in $B_n$ with $a+b+10$ odd. \end{itemize} There is no other possibility by Lemmas~\ref{le341} and~\ref{le36}, which completes the proof. \end{proof} \begin{lemma} \label{le105} If $(e,e+6) \in \left( E_n(2,6)\right)^2$, then $\left( K_e,\dotsc,K_{e+27} \right)$ has a configuration of the form $$\left\lbrace \begin{array}{rl} (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), & \text{if } e+25 \not \in 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), & \text{if } e+25 \in E_n. \end{array} \right.$$ \end{lemma} \begin{proof} \item[] 1. We first notice that, according to (\ref{e8}), if $(e,e+6) \in \left( E_n(2,6)\right)^2$, one can only have $e+2 \in E_n(3)$ and $e+8 \in E_n(1)$. We infer that $$(e,e+6) \in \left( E_n(2,6)\right)^2 \Longleftrightarrow \left( K_e,\dotsc,K_{e+14} \right) = (2,1,2,1,1,2,2,1,2,2,1,1,2,1,2).$$ \item[] 2. We then examine all the possibilities offered by the sequence $(K_n)$. \begin{itemize} \item[$\star$] Let us show that $e+15 \in E_n(2)$. Indeed, we necessarily have $e+15 \in E_n$, otherwise $\left( K_{e+11},\dotsc,K_{e+15} \right) = (1,2,1,2,1)$ which is impossible by Lemma~\ref{le0} (ii). We deduce that $K_{e+16}=1$. If $e+15 \not \in E_n(2)$, then $K_{e+17} = 1$ and we have $$\left( K_{e+8},\dotsc,K_{e+17} \right) = (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~\ref{le0} (ii). \item[$\star$] Thus, $e+15 \in 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~\ref{le341}. \item[$\star$] We also have $e+18 \not \in E_n(2)$ otherwise the lengths of the run $\left( K_{e+13},\dotsc,K_{e+19} \right)$ generate the run $(1,2,1,2,1)$. Similarly, we necessarily have $e + 18 \in E_n$ otherwise the lengths of the run $\left( K_{e+1}, \dotsc,K_{e+20} \right)$ give the sequence $(1,1,2,2,1,2,2,1,1,2,1,1,2,2)$ which is impossible. \item[$\star$] We infer that $K_{e+21} = 2$ otherwise $\left( K_{e+19}, \dotsc,K_{e+21} \right) = (1,1,1)$. One can also prove that $e+21 \not \in E_n(2)$ otherwise the lengths of the run $\left( K_{e+8}, \dotsc,K_{e+22} \right)$ give $(2,2,1,1,2,1,2,2,1,1)$ which is impossible. \item[$\star$] We have $K_{e+22} = 1$ otherwise $\left( K_{e+17}, \dotsc,K_{e+22} \right) = (2,2,1,1,2,2)$, which is impossible by Lemma~\ref{le0} (ii). \item[$\star$] We have $K_{e+23} = 1$ for $e+21 \not \in E_n(2)$. Thus $K_{e+24} = 2$ otherwise $\left( K_{e+22}, \dotsc,K_{e+24} \right) = (1,1,1)$. \item[$\star$] $K_{e+25} = 1$ or $2$. \item[] If $K_{e+25} = 1$, then $K_{e+26} = 2$ otherwise $\left( K_{e+19} \dotsc,K_{e+26} \right) = (1,1,2,1,1,2,1,1)$. In particular, we have $e+24 \in E_n(2)$. Moreover, we then have $K_{e+27} = 2$ otherwise $\left( K_{e+23}, \dotsc,K_{e+27} \right) = (1,2,1,2,1)$. \item[] If $K_{e+25} = 2$, then $K_{e+26}=1$ otherwise $\left( K_{e+24}, \dotsc,K_{e+26} \right) = (2,2,2)$, and $K_{e+27}=2$ otherwise $\left( K_{e+22}, \dotsc, K_ {e+27} \right) = (1,1,2,2,1,1)$, which is impossible by Lemma~\ref{le0} (ii), so that $e+25 \in E_n(2)$. \end{itemize} The proof is complete. \end{proof} \begin{lemma} \label{le11} We have $ \ |F_n(2) \cap A_n| \leq |F_n(2) \cap B_n| \ $ and $ \ |G_n(2) \cap A_n| \leq |G_n(2) \cap B_n|$. \end{lemma} \begin{proof} By definition of $A_n$ and Lemmas~\ref{le341} and~\ref{le36}, 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 \begin{itemize} \item[$\star$] $e \in E_n(2,10)$, for then $e+10 \in B_n$ by Lemma~\ref{le36}. \item[$\star$] $e \in E_n(2,6)$ and $e+6 \in B_n$. \end{itemize} 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)$. \item[] In what follows, we consider two pairs $(e,e+6)$ and $(e+a,e+6+a)$ consecutive in $\left( E_n(2,6)\right)^2$ where $a$ is a positive integer. By Dirichlet's pigeonhole principle, Lemma~\ref{le11} 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~\ref{le105}. \item[] 1. By Lemma~\ref{le36}, we have $e+12 \in B_n$. \item[] 2. By Lemma~\ref{le105}, if $e+25 \not \in E_n$, then $a \geq 27$ \item[] 3. Let us show that, if $e+25 \in E_n$, then $a \geq 33$. \item[] If $e+25 \in E_n$, then $K_{e+29} = 1$ otherwise $e+25$ and $e+27$ are consecutive in $E_n(2)$ which is impossible by Lemma~\ref{le341}. If $e+28 \in E_n$, then the lengths of the sequence $\left( K_{e+14}, \dotsc,K_{e+28} \right)$ 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~\ref{le0} (ii). Thus, we have $K_{e+28} = 1$ and hence $K_{e+30} = 2$. We notice that $e+30 \not \in E_n(2,6)$ otherwise $\left( K_{e+29},\dotsc,K_{e+33} \right) =(1,2,1,2,1)$. We also have $K_{e+31} = 1$ otherwise the lengths of the sequence $\left( K_{e+22}, \dotsc,K_{e+31} \right)$ 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 $\left( K_{e+26}, \dotsc,K_{e+33} \right)$ then give the impossible run $(1,2,1,2,1)$. But we also have $e+32 \not \in E_n(2,6)$ otherwise $\left( K_{e+31}, \dotsc,K_{e+35} \right) = (1,2,1,2,1)$. \item[] 4. Now we are in a position to conclude the proof of Lemma~\ref{le11}. \item[] Let $(e,e+6)$ and $(e+a,e+6+a)$ be two consecutive pairs of $\left( E_n(2,6)\right)^2$. According to the above arguments, we have \begin{itemize} \item[$\star$] If $e+25 \not \in E_n$, then $e+12$ and $e+24$ are two elements of $B_n$ comprised between these two pairs. \item[$\star$] If $e+25 \in E_n$, then $e+12$ and $e+30$ are two elements of $B_n$ comprised between these two pairs. \end{itemize} The proof is complete. \end{proof} \begin{lemma} \label{cor365} We have $$\Bigl | |F_n(2)| - |G_n(2)| \Bigr | \leq \frac{t_n+k_n-n + 7}{3}.$$ \end{lemma} \begin{proof} By Lemmas~\ref{le10} and~\ref{le11}, we have \begin{equation*} \begin{split} |F_n(2)| & \leq |F_n(2) \cap A_n| + |F_n(2) \cap B_n| + 1 \\ & \leq 2|F_n(2) \cap B_n| + 1 \\ & \leq 2|G_n(2) \cap B_n| + 3 \\ & \leq 2|G_n(2)| + 3, \\ \end{split} \end{equation*} and similarly we get $|G_n(2)| \leq 2|F_n(2)| + 3$. The relation $|E_n(2)| = |F_n(2)| + |G_n(2)|$ implies that $$\frac{|E_n(2)|}{3} - 1 \leq |F_n(2)| \leq \frac{2|E_n(2)|}{3} + 1$$ and similar inequalities for $|G_n(2)|$ so that $$\Bigl | |F_n(2)| - |G_n(2)| \Bigr | \leq \frac{|E_n(2)|}{3}+2$$ and we conclude the proof by using Lemma~\ref{le5}. \end{proof} Lemmas~\ref{le356} and~\ref{cor365}, used in Proposition~\ref{pro2}, give at once the following estimate. \begin{corollary} \label{cor7} We have $$\left | S_n - \frac{3n}{2} \right | \leq \frac{t_{k_n}+k_{k_n}-k_n}{6} + 4.$$ \end{corollary} \vspace*{0.3cm} \noindent We now are able to prove Theorem~\ref{t05}. \begin{proof}[Proof of Theorem~\ref{t05}] Using Corollary~\ref{cor7} and the inequalities $t_{k_n} \leq n+1-k_n$ from Lemma~\ref{le1} and $k_{k_n} \leq 3k_n/4+3/2$ from Theorem~\ref{t0}, we get $$S_n \leq \frac{3n}{2} + \frac{t_{k_n}+k_{k_n}-k_n}{6} + 4 \leq \frac{5n}{3} - \frac{5k_n}{24} + \frac{53}{12}$$ and the lower bound $k_n \geq 3n/5$ from Theorem~\ref{t0} implies that $$S_n \leq \frac{37n}{24} + \frac{53}{12},$$ and since $S_{k_n} \geq n$, we infer $$k_n \geq \frac{24n}{37} -3.$$ The same method, now using the lower bound $$S_n \geq \frac{3n}{2} - \frac{t_{k_n}+k_{k_n}-k_n}{6} - 4 \geq \frac{4n}{3} + \frac{5k_n}{24} - \frac{53}{12}$$ and the inequality $S_{k_n} \leq n+1$, leads to $$k_n \leq \frac{24n}{35} + 4.$$ At the end of this first step, we then have \begin{alignat}{1} \frac{24n}{37} -3 \leq k_n \leq \frac{24n}{35} + 4 \quad {\rm (} n \geq 1 {\rm )}. \label{e10} \end{alignat} We repeat this process by defining the sequences $(u_m)_{m \geq 1}$ and $(v_m)_{m \geq 1}$ by $$\left\lbrace \begin{array}{rcl} u_1 &=& \dfrac{24}{35} \\ & & \\ u_{m+1} &=& \dfrac{6(1-3u_m)}{u_m^2-26u_m+8} \end{array} \right. \quad \text{and} \quad v_m = \frac{u_m}{3u_m-1}.$$ It is easy to check that, for all positive integers $m$, we have ${1 \over 2} < u_m < 1$ and ${1 \over 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 \begin{alignat}{1} n v_m - 4 \leq k_n \leq n u_m + 5 \quad {\rm (} n \geq 1 {\rm )} \label{e11} \end{alignat} the case $m=1$ being a consequence of (\ref{e10}). Assume estimate (\ref{e11}) is true for some $m$. Then, using induction hypothesis rewritten in the form $k_{k_n} \leq k_n u_m +5$, we get $$S_n \leq \frac{3n}{2} + \frac{t_{k_n}+k_{k_n}-k_n}{6} + 4 \leq \frac{5n}{3} - \frac{k_n \left( 2-u_m \right)}{6} +5$$ and induction hypothesis used in the form $k_n \geq n v_m -4$ implies that $$S_n \leq \frac{n}{6} \left( u_m v_m -2v_m + 10 \right) - \frac{2u_m-19}{3} = \frac{n \left( u_m^2+28u_m-10 \right)}{6 \left( 3u_m - 1 \right)} - \frac{2u_m-19}{3} = \frac{n}{v_{m+1}} - \frac{2u_m-19}{3}$$ and the lower bound $S_{k_n} \geq n$ gives $$k_n \geq n v_{m+1} + \frac{v_{m+1} \left( 2u_m-19 \right)}{3} = n v_{m+1} - \frac{2\left( 19 - 2u_m \right) \left( 3 u_m - 1 \right)}{u_m^2+28u_m-10} \geq n v_{m+1} - 4.$$ Similarly, the lower bound $$S_n \geq \frac{3n}{2} - \frac{t_{k_n}+k_{k_n}-k_n}{6} - 4 \geq \frac{4n}{3} + \frac{k_n \left( 2-u_m \right)}{6} - 5$$ and the inequality $S_{k_n} \leq n+1$, lead to $$k_n \leq n u_{m+1} + \frac{2u_{m+1} \left( 11 - u_m \right) }{3} = n u_{m+1} + \frac{4(11-u_m)(3u_m-1)}{u_m^2-26u_m+8} \leq n u_{m+1} + 5$$ which completes the proof of (\ref{e11}). We conclude by noticing that the sequence $(u_m)$ converges to $\alpha$. \item[] 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. \end{proof} \section{Concluding remarks} \label{s7} \begin{remark} \label{re3} There exist other identites analogue to Proposition~\ref{pro2}. For instance, we were able to prove the following results. \begin{itemize} \item[{\rm (i)}] {\it For all positive integers $n$, we have} $$k_n = \dfrac{2}{3} \left( n + \sum_{\substack{j=1 \\ \left( K_{2j-1}, K_{2j} \right) =(1,1) }}^{\lfloor k_n/2 \rfloor} 1 - \sum_{\substack{j=1 \\ \left( K_{2j-1}, K_{2j} \right) =(2,2) }}^{\lfloor k_n/2 \rfloor} 1 \right) + r_n$$ {\it where} $r_1=1/3$ {\it and, for all integers} $n \geq 2$, $$r_n = \begin{cases} -1/3, & \text{if } \left( K_{n-1},K_n,K_{n+1} \right) = (1,1,2); \\ 0, & \text{if } \left( K_n,K_{n+1} \right) = (2,1) \\ 1/3, & \text{if } \left( K_n,K_{n+1} \right) = (1,1) \ \text{or } \left( K_{n-1},K_n,K_{n+1} \right) = (2,1,2) \\ 2/3, & \text{if\ } \left( K_n,K_{n+1} \right) = (2,2). \end{cases}$$ \item[{\rm (ii)}] {\it For all positive integers $n$, we have} $$t_n = \frac{k_n}{2} + \sum_{\substack{j=2 \\ (K_{j-1},K_{j}) = (2,2)}}^{n} 1 + \frac{K_n}{2} - 1.$$ \end{itemize} Although these identities are equivalent to Proposition~\ref{pro2}, they seemed to be less handy to get fine estimates of the remainder term. \end{remark} \begin{remark} \label{re4} 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 (\ref{e5}) by Abel summation, we get $$\sum_{j=1}^{m} (-1)^j a_j = \frac{(-1)^m a_m - a_1}{2} + \frac{(-1)^m \left( a_m - a_{m-1} \right)}{4} + \frac{a_2-a_1}{4} - \frac{1}{4} \sum_{j=2}^{m-1} (-1)^j \Delta^2 a_j$$ where we set $\Delta^2 a_j := a_{j+1} - 2a_j + a_{j-1}$ {\rm (}$j \geq 2${\rm )}. Applied to the sequence $(t_j)$ noticing that $\Delta^2 t_j = K_{j+1} - K_j$, this gives $$\sum_{j=1}^{k_n} (-1)^j t_j = \frac{(-1)^{k_n} t_{{k_n}}}{2} + \frac{(-1)^{k_n} \left( K_{k_n}-1 \right)}{4} + \frac{1}{4} - \frac{1}{4} \sum_{j=2}^{k_n-1} (-1)^j \left( K_{j+1} - K_j \right)$$ for all integers $n \geqslant 2$ and, following the proof of Proposition~\ref{pro2}, we infer that $$S_n = \frac{3n}{2} - \frac{1}{4} \sum_{j=2}^{k_n-1} (-1)^j \left( K_{j+1} - K_j \right) + \frac{(-1)^{k_n}}{4} \left( K_{k_n} - 2c_n \right)$$ where $c_n$ is defined in Proposition~\ref{pro2}. The trivial estimate of the sum gives $$\left | \sum_{j=2}^{k_n-1} (-1)^j \left( K_{j+1} - K_j \right) \right | \leq \sum_{j=2}^{k_n-1} \left| K_{j+1} - K_j \right| = \sum_{j=2}^{k_n-1} \left( k_{j+1} - k_j \right) = k_{k_n} - 2$$ where we used Lemma~\ref{le1}. Compared to (\ref{e6}), the saving is not significant. \end{remark} \section{Acknowledgments} We express our gratitude to the referee for his careful reading of the manuscript and the many valuable suggestions he provided. \begin{thebibliography}{9} \bibitem{ber} B. C. Berndt and L. Schoenfeld, Periodic analogues of the Euler--MacLaurin and Poisson summation formulas with applications to number theory, {\it Acta Arith.} {\bf 28} (1975), 23--68. \bibitem{brl} S. Brlek, S. Dulucq, A. Ladouceur, and L. Vuillon, Combinatorial properties of smooth infinite words, {\it Theor. Comp. Sci.} {\bf 352} (2006), 306--317. \bibitem{car} A. Carpi, On repeated factors in C$^\infty$-words, {\it Inf. Process. Lett.} {\bf 52} (1994), 289--294. \bibitem{chv} V. Chv\'{a}tal, Notes on the Kolakoski sequence, DIMACS Technical report, 1993. \bibitem{dek} F. M. Dekking, What is the long range order in the Kolakoski sequence?, {\it The Mathematics of Long--range Aperiodic Order}, NATO Adv. Sci. Inst. Ser. C Maths. Phys. Sci., {\bf 489}, Kluwer Acad. Publ., Dordrecht (1997), 115--125. \bibitem{joh} R. Johnsonbaugh, Summing an alternating series, {\it Amer. Math. Monthly} {\bf 86} (1979), 637--648. \bibitem{kol} W. Kolakoski, Problem 5304: self generating runs, {\it Amer. Math. Monthly} {\bf 72} (1965), 674. \bibitem{kup} E. J. Kupin and E. S. Rowland, Bounds on the frequency of $1$ in the Kolakoski word, preprint (2008). \bibitem{bry} K. O'Bryant, B. Reznick, and M. Serbinowska, Almost alternating sums, {\it Amer. Math. Monthly} {\bf 113} (2006), 673--688. \bibitem{slo} N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, published electronically at \href{http://oeis.org}{\tt http://oeis.org}. \bibitem{ste} B. Steinsky, A recursive formula for the Kolakoski sequence, {\it J. Integer Seq.} {\bf 9} (2006), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Steinsky/steinsky5.html}{Article 06.3.7}. \bibitem{par} \textsc{PARI/GP}, available at \textsf{ftp://megrez.math.u-bordeaux.fr/pub/pari}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B37; Secondary 11B83, 11B85. \noindent \emph{Keywords: } Kolakoski sequence, Dirichlet's pigeonhole principle. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A000002}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 7 2010; revised version received January 28 2011. Published in {\it Journal of Integer Sequences}, February 9 2011. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}