%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-32/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{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{fact}{Fact}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{remark}{Remarks}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}

\title{Some Sequences Associated with the Golden Ratio}
\author{Tom C. Brown and Allen R. Freedman}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown and A.R. Freedman, \emph{Some sequences associated with the golden ratio}, Fib. Quart.
  \textbf{29} (1991), 157--159.}\bigskip\end{center}

A number of people have considered the arithmetical, combinatorial, geometrical, and other properties of sequences of the form $([n\alpha]: n \geq 1)$, where $\alpha$ is a positive irrational number and $[]$ denotes the greatest integer function. (See, e.g.,~\cite{bang1957,connell1959-1,connell1959-2,connell1960,coxeter1953,fraenkel1969,fraenkel+levitt+shimshoni1972,fraenkel+mushkin+tassa1978,graham1973,knuth1973,markoff1882,mendelsohn1974,niven1963,rosenblatt1978,skolem1957,stolarsky1976} and the references contained in those papers, especially~\cite{fraenkel+mushkin+tassa1978} and~\cite{stolarsky1976}.)

There are several other sequences which may be naturally associated with the sequence $([n\alpha]: n \geq 1)$. They are the \emph{difference sequence}
\[ f_\alpha(n) = [(n + 1)\alpha] - [n\alpha] - [\alpha] \]
(the difference sequence is ``normalized" by subtracting $[\alpha]$ so that its values are $0$ and $1$), the \emph{characteristic function}
\[ g_\alpha(n) \quad (g_\alpha(n) = 1 \textup{ if $n = [k\alpha]$ for some $k$, and $g_\alpha(n) = 0$ otherwise}), \]
and the \emph{hit sequence}
\[ h_\alpha(n), \]
where $h_\alpha(n)$ is the number of different values of $k$ such that $[k \alpha] = n$.

We use the notation
\[ f_\alpha = (f_\alpha(n): n \geq 1), \quad g_\alpha = (g_\alpha(n): n \geq 1), \quad h_\alpha = (h_\alpha(n): n \geq 1). \]
Note that $f_\alpha = f_{\alpha + k}$ for any integer $k \geq 1$. In particular, $f_\alpha = f_{\alpha - 1}$ if $\alpha > 1$.

Special properties of these sequences in the case where $\alpha$ equals $\tau$, the golden mean, $\tau = (1 + \sqrt{5})/2$, are considered in~\cite{coxeter1953,mendelsohn1974,rosenblatt1978,stolarsky1976}. For example, the following is observed in~\cite{mendelsohn1974}. Let $u_n = [n\tau], n \geq 1$, and let $F_k$ denote the $k$th Fibonacci number. Given $k$, let $r = F_{2k}, s = F_{2k + 1}, t = F_{2k + 2}$. Then 
\[ u_r = s, \quad u_{2r} = 2s, \quad u_{3r} = 3s, \dots,u_{t-2}r = (t - 2)s; \]
thus, the sequence $([n\tau])$ contains the $(t - 2)$-term arithmetic progression $(s,2s,3s,\dots,(t - 2)s)$.

It was shown in~\cite{stolarsky1976}, using a theorem of A. A. Markov~\cite{markoff1882} (which describes the sequence $f_\alpha$ (for any $\alpha$) explicitly in terms of the simple continued fraction expansion of $\alpha$), that the difference sequence $f_\tau$ has a certain ``substitution property." We give a simple proof of this below (Theorem~\ref{thm: 2}) without using Markov's theorem. We also make several observations concerning the three sequences $f_\tau,g_\tau$, and $h_\tau$.

\begin{thm} \label{thm: 1} 
The golden mean $\tau$ is the smallest positive irrational real number $\alpha$ such that $f_\alpha = g_\alpha = h_\alpha$. In fact, $f_\alpha = g_\alpha = h_\alpha$ exactly when $\alpha^2 = k\alpha + 1$, where $k = [\alpha] \geq 1$.
\end{thm}

\begin{proof} It follows directly from the definitions (we omit the details) that if $\alpha$ is irrational and $\alpha > 1$, then $h_\alpha = g_\alpha = f_{1/\alpha}$. (The fact that $g_\alpha = f_{1/\alpha}$ is mentioned in~\cite{fraenkel+mushkin+tassa1978}. It is straightforward to show that 
\[ g_\alpha(n) = 1 \Rightarrow f_{1/\alpha}(n) = 1 \quad \textup{and} \quad g_\alpha(n) = 0 \Rightarrow f_{1/\alpha}(n) = 0.) \]
Also, if $\alpha$ is irrational and $\alpha > 0$, then 
\[ h_\alpha(n) = f_{1/\alpha}(n) + [1/\alpha] \quad \textup{for all $n \geq 1$}. \]
Thus, if $\alpha$ is irrational and $f_\alpha = g_\alpha = f_\alpha$, then $\alpha > 1$ (otherwise, $g_\alpha$ is identically equal to $1$, and $f_\alpha$ is not) and 
\[ f_{\alpha - [\alpha]}(n) = f_\alpha(n) = g_\alpha(n) = f_{1/\alpha}(n) \quad \textup{for all $n \geq 1$}. \]
Since the sequence $f_\beta$ determines $\beta$ if $\beta < 1$, this gives $\alpha - [\alpha] = 1/\alpha$, and the result follows.
\end{proof}

\begin{defn} For any finite or infinite sequence $w$ consisting of 0's and 1's, let $\bar{w}$ be the sequence obtained from $w$ by replacing each 0 in $w$ by 1, and each 1 in $w$ by 10. For example, $\overline{10110} = 10110101$. (Compare ``Fibonacci strings"~\cite[p.\ 85]{knuth1973}.)
\end{defn}

Note that $\overline{uv} = \bar{u} \cdot \bar{v}$, and that $\bar{u} = \bar{v} \Rightarrow u = v$ by induction on the length of $v$.

\begin{thm} \label{thm: 2} 
The sequences $f_\tau$ and $\overline{f_\tau}$ are identical.
\end{thm}

\begin{proof} First, we show that if $0 < \alpha < 1$, then $\overline{f_\alpha} = g_{1 + \alpha}$. Let $L(w)$ denote the \emph{length} of the finite sequence $w$, so that if $w = f_\alpha(1)f_\alpha(2) \cdots f_\alpha(k)$, then 
\[ L(\bar{w}) = k + f_\alpha(1) + \cdots + f_\alpha(k) = k + [(k + 1)\alpha]. \]
Thus,
\begin{align*} 
[\overline{f_\alpha}(n) = 1] &\Leftrightarrow [ n = L(\bar{w}) + 1 \textup{ for some initial segment $w$ of $f_\alpha$}] \\
&\Leftrightarrow [n = [(k + 1)(1 + \alpha)] \textup{ for some $k \geq 0$}] \Leftrightarrow [g_{1 + \alpha}(n) = 1].
\end{align*}

Therefore, $\overline{f_\tau} = \overline{f_{\tau - 1}} = g_\tau = f_{1/\tau} = f_{\tau - 1} = f_\tau$.
\end{proof}

\begin{cor} \label{cor: 1}
The sequence $f_\tau$ can be generated by starting with $w = 1$ and repeatedly replacing $w$ by $\bar{w}$.
\end{cor}

\begin{proof} If we define $E_1= 1$ and $E_{k + 1} = \overline{E_k}$, then, since $\bar{1} = 10$ begins with a 1, it follows that, for each $k$, $E_k$ is an initial segment of $E_{k + 1}$. By Theorem~\ref{thm: 2} and induction, each $E_k$ is an initial segment of $f_\tau$. Thus,
\begin{align*} 
&E_1 = 1, \quad E_2 = \overline{E_1} = 10, \quad E_3 = \overline{E_2} =101, \quad E_4 = \overline{E_3} = 10110, \\
&E_5 = \overline{E_4} = 10110101, \quad \textup{etc.}, 
\end{align*}
are all initial segments of $f_\tau$. (These blocks naturally have lengths $1,2,3,5,8,\dots$.)
\end{proof}

\begin{cor} \label{cor: 2}
For each $i \geq 1$, let $x_i$ denote the number of 1's in the sequence $f_\tau$ which lie between the $i$th and $(i + 1)$st 0's. Thus,
\begin{align*} f_\tau &= 101101011011010110101101101011011\cdots, \\
(x_n) &= \: \:\: \: \;\; 2 \: \; 1 \: \: \: \; 2 \: \: \; \; 2 \: \;1\: \: \: \;2 \; \; 1 \: \: \: \;2\: \: \: \; 2 \; \; 1 \: \: \: \;2 \: \: \: \; 2 \cdots . \end{align*}
Then the sequences $(x_n - 1)$ and $f_\tau$ are identical.
\end{cor}

\begin{proof} If we start with the sequence $(x_n)$ and replace each 1 by 10 and each 2 by 101, we obtain the sequence $f_\tau$. Since $\bar{\bar{0}} = 10$ and $\bar{\bar{1}} = 101$, this shows that $(\overline{\overline{x_n - 1}}) = f_\tau = \overline{\overline{f_\tau}}$. Therefore, $(\overline{x_n - 1}) = \overline{f_\tau}$, and, finally, $(x_n - 1) = f_\tau$.
\end{proof} 


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