\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{fullpage}
\usepackage{cite, url}
\usepackage{float}
\usepackage{epsf}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}
\newtheorem*{conjecture}{Conjecture}
\newtheorem{problem}{Problem}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem*{note}{Note}
\newtheorem{case}{Case}
\newtheorem{2case}{Case}
\newcommand{\kola}{\mathbf{k}}
\newcommand{\Kola}{\mathbf{K}}

\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 Some Remarks on Differentiable Sequences\\ 
\vskip .1in
and Recursivity}
\vskip 1cm
\large
Jean-Marc F\'{e}dou and Gabriele Fici\footnote{The second author acknowledges the support of an Exchange Grant on the program ``AutoMathA: Automata,
   from Mathematics to Applications'' of the European Science Foundation.}\\
Laboratoire d'Informatique, Signaux et Syst\`{e}mes de Sophia-Antipolis\\ 
UMR6070 - CNRS et Universit\'{e} de Nice-Sophia Antipolis\\
2000, route des Lucioles\\ 06903 Sophia-Antipolis Cedex \\ 
France\\
\href{mailto:fedou@i3s.unice.fr}{\tt fedou@i3s.unice.fr}\\
\href{mailto:fici@i3s.unice.fr}{\tt fici@i3s.unice.fr}\\
\end{center}

\vskip .2in

\begin{abstract}
We investigate the recursive structure of differentiable sequences over
the alphabet $\{1,2\}$. We derive a recursive formula for the $(n+1)$-th
symbol of a differentiable sequence, which yields to a new recursive
formula for the Kolakoski sequence. Finally, we show that the sequence
of absolute differences of consecutive symbols of a differentiable
sequence $u$ is a morphic image of the run-length encoding of $u$.
\end{abstract}

\section{Introduction}\label{sec:intro}

In 1965, W. Kolakoski \cite{Kolakoski:1965} proposed the following problem:

``Describe a simple rule for constructing the sequence:

$$\Kola=12211212212211211221211212211211212212211212212\cdots$$

What is the $n$-th term? Is the sequence periodic?''

This sequence, called now \emph{the Kolakoski sequence}, is in fact the unique sequence starting with 1 and identical to its own run-length encoding.

The Kolakoski sequence has been investigated in many papers \cite{Kimberling:1979,Paun:1993,
Culik&Karhumaki&Lepisto:1992,Carpi:1993c,Carpi:1994,Chvatal:1994,Lepisto:1994,Steacy:1996,Dekking:1997,Brlek:2003,Steinsky:2006}. 
Although the non-periodicity of the sequence was shown immediately, the
problem of finding a good formula for the $n$-th term is still open,
and is related to other open problems. The most famous open 
problems on the Kolakoski sequence (up to now) are as follows: Is the sequence
recurrent? Is the frequency of 1's and 2's asymptotically the same? Is
the set of factors of the sequence closed under reversal and/or swap of
the symbols?

The Kolakoski sequence $\Kola$ (sequence \seqnum{A000002} in 
Sloane's database) and the sequence $\kola$ (sequence \seqnum{A078880})
obtained from the former by deleting the first symbol are the unique
fixed point of the run-length encoding operator $\Delta$. A sequence
$u$ over the alphabet $\{1,2\}$ such that $\Delta(u)$ is still a
sequence over $\{1,2\}$ is called a \emph{differentiable sequence}. The
problems stated above for the Kolakoski sequence remain unsolved for the
wider class of sequences that are differentiable arbitrary many times,
called \emph{smooth sequences} \cite{Brlek:2003,Brlek:2006}.

In this paper we study the recursive relationship between any
differentiable sequence $u$ and its run-length encoding $\Delta(u)$. We
start by defining, for any differentiable sequence $u$, the sequences
$\varphi_{n}(u)$ and $\gamma_{n}(u)$.  The sequence $\varphi_{n}(u)$ is
defined by $\varphi_n(u)=|\Delta(u_1u_2\cdots u_{n})|$. In other words,
$\varphi_{n}(u)$ is equal to $1$ plus the number of symbol changes in
$u_{1}u_{2}\cdots u_{n}$. The sequence $\gamma_{n}(u)$ is defined by
$\gamma_{n}(u)=|u_{n+1}-u_{n}|$.

The sequences $\varphi_{n}(\Kola)$, $\varphi_{n}(\kola)$ and $\gamma_{n}(\Kola)$ are known (sequences \seqnum{A156253}, \seqnum{A156351}, and \seqnum{A156728} respectively).

\begin{remark}
We shall write $\varphi_{n}, \gamma_{n}$ instead of $\varphi_{n}(u), \gamma_{n}(u)$ when no confusion arises.
\end{remark}

In Theorem \ref{teor:main} we derive a recursive formula for $\gamma_{n}$
$$\gamma_{n}=1-(u'_{\varphi_{n}}-1)\gamma_{n-1}$$
where $u'=\Delta(u)$. This formula yields to recursive formulas for $u$ and  $\varphi(u)$ (Corollaries \ref{cor:mainu} and \ref{cor:mainphi})

$$u_{n+1}=3-u_{n}+(u'_{\varphi_{n}}-1)(u_{n}-u_{n-1})$$

$$\varphi_{n+1}=\varphi_{n}+1-(u'_{\varphi_{n}}-1)(\varphi_{n}-\varphi_{n-1})$$

When $u=K_{1}K_{2}\cdots$ is the Kolakoski sequence, our recursive formula gives

$$K_{n+1}=3-K_{n}+(K_{\varphi_{n}}-1)(K_{n}-K_{n-1})$$

A different approach allows us to derive an alternative recursive formula for the $n+1$-th term of a differentiable sequence. Indeed, in Theorem \ref{teor:recu}, we prove that

$$u_{n+1} = u_n+\left(3-2u_n\right)\left( n+1-\sum_{i=1}^{\varphi_n}u'_i\right)$$

When $u$ is the Kolakoski sequence, this latter formula is equivalent to one of Steinsky \cite{Steinsky:2006}, obtained with different techniques.

As a last result, in Lemma \ref{lem:morfK}, we show that for any differentiable sequence $u$, the sequence $\gamma_{n}$ is a morphic image of the sequence $\Delta(u)$, under the morphism $\mu: 1\mapsto 1, 2\mapsto 01$. 

\section{Differentiable sequences}\label{sec:nota}

An \textit{alphabet}, denoted by $\Sigma$, is a finite set of symbols.
A \emph{sequence} over $\Sigma$ is a sequence of symbols from $\Sigma$. The \textit{length} of a finite sequence $u$ is denoted
by $|u|$. A right-infinite sequence over $\Sigma$ is a non-ending sequence of symbols from $\Sigma$. Formally, a right-infinite
sequence is a function $f:\mathbb{N}\longmapsto \Sigma$. For an abuse of notation, we shall often write $f_n$ for $f(n)$.

A \emph{run} in a sequence $u$ is a maximal block of consecutive identical symbols.

Let $u$ be a sequence over $\Sigma$. Then $u$ can be uniquely written as a concatenation of consecutive runs of the symbols of
$\Sigma$, i.e.\ $u=x_1^{i_1}x_2^{i_2}x_{3}^{i_{3}}\cdots $, with $x_{j} \in \Sigma$, $x_{j}\neq x_{j+1}$ and $i_j >0$. The \emph{run-length encoding} of $u$, noted $\Delta(u)$, is the sequence of exponents $i_j$, i.e. $\Delta(u)=i_1i_2i_{3}\cdots $.

\begin{remark}
From now on we set $\Sigma=\{1,2\}$.
\end{remark}

We say that a sequence $u$ over $\Sigma$ is \emph{differentiable} if $\Delta(u)$ is still a sequence over $\Sigma$. Since
$\Sigma=\{1,2\}$ we have that $u$ is differentiable if and only if neither $111$ nor $222$ appear in $u$.

In the sequel we note $\Delta(u)=u'_{1}u'_{2}\cdots$ for $u$ a differentiable sequence.

\begin{definition}
A right-infinite sequence $u$ over $\Sigma$ is a \emph{smooth sequence} if it is differentiable arbitrary many times over
$\Sigma$.
\end{definition}

The most famous examples of smooth sequences are the Kolakoski sequences:
$$\kola=2211212212211211221211212211211212212211212212\cdots$$
and
$$\Kola=1\kola=12211212212211211221211212211211212212211212212\cdots$$
which are the fixed points of $\Delta$.

The following lemma is a straightforward consequence of the definition of $\Delta$.

\begin{lemma}\label{lem:collage}
Let $uv$ be a differentiable sequence. Then $\Delta(uv)=\Delta(u)\Delta(v)$ if and only if the last symbol of $u$ and the first symbol of $v$ are different.
\end{lemma}

Let $u=u_1u_2u_{3}\cdots$ be a finite or infinite sequence over $\Sigma$. We define the two functions $\Delta_1^{-1}$ and $\Delta_2^{-1}$ by:

$$\Delta_1^{-1}(u)=1^{u_1}2^{u_2}1^{u_3}\cdots$$

$$\Delta_2^{-1}(u)=2^{u_1}1^{u_2}2^{u_3}\cdots$$

In such a way, $u=\Delta(\Delta_{x}^{-1}(u))$ for any $x\in \Sigma$.

\begin{remark}\label{rem:deltaminus}
Let $u=u_{1}u_{2}\cdots u_{n}$ be a sequence over $\Sigma$. Then for every $x\in \Sigma$
$$|\Delta_{x}^{-1}(u_{1}u_{2}\cdots u_{n})|=\sum_{i=1}^{n}u_{i}$$
\end{remark}

\section{Recursivity}

Let $u=u_{1}u_{2}\cdots$ be a differentiable sequence. We define, for every $n>0$

$$\varphi_n(u)=|\Delta(u_1u_2\cdots u_{n})|$$

The definition of $\Delta$ directly implies that $\varphi_{n}(u)$ is equal to $1$ plus the number of symbol changes in $u_{1}u_{2}\cdots u_{n}$. With our notation:

\begin{equation}\label{eq:phiind}
\varphi_{n}(u)=\varphi_{n-1}(u)+|u_{n}-u_{n-1}|=1+\sum_{i=1}^{n-1}|u_{i+1}-u_{i}|
\end{equation}
for every $n>1$. 

We also define, for every $n>0$

$$\gamma_{n}(u)=|u_{n+1}-u_{n}|$$

\begin{example}
The sequences $\varphi_{n}(\Kola),\varphi_{n}(\kola)$ and $\gamma_{n}(\Kola)$ are present in the Sloane's database as sequence \seqnum{A156253}, \seqnum{A156351}, and \seqnum{A156728} respectively. The first values of these sequences are reported in Table 1.
\end{example}

Let $u=u_{1}u_{2}\cdots$ be a (right infinite) differentiable sequence and let $u'=\Delta(u)=u'_{1}u'_{2}\cdots$ be its run-length encoding. For any $n>0$ the two sequences $\Delta(u_{1}u_{2}\cdots u_{n})$ and $u'_{1}u'_{2}\cdots u'_{\varphi_{n}}$ are equal if and only if $u_{n+1}\neq u_{n}$, as a consequence of Lemma \ref{lem:collage}. If instead $u_{n}=u_{n+1}$ then $u_{n}\neq u_{n-1}$ since $u$ is differentiable, and hence the last symbol of $\Delta(u_{1}\cdots u_{n})$ is equal to $1$, while $u'_{\varphi_{n}}=2$.

In other words, if $u_{n}=u_{n-1}$ then clearly $u_{n+1}\neq u_{n}$ since $u$ is differentiable. If instead $u_{n}\neq u_{n-1}$ then $u_{n+1}=u_{n}$ when $u'_{\varphi_{n}}=2$, while $u_{n+1}\neq u_{n}$ when $u'_{\varphi_{n}}=1$. We thus have 

\begin{theorem}\label{teor:main}
Let $u=u_{1}u_{2}\cdots$ be a differentiable sequence. Then for every $n>0$
\begin{equation}\label{eq:main}
\gamma_{n}=1-(u'_{\varphi_{n}}-1)\gamma_{n-1}
\end{equation}
\end{theorem}

\begin{remark}\label{rem:abs}
Since $\Sigma=\{1,2\}$, one has that, $\forall x,y\in \Sigma$, $y=x+(3-2x)|y-x|$. 
\end{remark}

From the previous remark and from Equation \ref{eq:main} we have

\begin{corollary}\label{cor:mainu}
Let $u=u_{1}u_{2}\cdots$ be a differentiable sequence. Then for every $n>0$
\begin{equation}\label{eq:mainu}
u_{n+1}=3-u_{n}+(u'_{\varphi_{n}}-1)(u_{n}-u_{n-1})
\end{equation}
\end{corollary}

And from Equations \ref{eq:phiind} and \ref{eq:main} we derive

\begin{corollary}\label{cor:mainphi}
Let $u=u_{1}u_{2}\cdots$ be a differentiable sequence. Then for every $n>0$
\begin{equation}\label{eq:mainphi}
\varphi_{n+1}=\varphi_{n}+1-(u'_{\varphi_{n}}-1)(\varphi_{n}-\varphi_{n-1})
\end{equation}
\end{corollary}

\begin{example}
When $u$ is the Kolakoski sequence $\Kola$,  Equation \ref{eq:mainu} gives

\begin{equation}\label{eq:mainK}
K_{n+1}=3-K_{n}+(K_{\varphi_{n}}-1)(K_{n}-K_{n-1})
\end{equation}
\end{example}

We now give another recursive formula for the $n+1$-th symbol of a differentiable sequence.

\begin{theorem}\label{teor:recu}
Let $u=u_{1}u_{2}\cdots$ be a differentiable sequence. Then for every $n>0$

\begin{equation}\label{eq:recu}
u_{n+1} = u_n+\left(3-2u_n\right)\left( n+1-\sum_{i=1}^{\varphi_n}u'_i\right)
\end{equation}
\end{theorem}

\begin{proof}
If $u_{n}=u_{n+1}$ then $\varphi_{n}=\varphi_{n+1}$, so $\Delta_{u_{1}}^{-1}(u'_{1}\cdots u'_{\varphi_{n}})=\Delta_{u_{1}}^{-1}(u'_{1}\cdots u'_{\varphi_{n+1}})=u_{1}u_{2}\cdots u_{n+1}$. Hence, by Remark \ref{rem:deltaminus}, $\sum_{i=1}^{\varphi_{n}}u'_{i}=n+1$. 

If instead $u_{n}\neq u_{n+1}$ then, by Lemma \ref{lem:collage}, $\Delta(u_{1}\cdots u_{n})=u'_{1}\cdots u'_{\varphi_{n}}$, which implies that $\Delta_{u_{1}}^{-1}(u'_{1}\cdots u'_{\varphi_{n}})=u_{1}u_{2}\cdots u_{n}$. Hence, again by Remark \ref{rem:deltaminus}, $\sum_{i=1}^{\varphi_{n}}u'_{i}=n$. 

Thus

$$|u_{n+1}-u_n|=n+1-\sum_{i=1}^{\varphi_n}u'_i$$

The claim then follows from Remark \ref{rem:abs}.

\end{proof}

\begin{example}
For $u=\Kola$, Equation \ref{eq:recu} becomes

\begin{equation}\label{eq:kolastein}
K_{n+1} = K_n+\left(3-2K_n\right)\left( n+1-\sum_{i=1}^{\varphi_n}K_i\right)
\end{equation}
\end{example}

Equation \ref{eq:kolastein} can be found in a paper of Steinsky \cite{Steinsky:2006}, where  $\varphi_{n}(\Kola)$ is replaced by $\rho_{n}(\Kola)=\min\left\{ j:\sum_{i=1}^{j}K_{i}\geq n\right\}$. 
But it is easy to see that for any differentiable sequence $u$ one has $\varphi_{n}=\min\left\{ j:\sum_{i=1}^{j}u'_{i}\geq n\right\}$.

We now show that, for any differentiable sequence $u$, the sequence $\gamma_{n}(u)$ is a morphic image of the sequence $\Delta(u)$.

\begin{lemma}\label{lem:morfK}
Let $\mu$ be the morphism defined on $\Sigma$ by

\begin{equation*} \mu: \left\{ \begin{array}{ll}
1 & \longmapsto 1\\
2 & \longmapsto 01
\end{array} \right.
\end{equation*}
and let $v_{n}$ be the sequence $\mu(\Delta(u))$. Then $v_{n}=\gamma_{n}$.
\end{lemma}

\begin{proof}
It is sufficient to prove that the sequences $v_{n}$ and $\gamma_{n}$ have the same partial sums. We have two cases:

\begin{case}
$u_{n}\neq u_{n+1}$. Then, by Lemma \ref{lem:collage}, $\Delta(u_{1}\cdots u_{n})=u'_{1}\cdots u'_{\varphi_{n}}$. From the definition of $\mu$, one has $\sum_{i=1}^{n}v_{i}=|u'_{1}\cdots u'_{\varphi_{n}}|=\varphi_{n}$. 
\end{case}

\begin{case}
$u_{n}= u_{n+1}$. This implies that $u'_{\varphi_{n}}=2$ and so $\sum_{i=1}^{n}v_{i}=\sum_{i=1}^{n-1}v_{i}$. On the other hand, we must have $u_{n-1}\neq u_{n}$ and therefore, arguing as in Case 1, we obtain $\sum_{i=1}^{n-1}v_{i}=|u'_{1}\cdots u'_{\varphi_{n-1}}|=\varphi_{n-1}=\varphi_{n}-1$.
\end{case}

In summary, we have $\sum_{i=1}^{n}v_{i}=\varphi_{n}-1+\gamma_{n}$.

On the other hand, by Equation \ref{eq:phiind}, we have $\sum_{i=1}^{n}\gamma_{i}=\sum_{i=1}^{n-1}\gamma_{i}+\gamma_{n}=\varphi_{n}-1+\gamma_{n}$.

\end{proof}

\section{Conclusion}

The main purpose of this paper was to unify the description of various
sequences described in the Sloane's database and related to the
Kolakoski sequence. We showed that, indeed,  all these sequences or
recurrences can be easily deduced from more general equalities holding
for any differentiable sequence. Unfortunately, it appears that all
these results are finally only another way to write the definition of
differentiability of a sequence over the alphabet $\{1,2\}$. Thus, the
challenge to find a formula for the $n$-th symbol of the Kolakoski
sequence without the knowledge of the preceding symbols is still open.
 
\begin{table}[h]\label{tab:val}
\centering  \caption{First values of the sequences $\Kola$, $\varphi(\Kola)$, $\varphi(\kola)$, $\gamma(\Kola)$, corresponding, respectively, to Sloane's database entries \seqnum{A000002}, \seqnum{A156253}, \seqnum{A156351}, and \seqnum{A156728}}.
\begin{raggedright}
\vspace{4mm}

\begin{tabular}{c *{26}{@{\hspace{1ex}}l}}

 $n$  & & 1\hspace{1ex} & 2\hspace{1ex} & 3\hspace{1ex} & 4\hspace{1ex} & 5\hspace{1ex} & 6\hspace{1ex} & 7\hspace{1ex} & 8\hspace{1ex} & 9\hspace{1ex} & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25\\
\hline \rule[-6pt]{0pt}{22pt}
$\Kola$  & & 1& 2& 2& 1& 1& 2& 1& 2& 2& 1& 2& 2& 1& 1& 2& 1& 1& 2& 2& 1& 2& 1& 1& 2& 1 \\
\hline \rule[-6pt]{0pt}{22pt}
$\varphi(\Kola)$  & & 1& 2& 2& 3& 3& 4& 5& 6& 6& 7& 8& 8& 9& 9& 10& 11& 11& 12& 12& 13& 14& 15& 15& 16& 17 \\
\hline \rule[-6pt]{0pt}{22pt}
$\varphi(\kola)$ &  & 1& 1& 2& 2& 3& 4& 5& 5& 6& 7& 7& 8& 8& 9& 10& 10& 11& 11& 12& 13& 14& 14& 15& 16& 17  \\
\hline \rule[-6pt]{0pt}{22pt}
$\gamma(\Kola)$  & & 1& 0& 1& 0& 1& 1& 1& 0& 1& 1& 0& 1& 0& 1& 1& 0& 1& 0& 1& 1& 1& 0& 1& 1& 1 \\
\hline
\end{tabular}
\label{table:definitions}
\end{raggedright}
\end{table}

\begin{thebibliography}{10}

\bibitem{Brlek:2003}
S.~Brlek and A.~Ladouceur.
\newblock A note on differentiable palindromes.
\newblock {\em Theor. Comput. Sci.} {\bf 302} (1--3) (2003), 167--178.

\bibitem{Brlek:2006}
S.~Brlek, S.~Dulucq, A.~Ladouceur, and L.~Vuillon.
\newblock Combinatorial properties of smooth infinite words.
\newblock {\em Theor. Comput. Sci.} {\bf 352} (1) (2006), 306--317.

\bibitem{Carpi:1993c}
A.~Carpi.
\newblock Repetitions in the {Kolakovski} [sic] sequence.
\newblock {\em Bull. European Assoc. Theor. Comput. Sci.}, No.\ 50, (1993),
  194--196.

\bibitem{Carpi:1994}
A.~Carpi.
\newblock On repeated factors in {$C^\infty$}-words.
\newblock {\em Inform. Process. Lett.} {\bf 52} (1994), 289--294.

\bibitem{Chvatal:1994}
V.~{Chv\'atal}.
\newblock Notes on the {Kolakoski} sequence.
\newblock Technical Report 93-84, DIMACS, March 1994.
\newblock Revised.

\bibitem{Culik&Karhumaki&Lepisto:1992}
K.~Culik~II, J.~{Karhum\"aki}, and A.~{Lepist\"o}.
\newblock Alternating iteration of morphisms and the {Kolakovski} [sic]
  sequence.
\newblock In G.~Rozenberg and A.~Salomaa, editors, {\em Lindenmayer Systems},
  pp.\ 93--103. Springer-Verlag, 1992.

\bibitem{Dekking:1997}
F.~M. Dekking.
\newblock What is the long range order in the {Kolakoski} sequence?
\newblock In R.~V. Moody, editor, {\em The Mathematics of Long-Range Aperiodic
  Order}, Vol.\ 489 of {\em NATO ASI Ser., Ser. C., Math. Phys. Sci.}, pp.\ 
  115--125. Kluwer, 1997.

\bibitem{Kimberling:1979}
C.~Kimberling.
\newblock Advanced problem 6281.
\newblock {\em Amer. Math. Monthly} {\bf 86} (1979), 793.

\bibitem{Kolakoski:1965}
W.~Kolakoski.
\newblock Elementary problem 5304.
\newblock {\em Amer. Math. Monthly} {\bf 72} (1965), 674.
\newblock Solution in \emph{Amer. Math. Monthly} {\bf 73} (1966),
681--682.

\bibitem{Lepisto:1994}
A.~{Lepist\"o}.
\newblock Repetitions in {Kolakoski} sequence.
\newblock In G.~Rozenberg and A.~Salomaa, editors, {\em Developments in
  Language Theory}, pp.\ 130--143. World Scientific, 1994.

\bibitem{Paun:1993}
G.~{Paun}.
\newblock How much {Thue} is {Kolakovski} [sic]?
\newblock {\em Bull. European Assoc. Theor. Comput. Sci.},
No.\ 49, (February 1993), 183--185.

\bibitem{Steacy:1996}
R.~Steacy.
\newblock Structure in the {Kolakoski} sequence.
\newblock {\em Bull. European Assoc. Theor. Comput. Sci.},
No.\ 59, (1996), 173--182.

\bibitem{Steinsky:2006}
B.~Steinsky.
\newblock A recursive formula for the {Kolakoski} sequence \seqnum{A000002}.
\newblock {\em J. Integer Seq.} {\bf 9} (3) (2006), 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Steinsky/steinsky5.html}{Article 06.3.7}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 68R15; Secondary 11Y55, 11B83.

\noindent \emph{Keywords: } Kolakoski sequence, integer sequences,
differentiable sequences, smooth sequences, combinatorics of words.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000002},
\seqnum{A078880},
\seqnum{A156253},
\seqnum{A156351}, and
\seqnum{A156728}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 8 2009;
revised version received February 25 2010.
Published in {\it Journal of Integer Sequences}, February 25 2010.

\bigskip
\hrule
\bigskip

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


\end{document}