\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}

\def\R{\mathbb R}

\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 On Families of Nonlinear Recurrences\\ \vskip
0.3cm Related to Digits} \vskip 1cm  

\large
Th.~Stoll\footnote{Supported in part by the Austrian Science
Foundation (FWF) FSP-Project S8302-MAT}\\
Faculty of Mathematics \\
University of Vienna \\
Nordbergstra\ss e 15\\
1090 Vienna\\
Austria \\
\href{mailto:thomas.stoll@univie.ac.at}{\tt thomas.stoll@univie.ac.at} \\
and \\
Institute of Discrete Mathematics and Geometry \\
Wiedner Hauptstra\ss e 8--10\\
1040 Vienna\\
Austria\\
\href{mailto:stoll@dmg.tuwien.ac.at}{\tt stoll@dmg.tuwien.ac.at} \\
\end{center}

\vskip .2 in
\begin{abstract}
Consider the sequence of positive integers $(u_n)_{n\geq 1}$
defined by $u_1=1$ and
$u_{n+1}=\lfloor\sqrt{2}\left(u_n+\frac{1}{2}\right) \rfloor$.
Graham and Pollak discovered the unexpected fact that
$u_{2n+1}-2u_{2n-1}$ is just the $n$-th digit in the binary
expansion of $\sqrt{2}$. Fix $w\in \R_{>0}$. In this note, we
first give two infinite families of similar nonlinear recurrences
such that $u_{2n+1}-2u_{2n-1}$ indicates the $n$-th binary digit
of $w$. Moreover, for all integral $g\geq 2$, we establish a
recurrence such that $u_{2n+1}-gu_{2n-1}$ denotes the $n$-th digit
of $w$ in the $g$-ary digital expansion.
\end{abstract}


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


% \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{graphics,amsmath,amssymb}
% \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}}}
% 
% \renewcommand{\theequation}{\arabic{equation}}
% 
\newtheorem{prop}{Proposition}
% \newtheorem{lemma}[prop]{Lemma}
% \newtheorem{cor}{Corollary}
% \newtheorem{corollary}[cor]{Corollary}
% \newtheorem{conj}[prop]{Conjecture}
% \newtheorem{defi}[prop]{Definition}
% \newtheorem{theorem}[prop]{Theorem}
\newtheorem{fac}[prop]{Fact}
% \newtheorem{facs}[prop]{Facts}
% \newtheorem{com}[prop]{Comments}
% \newtheorem{prob}{Problem}
% \newtheorem{problem}[prob]{Problem}
% \newtheorem{ques}{Question}
% \newtheorem{question}[ques]{Question}
% \newtheorem{remark}[prop]{Remark}
% 
% \def\ord{{\mathrm{ord}}}
% \def\scr{\scriptstyle}
% \def\\{\cr}
% \def\({\left(}
% \def\){\right)}
% \def\[{\left[}
% \def\]{\right]}
% \def\<{\langle}
% \def\>{\rangle}
% \def\fl#1{\left\lfloor#1\right\rfloor}
% \def\rf#1{\left\lceil#1\right\rceil}
% \def\lcm{{\rm lcm\/}}
% 
% \def\C{\mathbb C}
% \def\Q{{\mathbb Q}}
% \def\F{{\mathbb F}}
\def\Z{{\mathbb Z}}
% \def\cO{{\mathcal O}}
% 
% \def\ord{{\mathrm{ord}}}
% \def\Nm{{\mathrm{Nm}}}
% \def\L{{\mathbb L}}
% 
% \def\xxx{\vskip5pt\hrule\vskip5pt}
% \def\yyy{\vskip5pt\hrule\vskip2pt\hrule\vskip5pt}



\section{Introduction}

In 1969, Hwang and Lin~\cite{HL69} studied Ford and Johnson's
algorithm for sorting partially-sorted sets (see also~\cite{K73}).
In doing so, they came across the sequence of integers
$$1,\,2,\,3,\,4,\,6,\,9,\,13,\,19,\,27,\,38,\,54,\,77,\,109\ldots$$
defined by the nonlinear recurrence
\begin{equation}\label{def1}
u_1=1,\qquad u_{n+1}=\left\lfloor \sqrt{2u_n(u_n+1)}\right\rfloor,
\quad n\geq 1.
\end{equation}
Since there is no integral square between $2u_n^2+2u_n$ and
$2u_n^2+2u_n+\frac{1}{2}=2(u_n+\frac{1}{2})^2$ we can rewrite the
recurrence in a more striking form, i.e.,
\begin{equation}\label{def2}
u_1=1,\qquad u_{n+1}=\left\lfloor \sqrt{2}(u_n+1/2)\right\rfloor,
\quad n\geq 1.
\end{equation}
While investigating closed-form expressions for $u_n$
in~(\ref{def2}), Graham and Pollak~\cite{GP70} discovered the
following amazing fact:

\begin{fac}[Graham/Pollak]\label{GPfact}
We have that $$d_n=u_{2n+1}-2u_{2n-1}$$ is the $n$-th digit in the
binary expansion of $\sqrt{2}=(1.011010100\ldots)_2$.
\end{fac}

Since then, sequences arising from the recurrence relation given
in~(\ref{def2}) are referred to as Graham-Pollak
sequences~\cite{S05,W05}. Sloane~\cite{S05} gives three special
sequences depending on the initial term $u_1$, i.e., sequence
\seqnum{A001521} for $u_1=1$, \seqnum{A091522} for $u_1=5$ and
sequence \seqnum{A091523} for $u_1=8$.


The curiosity of Fact~\ref{GPfact} has drawn the attention of
several mathematicians and has been cited a few times, see Ex. 30
in Guy~\cite{G88}, Ex. 3.46 in Graham/Knuth/Patashnik~\cite{GKP94}
and in Borwein/Bailey~\cite[pp.~62--63]{BB04}. A generalization to numbers
other than $\sqrt{2}$ is, however, not straightforward from
Graham and Pollak's proof. Nevertheless, Erd{\H{o}}s and
Graham~\cite[p.~96]{EG80} suspected that similar results would also
hold ``for $\sqrt{m}$ and other algebraic numbers'', but they
concluded that ``we have no idea what they are.''

By applying a computational guessing approach,
Rabinowitz and Gilbert~\cite{RG91} could give an answer in the
binary case:
\begin{theorem}[Rabinowitz/Gilbert]\label{RGtheo}
Let $w\in \R_{>0}$ and $t=w/2^m$, where $m=\lfloor\log_2
w\rfloor$. Furthermore, set
$$a=2\left(1-\frac{1}{t+2}\right),\qquad b=\frac{2}{a}.$$
Define a sequence $(u_n)_{n\geq 1}$ by the recurrence
\begin{align*}
  u_1&=1\\
  u_{n+1}&=
 \begin{cases} \lfloor a(u_n+1/2)\rfloor, & \mbox{if }n\mbox{ is odd;} \\
               \lfloor b(u_n+1/2)\rfloor, & \mbox{if }n\mbox{ is even.}
 \end{cases}
\end{align*}
Then $u_{2n+1}-2u_{2n-1}$ is the $n$-th digit in the binary
expansion of $w$.
\end{theorem}
Note that for $w=\sqrt{2}$ we get $a=b=\sqrt{2}$ and the statement
of Fact~\ref{GPfact} is obtained. However, the values of $a$ and
$b$ in Theorem~\ref{RGtheo} are somehow wrapped in mystery.
Rabinowitz and Gilbert first varied $a$ and $b$ in order that
$u_{2n+1}-2u_{2n-1}\in\{0,1\}$. They found that $ab=2$ and
discovered that the represented $w$ indeed equals $2(a-1)/(2-a)$
provided that $1<a<3/2$.

It is a natural question to ask, whether there exist other values
of $a$ and $b$ such that the binary expansion of $w$ is obtained.
Here we prove

\begin{theorem}\label{mtheo1}
Let $w\in \R_{>0}$ and $t=w/2^m$, where $m=\lfloor\log_2
w\rfloor$. Furthermore, let $j\in \Z_{>0}$ and set the values of
$a$ and $b$ according to one of the following cases:
\begin{itemize}
\item[]{\sc Case~I:}
$$a=2\left(j-\frac{1}{t+2}\right),\qquad\quad b=\frac{2}{a}.$$
\item[]{\sc Case~II:} $$a=2 j-\frac{t}{t+2},\qquad\quad
b=\frac{2}{a}.$$
\end{itemize}
Define a sequence $(u_n)_{n\geq 1}$ by the recurrence
\begin{align*}
  u_1&=1\\
  u_{n+1}&=
 \begin{cases} \lfloor a(u_n+1/2)\rfloor, & \mbox{if }n\mbox{ is odd;} \\
               \lfloor b(u_n+\varepsilon)\rfloor, & \mbox{if }n\mbox{ is even,}
 \end{cases}
\end{align*}
where $1/3\leq \varepsilon< 2/3$ in {\sc Case~I} and
$\varepsilon=1/2$ in {\sc Case~II}, respectively. Then
$u_{2n+1}-2u_{2n-1}$ is the $n$-th digit in the binary expansion
of $w$.
\end{theorem}

In the closing paragraph of~\cite{RG91}, the authors finally posed
the question, whether there exists an analogous statement for
ternary digits. Here we prove

\begin{theorem}\label{mtheo2}
Let $w\in \R_{>0}$ and $g\geq 2$ be an integer. Furthermore, set
$t=w/g^m$, where $m=\lfloor\log_g w\rfloor$ and
$$a=\frac{g}{(g-1)(t+g)},\qquad b=\frac{g}{a}.$$
Define a sequence $(u_n)_{n\geq 1}$ by the recurrence
\begin{align*}
  u_1&=1\\
  u_{n+1}&=
 \begin{cases} \lfloor a(u_n+\varepsilon)\rfloor, & \mbox{if }n\mbox{ is odd;} \\
               \lfloor b(u_n+1/(g-1))\rfloor, & \mbox{if }n\mbox{ is even,}
 \end{cases}
\end{align*}
where $-1/g \leq \varepsilon<(g+1)(g-2)/g$. Then $u_{2n+1}-gu_{2n-1}$
is the $n$-th digit in the $g$-ary digital expansion of $w$.
\end{theorem}

In view of Fact~\ref{GPfact}, we note two immediate consequences of
Theorem~\ref{mtheo1} and Theorem~\ref{mtheo2}. To begin with, we substitute
$w=t=\sqrt{2}$ in {\sc Case~I} and {\sc Case~II} of Theorem~\ref{mtheo1}. This
implies $a=2j-2+\sqrt{2}$ ({\sc Case~I}) and $a=2j+1-\sqrt{2}$ ({\sc Case~II})
for $j\geq 1$. By ordering all such values into a single sequence, we obtain

\begin{corollary}
  Let $a_j=j+(-1)^j\sqrt{2}$ for $j=0,2,3\ldots$ and $b_j=2/a_j$.
  Define a sequence $(u_n)_{n\geq 1}$ by
  \begin{align*}
    u_1&=1\\
    u_{n+1}&=
   \begin{cases} \lfloor a_j(u_n+1/2)\rfloor, & \mbox{if }n\mbox{ is odd;} \\
               \lfloor b_j(u_n+1/2)\rfloor, & \mbox{if }n\mbox{ is even.}
   \end{cases}
  \end{align*}
Then $u_{2n+1}-2u_{2n-1}$ is the $n$-th digit in the binary
expansion of $\sqrt{2}=(1.011010100\ldots)_2$.
\end{corollary}

Note that for $j=1$ we have $a_1=1-\sqrt{2}<0$ and $u_5-2 u_3=7-2\cdot 2=3$,
which is not a binary digit.

On the other hand, if we take $g=3$, $w=t=\sqrt{2}$
and $\varepsilon=1/2$ in Theorem~\ref{mtheo2}, we get

\begin{corollary}
  Define a sequence $(u_n)_{n\geq 1}$ by
  \begin{align*}
    u_1&=1\\
    u_{n+1}&=
   \begin{cases} \lfloor a(u_n+1/2)\rfloor, & \mbox{if }n\mbox{ is odd;} \\
               \lfloor b(u_n+1/2)\rfloor, & \mbox{if }n\mbox{ is even,}
   \end{cases}
  \end{align*}
  where $a=(9-3\sqrt{2})/14$ and $b=6+2\sqrt{2}$. Then $u_{2n+1}-3u_{2n-1}$
  is the $n$-th digit in the ternary expansion of $\sqrt{2}=(1.102011221\ldots)_3$.
\end{corollary}

\section{Proofs}

For later reference we state an easy, but useful proposition.

\begin{prop}\label{prop1}
  Let $g\geq 2$ be an integer and $w=(d_1 d_2 d_3\ldots)_g$ be the
  $g$-ary digital expansion of $w$ with $d_1\neq 0$ and $0\leq
  d_n<g$ for $n\geq 1$. Suppose further that for $n\geq 1$ not all of $d_n,d_{n+1},\ldots$
  equal $g-1$. Then
  \begin{itemize}
  \item $t=(d_1.d_2 d_3\ldots)_g$ with $1\leq t<g$,
  \item $d_n=\lfloor t g^{n-1}\rfloor-g\lfloor tg^{n-2}\rfloor.$
  \end{itemize}
\end{prop}

\begin{proof}
  Since $m=\lfloor\log_g w\rfloor$ it is immediate that $1\leq w/g^m<g$. Moreover,
  $$\lfloor t g^{n-1}\rfloor-g\lfloor tg^{n-2}\rfloor=(d_1d_2\ldots d_n)_g-
  (d_1d_2\ldots d_{n-1}0)_g=d_n.$$
\end{proof}

\subsection{Proof of Theorem~\ref{mtheo1}}

First, we prove that in {\sc Case~I} there hold
\begin{align*}
u_{2k}&=2^{k-1}+\lfloor t 2^{k-1}\rfloor+(j-1)(2^k+2\lfloor t 2^{k-2}\rfloor+1),\\
u_{2k+1}&=2^k+\lfloor t 2^{k-1}\rfloor,
\end{align*}
so that Proposition~\ref{prop1} gives $u_{2n+1}-2u_{2n-1}=d_n$. To
begin with, we have $u_1=2^0+\lfloor t/2 \rfloor=1$ because of
$1\leq t<2$. We are going to employ an induction argument. Suppose
that the result holds true for $u_{2k-1}$. Then
\begin{align*}
  u_{2k}&=\left\lfloor 2\left(j-\frac{1}{t+2}\right)\left(2^{k-1}+\left\lfloor t2^{k-2}
  \right\rfloor+\frac{1}{2}\right)\right\rfloor\\
  &=(j-1)(2^k+2\lfloor t 2^{k-2}\rfloor+1)+
  \left\lfloor \left(1-\frac{1}{t+2}\right)
  \left(2^k+2\left\lfloor t 2^{k-2}\right\rfloor+1\right)\right\rfloor.
\end{align*}
Thus, it suffices to show that
\begin{equation}\label{prove1}
  \left\lfloor \frac{t+1}{t+2}\cdot
  \left(2^k+2\left\lfloor t 2^{k-2}\right\rfloor+1\right)\right\rfloor
  =2^{k-1}+\left\lfloor t 2^{k-1}\right\rfloor.
\end{equation}
Since $2\left\lfloor t2^{k-2}\right\rfloor=\left\lfloor
t2^{k-1}\right\rfloor-d_k$ by Proposition~\ref{prop1}, we may
rewrite~(\ref{prove1}) in the equivalent form
\begin{align*}
  (t+2)\left(2^{k-1}+\left\lfloor t2^{k-1}\right\rfloor\right)&\leq
(t+1)\left(2^k+\left\lfloor t 2^{k-1}\right\rfloor-d_k+1\right)\\
&<(t+2)\left(2^{k-1}+\left\lfloor t2^{k-1}\right\rfloor+1\right).
\end{align*}
Straightforward algebraic manipulation leads to
$$t2^{k-1}+\left\lfloor t2^{k-1}\right\rfloor\leq t2^k+(1-d_k)(t+1)<
\left(t2^{k-1}+\left\lfloor
t2^{k-1}\right\rfloor+1\right)+1\cdot(t+1),$$ which is obviously
true because of $\left\lfloor t2^{k-1}\right\rfloor\leq t2^{k-1}<
\left\lfloor t2^{k-1}\right\rfloor+1.$

\noindent Now, assume that the result is true for $u_{2k}$. Thus,
we have to show that
\begin{equation}\label{prove2}
u_{2k+1}=\left\lfloor\frac{t+2}{j(t+2)-1}(u_{2k}+\varepsilon)\right\rfloor=
2^k+\lfloor t2^{k-1}\rfloor.
\end{equation}
The equality of integer floors~(\ref{prove2}) can be rewritten in
terms of two inequalities, i.e.,
\begin{align*}
 (j(t+2)-1)(2^k+\left\lfloor t2^{k-1}\right\rfloor)&\leq
 (t+2)\left(2^{k-1}+\left\lfloor t2^{k-1}\right\rfloor+
 \varepsilon+(j-1)(2^k+2\left\lfloor t2^{k-2}\right\rfloor+1)\right)\\
 &<(j(t+2)-1)(2^k+\left\lfloor t2^{k-1}\right\rfloor+1).
\end{align*}
Again, we use Proposition~\ref{prop1} and proper term cancelling
such that~(\ref{prove2}) translates into
$$0\leq \left\lfloor t2^{k-1}\right\rfloor-t2^{k-1}+
(t+2)\left(\varepsilon+(j-1)(1-d_k)\right)<j(t+2)-1.$$ Since
$-1<\left\lfloor t2^{k-1}\right\rfloor-t2^{k-1}\leq 0$ and
$\varepsilon<2/3$ we have
$$\left\lfloor t2^{k-1}\right\rfloor-t2^{k-1}+
(t+2)\left(\varepsilon+(j-1)(1-d_k)\right)<(t+2)(2/3+(j-1))\leq
j(t+2)-1.$$ On the other hand, $\varepsilon\geq 1/3$ implies
$$\left\lfloor t2^{k-1}\right\rfloor-t2^{k-1}+
(t+2)\left(\varepsilon+(j-1)(1-d_k)\right)>-1+(t+2)\varepsilon\geq
0.$$ This finishes the proof of Theorem~\ref{mtheo1} for {\sc
Case~I}.

Let now $a$, $b$ and $\varepsilon$ be according to {\sc Case~II}.
Again, by Proposition~\ref{prop1} it suffices to show that
\begin{align*}
u_{2k}&=2^k+\lfloor t 2^{k-2}\rfloor+(j-1)(2^k+2\lfloor t 2^{k-2}\rfloor+1),\\
u_{2k+1}&=2^k+\lfloor t 2^{k-1}\rfloor.
\end{align*}
As before, we have $u_1=2^0+\lfloor t/2\rfloor=1$. Assume that the
closed-form expression holds true for $u_{2k-1}$. Then
\begin{align*}
  u_{2k}&=\left\lfloor \left(2j-\frac{t}{t+2}\right)\left(2^{k-1}+\left\lfloor t2^{k-2}
  \right\rfloor+\frac{1}{2}\right)\right\rfloor\\
  &=(j-1)(2^k+2\lfloor t 2^{k-2}\rfloor+1)+
  \left\lfloor \left(1-\frac{t}{2(t+2)}\right)
  \left(2^k+2\left\lfloor t 2^{k-2}\right\rfloor+1\right)\right\rfloor.
\end{align*}
Hence, it is sufficient to prove that
\begin{equation}\label{ineq1}
2^k+\lfloor t 2^{k-2}\rfloor\leq \frac{t+4}{2(t+2)}\cdot
(2^k+2\lfloor t2^{k-2}\rfloor+1)<2^k+\lfloor t 2^{k-2}\rfloor+1.
\end{equation}
By multiplying~(\ref{ineq1}) with $2(t+2)$ and simply canceling
out all terms with $\lfloor t2^{k-2}\rfloor$,~(\ref{ineq1})
simplifies to
\begin{equation}\label{ineq2}
  0\leq 4\left(\lfloor t 2^{k-2}\rfloor-t 2^{k-2}\right)+t+4<2t+4.
\end{equation}
Relation~(\ref{ineq2}) is obviously true, since $-1<\lfloor t
2^{k-2}\rfloor-t 2^{k-2}\leq 0$.

\noindent For the induction step from $u_{2k}$ to $u_{2k+1}$ we
have to ensure that
$$u_{2k+1}=\left\lfloor\frac{2(t+2)}{2j(t+2)-t}\left(u_{2k}+\frac{1}{2}\right)\right\rfloor
=2^k+\lfloor t2^{k-1}\rfloor,$$ or equivalently, that
\begin{align*}
  2^k+\lfloor t2^{k-1}\rfloor&\leq \frac{2(t+2)}{2j(t+2)-t}
  \left(2^k+\lfloor t 2^{k-2}\rfloor+\frac{1}{2}+(j-1)(2^k+2\lfloor t2^{k-2}\rfloor
  +1)\right)\\
  &<2^k+\lfloor t2^{k-1}\rfloor+1.
\end{align*}
We replace all $\lfloor t 2^{k-2}\rfloor$ by $\left(\lfloor t
2^{k-1}\rfloor-d_k\right)/2$ and after some term sorting we obtain
\begin{equation}\label{ineq3}
  0\leq (t+2)(2j-1)(1-d_k)+t 2^k-2\lfloor t
  2^{k-1}\rfloor<2j(t+2)-t.
\end{equation}
Since $0\leq t 2^k-2\lfloor t 2^{k-1}\rfloor=d_{k+1}+t 2^k-
\lfloor t 2^k\rfloor=(d_{k+1}.d_{k+2}d_{k+3}\ldots)_2<2$, the
inequalities given in~(\ref{ineq3}) hold true for all $k\geq 1$.
The proof of Theorem~\ref{mtheo1}, {\sc Case~II} is done. It is
not difficult to see that $\varepsilon=1/2$ cannot be replaced by
any other value.

\subsection{Proof of Theorem~\ref{mtheo2}}

Here we prove
\begin{align*}
u_{2k}&=(g^{k-1}-1)/(g-1),\\
u_{2k+1}&=g^k+\lfloor t g^{k-1}\rfloor.
\end{align*}
Similarly as before, the statement of Theorem~\ref{mtheo2} is then
obtained from Proposition~\ref{prop1}. Again, $u_1=g^0+\lfloor
t/g\rfloor=1$. Suppose first, the result holds for $u_{2k}$. Then
$$u_{2k+1}=\left\lfloor b\left(u_{2k}+\frac{1}{g-1}\right)\right\rfloor=
\left\lfloor (t+g)(g^{k-1}-1)+(t+g)\right\rfloor=g^k+\lfloor t
g^{k-1}\rfloor.$$ Vice versa, assume the result holds for
$u_{2k+1}$. Let $\{x\}$ denote the fractional part of $x\in
\R_{>0}$. Then
\begin{align*}
  u_{2k+2}&=\lfloor a(u_{2k+1}+\varepsilon)\rfloor=
  \lfloor a \lfloor g^{k-1} (t+g)\rfloor +a \varepsilon\rfloor\\
  &=\left\lfloor a\left\lfloor\frac{g^k}{a(g-1)}\right\rfloor+a\varepsilon\right\rfloor
  =\frac{g^k-1}{g-1}+\left\lfloor \frac{1}{g-1}-a\left\{\frac{g^k}{a(g-1)}\right\}
  +a\varepsilon\right\rfloor.
\end{align*}
Since $0<a\leq g/(g^2-1)$, we have $1/(g-1)-a\geq a/g$. Thus, for $\varepsilon\geq -1/g$
we get
$$\frac{1}{g-1}-a\left\{\frac{g^k}{a(g-1)}\right\}
  +a\varepsilon>\frac{1}{g-1}-a+a\varepsilon\geq\frac{a}{g}-\frac{a}{g}= 0.$$
On the other hand, if $\varepsilon<(g+1)(g-2)/g$ then
$$\frac{1}{g-1}-a\left\{\frac{g^k}{a(g-1)}\right\}
  +a\varepsilon\leq \frac{1}{g-1}+a\varepsilon <
  \frac{1}{g-1} +\frac{g}{g^2-1}\cdot\frac{(g+1)(g-2)}{g}=1.$$
This finishes the proof of Theorem~\ref{mtheo2}.

\section*{Acknowledgment}

The author wishes to thank the referee for her/his detailed remarks on the original
manu--script; in particular, for pointing out several inaccuracies in the statement of
the results.

\begin{thebibliography}{10}

\bibitem{BB04}
J.~Borwein and D.~Bailey, {\em Mathematics by Experiment}, Natick,
MA, 2003.

\bibitem{EG80}
P.~Erd{\H{o}}s and R.~L. Graham, {\em Old and New Problems and
Results in Combinatorial Number Theory}, L'Enseignement
Math\'ematique, Gen\`eve, 1980.

\bibitem{GKP94}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik, {\em Concrete
Mathematics}, Addison-Wesley, MA, second edition, 1994.

\bibitem{GP70}
R.~L. Graham and H.~O. Pollak, Note on a nonlinear recurrence
related to {$\sqrt 2$}, {\em Math. Mag.}, {\bf 43} (1970),
143--145.

\bibitem{G88}
R.~K. Guy, The strong law of small numbers, {\em Amer. Math.
Monthly}, {\bf 95} (1988), 697--712.

\bibitem{HL69}
F.~Hwang and S.~Lin, An analysis of {F}ord and {J}ohnson's sorting
algorithm, in: {\em Proc. Third Annual Princeton Conf. on Inform.
Sci. and Systems}, 1969, pp. 292--296.

\bibitem{K73}
D.~E. Knuth, {\em The Art of Computer Programming -- {V}olume 3},
Addison-Wesley, Mass.-London-Don Mills, Ont., 2nd ed., 1998.

\bibitem{RG91}
S.~Rabinowitz and P.~Gilbert, A nonlinear recurrence yielding
binary digits, {\em Math. Mag.}, {\bf 64} (1991), 168--171.

\bibitem{S05}
N.~J.~A. Sloane, {\em \htmladdnormallink{The On-Line Encyclopedia
of Integer Sequences}{http://www.research.att.com/~njas/sequences/}}, published
electronically at www.research.att.com/$\sim$njas/sequences,
1996--2005.

\bibitem{W05}
E.~W. Weisstein, {\em \htmladdnormallink{Graham-Pollak Sequence}{http://mathworld.wolfram.com/Graham-PollakSequence.html}} 
(from Mathworld, a Wolfram Web Re--source), 
http://mathworld.wolfram.com/Graham-PollakSequence.html,
1999--2005.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11B37; Secondary 11A67.

\noindent \emph{Keywords: } Graham-Pollak sequence, nonlinear
recurrence, digits.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A001521},
\seqnum{A091522} and \seqnum{A091523}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 1 2005;
revised version received May 12 2005.
Published in {\it Journal of Integer Sequences}, May 24 2005.

\bigskip
\hrule
\bigskip

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

\end{document}