\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{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{amsthm}

\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 Self-Indexed Sequence}

\vskip 1cm
\large
Emmanuel Preissmann \\
11 rue Vinet \\
1004 Lausanne \\
Switzerland \\
\href{mailto:emmanuel.preissmann@lth.epfl.ch}{\tt emmanuel.preissmann@lth.epfl.ch} \\
\end{center}

\vskip .2 in
\begin{abstract}
We investigate the integer sequence $\left(t_{n}\right)_{n\in\mathbb{Z}}$
defined by $t_{n}=0$ if $n\leq0$, $t_{1}=1$,
and $t_{n}=\sum_{i=1}^{n-1}t_{n-t_{i}}$ for $n \geq 2$.
This sequence has the following properties: if we consider $f_{n}(X):=-1+\sum_{i=1}^{n}X^{t_{i}}$
and take $x_{n}$ to be the real positive number such that $f_{n}(x_{n})=0$,
then \[
\lim_{n\rightarrow\infty}\frac{t_{n}}{t_{n+1}}=\lim_{n\rightarrow\infty}x_{n}=0.410098516\cdots\]
Moreover, if $u$ is the real positive number such that $1=\sum_{i=1}^{\infty}
u^{-t_i}$, then there is a positive constant $M$ such that $t_n\sim Mu^n$.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 
\newtheorem{remark}{Remark}[section]


%\documentclass[12pt]{amsart}
%\usepackage[T1]{fontenc}
%\usepackage[latin1]{inputenc}
%\pagestyle{empty}
%\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 %\theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 %\theoremstyle{plain}
 %\theoremstyle{plain}    
 %\newtheorem*{thm*}{Theorem} 
 %\theoremstyle{plain}    
 %\newtheorem*{cor*}{Corollary}
 %\theoremstyle{plain}    
 %\newtheorem{lem}[thm]{Lemma} %%Delete [thm] to re-start numbering
 %\theoremstyle{remark}
 %\newtheorem*{rem*}{Remark}
 %\theoremstyle{remark}    
 %\newtheorem*{acknowledgement*}{Acknowledgement} 
 %\usepackage{verbatim}

%\usepackage{babel}
%\makeatother
%\begin{document}



\section{Definitions and main results}

If we look in the \href{http://www.research.att.com/~njas/sequences/index.html}{Online Encyclopedia of Integer Sequences} of
N.~J.~A.~Sloane 
\cite{ref1}, we
find a remarkable sequence by $\left(t_{n}\right)_{n\in\mathbb{Z}}$
defined by $t_{n}=0$ if $n\leq0$, $t_{1}=1$ and\begin{eqnarray}
t_{n} & = & \sum_{i=1}^{n-1}t_{n-t_{i}}\label{eq:1}\end{eqnarray}
for $n \geq 2$.
This sequence is due to Robert Lozyniak (\seqnum{A052109} in Sloane)
and is a cousin of the Hofstadter-Conway \$10,000 challenge sequence
(\seqnum{A004001} in Sloane).

We find $t_{2}=1,t_{3}=2,t_{4}=5,t_{5}=12,t_{6}=30,t_{7}=73,\ldots$
Observe that if $n\geq2$ , $t_{n+1}=2t_{n}+\cdots\geq2t_{n}$. Since
$t_{4}=4+1$, we have\begin{equation}
t_{n}\geq n+1\quad(n\geq4)\label{eq:2}\end{equation}
The serie $\sum_{i=1}^{\infty}X^{t_{i}}=2X+X^{2}+\cdots$ converges
for $\left|X\right|<1$. Let $u$ be the real positive number such
that\begin{equation}
\sum_{i=1}^{\infty}u^{-t_{i}}=1\label{eq:3}\end{equation}
 We easily see that $2<u<3$.
 Indeed we have $\sum_{i=1}^{\infty}\left(\frac{1}{2}\right)^{t_{i}}=\frac{1}{2}+\frac{1}{2}+\cdots>1$
and $\sum_{i=1}^{\infty}\left(\frac{1}{3}\right)^{t_{i}}<\frac{2}{3}+\frac{1}{9}\sum_{i=0}^{\infty}\left(\frac{1}{3}\right)^{i}=\frac{5}{6}$.

\begin{theorem}
There exists a positive constant $M$ such that \[
\lim_{n\rightarrow\infty}\frac{t_{n}}{u^{n}}=M .\] 
\end{theorem}

\begin{corollary}
Let $n\geq2$ be an integer. Let $f_{n}(X)=-1+\sum_{i=1}^{n}X^{t_{i}}$
and take $x_{n}$ the real positive number such that $f_{n}(x_{n})=0$.
Then\[
\lim_{n\rightarrow\infty}\frac{t_{n}}{t_{n+1}}=
\frac{1}{u}=\lim_{n\rightarrow\infty}x_{n}=0.410098516\cdots . \]
\end{corollary}

\begin{proof}
By the theorem, $t_n\sim Mu^n$, therefore
$\lim_{n\rightarrow\infty}\frac{t_{n}}{t_{n+1}}=\frac{1}{u}$  .



In addition, the sequence $\left(x_{n}\right)_{n=1}^{\infty}$ is strictly
decreasing. Indeed,\[
\sum_{i=1}^{n}x_{n}^{t_{i}}=1=\sum_{i=1}^{n+1}x_{n+1}^{t_{i}}\]
so that \[
\sum_{i=1}^{n}\left(x_{n+1}^{t_{i}}-x_{n}^{t_{i}}\right)=-x_{n+1}^{t_{n+1}}<0\]
This proves that $x_{n+1}<x_{n}$ for every $n$. Moreover, this sequence
is bounded, so it converges to an element, say $v$. The function
$f_{\infty}(x)=-1+\sum_{i=1}^{\infty}x^{t_{i}}$ is continuous. Let
$\epsilon>0$. We have\[
0<f_{\infty}(x_n)=\sum_{i=n+1}^{\infty}x_{n}^{t_{i}}<\epsilon\]
 if $n$ is big enough. Finally, \[
f_{\infty}(v)=\lim_{n\rightarrow\infty}f_{\infty}(x_n)=0 .\]
That is, $v=\frac{1}{u}$, because $\frac{1}{u}$ is the only positive
zero of $f_{\infty}$. 
\end{proof}

\section{Proof of the Theorem }

We begin with a lemma:

\begin{lemma}
\label{lem:1}If $0\leq v_{n}<1$ for every integer $n>0$, then the
following inequalities are equivalent\begin{eqnarray}
\sum_{n=1}^{\infty}v_{n} & < & \infty\label{eq:a}\\
\prod_{n=1}^{\infty}\left(1-v_{n}\right) & > & 0 .\label{eq:b}\end{eqnarray}
\end{lemma}

\begin{proof}
Without loss of generality, we can suppose that $v_{n}\leq\frac{1}{2}$.
If an infinite number of $v_{n}>\frac{1}{2}$, the claims \ref{eq:a}
and \ref{eq:b} are both wrong, otherwise we can take out the finite
number of $v_{n}>\frac{1}{2}$. By Taylor expansion, we have for $0\leq x \leq
\frac{1}{2}$
\[
-\log(1-x)=x+\frac{1}{2} \frac{x^2}{(1-\theta x)^{2}},\quad0\leq\theta\leq1 ;
\]
hence $x\leq-\log(1-x)\leq2x$ for $0\leq x\leq\frac{1}{2}$. It follows
that for every integer $N>0$ we have\[
\sum_{n=1}^{N}v_{n}\leq-\log\prod_{n=1}^{N}\left(1-v_{n}\right)\leq2\sum_{n=1}^{N}v_{n} .\]
So the lemma is proved.
\end{proof}

\begin{lemma}
\label{lem:2}There exists a constant $d$ such that\[
0<d\leq\frac{t_{n}}{u^{n}}\quad\textrm{for every integer }n>0 . \] 
\end{lemma}

\begin{proof}
Suppose that $n\geq4$ and $d_{n}$ is such that $0<d_{n}\leq\frac{t_{k}}{u^{k}}$
for $1\leq k\leq n$. Then we have\[
t_{n+1}=\sum_{i=1}^{n}t_{n+1-t_{i}}\geq
\sum_{i=1 \atop n+1-t_{i}>0}^{n}d_{n}u^{n+1-t_{i}} . \]
By Eq.\ (\ref{eq:2}), $n+1-t_{n}\leq0$. Hence\[
t_{n+1}\geq d_{n}u^{n+1}\sum_{i=1 \atop n+1-t_i >
0}^{n}u^{-t_{i}}=d_{n}u^{n+1}\sum_{i=1 \atop n+1-t_i > 0}^{\infty}u^{-t_{i}}=d_{n}u^{n+1}(1-v_{n})\]
where $v_{n}=\sum_{i=1,\, t_{i}\ge n+1}^{\infty}u^{-t_{i}}$ by definition
of $u$. So we have\begin{equation}
d_{n}(1-v_{n})\leq\frac{t_{k}}{u^{k}}\quad\textrm{for }1\leq k\le n+1 .
\label{eq:4}
\end{equation}
The series
$$
\sum_{n=4}^{\infty}v_{n} =
\sum_{n=4}^{\infty}\sum_{i=1 \atop t_{i}\geq n+1}^{\infty}u^{-t_{i}}
= \sum_{i=1}^{\infty}u^{-t_i} \sum_{4\leq n<t_{i}}^{\infty}1\\
= \sum_{i=4}^{\infty}u^{-t_{i}}(t_{i}-4)
$$
is convergent; just compare this sum with $\frac{1}{(X-1)^{2}}=\sum_{i=1}^{\infty}iX^{i-1}$
for $\left|X\right|<1$. Set $d_{4}=\min_{1\leq k\leq4}\frac{t_{k}}{u^{k}}$.
By Lemma \ref{lem:1} and (\ref{eq:4}), $d=d_{4}\prod_{n=4}^{\infty}(1-v_{n})$
is such that $0<d\leq\frac{t_{n}}{u^{n}}$ for every positive integer
$n$.
\end{proof}

\begin{lemma}
\label{lem:3}For every integer $n$, one has $t_{n\ }\leq u^{n-1}$.
\end{lemma}

\begin{proof}
If $n\leq1$, this is evident. Suppose that $n\geq1$ and by induction
that $t_{i}\leq u^{i-1}$ when $i\leq n$. Then by (\ref{eq:1}) and
(\ref{eq:3}), we have\[
t_{n+1}=\sum_{i=1}^{n}t_{n+1-t_{i}}\leq\sum_{i=1}^{n} u^{n-t_i}\leq\sum_{i=1}^{\infty}u^{n-t_{i}}=u^{n}. \] 
\end{proof}

\begin{remark}
Let $N\geq1$. Set $C_{N}=\sup_{n\geq N}\left(\frac{t_{n}}{u^{n}}\right)$
and $D_{N}=\inf_{n\geq N}\left(\frac{t_{n}}{u^{n}}\right)$. Lemmas
\ref{lem:2} and \ref{lem:3} prove that $C=\lim_{N\rightarrow\infty}C_{N}$
and $D=\lim_{N\rightarrow\infty}D_{N}$ with $0<D\leq C$ are meaningful.
Define $\left(t'_{n}\right)_{n\in\mathbb{Z}}$ by $t'_{i}=0$ when
$i\leq1$, $t'_{2}=1$ and for $n\geq3$ define
\begin{equation}
t'_{n}=\sum_{i=1}^{\infty}t'_{n-t_{i}} . \label{eq:5}\end{equation}
 Define also $\left(a{}_{n}\right)_{n\in\mathbb{Z}}$ by $a_{n}=0$
when $n\leq0$, $a_{1}=1$ and for $n\geq2$:\begin{equation}
a_{n}=1+\sum_{i=1}^{\infty}a{}_{n-t_{i}} .\label{eq:6}\end{equation}
\end{remark}

\begin{lemma}
\label{lem:4}Let $n$, $N$, $k$ be positive integers such that
$n>N\geq1$.   Then we have \[
t_{n+k}\leq t'_{k+2}t_{n}+u^{n+k}C_{N}\left(1-\frac{t'_{k+2}}{u^{k}}\right)+a_{k}u^{N} . \]
\end{lemma}

\begin{proof}
By induction on $k$. For $k=0$, the claim is true. Suppose that $l\geq1$
and that the lemma is true for $k=0,1,\ldots,(l-1)$. By Eq.\ (\ref{eq:1}),
\[
t_{n+l}=\sum_{i=1}^{n+l-1}t_{n+l-t_i}\leq\sum_{i=1}^{\infty}t_{n+l-t_{i}}=
\Sigma_{1}+\Sigma_{2}+\Sigma_{3}\]
where\begin{eqnarray*}
\Sigma_{1} & = & \sum_{i=1 \atop n+l-t_{i}\geq n}^{\infty}t_{n+l-t_{i}}\\
\Sigma_{2} & = & \sum_{i=1 \atop N\leq n+l-t_{i}<n}^{\infty}t_{n+l-t_{i}}\\
\Sigma_{3} & = & \sum_{i=1 \atop n+l-t_{i}<N}^{\infty}t_{n+l-t_{i}} . \end{eqnarray*}
By induction we have \[
\Sigma_{1}\leq\sum_{i=1 \atop l-t_{i}\geq0}^{\infty} \left(
t'_{l-t_{i}+2}t_{n}+u^{n+l-t_{i}}C_{N}(1-\frac{t'_{l-t_{i}+2}}{u^{l-t_{i}}})
+a_{l-t_{i}}u^{N}\right) . \]
By the definition of $C_{N}$\[
\Sigma_{2}\leq\sum_{i=1\atop N\leq n+l-t_{i}<n}^{\infty}C_{N}u^{n+l-t_{i}} . \] 
By Lemma \ref{lem:3} and the fact that $u>2$,\[
\Sigma_{3}\leq\sum_{i=1}^{N}t_{i}\leq\sum_{i=0}^{N-1}u^{i}=\frac{u^{N}-1}{u-1}<u^{N} . \]
Finally\[
t_{n+l}\leq t_{n}\sum_{i\geq 1 \atop
l-t_{i}\geq0}t'_{l-t_{i}+2}+C_{N}\sum_{i\geq 1 \atop n+l-t_{i}\geq
N}u^{n+l-t_{i}}-C_{N}\sum_{i\geq 1 \atop
l-t_{i}\geq0}u^{n}t'_{l-t_{i}+2}+\sum_{i\geq 1 \atop l-t_{i}\geq0}a_{l-t_{i}}u^{N}+u^{N} .\]
This means by (\ref{eq:5}), (\ref{eq:6}) and (\ref{eq:3}) that\[
t_{n+l}\leq t'_{l+2}t_{n}+u^{n+l}C_{N}(1-\frac{t'_{l+2}}{u^{l}})+a_{l}u^{N}. \]
\end{proof}

\begin{lemma}
\label{lem:5}There exists $d'>0$ such that $d'\leq\frac{t'_{n}}{u^{n}}$
for every $n\geq2$.
\end{lemma}

\begin{proof}
Suppose that $d'_{n}\leq\frac{t'_{k}}{u^{k}}$ for every $2\leq k\leq n$.
Then\[
t'_{n+1}=
\sum_{i=1}^{\infty}t'_{n+1-t_{i}}\geq
\sum_{i=1,\, n+1-t_{i}>1}^{\infty}d'_{n}u^{n+1-t_{i}} .\]
So we proved $\frac{t'_{n+1}}{u^{n+1}}\geq d'_{n}
(1-\sum_{i=1,\, t_{i}\geq n}^{\infty}u^{-t_{i}})=d'_{n}(1-v_{n-1})$,
with $v_{n}$ defined as in Lemma \ref{lem:2}. Hence, $0<d'=\frac{1}{u^{2}}\prod_{n\geq1}(1-v_{n})$
is such that $d'\leq\frac{t'_{n}}{u^{n}}$ for every $n\geq2$.
\end{proof}

\begin{lemma}
\label{lem:6}We have $a_{m}\leq u^{m}-1$ for every integer $m>0$.
\end{lemma}

\begin{proof}
For $m=1,$ this is true. if $m\geq2$, we see by induction that \[
a_{m}=1+\sum_{i=1,\, m>t_{i}}^{\infty}a_{m-t_{i}}\leq1+\sum_{i=1,\, m>t_{i}}^{\infty}(u^{m-t_{i}}-1)\]
Since $\sum_{i=1,\, m>t_{i}}1\geq2$ and by (\ref{eq:3}),\[
a_{m}\leq1-\sum_{i=1,\: m>t_{i}}^{\infty}1+u^{m}\sum_{i=1,\: m>t_{i}}^{\infty}u^{-t_{i}}<u^{m}-1\]

\end{proof}
\emph{Proof of the Theorem.} 
According to Lemmas (\ref{lem:4}), (\ref{lem:5}), (\ref{lem:6})
and the definition of $C_{N}$, we have, for $1\leq N<n$ and $k\geq0$:\[
t_{n+k}\leq C_{N}u^{n+k}-t'_{k+2}(C_{N}u^{n}-t_{n})+a_{k}u^{N}\leq C_{N}u^{n+k}-d'u^{k+2}(C_{N}u^{n}-t_{n})+u^{N+k}\]
Let $\epsilon>0$. There exists $N$ such that $C\leq C_{N}<C+\epsilon$,
and $n>N$ such that $u^{N-n}<\epsilon$ and $\frac{t_{n}}{u^{n}}<D+\epsilon.$
In these conditions, we have \[
\frac{t_{n+k}}{u^{n+k}}<C+\epsilon-d'u^{2}(C-D-\epsilon)+\epsilon .\]
There exists $k$ such that $\frac{t_{n+k}}{u^{n+k}}>C-\epsilon.$
Then $C-\epsilon<C+\epsilon-d'u^{2}(C-D-\epsilon)+\epsilon$. 
Letting $\epsilon$ tend to 0 gives $C\leq C-d'u^2(C-D)$.
Hence $d'u^2(C-D)\leq 0$. This implies $C\leq D$ and thus $C=D$.

\section{Acknowledgments}

I am grateful to M. Mischler for valuable help and many fruitful discussions
during the course of this work.

%\begin{comment}
%\[
%\Sigma_{1}=\sum_{n+l-t_{i}\geq n}t_{n+l-t_{i}},\:,\Sigma_{2}=\sum_{N\leq n+l-t_{i}<n}t_{n+l-t_{i}}\textrm{, and }\Sigma_{3}=\sum_{n+l-t_{i}<n}t_{n+l-t_{i}}\]
%the three sums run from $n=1$to infinity.\end{comment}

\begin{thebibliography}{XX}

\bibitem{ref1}N.~J.~A.~Sloane, Online Encyclopedia of Integer Sequences,\\
\href{http://www.research.att.com/~njas/sequences}{http://www.research.att.com/\textasciitilde{}njas/sequences/}

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11Y55.

\noindent \emph{Keywords: } integer sequences.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A052109}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 16 2005;
revised version received  July 28 2005.
Published in {\it Journal of Integer Sequences}, August 2 2005.

\bigskip
\hrule
\bigskip

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



\end{document}