\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amssymb, latexsym, amsfonts}

\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://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
A Recursive Formula for the\\ \vskip .1in
Kolakoski Sequence \seqnum{A000002}}
\vskip 1cm
\large
Bertran Steinsky\\
F\"urbergstrasse 56 \\
5020 Salzburg\\
Austria\\
\href{mailto:steinsky@finanz.math.tu-graz.ac.at}{\tt steinsky@finanz.math.tu-graz.ac.at}\\
\end{center}

\vskip .2 in

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

\begin{abstract}
We present a recursive formula for the $n$th term of the Kolakoski
sequence. Using this formula, it is easy to find recursions for the
number of ones in the first $n$ terms and for the sum of the first $n$
terms of the Kolakoski sequence.
\end{abstract}

%-------------------------------------------------------------------------------------
\section{Introduction}
%-------------------------------------------------------------------------------------
The Kolakoski sequence $K_n$ \cite{kolakoski1,kolakoski2}, which we
study here, is the unique sequence starting with $1$ which is identical
to its own runlength sequence. $K_n$ is Sloane's sequence
\seqnum{A000002}. Kimberling asks $5$ questions about this sequence on
his homepage \cite{kimberling}. The first one is, whether there exists a
formula for the $n$th term of the Kolakoski sequence. For a survey of
known properties of the Kolakoski sequence we refer to
Dekking \cite{dekking95}. Cloitre wrote the formulas

\[
K_N=\frac{3+(-1)^n}{2}\mbox{ and } K_{N+1}=\frac{3-(-1)^n}{2}, \mbox{ where }{N=\sum_{i=1}^n K_i},
\]
in the entry of Sloane's sequence \seqnum{A000002}, where we also find
block-substitution rules, which where posted by Lagarias. I.e.,
starting with $22$ we have to apply $22 \rightarrow 2211$, $21
\rightarrow 221$, $12 \rightarrow 211$, and $11 \rightarrow 21$, as it
was mentioned by Dekking \cite{dekking80,dekking95}. Culik \emph{et
al.} \cite{culik} proposed the double substitution rules
$\sigma_1(1\rightarrow 1, 2\rightarrow 11)$ and $\sigma_2(1\rightarrow
2, 2\rightarrow 22)$, which are applied alternatingly to each letter of
a word. These substitutions can also be found at Allouche \emph{et
al.} \cite[p.\ 336]{allouche}. Cloitre added the relationship
\[
f_1(n)+f_2(n)=1+\sum_{i=0}^{n-1} f_2(i)
\]
to Sloane's sequence \seqnum{A054349}, where $f_1(n)$ denotes the
number of ones and $f_2(n)$ denotes the number of twos in the $n$th
string of Sloane's sequence \seqnum{A054349}.

%-------------------------------------------------------------------------------------
\section{A Recursive Formula for the Kolakoski Sequence}\label{sec:}
%-------------------------------------------------------------------------------------
We will now derive a recursive formula for $K_n$.
Let $k_n=\min\left\{j:\sum_{i=1}^j K_i\ge n \right\}$.
\begin{table}[h]
\begin{center}
\begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r}
$n$ & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15 \\
\hline
$K_n$ & 1& 2& 2& 1& 1& 2& 1& 2& 2& 1& 2& 2& 1& 1& 2 \\
\hline
$k_n$ & 1& 2& 2& 3& 3& 4& 5& 6& 6& 7& 8& 8& 9& 9& 10 \\
\end{tabular}
\caption{$K_n$ and $k_n$}
\end{center}
\end{table}
\begin{lemma}\label{lemma:kn1}
\[
k_n=k_{n-1}+n-\sum_{i=1}^{k_{n-1}} K_i, \mbox{ where } n\ge 2.
\]
\end{lemma}
\begin{proof}We first notice that 
\[
n-1\le \sum_{i=1}^{k_{n-1}} K_i \le n.
\]
The left inequality holds by definition and the right one is valid, since if 
\[
\sum_{i=1}^{k_{n-1}} K_i \ge n+1
\]
we would have
\[
\sum_{i=1}^{k_{n-1}-1} K_i \ge n-1
\]
which is a contradiction to the minimality of $k_{n-1}$. So, as the
first case, we consider $\sum_{i=1}^{k_{n-1}} K_i=n-1$ which implies
$k_n=k_{n-1}+1=k_{n-1}+n-\sum_{i=1}^{k_{n-1}} K_i$. In the second case
$\sum_{i=1}^{k_{n-1}} K_i=n$ leads to
$k_n=k_{n-1}=k_{n-1}+n-\sum_{i=1}^{k_{n-1}} K_i$.
\end{proof}
We notice that Lemma~\ref{lemma:kn1} holds in general for every sequence, whose only values are $1$ and $2$.
\begin{lemma}\label{lemma:kn2}
\[
k_n=k_{n-1}+|K_n-K_{n-1}|=1+\sum_{i=2}^{n} |K_i-K_{i-1}|, \mbox{ where } n\ge 2.
\]
\end{lemma}

\begin{proof}
The following well known construction produces a sequence which is
identical to $K$. Start with $K_1$ ones, continue with $K_2$ twos,
followed by $K_3$ ones, and so on. In this construction, after
$k_{n-1}$ steps two cases can appear, as described in the proof of
Lemma~\ref{lemma:kn1}. The first possibility is that
$\sum_{i=1}^{k_{n-1}} K_i=n-1$, which means that we have constructed
$n-1$ terms of the sequence. Therefore, by construction, $K_n$ must be
different from $K_{n-1}$ implying $k_n-k_{n-1}=|K_n-K_{n-1}|$. In the
second case that $\sum_{i=1}^{k_{n-1}} K_i=n$, it is necessary that
$K_{k_{n-1}}=2$, for if otherwise $\sum_{i=1}^{k_{n-1}-1} K_i=n-1$,
contradicting the minimality of $k_{n-1}$. So our construction has
added $2$ equal numbers at the $k_{n-1}$th step, such that
$K_n=K_{n-1}$ and finally $k_n-k_{n-1}=|K_n-K_{n-1}|$. The second
equality follows by induction.
\end{proof}

Corollary~\ref{corollary:akn} is an implication of Lemma~\ref{lemma:kn2}.
\begin{corollary}\label{corollary:akn}
\[
K_n \equiv k_n \ ({\rm mod}\ 2) \mbox { or } K_n=\frac{(-1)^{k_n}+1}{2}+1 \mbox { respectively}.
\]
\end{corollary}
Corollary~\ref{corollary:kn} uses Lemma~\ref{lemma:kn1} and Corollary~\ref{corollary:akn}.
\begin{corollary}\label{corollary:kn}
\[
k_n=n-\frac{1}{2}\sum_{i=1}^{k_{n-1}} \left((-1)^{k_i}+1\right), \mbox{ where } n\ge 2.
\]
\end{corollary}
Corollary~\ref{corollary:short} follows from Corollary~\ref{corollary:kn}.
\begin{corollary}\label{corollary:short}
\[
k_n=k_{n-1}+1-\frac{1}{2}\left(k_{n-1}-k_{n-2}\right)\left((-1)^{k_{k_{n-1}}}+1\right), \mbox{ where } n\ge 3.
\]
\end{corollary}
\begin{theorem}\label{theorem:a}
For $n\ge 3$ we have
\begin{eqnarray}
K_n
&=&K_{n-1}+\left(3-2 K_{n-1} \right) \Bigl(n-\sum_{i=1}^{1+\sum_{j=2}^{n-1}|K_j-K_{j-1}|}K_i \Bigr)\label{eq:1}\\
&=&K_{n-1}+\left(3-2 K_{n-1} \right) \Bigl(n-\sum_{i=1}^{1+\sum_{j=2}^{n-1}\frac{K_j-K_{j-1}}{3-2 K_{j-1}}}K_i \Bigr)\label{eq:2}\\
&=&K_{n-1}+(3-2 K_{n-1})\left(1-\frac{1}{2}\frac{K_{n-1}-K_{n-2}}{3-2 K_{n-2}}\left( 1+(-1)^{K_{1+\sum_{j=2}^{n-1}\frac{K_j-K_{j-1}}{3-2 K_{j-1}}}}\right)\right).\label{eq:3}\\
\nonumber\end{eqnarray}
\end{theorem}
\begin{proof}From Lemma~\ref{lemma:kn1} and Lemma~\ref{lemma:kn2} we obtain
\[
|K_n-K_{n-1}|=n-\sum_{i=1}^{1+\sum_{j=2}^{n-1}|K_j-K_{j-1}|} K_i
\]
and use the fact that
\[
|K_n-K_{n-1}|=\frac{K_n-K_{n-1}}{3-2 K_{n-1}}
\]
to complete the proof of (\ref{eq:1}) and (\ref{eq:2}). The third equation (\ref{eq:3}) follows from Corollary~\ref{corollary:short} and Lemma~\ref{lemma:kn2}.
\end{proof}
\section{Concluding Remarks}
Let $s_n=\sum_{i=1}^{n} K_i$, which is Sloane's sequence \seqnum{A054353}, $o_n=\left|\left\{1\le j \le n:K_j=1 \right\}\right|$, and $t_n=\left|\left\{1\le j \le n:K_j=2 \right\}\right|$, which is Sloane's sequence \seqnum{A074286}. With Theorem~\ref{theorem:a} and the equations
\begin{eqnarray}
K_n&=&s_n-s_{n-1}\nonumber,\\
K_n&=&-o_n+o_{n-1}+2\nonumber,\mbox{ and}\\
K_n&=&t_n-t_{n-1}+1\nonumber \\
\nonumber\end{eqnarray}
it is easy to produce recursive formulas for $s_n$, $o_n$, and $t_n$. 

By Lemma~\ref{lemma:kn1}, we obtain $k_n=n-t_{k_{n-1}}$, from which it
follows that $t_n/n$ converges if and only if the limit of $k_n/n$
exists. The definition of $k_n$ gives the equations $k_{s_n}=n$ and
$k_{s_n+1}=n+1$, which yield that the limit of $k_n/n$ exists, if and
only if $s_n/n$ converges. Therefore, if we assume that one of the
sequences $t_n/n$, $o_n/n$, $k_n/n$ or $s_n/n$ converges then all
sequences have a limit. If $a=\lim_{n\rightarrow \infty}t_n/n$ then
$\lim_{n\rightarrow \infty}o_n/n=1-a$, $\lim_{n\rightarrow
\infty}s_n/n=1+a$, and $\lim_{n\rightarrow \infty}k_n/n=1/(1+a)$.

Using the recursion of Corollary~\ref{corollary:short}, we computed
$k_n/n$ up to $n=3\cdot 10^8$. Figure~\ref{fig:kn_by_n} shows $k_n/n$
for $n$ from $10^8$ to $3\cdot 10^8$, where only each $1000$th point is
drawn, i.e., the subsequence $k_{1000n}/(1000n)$, for
$n=100000,\dots,300000$. The $x$-axis is positioned at $2/3$.

\begin{figure}[hhhh]
\begin{center}
\includegraphics{steinsky-graph.eps}
\caption{$\frac{k_n}{n}$ for $n$ from $10^8$ to $3\cdot 10^8$.}\label{fig:kn_by_n}
\end{center}
\end{figure}

If we assume that the limit of $o_n/n$ exists and is equal to $1/2$
then $k_n/n$ must tend to $2/3$. Thus, the graph in
Figure~\ref{fig:kn_by_n} does not support the conjecture that $o_n/n$
converges to $1/2$.  \section{Acknowledgement}\label{sec:ackn}

We thank the referees for fruitful suggestions and Benoit Cloitre for helpful email discussion.

\begin{thebibliography}{99}

\bibitem{allouche} J.-P. Allouche, J. Shallit, \emph{Automatic Sequences}, Cambridge Univ. Press, Cambridge, 2003. 

\bibitem{culik} K. Culik, J. Karhum\"aki,  Iterative devices generating infinite words, \emph{Lec. Notes in Comp. Sc.} \textbf{577} (1992), 531--544.

\bibitem{dekking80} F. M. Dekking,  Regularity and irregularity of sequences generated by automata, \emph{S\'em. Th. Nombres Bordeaux `79-`80} (1980), 901--910.

\bibitem{dekking95} F. M. Dekking,  What is the long range order in the Kolakoski sequence?, \emph{The Mathematics of Long-Range Aperiodic Order}, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. \textbf{489}, Kluwer Acad. Publ., Dordrecht (1997), 115--125.

\bibitem{kimberling} C. Kimberling, \href{http://faculty.evansville.edu/ck6/integer/index.html}{\texttt{http://faculty.evansville.edu/ck6/integer/index.html}}

\bibitem{kolakoski1} W. Kolakoski, Problem 5304: Self Generating Runs, \emph{Amer. Math. Monthly} \textbf{72} (1965), 674.

\bibitem{kolakoski2} W. Kolakoski, Problem 5304, \emph{Amer. Math. Monthly} \textbf{73} (1966), 681--682.  

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 
Primary 11B83; Secondary 11B85, 11Y55, 40A05.

\noindent \emph{Keywords:} Kolakoski sequence, recursion, recursive formula.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000002},
\seqnum{A054349},
\seqnum{A054353},
and \seqnum{A074286}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 13 2006;
revised version received  August 19 2006.
Published in {\it Journal of Integer Sequences}, August 19 2006.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}