\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} %\usepackage{url,amsbsy,amsopn,amstext,amsxtra,euscript,amscd} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{cor}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{problem}[theorem]{Problem} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf On Functions Expressible as Words \\ \vskip .1in on a Pair of Beatty Sequences } \vskip 1cm \large Christian Ballot \\ D\'epartement de Math\'ematiques et Informatique\\ Universit\'e de Caen-Normandie \\ France \\ \href{mailto:christian.ballot@unicaen.fr}{\tt christian.ballot@unicaen.fr} \\ \end{center} \vskip .2 in \def\cI{{\mathcal I}} \def\cR{{\mathcal R}} \def\a{{\alpha}} \def\b{{\beta}} \def\g{{\gamma}} \def\d{{\delta}} \def\l{{\lambda}} \def\o{{\omega}} \def\e{{\epsilon}} \def\ep{{\varepsilon}} \def\s{{\sigma}} \def\t{{\tau}} \def\v{{\nu}} \def\th{{\theta}} \def \K{{\bbbk}} \def\E{{\mathbf E}} \def\G{{\mathcal G}} \def\O{{\mathcal O}} \def \R{{\bbbr}} \def\({\left(} \def\){\right)} \def\lf{\lfloor} \def\rf{\rfloor} \def\lc{\lceil} \def\rc{\rceil} \begin{abstract} Let $a(n)=\lfloor n\a\rfloor$ and $b(n)=\lfloor n\a^2\rfloor$, where $\a=\frac{1+\sqrt{5}}2$. Then a theorem of Kimberling states that each function $f$, composed of several $a$'s and $b$'s, can be expressed in the form $c_1a+c_2b-c_3,$ where $c_1$ and $c_2$ are consecutive Fibonacci numbers determined by the numbers of $a$'s and of $b$'s composing $f$ and $c_3$ is a nonnegative constant. We provide generalizations of this theorem to two infinite families of complementary pairs of Beatty sequences. The particular case involving `Narayana' numbers is examined in depth. The details reveal that $x_n= \lf\a^3\lf\a^3\lf\cdots\lf\a^3\rf\cdots\rf\rf\rf$, with $n$ nested pairs of $\lf\;\rf$, is a 7th-order linear recurrence, where $\a$ is the dominant zero of $x^3-x^2-1$. \end{abstract} \section{Introduction} \label{sec1} If $\a$ is a positive irrational number, then $a(n)=\lfloor n\a\rfloor$ is said to be a {\it Beatty sequence}. A pair of Beatty sequences $a(n)=\lfloor n\a\rfloor$ and $b(n)=\lfloor n\b\rfloor$ is said to be {\it complementary} whenever their ranges form a partition of the positive integers. A famous theorem states that complementarity occurs if and only if $1/\a+1/\b=1$. According to Kimberling \cite{Ki2}, though this theorem was stated as a problem \cite{Bea}, it had appeared even earlier in the book \cite[p.~123]{Ray}. The lower and upper Wythoff sequences, i.e., the sequences $a(n)=\lfloor n\a\rfloor$ and $b(n)=\lfloor n\a^2\rfloor$, where $\a=\frac{1+\sqrt{5}}2$, are a pair of complementary Beatty sequences. This pair has often been considered, in part because the positions $(a(n), b(n))$ are winning positions in a variant of the game of Nim \cite{Wyt}. Kimberling \cite{Ki} studied the functions $(w(n))_{n\ge1}$, where $w=\ell_1\circ\ell_2\circ\cdots\circ\ell_s$ and each $\ell_i$ is either the $a$ or the $b$ sequence. The following lemma was proved \begin{lemma}\label{lem:Kim} Let $a(n)=\lf n\a\rf$ and $b(n)=\lf n\a^2\rf$, where $\a=(1+\sqrt{5})/2$. Then \begin{align*} a^2&=b-1,\\ ba&=a+b-1,\\ ab&=a+b,\\ b^2&=a+2b, \end{align*} where $\ell_1\ell_2$ stands for $\ell_1\circ\ell_2$ and $\ell^2$ for $\ell\ell$. \end{lemma} One of the key facts is that, as $\a^2=\a+1$, we have $b(n)=a(n)+n$, for all integers $n$. Here is the principal theorem of Kimberling \cite{Ki}, proved by induction on $s$ using Lemma \ref{lem:Kim}. \begin{theorem}\label{thm:Kim} Let $w=\ell_1\circ\ell_2\circ\cdots\circ\ell_s$, $(s\ge1)$, where each $\ell_i$ is either $a$ or $b$. Assume $x$ and $y$ are, respectively, the number of $a$'s and the number of $b$'s in $w$. Then, $$ w(n)=F_{x+2y-2}\,a(n)+F_{x+2y-1}\,b(n)-e_w, $$ where $e_w=F_{x+2y+1}-w(1)\ge0$ and $F_k$ denotes the $k$th Fibonacci number. \end{theorem} As usual, the Fibonacci sequence $(F_k)$ is defined by $F_0=0$, $F_1=1$ and $F_{k+2}=F_{k+1}+F_k$ for all integers $k$. With $f^x$ denoting the $x$-fold composite function $f\circ f\circ\cdots\circ f$, we state a corollary from material observed by Kimberling \cite{Ki}. \begin{cor}\label{cor:Kim} We have $a^x=F_{x-2}a+F_{x-1}b-F_{x+1}+1$ and $b^y=F_{2y-2}a+F_{2y-1}b$. In particular, $b^y(1)=F_{2y+1}$. \end{cor} For each pair $a(n)=\lf n\a\rf$ and $b(n)=\lf n\b\rf$ of complementary Beatty sequences, we will always take $\a$ to be less than $\b$. Then we necessarily have $1<\a<2<\b=\a/(\a-1)$. This paper studies two infinite families of pairs of complementary Beatty sequences. Each of the two families contains the Wythoff pair as its simplest case. For each family, our main goal is to find a sensible generalization of Theorem \ref{thm:Kim}. Our investigation begins in Section~\ref{sec2} by looking at the pair of complementary Beatty sequences $(\a,\b)= (\sqrt{2},2+\sqrt{2})$. That is, $a(n)=\lfloor n\sqrt{2}\rfloor$ and $b(n)=\lfloor n(2+\sqrt{2})\rfloor$. This pair satisfies the obvious property $b(n)=a(n)+2n$ instead of $b(n)=a(n)+n$ for the Wythoff pair. In Section~\ref{sec3}, we study the general pair of complementary Beatty sequences where $b(n)=a(n)+rn$, $r\ge1$ any integer. We obtain Theorem \ref{thm:R}, a most general theorem. \medskip The second infinite family we study stems from the observation \cite{Ba} that for all integers $q\ge2$, the complex polynomial $x^q-x^{q-1}-1$ has a simple dominant real zero $\a$, $1<\a<2$, and the pair $(\a,\b)$, where $\b=\a^q$, generates a complementary pair of Beatty sequences $(a(n),b(n))$. Section~\ref{sec4} studies in detail the case $q=3$. Then, of course, $\b$ is the cube rather than the square of $\a$, as was the case for the Wythoff pair. Section~\ref{sec5} is a brief section on the case $q=4$. A sixth section deals with the general case $q\ge2$, where we reach our most general result, Theorem \ref{thm:G}. We believe beginning with particular cases makes the transition to the general case both more readable and more enjoyable. However, readers can skip Sections~\ref{sec2} and \ref{sec5}, if they wish. Yet in Sections \ref{sec2}, \ref{sec4}, and \ref{sec5}, we investigate the functions $e_w$ in more detail than in the general cases. For instance, the functions $e_w$ studied in Sections \ref{sec2} and \ref{sec4} are nonnegative, in contrast to their general counterparts in Theorems \ref{thm:R} and \ref{thm:G}. \smallskip A subsidiary investigation of the paper is the study of the sequences $(b^y(n))_y$. This function turns out to be a second-order linear recurrence whose characteristic polynomial is the minimal polynomial of $\b$ not just in the Wythoff case, but in all $(a(n),a(n)+rn)$ cases for $r\ge1$, as shown in the later part of Section~\ref{sec3}. Also, Section~\ref{sec4}, where $a(n)=\lf\a n\rf$ and $b(n)=\lf\a^3 n\rf$, $\a^3=\a^2+1$, $\a>1$, is divided into two subsections, the second of which studies the behavior of $b^y(1)=\lf\a^3\lf\a^3\lf\cdots\lf\a^3\rf\cdots\rf\rf\rf$, with $y$ nested pairs $\lf\;\rf$. This sequence $(b^y(1))_y$ turns out to be a seventh-order linear recurrence. We find several explicit formulas for it. Note that the corresponding sequence $(a^x(1))_x$ is the constant sequence equal to $1$ as $\lf\a\rf=1$ for all complementary Beatty pairs. \medskip We now relate our paper to general questions and other work. We begin with the mention that Stolarsky \cite{Sto0} compiled an extended bibliography of work linked to Beatty sequences done before 1973. A quite general question is `what sort of behavior and structures emerge from all possible compositions of a given set of functions?' For a single function this is the problem of analyzing iteration (e.g., see the comments on $b^y (n)$ above). Here we examine functions of the form $$ g(n) = \lf n\a_i\rf $$ (i.e., Beatty sequences), where the $\a_i$ are algebraic irrationalities. In various cases of interest we determine the nature of `homogeneous' compositions $$ g_1 (g_2 (\cdots(g_k (n))\cdots). $$ There has also been some study of `inhomogeneous' compositions such as $$ g_1 (g_2 (n) + c_1 n + c_2 ) $$ in the Beatty context. See \cite{Por}, especially formula (1.1.4), and \cite{Fra}, in particular Theorem 1 of \S2. Boshernitzan and Fraenkel \cite{Bos} discussed characteristic properties of functions of the form $$ g(n) = \lf n\a_i + \b_i\rf, $$ but perhaps the study of arbitrarily long compositions of such functions has not been done in any detail. Fraenkel et al. \cite{Fra2} studied more general combinations of such functions. Cases in which the most interesting results are found frequently involve numbers $\a$  that are real algebraic integers larger than their conjugates. Even more special are cases in which $\a$ is a Pisot number. For example, the dominant real zero of $x^q-x^{q-1}-1$ is a Pisot number for $q=2$, $3$, and $4$. In \S4, i.e., in Section~\ref{sec4}, we examine in special detail the `Narayana case' $q=3$. Bertin et al. \cite{Ber} published a general reference book on Pisot numbers and their relatives. In fact, the Fibonacci ($q=2$) and Narayana cases involve a dominant zero that comes from the finite set of `special Pisot numbers'. The significance of these numbers appears in various papers \cite{Lag, Lag2, Sch}. Smyth \cite{Smy} provided a definitive complete determination of them. The $\a$ of \S5 is also a special Pisot number. In connection with \S6 we note that the dominant zero of $P(q,x)=x^q-x^{q-1}-1$ is not Pisot for $q\ge6$, and that $P(5, x) = (x^3-x-1)(x^2-x+1)$. It has been noted that a full understanding of the Beatty sequences and Wythoff pairs related to $\sqrt{5}$ involves recurrences of degree 4. This is the basic theme of two papers \cite{Sto, Rid}. Here in \S4 we find that the study of Beatty sequences corresponding to the `Narayana' cubic irrationality (one of the special Pisot numbers) inevitably involves recurrences of degree 7. See Problems \ref{problem:3} and \ref{problem:4} of Section~\ref{sec7} for precise questions. \medskip Indeed, Section~\ref{sec7}, our final section, proposes five problems for further consideration. \medskip By convention, throughout the paper, the sums $\sum_{i\le j\le k}a_j$ or $\sum_{j=i}^ka_j$ are zero whenever $k2>\a$. Therefore, using the triangle inequality, we find that $|w(n)-w_0(n)|\le2\b^{x+y}$ for all $w$ satisfying the hypotheses of the theorem and all $n\ge1$, where $w_0=a^xb^y$. Thus, it suffices to prove the theorem for the function $w=w_0$. Since $b=0\cdot a+1\cdot b$, we can find the vector $\left(\begin{matrix}s_w\\t_w\end{matrix}\right)$ by computing the matrix product $E_a^xE_b^{y-1}\left(\begin{matrix}0\\1\end{matrix}\right)$. By Lemma \ref{lem:Mat}, \begin{align*} E_a^xE_b^{y-1}\left(\begin{matrix}0\\1\end{matrix}\right) &=\left(\begin{matrix}U_{x+1}^\a-U_x^\a & U_x^\a \\U_x^\a & U_x^\a+rU_{x-1}^\a \end{matrix}\right)\left(\begin{matrix}U_{y-1}^\b\\U_y^\b-U_{y-1}^\b\end{matrix}\right)\\ &=\left(\begin{matrix}U_x^\a U_y^\b+U_{y-1}^\b(U_{x+1}^\a-2U_x^\a)\\ U_x^\a U_y^\b+rU_{x-1}^\a(U_y^\b-U_{y-1}^\b)\end{matrix}\right). \end{align*} The other expressions for $s_{x,y}$ and $t_{x,y}$ in (\ref{eq:Rcoef}) are obtained using the relations $U_{x+1}^\a=(2-r)U_x^\a+rU_{x-1}^\a$ and $(2+r)U_y^\b-rU_{y-1}^\b=U_{y+1}^\b$, respectively. Our derivation assumed $y\ge1$. However, it is easy to check that putting $y=0$ in (\ref{eq:Rcoef}) yields $\left(\begin{matrix}s_{x,0}\\t_{x,0}\end{matrix}\right)= \left(\begin{matrix}U_x^\a-U_{x-1}^\a\\U_{x-1}^\a\end{matrix}\right)$, which equals $E_a^{x-1}\left(\begin{matrix}1\\0\end{matrix}\right) =\left(\begin{matrix}s_{a^x}\\t_{a^x}\end{matrix}\right)$, by Lemma \ref{lem:Mat}. \end{proof} \begin{remark} The functions $s_{x,y}$ and $t_{x,y}$ are integral linear recurrences in $x$ with characteristic polynomial the minimal polynomial of $\a$ when $y$ is fixed, and linear recurrences in $y$ with characteristic polynomial the minimal polynomial of $\b$ when $x$ is fixed. \end{remark} \begin{remark} One can easily recover $s_{x,y}$ and $t_{x,y}$ when $r=1$ or $r=2$ obtained in Theorems \ref{thm:Kim} and \ref{thm:root2}. For instance, if $r=1$, then $U_x^\a=F_x$ and $U_y^\b=F_{2y}$ so $s_{x,y}=F_xF_{2y}+F_{2y-2}(F_{x+1}-2F_x)=F_xF_{2y}-F_{x-2}F_{2y-2}$. To see that $F_xF_{2y}-F_{x-2}F_{2y-2}=F_{x+2y-2}$, it is enough to observe that both sides of the equation are linear recurrences satisfying the Fibonacci recursion once $y$ is fixed. Thus, we are left with verifying equality, say, at $x=0$ and $x=1$. \end{remark} \begin{remark} In contrast with to the cases $r=1$ or $r=2$, the functions $d_w(n)$ in (\ref{eq:R}) are not necessarily always nonnegative when $r\ge3$. For instance, for $r=3$, $$ d_{a^3}(n)=\lc(\a+1)\{\a a(n)\}\rc-\lc(\a+1)\{n\a\}\rc, $$ which is $-1$ for $n=6$. \end{remark} In the Wythoff case, as we can see from Corollary \ref{cor:Kim}, the sequences $(b^y(n))_y$ for a fixed integer $n\ge1$ are all second-order recurrences with characteristic polynomial the minimal polynomial of $\b=\a+1$. The next two corollaries show this phenomenon holds for all pairs of Beatty sequences stemming from a pair $(\a,\a+r)$, ($r\ge1$). \begin{cor}\label{cor:byofn} For all $y\ge0$ and all $n\ge1$, we find that $$ b^y(n)=u_ya(n)+v_yb(n), $$ where $(u_y)$ and $(v_y)$ are both second-order linear recurrences with characteristic polynomial $x^2-(r+2)x+r$ and initial values $u_1=0$, $u_2=1$ and $v_1=1$, $v_2=r+1$. \end{cor} \begin{proof} We saw in (\ref{eq:ab}) that $d_{wb}(n)=d_w(b(n))$. But for $w=b$, $d_w=0$. Hence, we see inductively that $d_{b^y}=0$, for all $y\ge1$. Therefore, by Theorem \ref{thm:R}, we get $$b^y(n)=U_{y-1}^\b a(n)+(U_y^\b-U_{y-1}^\b)b(n).$$ Both $U_{y-1}^\b$ and $U_y^\b-U_{y-1}^\b$ are linear recurrences with characteristic polynomial $x^2-(r+2)x+r$, the minimal polynomial of $\b$, and their initial conditions are those indicated. For $y=0$, $b^y(n)=n$ and $$U_{y-1}^\b a(n)+(U_y^\b-U_{y-1}^\b)b(n)= U_{-1}^\b\big(a(n)-b(n)\big)=-r^{-1}(-rn)=n.$$ \end{proof} \begin{cor}\label{cor:byof1} Given $n\ge1$, the sequence $(b^y(n))_y$ is linear recurrent with characteristic polynomial the minimal polynomial of $\b$, namely $x^2-(r+2)x+r$. In particular, $(b^y(1))_y=v_{y+1}$, where the sequence $(v_y)$ was defined in the statement of Corollary \ref{cor:byofn}. \end{cor} \begin{proof} By Corollary \ref{cor:byofn}, once $n$ is fixed, $b^y(n)$ is a linear combination of $u_y$ and $v_y$. Moreover, $b^y(1)=a(1)u_y+b(1)v_y=\lf\a\rf u_y+\lf\b\rf v_y= u_y+(r+1)v_y=v_{y+1}$, since $\a\in(1,2)$ implies $\b\in(r+1,r+2)$. \end{proof} For future reference, we give a direct proof of Corollary \ref{cor:byof1}. \begin{proof} Put $\nu_y=b^y(n)$. Then \begin{align*} \nu_{y+2}&=\lf\b^2\nu_y-\b\{\b\nu_y\}\rf= \lf(r+2)\b\nu_y-r\nu_y-\b\{\b\nu_y\}\rf \\ &= (r+2)\nu_{y+1}-r\nu_y+\lf(r+2-\b)\{\b\nu_y\}\rf =(r+2)\nu_{y+1}-r\nu_y, \end{align*} since, as $\b\in(r+1,r+2)$, it follows that $r+2-\b$ is in $(0,1)$. \end{proof} \section{The Narayana case} \label{sec4} Here we consider $a(n):=\lfloor \a n\rfloor$ and $b(n):=\lfloor \a^3n\rfloor$, where $\a\doteq 1.46557$ is the dominant zero of $x^3-x^2-1$. Note that we do have $1/\a+1/\a^3=1$. \smallskip The Narayana sequence $(N_k)_{k\ge0}$ is the fundamental recurrence with characteristic polynomial $x^3-x^2-1$, i.e., with initial values $0,0,1$. This sequence was used in the 14th century to model the population growth of a herd of cows \cite{AJ}. Its OEIS number \cite{Slo} is \seqnum{A078012}. \subsection{General results} \begin{lemma}\label{lem:N} For all integers $n\ge1$, we have \begin{align*} a^2(n)&=b(n)-n-e_1(n)\\ ba(n)&=a(n)+b(n)-e_2(n)\\ ab(n)&=a(n)+b(n)-e_3(n)\\ b^2(n)&=a(n)+3b(n)-n-e_4(n), \end{align*} where the ranges of $e_1$ and $e_2$ are, respectively, $\{0,1,2\}$ and $\{0,1,2,3\}$, and the ranges of $e_3$ and $e_4$ are both $\{0,1\}$. \end{lemma} \begin{proof} Since $\a^3=\a^2+1$, we see that \begin{align*} a^2(n) &=\lfloor\a\lfloor\a n\rfloor\rfloor= \lfloor\a^2 n-\a\{\a n\}\rfloor= \lfloor\a^3 n-\a\{\a n\}\rfloor-n \\ & =\lfloor\lfloor\a^3 n\rfloor+\{\a^3 n\}-\a\{\a n\}\rfloor-n= b(n)-n+\lfloor\{\a^2 n\}-\a\{\a n\}\rfloor. \end{align*} Clearly $-2<-\a< -\a\{\a n\}< \{\a^2 n\}-\a\{\a n\}<\{\a^2 n\}<1$, which explains that $e_1(n)$ is either $0$, $1$ or $2$. Similarly, $ba(n)=\lfloor\a^3\lfloor\a n\rfloor\rfloor=\lfloor\a^2\lfloor\a n\rfloor+\lfloor\a n \rfloor\rfloor=a(n)+\lfloor\a^3n-\a^2\{\a n\}\rfloor=a(n)+b(n)+\lfloor\{\a^3n\}-\a^2\{\a n\}\rfloor$. Note that $\a^2>2$, so $e_2(n)$ is potentially equal to $3$. Also, \begin{align*} ab(n)&=\lfloor\a(\a^3n-\{\a^3n\})\rfloor =\lfloor(\a^3+\a)n-\a\{\a^3n\}\rf \\ &= a(n)+b(n)+\lf\{\a^3n\}+\{\a n\}-\a\{\a^3n\}\rf=a(n)+b(n)+\lf\{\a n\}+(1-\a)\{\a^2n\}\rf. \end{align*} Noting that $(1-\a)\{\a^2n\}\in(-1,0)$ explains the range of $e_3$. Finally, as $\a^6=3\a^3+\a-1$, we see that \begin{align*} b^2(n)&=\lf\a^3(\a^3n-\{\a^3n\})\rf=-n+\lf3\a^3n+\a n-\a^3\{\a^3n\}\rf \\ &=a(n)+3b(n)-n+\lf(3-\a^3)\{\a^3n\}+ \{\a n\}\rf. \end{align*} Noting that $(3-\a^3)\{\a^3n\}\in(-1,0)$ explains the range of $e_4$. \end{proof} It might be worth listing the exact expressions of the functions $e_i$ found in the above proof. Namely, \begin{align*} e_1(n)&=\lceil\a\{\a n\}-\{\a^2n\}\rceil \\ e_2(n)&=\lceil\a^2\{\a n\}-\{\a^2n\}\rceil \\ e_3(n)&=\lceil(\a-1)\{\a^2n\}-\{\a n\}\rceil \\ e_4(n)&=\lceil(\a^3-3)\{\a^2n\}-\{\a n\}\rceil. \end{align*} We observe that all values in the various ranges of the $e_i$'s are attained for some $n$. For instance, $e_2(n)$ takes on the value $3$, though only three times in the interval $[1,500]$. \begin{theorem}\label{thm:N} Let $w=\ell_1\circ\ell_2\circ\cdots\circ\ell_s$, $(s\ge1)$, where each $\ell_i$ is either $a$ or $b$. Assume $x$ and $y$ are, respectively, the number of $a$'s and the number of $b$'s in $w$. Then, \begin{equation}\label{eq:N} w(n)=N_{x+3y-2}\,a(n)+N_{x+3y}\,b(n)-N_{x+3y-3}\,n-e_w(n), \end{equation} where $e_w$ is a nonnegative bounded integral function of $n$ that depends on $w$ and satisfies $e_w\le3pN_p$ with $p=x+3y$. \end{theorem} \begin{proof} The proof is by induction on $\ell\ge1$ and analogous to that of Theorem \ref{thm:H}, albeit less demanding, and also subsumed by the proof presented in Theorem \ref{thm:G}. We only outline the bounds on $e_w$ that Theorems \ref{thm:H}, or \ref{thm:G}, do not address. Assume $w(n)$ satisfies (\ref{eq:N}) with $p=x+3y$. Computing $w(a(n))$ with the expressions of $a^2(n)$ and $b(a(n))$ from Lemma \ref{lem:N}, we find $$w(a(n))=N_{(p+1)-2}a(n)+N_{p+1}b(n)-N_{(p+1)-3}n-e_{wa}(n),$$ where $e_{wa}(n)=N_{p-2}e_1(n)+N_pe_2(n)+e_w(a(n))$. Since $0\le e_1\le2$ and $0\le e_2\le3$ according to Lemma \ref{lem:N}, we deduce, with the inductive hypothesis, that $$0\le e_{wa}(n)\le2N_{p-2}+3N_p+3pN_p\le N_p+2N_{p+1}+3pN_p\le3N_{p+1}+3pN_{p+1}=3(p+1)N_{p+1}.$$ Similarly, $e_{wb}(n)=e_4(n)N_{p-2}+e_3(n)N_p+e_w(b(n))$. Clearly $e_{wb}(n)\le N_{p+1}+3pN_p\le3(p+3)N_{p+3}$. Note that $N_{-1}=1$ so $e_{wa}$ and $e_{wb}$ are both nonnegative even when $p=1$. \end{proof} The upper bound on the function $e_w(n)$ can be substantially reduced for some subfamilies of sequences as the corollary below shows. \begin{cor}\label{cor:N} We have $b^y(n)=N_{3y-2}a(n)+N_{3y}b(n) -N_{3y-3}n-e_{(y)}(n)$ where $0\le e_{(y)}(n)\le N_{3y-2}$. \end{cor} \begin{proof} Theorem \ref{thm:N} gives that $b^y(n)=N_{3y-2}a(n)+N_{3y}b(n)-N_{3y-3}n-e_{(y)}(n)$ for some nonnegative bounded function $e_{(y)}$. Thus, $$b^{y+1}(n)=b^y(b(n))=N_{3y-2}a(b(n))+ N_{3y}b^2(n)-N_{3y-3}b(n)-e_{(y)}(b(n)),$$ which, using Lemma \ref{lem:N} and the Narayana recursion $N_n+N_{n-2}=N_{n+1}$, yields $b^{y+1}(n)=N_{3y+1}a(n)+N_{3y+3}b(n)-N_{3y}n-N_{3y}e_4(n)-e_{(y)}(b(n))$. On the other hand, we have $b^{y+1}(n)=N_{3y+1}a(n)+N_{3y+3}b(n)-N_{3y}n-e_{(y+1)}(n)$. Therefore, $e_{(y+1)}(n)=N_{3y}e_4(n)+e_{(y)}(b(n))$. Thus, $e_{(y+1)}(n)-e_{(y)}(b(n))\le N_{3y}$. Hence, $$e_{(y)}(b(n))-e_{(y-1)}(b^2(n))\le N_{3y-3}, \ldots, e_{(2)}(b^{y-1}(n))-e_{(1)}(b^y(n))\le N_3.$$ But $e_{(1)}=0$, so adding those inequalities yields $e_{(y+1)}(n)\le\sum_{t=1}^yN_{3t}$. An easy induction shows $\sum_{t=1}^yN_{3t}=N_{3y+1}$, which terminates our proof. \end{proof} We are curious to know whether the sequences $(b^y(n))_y$, for fixed $n$, are linear recurrences as Corollaries \ref{cor:byofn} and \ref{cor:byof1} showed it is the case when $\b$ is of the form $\b=\a+r$, $r$ an integer. Clearly, this will hold iff the sequences $(e_{(y)}(n))_y$ of Corollary \ref{cor:N} are linear recurrences. The next subsection proves this is true when $n=1$. However, before jumping to this next subsection, we fix an $n\ge1$, set $\t_y:=b^y(n)$ and mimic the second proof of Corollary \ref{cor:byof1} to establish that $(\t_y)$, if not a linear recurrence, is nearly one, and with characteristic polynomial the minimal polynomial $x^3-4x^2+3x-1$ of $A:=\a^3$. (See Lemma \ref{lem:1}.) \begin{lemma}\label{lem:3} The sequence $(\t_y)_{y\ge0}$ satisfies the relation $$ \t_{y+3}-4\t_{y+2}+3\t_{y+1}-\t_y=\xi_y, \text{ where } \xi_y=\lf(4-A)\{A \t_{y+1}\}-A^{-1}\{A \t_y\}\rf, (y\ge0). $$ \end{lemma} \begin{proof} Using $A^3-4A^2+3A-1=0$, we find that \begin{align*} \t_{y+3}&=\lf A\t_{y+2}\rf=\lf4\t_{y+2}+ (A-4)\lf A\t_{y+1}\rf\rf \\ &= 4\t_{y+2}+\lf(A-4)A \t_{y+1}+(4-A)\{A\t_{y+1}\}\rf. \end{align*} But $A^2-4A=-3+A^{-1}$ so $\t_{y+3}=4\t_{y+2}-3\t_{y+1}+\lf A^{-1}(A\t_y-\{A\t_y\})+(4-A)\{A\t_{y+1}\}\rf$, which leads to the relation the lemma claims. \end{proof} We see that $\xi_y$ is either $0$ or $-1$ because $4-A\doteq 0.8521$ and $A^{-1}\doteq 0.3176$, and seems more likely to be $0$ than $-1$. \subsection{The sequence $(b^y(1))_y=\lf\a^3\lf\a^3\lf\cdots\lf\a^3\rf\cdots\rf\rf\rf$} In this subsection, we write $\t_y$ for $b^y(1)$, $A$ for $\a^3$ and we define $\s_y$ as the function \begin{equation}\label{eq:1} \s_y:=N_{3y+3}-\sum_{k=0}^{\lf(3y-14)/12\rf}N_{3y-14-12k}. \end{equation} \smallskip We intend to prove that $\s_y$ is a linear recurrence with characteristic polynomial equal to $x^4-1$ times the minimal polynomial of $A$. This will give us a closed form for $\s_y$ from which we can see that $\s_{y+1}=\lf\a^3\s_y\rf$ for $y\ge20$. Induction will then yield the equality of the sequences $(\s_y)$ and $(\t_y)$. The expression in (\ref{eq:1}) was found experimentally to match the first values of $\t_y$. Using PARI, we then had checked the coincidence of $\t_y$ and $\s_y$ for all $y$, $0\le y\le199$. \begin{lemma}\label{lem:1} For any fixed integer $t$, the sequence $(N_{3y+t})_y$ is a third-order recurrence with characteristic polynomial $x^3-4x^2+3x-1$. \end{lemma} \begin{proof} It suffices to verify that $x^3-4x^2+3x-1=(x-\a^3) (x-\b^3)(x-\g^3)$, where $\b$ and $\g$ are, besides $\a$, the two other zeros of $x^3-x^2-1$. Note that $\a+\b+\g=1$, $\a\b+\a\g+\b\g=0$ and $\a\b\g=1$. Thus, putting $V_n=\a^n+\b^n+\g^n$, we find that $V_0=3$, $V_1=1$, $V_2=V_1^2-2(\a\b+\a\g+\b\g)=1$. Hence, $V_3=V_2+V_0=4$. Now writing $W_n$ for $(\a\b)^n+(\a\g)^n+(\b\g)^n$, we see that $(W_n)$'s characteristic polynomial is $x^3-0x^2+\a\b\g(\a+\b+\g)x-1=x^3+x-1$. Therefore, $W_3=-W_1+W_0=3$ and, consequently, $(x-\a^3)(x-\b^3)(x-\g^3)=x^3-V_3x^2+W_3x-1=x^3-4x^2+3x-1$, as we claimed. \end{proof} \medskip \begin{lemma}\label{lem:2} The sequence $(\s_y)_{y\ge0}$ satisfies the recursion $$ \s_{y+3}-4\s_{y+2}+3\s_{y+1}-\s_y=\ep_y, \text{ where } \ep_y=\begin{cases}0,&\text{ if }y \equiv0,1\text{ or }2\pmod 4;\\ -1,&\text{ if }y\equiv3\pmod 4. \end{cases} $$ In particular, $(\s_y)$ is a seventh-order recurrence with characteristic polynomial $(x^4-1)(x^3-4x^2+3x-1)$. \end{lemma} \begin{proof} Define $V_y$ as $\s_{y+3}-4\s_{y+2}+3\s_{y+1}-\s_y$ for all $y$. By (\ref{eq:1}) and Lemma \ref{lem:1}, we see that \begin{equation} \begin{split} -V_y=&\sum_{k=0}^{\lf(3y-5)/12\rf}N_{3y-5-12k}-4\sum_{k=0}^{\lf(3y-8)/12\rf}N_{3y-8-12k}\\ +&3\sum_{k=0}^{\lf(3y-11)/12\rf}N_{3y-11-12k}-\sum_{k=0}^{\lf(3y-14)/12\rf}N_{3y-14-12k}. \end{split} \label{eq:2} \end{equation} By Lemma \ref{lem:1}, if all four sums in the expression of $-V_y$ above have the same number of terms, then $V_y=0$. If $\cI$ designates the set of all intervals $J$ such that $J\subset[m,m+1)$, for some integer $m$, then those four sums will all have $1+\lf(3y-14)/12\rf$ terms iff the interval $[(3y-14)/12,(3y-5)/12]\in \cI$. Putting $y=4\ell+r$, $0\le r\le3$, we see that $$[(3y-14)/12,(3y-5)/12]\in \cI \text{ iff } [(3r-14)/12,(3r-5)/12]\in \cI,$$ which occurs iff $r=1$. Suppose $y=4\ell$. Then $\lf(3y-5)/12\rf=\lf(3y-8)/12\rf=\lf(3y-11)/12\rf=\ell-1$ and $\lf(3y-14)/12\rf=\ell-2$. Thus, using Lemma \ref{lem:1}, we obtain that $-V_y=N_{3y-5-12(\ell-1)}-4 N_{3y-8-12(\ell-1)}+3N_{3y-11-12(\ell-1)}=N_7-4N_4+3N_1=4-4+0=0$. Thus, $V_{4\ell}=0$ as well. Assume now $y=4\ell+2$. Then the first sum, i.e., $\sum_{k=0}^{\lf(3y-5)/12\rf}N_{3y-5-12k}$ in (\ref{eq:2}), contains one more term than the three others. Hence, as $\lf(3y-5)/12\rf=\ell$, we see that $-V_y=N_{3y-5-12\ell}=N_1=0$. Finally, suppose $y=4\ell+3$. Then $\lf(3y-5)/12\rf=\lf(3y-8)/12\rf=\ell$, while $\lf(3y-11)/12\rf=\lf(3y-14)/12\rf=\ell-1$. Thus, $-V_y=N_{3y-5-12\ell}-4N_{3y-8-12\ell}= N_4-4N_1=1$. Hence, $V_{4\ell+3}=-1$, which ends the proof. \end{proof} Since $(\s_y)$ is a seventh-order recurrence with the zeros of its characteristic polynomial all identified, namely $\a^3$, $\b^3$, $\g^3$ and all complex fourth roots of unity, we solved a $7\times7$ linear system and got a closed-form expression for $\s_y$. We found $\s_y=I_y+r_y$, where \begin{align}\begin{split} I_y&:=\frac{1}{117}\big(2N_{3y}+103N_{3y+1}+100N_{3y+2}\big),\\ r_y&:=\frac14-\frac{(-1)^y}{36}- \frac{3i+2}{52}i^y+\frac{3i-2}{52}(-i)^y, \end{split}\label{eq:3}\end{align} and $i=\sqrt{-1}$. \smallskip We may observe that $\a^3I_y-I_{y+1}$ can be made arbitrarily small, for all large enough $y$'s. Indeed, for $t$ a fixed integer, $N_{3y+t}$ is a linear combination of $\a^{3y}$, $\b^{3y}$ and $\g^{3y}$. But, as the absolute values of $\b$ and $\g$ are smaller than one, $\a^3N_{3y+t}-N_{3y+3+t}$ tends to $0$ as $y$ tends to infinity. The next lemma quantifies this observation. \begin{lemma}\label{lem:E} We have $|E_y|<6\cdot10^{-5}$ for all $y\ge20$, where $E_y:=\a^3I_y-I_{y+1}$. \end{lemma} \begin{proof} For all $n\ge0$, we have the closed-form expression $$ N_n=\frac{\a^n}{f'(\a)}+2\,\cR e\bigg(\frac{\b^n}{f'(\b)}\bigg), $$ where $f'$ is the derivative of $f(x)=x^3-x^2-1$ and $\cR e(z)$ stands for the real part of a complex $z$. Therefore, for $t=0$, $1$ or $2$, %\begin{eqnarray*} $$ |\a^3N_{3y+t}-N_{3y+3+t}|\le\big|2\a^3\cR e\bigg(\frac{\b^{3y+t}}{f'(\b)}\bigg)-2\cR e\bigg(\frac{\b^{3y+3+t}}{f'(\b)}\bigg)\big|\le3\a^3\frac{|\b|^{3y}}{|f'(\b)|}. %\end{eqnarray*} $$ Hence, $$|\a^3I_y-I_{y+1}|\le\frac{2+103+100}{117}\cdot\frac{3\a^3}{|f'(\b)|}\cdot|\b|^{3y}<5.6\times|\b|^{3y}.$$ Since $|\b|<1$ and $5.6\times|\b|^{60}\doteq 0.0000581\cdots$, the lemma follows. \end{proof} We are ready to prove that the two sequences are identical. \begin{theorem} For all $y\ge0$, $\t_y=\s_y$. \end{theorem} \begin{proof} It is easy to check that $r_y$ defined in (\ref{eq:3}) is of period $4$ and that $$ r_y=\frac1{117}\times\begin{cases}17,&\text{ if }y\equiv0\pmod4;\\ 46,&\text{ if }y\equiv1\pmod4;\\ 35,&\text{ if }y\equiv2\pmod4;\\ 19,&\text{ if }y\equiv3\pmod4. \end{cases} $$ (Thus, $r_y+r_{y+1}+r_{y+2}+r_{y+3}=1$ for all $y\ge0$.) We will need the differences $Ar_y-r_{y+1}$ for all $y$'s so we compute them to three significant digits \begin{equation}\label{eq:4} Ar_y-r_{y+1}=117^{-1} \begin{cases}17A-46&\\ 46A-35&\\ 35A-19&\\ 19A-17& \end{cases}\doteq\begin{cases}0.064,&\text{ if }y\equiv0\pmod4;\\ 0.938,&\text{ if }y\equiv1\pmod4;\\ 0.779,&\text{ if }y\equiv2\pmod4;\\ 0.366,&\text{ if }y\equiv3\pmod4. \end{cases} \end{equation} Let $y\ge20$ be an integer. We suppose that $\t_k=\s_k$ for all $k$'s, $0\le k\le y$, and proceed by induction. Thus, we need to show that $\t_{y+1}=\s_{y+1}$. Using our inductive hypothesis, we see that $A\t_y=A\s_y=AI_y+Ar_y=I_{y+1}+E_y+Ar_y=(\s_{y+1}-r_{y+1})+E_y+Ar_y$. That is, $A\t_y=\s_{y+1}+(Ar_y-r_{y+1}+E_y)$. By Lemma \ref{lem:E}, $|E_y|<6\cdot10^{-5}$ and, by (\ref{eq:4}), $6\cdot10^{-5}1$} \label{sec5} Here $\a$ is the dominant zero of $x^4-x^3-1$. We find that $\a\doteq 1.38028$. Thus, $a(n)=\lfloor n\a\rfloor$ and $b(n)=\lfloor n\a^4\rfloor$. We denote the fundamental sequence associated with $x^4-x^3-1$ as $H=(H_k)_{k\ge0}$. That is, $H_0=H_1=H_2=0$ and $H_3=1$ with $H_{n+4}=H_{n+3}+H_n$, for all integers $n$. This is sequence \seqnum{A017898} in the OEIS \cite{Slo}. \begin{lemma}\label{lem:H} For all integers $n\ge1$, we have \begin{align*} a^2(n)&=b(n)-n-\lfloor\frac{n}{\a}\rfloor-e_1(n)\\ ba(n)&=a(n)+b(n)-e_2(n)\\ ab(n)&=a(n)+b(n)-e_3(n)\\ b^2(n)&=a(n)+4b(n)-2n-\lfloor\frac{n}{\a}\rfloor+e_4(n), \end{align*} where the four $e_i$'s are bounded integral functions of $n$ with ranges $\{0,1,2,3\}$ for $e_1$ and $e_2$, $\{0,1\}$ for $e_3$ and $\{-1,0,1\}$ for $e_4$. \end{lemma} In fact, \begin{align*} e_1(n)&=\lceil\{\frac{n}{\a}\}+\a\{\a n\}-\{\a^3 n\}\rceil \\ e_2(n)&=\lc\a^3\{\a n\}-\{\a^3 n\}\rc, \\ e_3(n)&=\lceil(\a-1)\{\a^3 n\}-\{\a n\}\rceil \\ e_4(n)&=\lf(4-\a^4)\{\a^3n\}+\{\a n\}-\{\frac{n}{\a}\}\rf . \end{align*} The least value of $n$ for which $e_1(n)=3$ is $113$. The least $n$ with $e_4(n)=1$ is $47$. We omit the proof of Lemma \ref{lem:H} as it is similar in spirit to that of Lemma \ref{lem:N}. \begin{theorem}\label{thm:H} Let $w=\ell_1\circ\ell_2\circ\cdots\circ\ell_s$, $(s\ge1)$, where each $\ell_i$ is either $a$ or $b$. Assume $x$ and $y$ are, respectively, the number of $a$'s and the number of $b$'s in $w$. Then $w(n)$ equals $$ H_{x+4y-2}a(n)+H_{x+4y+1}b(n)-(H_{x+4y-3}+H_{x+4y-4})n-H_{x+4y-3}\bigg\lf\frac{n}{\a}\bigg\rf+e(n), $$ where $e$ is a bounded integral function of $n$. \end{theorem} \begin{proof} We carry out an inductive proof on the number of letters $\ell$ in the word $w$. By running the recursion defining the sequence $H$ backwards, we find that $H_{-3}=H_{-2}=0$ and $H_{-1}=1$. Thus we easily check the result when $\ell=1$ and, using Lemma \ref{lem:H}, for $\ell=2$. Assuming $w$ is a word with $\ell\ge2$ letters and the theorem holds for such words, we show the theorem still holds for $wa$ and $wb$. The inductive hypothesis gives that \begin{eqnarray*} wa(n)&=&H_{x+4y-2}\,a^2(n)+H_{x+4y+1}\,ba(n)\\ &-&(H_{x+4y-3}+H_{x+4y-4})a(n)-H_{x+4y-3} \bigg\lfloor\frac{a(n)}{\a}\bigg\rfloor+e\big(a(n)\big). \end{eqnarray*} Note that $\big\lf\frac{a(n)}{\a}\big\rf=\big\lf n-\frac{\{\a n\}}{\a} \big\rf=n-1$. So using Lemma \ref{lem:H} and regrouping terms we obtain \begin{eqnarray*} wa(n)&=&(H_{x+4y+1}-H_{x+4y-3}-H_{x+4y-4})\,a(n)+(H_{x+4y-2}+H_{x+4y+1})\,b(n)\\ &-&(H_{x+4y-2}+H_{x+4y-3})n-H_{x+4y-2}\bigg\lf\frac{n}{\a}\bigg\rf +e'(n),\end{eqnarray*} where $e'(n)=H_{x+4y-3}-H_{x+4y-2}e_1(n)+H_{x+4y+1}e_2(n)+e\big(a(n)\big)$. But $H_{x+4y+1}-H_{x+4y-3}-H_{x+4y-4}=H_{x+4y}-H_{x+4y-4}=H_{x+4y-1}=H_{(x+1)+4y-2}$ and $H_{x+4y-2}+H_{x+4y+1}=H_{x+4y+2}=H_{(x+1)+4y+1}$. Therefore, $wa(n)$ has the form claimed in the theorem. \medskip Also by the inductive hypothesis, \begin{eqnarray*} wb(n)&=&H_{x+4y-2}\,ab(n)+H_{x+4y+1}\,b^2(n)\\ &-&(H_{x+4y-3}+H_{x+4y-4})\,b(n)-H_{x+4y-3} \bigg\lf\frac{b(n)}{\a}\bigg\rf+e(b(n)). \end{eqnarray*} Note that $$ \bigg\lf\frac{b(n)}{\a}\bigg\rf=\bigg\lf\frac{(\a^5-\a)n-\{\a^4n\}}{\a}\bigg\rf=b(n)-n+\bigg\lf \bigg(1-\frac1\a\bigg)\{\a^4n\}\bigg\rf. $$ But $(1-1/\a)\{\a^4n\}\in(0,1)$ so $\lfloor b(n)/\a\rfloor=b(n)-n$. Using Lemma \ref{lem:H}, the identity $\lfloor b(n)/\a\rfloor=b(n)-n$, and regrouping like-terms, we obtain \begin{eqnarray*} wb(n)&=&(H_{x+4y-2}+H_{x+4y+1})a(n)\\ &+&(H_{x+4y-2}+4H_{x+4y+1}-2H_{x+4y-3}-H_{x+4y-4})b(n)\\ &-&(2H_{x+4y+1}-H_{x+4y-3})n-H_{x+4y+1}\bigg\lfloor\frac{n}{\a}\bigg\rfloor+e''(n), \end{eqnarray*} where $e''(n)=H_{x+4y-2}e_2(n)+H_{x+4y+1}e_4(n)+e\big(b(n)\big)$ is an integral and bounded function of $n$. Using the recursion for $H$, we obtain the expected coefficients for $a(n)$, $b(n)$, $n$ and $\big\lfloor\frac{n}{\a}\big\rfloor$. For the coefficient of $b(n)$, put $t=x+4y+1$. Then we check that $H_{t+4}=4H_t+H_{t-3}-2H_{t-4}-H_{t-5}$. It holds iff $H_{t+3}=3H_t+H_{t-3}-2H_{t-4}-H_{t-5}$. But $$H_{t+3}=H_{t+2}+H_{t-1}=H_{t+1}+ H_{t-1}+H_{t-2}=H_t+H_{t-1}+H_{t-2}+H_{t-3}.$$ Thus, the identity to prove holds iff $H_{t-1}+H_{t-2}=2H_t-2H_{t-4}-H_{t-5}$. But the latter is true as $H_t-H_{t-4}=H_{t-1}$ and $2H_{t-1}-H_{t-5}=H_{t-1}+H_{t-2}$. \end{proof} \section{The general case $(\a,\a^q)$, $(q\ge2)$} \label{sec6} Let $q\ge2$ be an integer. The polynomial $f(x):=x^q-x^{q-1}-1$ possesses a simple dominant real zero $\a>1$ \cite[Lemma 3]{Ba}. Here, $a(n)=\lf n\a\rf$ and $b(n)=\lf n\a^q\rf$. We denote the fundamental sequence associated with $f(x)$ as $G=(G_k)_{k\ge0}$. That is, $G_0=G_1=\cdots=G_{q-2}=0$ and $G_{q-1}=G_q=\cdots= G_{2q-2}=1$ as $G_{t+q}=G_{t+q-1}+G_t$. \begin{lemma}\label{lem:geo} Let $\th$ be a zero of $x^q-x^{q-1}-1$. Then, for all integers $n\ge m$, we find that $$ \sum_{i=m}^n\th^i=\th^{n+q}-\th^{m+q-1}. $$ \end{lemma} \begin{proof} Summing the geometric series $\sum_{i=m}^n\th^i$ yields the expression $\frac{\th^{n+1}-\th^m}{\th-1}$. But $\th^{n+1}=\th^{n+q+1}-\th^{n+q}=\th^{n+q}(\th-1)$ and $\th^m=\th^{m+q-1}(\th-1)$. \end{proof} \begin{lemma}\label{lem:G} For all integers $n\ge1$, we have \begin{align*} a^2(n)&=b(n)-n-\bigg\lf\frac{n}{\a}\bigg\rf-\cdots-\bigg\lf\frac{n}{\a^{q-3}} \bigg\rf+O(1),\\ ba(n)&=a(n)+b(n)+O(1),\\ ab(n)&=a(n)+b(n)+O(1),\\ b^2(n)&=a(n)+q\,b(n)-(q-2)\,n-(q-3)\bigg\lf\frac{n}{\a}\bigg\rf-\cdots-\bigg\lf\frac{n} {\a^{q-3}}\bigg\rf+O(1). \end{align*} \end{lemma} \begin{proof} By Lemma \ref{lem:geo}, $\sum_{i=0}^{q-3}\a^{-i}=\sum_{i=3-q}^0\a^i=\a^q-\a^2$. Hence, \begin{align*} a^2(n)&=\lf\a^2n-\a\{\a n\}\rf= \lf\a^q n-\sum_{i=0}^{q-3}\frac{n}{\a^i}-\a\{\a n\}\rf \\ &=b(n)-\sum_{i=0}^{q-3}\lf\frac{n}{\a^i}\rf+O(1). \end{align*} Now $ab(n)=\lf\a^q\lf\a n\rf\rf=\lf(\a^{q-1}+1)(\a n-\{\a n\})\rf=a(n)+b(n)+O(1)$. A similar expansion also yields our claim for $ba(n)$. The expression for $b^2(n)$ will hold if $\a^{2q}=\a+q\a^q -\sum_{i=0}^{q-3}\a^{-i}-\sum_{i=0}^{q-2}\a^{-i}-\cdots-\a^{-0}$. That is, if $\a^{2q}=\a+q\a^q- \sum_{j=0}^{q-3}\sum_{i=3+j-q}^0\a^i$. Now, using Lemma \ref{lem:geo} twice, we obtain \begin{align*} \a+q\a^q-\sum_{j=0}^{q-3}\sum_{i=3+j-q}^0\a^i &=\a+q\a^q-\sum_{j=0}^{q-3}(\a^q-\a^{2+j}) \\ &= \a+2\a^q +(\a^{2q-1}-\a^{q+1})=-(\a^{q+1}-\a^q-\a)+(\a^q+\a^{2q-1}) \\ &=0+\a^{2q}. \end{align*} \end{proof} \begin{remark} The third bounded function $O(1)$ in the identity $ab(n)=a(n)+b(n)+O(1)$ is $\lf(1-\a)\{\a^qn\}+\{\a n\}\rf$, so it is either $0$  or $-1$. \end{remark} \begin{lemma}\label{lem:g} Let $n\ge m$ be integers. Then $$ \sum_{i=m}^nG_i=G_{n+q}-G_{m+q-1}. $$ \end{lemma} \begin{proof} The derivative of $f(x)$ only has $0$ and $(q-1)/q$ as zeros. Since neither $0$, nor $(q-1)/q$ is a zero of $f$, the zeros $\th_1,\ldots,\th_q$ of $f(x)$ are simple. Thus, $G_i$ is a linear combination of the $\th_t^i$, $t=1,\ldots,q$. Hence, the lemma is a direct consequence of Lemma \ref{lem:geo}. \end{proof} \begin{cor}\label{cor:g2} Let $p\ge1$, $q\ge3$ and $0\le j\le q-3$ be integers. Then $$ \sum_{3\le i\le q-j}G_{p-i}=G_{p+q-3}-G_{p+j-1}. $$ \end{cor} \begin{proof} We note that $\sum_{3\le i\le q-j}G_{p-i}=\sum_{i=p+j-q}^{p-3}G_i$ and apply Lemma \ref{lem:g}. \end{proof} \begin{theorem}\label{thm:G} Let $w$ be a composite function of some $a$'s and $b$'s. Putting $p=x+qy$, where $x$ and $y$ are, respectively, the number of $a$'s and the number of $b$'s in $w$, we find that, for all $n\ge1$, \begin{equation}\label{eq:main} w(n)=G_{p-2}\,a(n)+G_{p+q-3}\, b(n)-\sum_{0\le j\le q-3}c_j\bigg\lf\frac{n}{\a^j}\bigg\rf+O(1), \end{equation} where $c_j=\sum_{3\le i\le q-j}G_{p-i}$, or alternatively $c_j=G_{p+q-3}-G_{p+j-1}$. \end{theorem} \begin{proof} Note that for $q=2$, the sum $\sum_{0\le j\le q-3}c_j\lf n/\a^j\rf$ is empty and equals $0$ by convention. Hence, in that case, the theorem is implied by Theorem \ref{thm:Kim}. Thus, assume $q\ge3$. Observe that, by Corollary \ref{cor:g2}, $\sum_{3\le i\le q-j}G_{p-i}=G_{p+q-3}-G_{p+j-1}$. We may proceed by induction on $x+y$ as was done in Theorems \ref{thm:Kim}, \ref{thm:root2}, \ref{thm:N} and \ref{thm:H}. One checks the result for $x+y=1$ directly. For instance, if $w=a$, then taking the function $O(1)$ to be the null function and noting that $G_{-1}=1$ and $G_{-i}=0$, $2\le i\le q-1$, we find that all coefficients $c_j$ of (\ref{eq:main}) are zero so that $G_{-1}a(n)+G_{q-2}b(n)-0+0$ is indeed $a(n)$. \smallskip Now suppose (\ref{eq:main}) holds for some $w$ with $x+y\ge1$ letters. Replacing $n$ by $a(n)$ in (\ref{eq:main}), using Lemma \ref{lem:G} to express $a^2(n)$ and $ba(n)$ and filling in some constant terms into the $O(1)$ term, we find that \begin{equation} \begin{split} wa(n)&=G_{p-2}\bigg(b(n)-\sum_{0\le j\le q-3}\bigg\lf\frac{n}{\a^j}\bigg\rf\bigg)+G_{p+q-3} \big(a(n)+b(n)\big)\\ &-\sum_{0\le j\le q-3}\big(G_{p+q-3}-G_{p+j-1}\big) \bigg\lf\frac{a(n)}{\a^j}\bigg\rf+O(1). \end{split} \label{eqn:wa} \end{equation} The coefficient of $b(n)$ is $G_{p-2}+G_{p+q-3}=G_{p+q-2}=G_{(p+1)+q-3}$, while that of $a(n)$ is $G_{p+q-3}-(G_{p+q-3}-G_{p-1})=G_{(p+1)-2}$, as expected. Since $\lf n/\a^{j-1}\rf-\lf a(n)/\a^j\rf$ is $0$ or $1$ for all $j\ge1$, the remaining terms are $$ -G_{p-2}\sum_{0\le j\le q-3}\bigg\lf\frac{n}{\a^j}\bigg\rf-\sum_{1\le j\le q-3} \big(G_{p+q-3}-G_{p+j-1}\big)\bigg\lf\frac{n}{\a^{j-1}}\bigg\rf+O(1). $$ But $\sum_{1\le j\le q-3}\big(G_{p+q-3}-G_{p+j-1}\big)\lf n/\a^{j-1}\rf= \sum_{0\le j\le q-4}\big(G_{p+q-3}-G_{p+j}\big)\lf n/\a^j\rf$, so we see that the coefficient $c_j(wa)$ of $-\lf n/\a^j\rf$ in $wa(n)$ is, for $0\le j\le q-4$, equal to $$(G_{p-2}+G_{p+q-3})-G_{p+j}=G_{p+q-2}-G_{p+j}=G_{(p+1)+q-3}-G_{(p+1)+j-1},$$ while $c_{q-3}(wa)=G_{p-2}=G_{(p+1)-3}$, as expected. \smallskip Similarly, we expand $wb(n)$, expressing $ab(n)$ and $b^2(n)$ with Lemma \ref{lem:G}, to find that $wb(n)$ may be written as \begin{align} &G_{p-2}\big(a(n)+b(n)\big)+G_{p+q-3}\bigg(a(n)+q\,b(n)-\sum_{0\le i\le q-3} (q-2-i)\bigg\lf\frac{n}{\a^i}\bigg\rf\bigg)\nonumber\\ &-\sum_{0\le j\le q-3}\big(G_{p+q-3}-G_{p+j-1}\big) \bigg\lf\frac{b(n)}{\a^j}\bigg\rf+O(1).\label{eqn:wb} \end{align} The coefficient of $a(n)$, $G_{p-2}+G_{p+q-3}$, is, as expected, equal to $G_{(p+q)-2}$. Given $j$ between $1$ and $q-3$, and noting that $$\a^qn=(\a^{q+1}-\a)n=(\a^{q+2}-\a^2-\a)n= \cdots=(\a^{q+j}-\a^j-\a^{j-1}-\cdots-\a)n,$$ we see that, for all $j\ge0$, \begin{equation}\label{eq:wb} \bigg\lf\frac{b(n)}{\a^j}\bigg\rf=b(n)-\sum_{0\le k\le j-1}\bigg\lf\frac{n}{\a^k}\bigg\rf+O(1). \end{equation} Therefore the (natural) coefficient of $b(n)$ in $wb(n)$ is \begin{align} G_{p-2}&+q\,G_{p+q-3}-\sum_{0\le j\le q-3}\big(G_{p+q-3}-G_{p+j-1}\big)\nonumber\\ &=G_{p-2}+2G_{p+q-3}+\sum_{0\le j\le q-3}G_{p-1+j}\nonumber\\ &=G_{p-2}+2G_{p+q-3}+(G_{p-1+2q-3}-G_{p+q-2})\label{eq:5}\\ &=2G_{p+q-3}+G_{p+2q-4}-(G_{p+q-2}-G_{p-2})\nonumber\\ &=G_{p+q-3}+G_{p+2q-3}-G_{p+q-3}=G_{p+2q-3}\nonumber, \end{align} as expected, where in (\ref{eq:5}) we used Corollary \ref{cor:g2}. \smallskip By (\ref{eqn:wb}) and (\ref{eq:wb}), the coefficient $c_k(wb)$ is \begin{align} &(q-2-k)G_{p+q-3}-\sum_{k+1\le j\le q-3}(G_{p+q-3}-G_{p+j-1})\nonumber\\ \qquad&=\big(q-2-k-(q-3-k)\big)G_{p+q-3}+\sum_{j=k+1}^{q-3}G_{p-1+j}\nonumber\\ \qquad&=(G_{p+q-3}+G_{p+2q-4})-G_{p+q+k-1}\label{eq:6}\\ &=G_{(p+q)+q-3}-G_{(p+q)+k-1}\nonumber, \end{align} which is what we intended to prove. Again, in (\ref{eq:6}), we used Corollary \ref{cor:g2}. \end{proof} \begin{remark} The basis functions $a(n)$, $b(n)$, and the $\lf\frac{n}{\a^j}\rf$, used to express $w(n)$ in Theorem \ref{thm:G}, are all integral, and so are their coefficients, but there is no uniqueness in this property. Other choices could have been made. For instance, in Lemma \ref{lem:G}, we could have chosen to express $a^2(n)$ as $a(n)+\lf\frac{n}{\a^{q-2}}\rf-e(n)$, where $e(n)=\lceil(\a-1)\{\a n\}-\{n/\a^{q-2}\}\rceil\in\{0,1\}$. Had we made this choice for $a^2(n)$, the general expression of $b^y(n)$, when $q=3$, in Corollary \ref{cor:N}, would have taken the form $b^y(n)=(N_{3y-1}+N_{3y-6})a(n)+N_{3y-1}b(n)+N_{3y-3} \lf n/\a\rf+O(1)$. \end{remark} \section{Problems for future research} \label{sec7} We provide some ideas for further investigation. These ideas only reflect how we see things at the moment and are probably more a measure of our ignorance than anything else. \medskip \begin{problem} \label{problem:1} Find other pairs of complementary Beatty sequences, preferably infinite families of such pairs $\big(a_s(n),b_s(n)\big)$, and discover theorems comparable to Theorems \ref{thm:R} and \ref{thm:G} that express a word in $a_s$ and $b_s$ as nearly a linear combination of $a_s$ and $b_s$. \end{problem} (The referee pointed out the polynomials $x^q-x^{q-1}-x-1$ for $q\ge3$. Each such polynomial \cite[Lemma 3]{Ba} has a simple dominant zero $\a$. In fact, for $q=3$, $\a$ is a cubic Pisot number that can play a fundamental role in the construction of Rauzy fractals \cite{Rau}.) \medskip The secondary question tackled in this paper of whether the sequences $(b^y(n))_y$ are linear recurrences leads to a simple fundamental problem. \smallskip \begin{problem}\label{problem:2} Let $\a>1$ be, say, a real algebraic integer of minimal polynomial $P$. Put $f(n):=\lf\a n\rf$. Fix an integer $n\ge1$ and define, for $y$ a positive integer, $u_y$ as $f^y(n)$, where $f^y$ is the $y$-fold composite function $f\circ\cdots\circ f$. \smallskip {\bf 1.} Characterize those algebraic integers $\a$ for which the sequence $(u_y)_y$ is a linear recurrence of characteristic polynomial $P$ for all choices of $n$. \smallskip {\bf 2.} Characterize those algebraic integers $\a$ for which the sequence $(u_y)_y$ is a linear recurrence for all choices of $n$. Is it necessarily true that the characteristic polynomial of $(u_y)$ must be a multiple of $P$? Or that it must be of the form $(x^h-1)P$ for some $h\ge0$? \smallskip {\bf 3.} Suppose $(u_y)_y$ is a linear recurrence for $n=1$. Does it follow that it is linear recurrent for all choices of $n$? If so, would there always be an annihilating polynomial common to all $(u_y)$ for all values of $n\ge1$? How often would that common polynomial turn out to be the characteristic polynomial of $(u_y)$ when $n=1$? \end{problem} \medskip Given a pair of complementary Beatty sequences $(a,b)$, write $A$ and $B$ for the respective ranges of the functions $a$ and $b$. For the Wythoff pair $(a,b)$, we saw that $b^y(1)=F_{2y+1}$. Stolarsky \cite[p.~441]{Sto} observed that for all $y\ge1$, the pair $V_y=(F_{2y},F_{2y+1})$ belongs to $A\times B$ and that the vectors $V_y$ satisfy the second-order recursion $V_{y+2}=3V_{y+1}-V_y$. Note that $V_y=(\lf F_{2y-1}\a\rf,\lf F_{2y-1}\a^2\rf)=\big(ab^{y-1}(1),b^y(1)\big)$. More generally, the vectors $V_y=\big(ab^{y-1}(1),b^y(1)\big)$ satisfy the same second-order recurrence as $(b^y(1))_y$ for all Beatty pairs of Section~\ref{sec3}, where $\b=\a+r$, $r\ge1$. Indeed, by Corollary \ref{cor:byof1}, $(b^y(1))_y$ is a second-order recurrence, and one easily sees that $ab^{y-1}(1)=b^y(1)-rb^{y-1}(1)$. In the Narayana case, we saw that $(b^y(1))_y$ satisfies a 7th-order linear recurrence and it does seem experimentally that the vectors $\big(ab^{y-1}(1),b^y(1)\big)$, all in $A\times B$, satisfy the same 7th-order recursion. These various instances of the same phenomenon raise another problem \smallskip \begin{problem}\label{problem:3} Characterize pairs of complementary Beatty sequences $(a,b)$ such that the vectors $V_y:=\big(ab^{y-1}(1),b^y(1)\big)$ satisfy a linear recurrence relation. \end{problem} \medskip In the Wythoff context, Stolarsky \cite{Sto} discovered a sequence of vectors in $A\times B$ which satisfy a fourth-order linear recurrence with characteristic polynomial $x^4-10x^3+16x^2-5x-1$ coprime to $x^2-3x+1$. Later, Ridley \cite{Rid} found infinitely many sequences of Wythoff pairs that satisfy fourth-order linear recurrences, one being a recurrence with characteristic polynomial $x^4-x^3-5x^2+7x-1$. \smallskip \begin{problem}\label{problem:4} Given a pair of complementary Beatty sequences $(a,b)$ with $\a$ algebraic, are there general methods to generate sequences of vectors in $A\times B$ that satisfy higher-order linear recurrences? \end{problem} \medskip The referee suggested another problem, not unrelated to Problem \ref{problem:2}, which he illustrated with an example. \smallskip \begin{problem} In \S4, Lemma \ref{lem:3}, we reach an identity of the form $$ \sum_{k=0}^mc_ka_{n+k}=F(a_n,a_{n+1}), $$ where $F$ is a floor function of a linear combination of fractional parts involving $a_n$ and $a_{n+1}$ which can only take finitely many values. As turned out the $a_n$'s of \S4 satisfy a homogeneous linear recurrence, though of higher order. To be more specific, the characteristic polynomial has an `additional factor' of $x^4-1$. Can any general results of this nature be obtained? A simple example of such recurrences is the following `almost Fibonacci' recurrence $$ a_{n+2}=a_{n+1}+a_n +\lf k\{a_{n+1}\a\}\rf, $$ where $k$ is a fixed positive integer, $\a= (1+\sqrt{5})/2$. Do the $a_n$'s satisfy homogeneous linear recurrences? If so, {\bf 1.} what are the corresponding characteristic polynomials and {\bf 2.} is the linear recurrence independent of the initial conditions? Computer experiments suggest that (for example) for $k=11$ both $(x^3-1)(x^2-x-1)$ and $(x^8-1)(x^2-x-1)$ are possible depending upon the initial conditions. The same sort of thing seems true for $k = 12$ and $13$ with possibly different such recurrences for different initial conditions. Perhaps there is always a recurrence whose characteristic polynomial has the form $x^2-x-1$ or $(x^2-x-1)(x^h-1)$ for some positive integer $h$? \end{problem} \section{Acknowledgments} \label{sec8} We are thankful to the referee in three ways. He accepted our text as it was. He offered numerous references, with comments, to beautiful papers we were not aware of that may have connections with our text. Those appear at the end of the introduction and enrich the present paper. Finally, he suggested that we wrote an additional section for open investigations providing a couple of his own. \begin{thebibliography}{99} \bibitem{AJ} J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, {\it Cahiers du GREYC}, JIM 96 {\bf 4} (1996) 2--7, available at \\ \url{http://recherche.ircam.fr/equipes/repmus/jim96/actes/Allouche.ps}. \bibitem{Ba} C. Ballot, On the constant in the average digit sum for a recurrence-based numeration, {\it Unif. Distrib. Theory}, {\bf 11} (2016), 125--150. \bibitem{Bea} S. Beatty, Problem 3173, {\it Amer. Math. Monthly}, {\bf 33} (1926), 159; {\bf 34} (1927), 159. \bibitem{Ber} M.-J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, M. Pathiaux-Delefosse, and J.-P. Schreiber, {\it Pisot and Salem Numbers}, Birkh\"auser Verlag, 1992. \bibitem{Bos} M. Boshernitzan and A. S. Fraenkel, Nonhomogeneous spectra of numbers, {\it Discrete Math.} {\bf 34} (1981), 325--327. \bibitem{Fra} A. S. Fraenkel, Iterated floor function, algebraic numbers, discrete chaos, Beatty subsequences, semigroups, {\it Trans. Amer. Math. Soc.} {\bf 341} (1994), 639--664. \bibitem{Fra2} A. S. Fraenkel, H. Porta, and K. B. Stolarsky, Some arithmetical semigroups, {\it Progress in Math.} {\bf 85} (1990), 255--264. \bibitem{Ki} C. Kimberling, Complementary equations and Wythoff sequences, {\it J. Integer Sequences}, {\bf 11} (2008), \href{https://cs.uwaterloo.ca/journals/JIS/VOL11/Kimberling/kimberling719a.html}{Article 08.3.3}. \bibitem{Ki2} C. Kimberling, Beatty sequences and Wythoff sequences, generalized, {\it Fibonacci Quart.}, {\bf 49} (2011) 195--200. \bibitem{Lag} J. C. Lagarias, H. Porta, and K. B. Stolarsky, Asymmetric tent map expansions I: eventually periodic points, {\it J. London Math. Soc.} {\bf 47} (1993), 542--556. \bibitem{Lag2} J. C. Lagarias, H. Porta, and K. B. Stolarsky, Asymmetric tent map expansions II, {\it Illinois J. Math.} {\bf 38} (1994), 574--588. \bibitem{Por} H. A. Porta and K. B. Stolarsky, Wythoff pairs as semigroup invariants, {\it Adv. in Math.} {\bf 85} (1991), 69--82. \bibitem{Rau} G. Rauzy, Nombres alg\'ebriques et substitutions, {\it Bull. Soc. Math. France}, {\bf 110} (1982), 147--178. \bibitem{Ray} J. W. S. Rayleigh, {\it The Theory of Sound}, Vol.~1, 2nd edition, Macmillan, 1894. \bibitem{Rid} J. Ridley, Fourth order linear recurrences satisfied by Wythoff pairs, {\it Ramanujan J.} {\bf 5} (2001), 159--165. \bibitem{Sch} K. Scheicher, V. F. Sirvent, and P. Surer, Dynamical properties of the tent map, {\it J. London Math. Soc.} {\bf 93} (2016), 319--340. \bibitem{Slo} N. J. A. Sloane, The Online Encyclopedia of Integer Sequences, published electronically at \url{http://oeis.org}. \bibitem{Smy} C. J. Smyth. There are only eleven special Pisot numbers, {\it Bull. London Math. Soc.} {\bf 311} (1999), 1--5. \bibitem{Sto0} K. Stolarsky, Beatty sequences, continued fractions, and certain shift operators, {\it Canad. Math. Bull.} {\bf 19} (1976), 473--482. \bibitem{Sto} K. Stolarsky, Fourth order linearly recurrent Wythoff pairs. {\it Ramanujan J.} {\bf 2} (1998), 441--448. \bibitem{Wyt} W. A. Wythoff, A modification of the game of Nim, {\it Nieuw Arch. Wisk.}, {\bf 2} (1905--07), 199--202. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B83; Secondary 11B37, 11B39. \noindent \emph{Keywords: } Beatty sequence, Wythoff pair, integer part, linear recurrence. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum {A078012}, \seqnum {A017898}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received July 26 2016; revised versions received January 17 2017; January 28 2017. Published in {\it Journal of Integer Sequences}, January 28 2017. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}