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