%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-28/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{lmma}{Lemma}
\theoremstyle{remark}
\newtheorem*{rmrk}{Remark}
\newtheorem*{ackn}{Acknowledgement}

\theoremstyle{namedthrm}
\newtheorem{thrm}{Theorem}

\title{A Simple Proof of a Remarkable Continued Fraction Identity}
\author{
P. G. Anderson\footnote{Department of Computer Science, Rochester Institute of Technology, Rochester, New York 14623-0887. \texttt{pga@cs.rit.edu}},
T. C. Brown\footnote{Department of Mathematics and Statistics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6, Canada. \texttt{tbrown@sfu.ca}} and
P. J.-S. Shiue\footnote{Department of Mathematical Sciences, University of Nevada, Las Vegas, NV, USA 89154-4020. \texttt{shiue@nevada.edu}}}
\maketitle
\begin{center}{\small {\bf Citation data:} P.G. Anderson, T.C. Brown, and P.J.-S. Shiue, \emph{A simple proof of a
  remarkable continued fraction identity}, Proc. Amer. Math. Soc. \textbf{123}
  (1995), 2005--2009.}\bigskip\end{center}

\newcommand{\floor}[1]{{\left[{#1}\right]}}


\begin{abstract}We give a simple proof of a generalization of the equality
\[ \sum_{n=1}^\infty \frac1{2^\floor{n/\tau}} = [2, 2^0, 2^1, 2^1, 2^2, 2^3, 2^5, \ldots], \]
where $\tau = (1 + \sqrt5)/2$ and the exponents of the partial quotients
are the Fibonacci numbers, and some closely related results.
\end{abstract}

P. E. B\"ohmer \cite{bohmer1926}, L. V. Danilov \cite{danilov1972}, and W. W. Adams
and J. L. Davison \cite{adams+davison1977} showed independently that if $\alpha>0$
is irrational, $b>1$ is an integer, and $S_b(\alpha) = (b-1)\sum_{k=1}^\infty\frac1
{b^{\floor{k/\alpha}}}$, then the simple continued fraction for $S_b(\alpha)$ can
be described explicitly in the following way. Let $\alpha$ have simple continued
fraction
\[ \alpha = a_0 + \frac1{a_1 + \frac1{a_2 + \cdots}} = [a_0, a_1, \ldots], \]
with $\frac{p_n}{q_n} = [a_0,\ldots,a_n]$, $n\geq0$. Let $t_0=a_0b$, $t_n = \frac{b^{q_n}
- b^{q_n-2}}{b^{q_n-1}-1}$, $n\geq1$. Then $S_b(\alpha) = [t_0,t_1,\ldots]$. Thus
in the case $\alpha = \tau = (1+\sqrt5)/2$, the golden ratio, and $b=2$, one gets
the remarkable equality $\sum_{n=1}^\infty\frac1{2^{\floor{n/\tau}}} = [2,2^0,2^1,
2^2, 2^3, 2^5,\ldots]$, where the exponents of the partial quotients are the
Fibonacci numbers.

More recently, R. L. Graham, D. E. Knuth, and O. Patashnik \cite{graham+knuth+patashnik1989}
indicated how to give a very different proof of the power series version of this
result, where the number $b$ is replaced by an indeterminate (they carried out
the proof for the case $\alpha = (1+\sqrt5)/2$), using the continuant polynomials
of Euler \cite{euler1762}.

In this note we give a proof, which we feel is simpler than the others, which makes
use of a property of the ``characteristic sequence'' of $\alpha$ discovered by H.
J. S. Smith \cite{smith1876}. The crucial idea of our approach appears in Lemma
\ref{l2} below, where we regard certain initial segments of the characteristic
sequence of $\alpha$ as base $b$ representations of integers.

(B\"ohmer, Danilov, and Adams and Davison also show that $S_b(\alpha)$ is
transcendental for every irrational $\alpha$. We omit the proof of this fact,
which is an easy application of a theorem of Roth \cite{roth1955}, using
Lemma \ref{l3} and Theorem \ref{tB} below.)

\paragraph{Preliminaries.} Let $\alpha$ be an irrational number with $0<\alpha<1$.
(At the end, we will remove the restriction $\alpha<1$.) Let $\alpha = [0,a_1,
a_2,\ldots]$ and $\frac{p_n}{q_n} = [0,a_1,\ldots,a_n]$, $n\geq0$, where $p_n$,
$q_n$ are relatively prime non-negative integers. (As usual, we put $p_{-2} = 0$,
$p_{-1} = 1$, $q_{-2} = 1$, $q_{-1} = 0$, so that $p_n = a_np_{n-1} + p_{n-2}$,
$q_n = a_nq_{n-1} + q_{n-2}$ for all $n\geq0$.) For $n\geq1$, define $f_\alpha(n)
= \floor{(n+1)\alpha} - \floor{n\alpha}$, and consider the infinite binary
sequence $f_\alpha = (f_\alpha(n))_{n\geq1}$, which is sometimes called the
\emph{characteristic sequence} of $\alpha$. Define binary words $X_n$, $n\geq0$,
by $X_0=0$, $X_1 = 0^{a_1-1}1$, $X_k = X_{k-1}^{a_k}X_{k-2}$, $k\geq2$, where
$X^a$ denotes the word $X$ repeated $a$ times, and $X_1 = 1$ if $a_1 = 1$.

The following result was first proved by Smith \cite{smith1876}. Other proofs
can be found in \cite{brown1993,fraenkel+mushkin+tassa1978,shallit1991,
stolarsky1976}, and further references to the characteristic sequence can be
found in \cite{brown1993}. Nishioka, Shiokawa, and Tamura \cite{nishioka+shiokawa+tamura1992}
treat the more general case $\floor{(n+1)\alpha+\beta} - \floor{n\alpha+\beta}$.

\begin{lmma}\label{l1} For each $n\geq1$, $X_n$ is a prefix of $f_\alpha$.
That is, $X_n = f_\alpha(1)f_\alpha(2)\cdots f_\alpha(s)$, where $s$ is the
length of $X_n$.\end{lmma}

\paragraph{The main proof.} We are now ready to prove the result stated in
the Introduction. (However, we will keep the restriction $\alpha<1$ until the
following section.) Let $b>1$ be an integer, let $0<\alpha<1$ be irrational,
$\alpha = [0,a_1,a_2,\ldots]$, let $\frac{p_n}{q_n} = [0,a_1,\ldots,a_n]$,
$n\geq0$, and let the binary words $X_n$, $n\geq0$, be defined as above.

According to Lemma \ref{l1}, the binary word $X_n$ (which has length $q_n$
by a trivial induction using $q_n = a_nq_{n-1} + q_{n-2}$) is identical
with the binary word $f_\alpha(1)f_\alpha(2)\cdots f_\alpha(q_n)$. If
we let $x_n$ denote the integer whose base $b$ representation is $X_n$,
i.e., $x_n = f_\alpha(1)b^{q_n-1} + f_\alpha(2)b^{q_n-2} + \cdots + f_\alpha(q_n)b^0$,
then we can write
\[ x_n = b^{q_n}\cdot\sum_{k=1}^{q_n}\frac{f_\alpha(k)}{b^k}. \]

Now we come to the crucial step.

\begin{lmma}\label{l2} For $n\geq0$, let $t_{n+1} = \frac{b^{q_{n+1}} - b^{q_{n-1}}}{b^n-1}$.
Then for $n\geq1$,
\[ x_{n+1} = t_{n+1}x_n + x_{n-1}. \]
\end{lmma}
\begin{proof} Using the facts that $X_n$ has length $q_n$, $X_{n-1}$ has
length $q_{n-1}$, $x_{n+1}$ is the integer whose base $b$ representation
is $X_{n+1}$, and $X_{n+1} = X_n^{a_{n+1}}X_{n-1}$, it follows that
\begin{align*}
x_{n+1}
&= b^{q_{n-1}}(1 + b^{q_n} + b^{2q_n} + \cdots + b^{(a_{n+1} - 1)q_n})x_n + x_{n-1} \\
&= \frac{b^{q_{n-1}}(b^{a_{n+1}q_n}-1)}{(b^{q_n}-1)}x_n + x_{n-1} = t_{n+1}x_n + x_{n-1}
\end{align*}\end{proof}

\begin{lmma}\label{l3} For $n\geq1$,
\[ [0, t_1,\ldots, t_n] = \frac{b-1}{b^{q_n}-1}\cdot x_n. \]
\end{lmma}\begin{proof} Let $y_n = \frac{b^{q_n}-1}{b-1}$, $n\geq0$. We show
by induction on $n$ that $[0,t_1,\ldots,t_n] = \frac{x_n}{y_n}$. We start
the induction at $n = 0$ by setting $t_0 = 0$. Note that $x_0 = 0$, $x_1=1$,
$y_0=1$, $y_1 = \frac{b^{q_1}-1}{b-1} = t_1$. For the induction step, we
simply note that $x_{n+1} = t_{n+1}x_n + x_{n-1}$ and $y_{n+1} = t_{n+1}y_n
+ y_{n-1}$.\end{proof}

\begin{thrm}[A]\namedthmlabel{tA} Let $b>1$ be an integer, and let $0<\alpha<1$
be irrational, with $f_\alpha(n) = \floor{(n+1)\alpha} - \floor{n\alpha}$, $n\geq1$.
Let $\alpha = [0,a_1,a_2,\ldots]$, let $\frac{p_n}{q_n} = [0,a_1,\ldots,a_n]$,
$n\geq0$ (where $p_n,q_n$ are relatively prime non-negative integers), and
let $t_n = \frac{b^{q_n} - b^{q_n-2}}{b^{q_n-1}-1}$, $n\geq1$. Then
\[ (b-1)\sum_{k=1}^\infty\frac{f_\alpha(k)}{b^k} = [0,t_1,t_2,\ldots]. \]
\end{thrm}\begin{proof} We have seen that $x_n = b^{q_n}\sum_{k=1}^{q_n}
\frac{f_\alpha(k)}{b^k}$. Hence by Lemma \ref{l3},
\[ (b-1)\left(\frac{b^{q_n}}{b^{q_n}-1}\right)\sum_{k=1}^{q_n}\frac{f_\alpha(k)}{b^k} = [0,t_1,\ldots,t_n], \]
and we can take the limit as $n\to\infty$.\end{proof}

\begin{thrm}[B]\namedthmlabel{tB} With the same hypotheses as in Theorem
\ref{tA}, we have
\[ (b-1)\sum_{n=1}^\infty \frac1{b^{\floor{n/\alpha}}} = [0,t_1,t_2,\ldots]. \]
\end{thrm}\begin{proof}This is a restatement of Theorem \ref{tA}, using
the easily verified fact (when $0<\alpha<1$) that $f_\alpha(k) = 1$ if and
only if $k = \floor{n/\alpha}$ for some $n$.\end{proof}

\begin{thrm}[C]\namedthmlabel{tC} With the same hypotheses as in Theorem
\ref{tA}, we have
\[ (b-1)^2\sum_{k=1}^\infty \frac{\floor{k\alpha}}{b^k} = [0,t_1,t_2,\ldots]. \]
\end{thrm}\begin{proof} Using $f_\alpha(k) = \floor{(k+1)\alpha} - \floor{k\alpha}$
and $\floor{\alpha} = 0$, the series in Theorem \ref{tC} is obtained from the
series in Theorem \ref{tA} by a slight rearrangement.\end{proof}

\begin{thrm}[D]\namedthmlabel{tD} With the same hypotheses as in Theorem
\ref{tA}, we have
\[ \sum_{k=1}^\infty\frac{f_\alpha(k)}{b^k} = (b-1)\sum_{k=1}^\infty \frac{(-1)^{k-1}}{(b^{q_k} - 1)(b^{q_{k-1}} - 1)}. \]
\end{thrm}\begin{proof} We say in the proof of Lemma \ref{l3} that $[0,t_1,\ldots,t_n]
= \frac{x_n}{y_n}$, $n\geq1$, where $y_n = \frac{b^{q_n}-1}{b-1}$, $n\geq0$.
By a well-known theorem (J. B. Roberts \cite[pp. 101]{roberts1977}),
$\frac{x_n}{y_n} = \sum_{k=1}^n \frac{(-1)^{k-1}}{y_ky_{k-1}}$, $n\geq1$,
and Theorem \ref{tD} now follows from Theorem \ref{tA}.\end{proof}


\paragraph{Removing the restriction $\alpha < 1$.} Now let $\alpha' = a_0+\alpha$,
where $a_0\geq0$ is an integer, $\alpha$ is irrational, and $0<\alpha<1$.

By Theorem \ref{tA} we get
\begin{align*}
(b-1)\sum_{k=1}^\infty \frac{f_{\alpha'}(k)}{b^k}
&= (b-1)\sum_{k=1}^\infty\frac{a_0+f_\alpha(k)}{b^k} \\
&= (b-1)a_0\sum_{k=1}^\infty\frac1{b^k} + (b-1)\sum_{k=1}^\infty\frac{f_\alpha(k)}{b^k} \\
&= a_0 + [0, t_1,t_2,\ldots] \\
&= [a_0,t_1,t_2,\ldots].
\end{align*}

To handle Theorem \ref{tB} we need to use the fact, whose simple proof
we omit, that if $\alpha' = a_0 + \alpha$, where $0<\alpha<1$, then for
each $k=0,1,2,\ldots$, the value $k$ is assumed by the expression
$\floor{n/\alpha'}$ exactly $a_0+1$ times if $\floor{n/\alpha} = k$
for some $n\geq1$, and exactly $a_0$ times if $\floor{n/\alpha}$
never equals $k$. It then follows from Theorem \ref{tB} that $(b-1)
\sum_{n=1}^\infty\frac1{b^{\floor{n/\alpha'}}} = [a_0b,t_1,t_2,\ldots]$.

By Theorem \ref{tC} and some careful rearrangement we get $(b-1)^2
\sum_{k=1}^\infty\frac{\floor{k\alpha'}}{b^k} = [a_0b,t_1,t_2,\ldots]$.

Finally, the modified Theorem \ref{tD} (using the modified Theorem \ref{tA})
is
\[ (b-1)\sum_{k=1}^\infty \frac{f_{\alpha'}(k)}{b^k} = a_0 + \sum_{k=1}^\infty \frac{(-1)^{k-1}(b-1)^2}{(b^{q_k}-1)(b^{q_{k-1}}-1)}. \]

\begin{rmrk} This paper grew out of the first author's consideration
of the number $\sum_{k=1}^\infty \frac{f_\alpha(k)}{2^k}$, where
$\alpha = \frac{1+\sqrt5}2$, as the fixed point of the sequence $\{g_n(0)\}$,
$n\geq1$, where $g_1(x) = x/2$, $g_2(x) = (x+1)/2$, $g_n(x) = g_{n-1}(g_{n-2}(x))$,
$n\geq3$. This quickly leads (upon setting $g_n(x) = (x + a_n)/b_n$ and
solving for $a_n$ and $b_n$) to
\[ \sum_{k=1}^\infty \frac{f_\alpha(k)}{2^k} = [2,2^0,2^1,2^1,2^2,2^3,2^5,\ldots]. \]
\end{rmrk}

\begin{ackn} The authors are grateful to the referee for references
\cite{bohmer1926} and \cite{danilov1972} and for several helpful remarks.
\end{ackn}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}

