%%%% 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, ¶¡ÏãÔ°AV, 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}