\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 $k<i$. If $\a$ is an irrational real number, then the uniform distribution of 
the sequence of fractional parts of the multiples of $\a$, i.e., the sequence $(\{n\a\})_{n\ge1}$, is 
a well-known fact that we occasionally use.  
 
 
\section{The $(\sqrt{2},2+\sqrt{2})$ case} 
\label{sec2}

 Thus, we now have $a(n):=\lfloor n\a\rfloor$ and $b(n):=\lfloor n\b\rfloor$, where  
$\a=\sqrt{2}$ and $\b=2+\sqrt{2}$. 

\begin{lemma}\label{lem:Cas1} For all integers $n\ge1$, we have 
\begin{align*} 
a^2(n)&=-a(n)+b(n)-d(n)\\
ba(n)&=a(n)+b(n)-d(n)\\
ab(n)&=a(n)+b(n)\\
b^2(n)&=a(n)+3b(n),
\end{align*} where  
$d(n)$ is the function $\lceil\sqrt{2}\{n\sqrt{2}\}\rceil$ which is either $1$ or $2$. 
\end{lemma}
\begin{proof} See the proof of the more general Lemma \ref{lem:cas-r} of the next section. 
\end{proof}

\begin{theorem}\label{thm:root2} Let $w=\ell_1\circ\ell_2\circ\cdots\circ\ell_s$, $(s\ge1)$, 
where each $\ell_i$ is either $a$ or $b$. If $w$ has an even number of $a$'s, say $2x$, 
and $y$ $b$'s ($x\ge0$, $y\ge0$), then  
\begin{equation}\label{eq:xeven}
w(n)=2^xu_y\,a(n)+2^xv_y\,b(n)-e(n),
\end{equation}
whereas, if $w$ has $2x+1$ $a$'s and $y$ $b$'s, then
\begin{equation}\label{eq:xodd}
w(n)=2^{x+1}v_{y-1}\,a(n)+2^xu_{y+1}\,b(n)-e(n),
\end{equation} where in both cases $e=e_w$ is some nonnegative integral bounded function 
of $n$ that depends on $w$, and $(u_y)$ and $(v_y)$ are the recurrences with characteristic 
polynomial $x^2-4x+2$ that satisfy $u_1=0$, $u_2=1$ and $v_1=1$, $v_2=3$.
\end{theorem}
\begin{proof} It is easy to verify that 
\begin{equation}
\begin{aligned} 
u_y+v_y & =u_{y+1}& \quad
v_y-u_y& =2v_{y-1} \\
u_y+3v_y &=v_{y+1}& \quad
u_{y+1}-2v_{y-1} &=2u_y.
\end{aligned}
\label{eq:comb}
\end{equation}
We may proceed by induction on $s$. Both (\ref{eq:xeven}) and (\ref{eq:xodd}) 
trivially hold for $s=1$ with $e=0$, as $v_{-1}=v_0=1/2$. Assuming the property holds for some $s\ge1$ and 
$w$ is a `word' with $s$ letters, we check the property for $wa$ and $wb$. 
There are four cases to treat as the form of $w$ depends on the parity of the 
number of $a$'s in $w$. If $w$ has $2x$ $a$'s and $y$ $b$'s, then, by the inductive hypothesis,
$$
wa(n)=w(a(n))=2^xu_y\,a^2(n)+2^xv_y\,b(a(n))-e(a(n)), 
$$ for some nonnegative bounded function $e$. Using Lemma \ref{lem:Cas1} and 
gathering together the coefficients of $a(n)$ and $b(n)$, we find that 
$$
wa(n)=2^x(v_y-u_y)\,a(n)+2^x(u_y+v_y)\,b(n)-e'(n),
$$ with $e'(n)=u_{y+1}d(n)+e(a(n))$. By (\ref{eq:comb}), $wa(n)=2^{x+1}v_{y-1}\,a(n)+
2^xu_{y+1}\,b(n)-e'(n)$, which is the expected result for the word $wa$. We proceed in 
the same manner for $wb(n)$ and obtain 
$$
wb(n)=2^x(u_y+v_y)\,a(n)+2^x(u_y+3v_y)\,b(n)-e(b(n)). 
$$ We conclude using the first pair of equations of (\ref{eq:comb}). 
If $w$ has $2x+1$ $a$'s and $y$ $b$'s, then the inductive hypothesis yields 
$$
wa(n)=2^{x+1}v_{y-1}\,a^2(n)+2^xu_{y+1}\,ba(n)-e(a(n)).
$$ Using Lemma \ref{lem:Cas1}, we find that $wa(n)=2^x(u_{y+1}-2v_{y-1})\,a(n)+2^x(u_{y+1}+2v_{y-1})\,b(n)
-e''(n)$, where $e''(n)=2^x(2v_{y-1}+u_{y+1})d(n)+e(a(n))$. Since $v_{-1}=v_0=1/2$, we see 
that $e''$ is nonnegative in all cases. We conclude using the second pair of identities of (\ref{eq:comb}), 
as $u_{y+1}-2v_{y-1}=2u_y$ and $u_{y+1}+2v_{y-1}=(u_{y+1}-2v_{y-1})+4v_{y-1}=2(u_y+2v_{y-1})=2v_y$. 
Finally, we obtain, in similar fashion, $wb(n)=2^x(u_{y+1}+2v_{y-1})\,a(n)+2^x(3u_{y+1}+2v_{y-1})\,b(n)-e(b(n))$. 
We just saw that $u_{y+1}+2v_{y-1}=2v_y$. Moreover, 
$$3u_{y+1}+2v_{y-1}=2u_{y+1}+2v_y= 
u_{y+1}+(u_{y+1}+2v_y)=u_{y+1}+v_{y+1}=u_{y+2},$$
according to the two identities on the first line of (\ref{eq:comb}).  
\end{proof}

\section{The general $(\a,\a+r)$ case, ($r\ge1$)}
\label{sec3}

 We fix an integer $r\ge1$. If $\b=\a+r$, then we see that $b(n)=a(n)+rn$. 
Solving $1/\a+1/(\a+r)=1$ leads to $\a^2+(r-2)\a-r=0$. Since $\a\in(1,2)$, 
we find that $\a=1+\frac{\sqrt{r^2+4}-r}2$. Thus, $\b=1+\frac{\sqrt{r^2+4}+r}2$ and 
$\b$ satisfies $\b^2-(r+2)\b+r=0$. As $r^2+4$ is never a perfect square, we note that 
$\a$ and $\b$ are irrational. 

\begin{lemma}\label{lem:cas-r} For all integers $n\ge1$, we have 
\begin{align*} 
a^2(n)&=(1-r)a(n)+b(n)-d(n)\\
ba(n)&=a(n)+b(n)-d(n)\\
ab(n)&=a(n)+b(n)\\
b^2(n)&=a(n)+(r+1)b(n),
\end{align*} where  
$d(n)$ is the function $\lceil(\a+r-2)\{n\a\}\rceil$ whose range is $\{1,2,\ldots,r\}$. 
\end{lemma}
\begin{proof} Using $\a^2=(2-r)\a+r$ and $\{\a n\}=\{\b n\}$, we find that
\begin{align*}
a^2(n)&=\lf\a\lf\a n\rf\rf=\lf\a^2n-\a\{\a n\}\rf=\lf\big((1-r)\a+(\a+r)\big)n-\a\{\a n\}\rf \\
&= (1-r)a(n)+b(n)+\lf(1-r)\{\a n\}+\{\a n\}-\a\{\a n\}\rf \\
&=(1-r)a(n)+b(n)-\lc(r-2+\a)\{\a n\}\rc .
\end{align*}
But the sequence $(\{\a n\})_{n\ge1}$ is dense in $(0,1)$ and $r-2+\a$ lies in $(r-1,r)$, so the range of $d$ is $\{1,2,\ldots,r\}$.
Hence, $b(a(n))=\lf(\a+r)a(n)\rf=ra(n)+a^2(n)=a(n)+b(n)-d(n)$. 
Now 
\begin{align*}
ab(n) &=\lf\a(\a+r)n-\a\{(\a+r)n\}\rf=\lf\a n+(\a+r)n-\a\{\a n\}\rf \\
&=a(n)+b(n) +\lf(2-\a)\{\a n\}\rf=a(n)+b(n),
\end{align*}
as both $2-\a$ and $\{\a n\}$ lie in the 
interval $(0,1)$. Thus,
$$b^2(n)=\lf(\a+r)b(n)\rf=rb(n)+ab(n)=a(n)+(r+1)b(n).$$
\end{proof}

 Define $(U_n^\a)_{n\ge0}$ and $(U_n^\b)_{n\ge0}$, respectively, as the fundamental 
Lucas sequences associated with $(x-\a)(x-\bar\a)$ and with $(x-\b)(x-\bar\b)$, 
where $\bar\a$ and $\bar\b$ are the respective algebraic conjugates of $\a$ and $\b$. 
Thus, 
\begin{equation}\label{eq:Luc}
U_n^\a=\frac{\a^n-\bar\a^n}{\a-\bar\a}\quad\text{ and }\quad U_n^\b=\frac{\b^n-\bar\b^n}{\b-\bar\b}. 
\end{equation} 

 We also define two matrices 
\begin{equation}\label{eq:Mat}
E_a=\left(\begin{matrix}1-r & 1\\1 & 1\end{matrix}\right)\quad\text{ and }\quad
E_b=\left(\begin{matrix}1 & 1\\1 & 1+r\end{matrix}\right).
\end{equation}

\begin{lemma}\label{lem:Mat} For all integers $x\ge0$ and $y\ge0$, we find that  
$$ 
E_a^x=\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)\;\text{ and }\;
E_b^y=\left(\begin{matrix}U_y^\b-rU_{y-1}^\b & U_y^\b\\ U_y^\b & U_{y+1}^\b-U_y^\b\end{matrix}\right).
$$
\end{lemma}
\begin{proof} The characteristic polynomials of $E_a$ and $E_b$ are, respectively, 
the minimal polynomials of $\a$ and $\b$. Thus, their respective eigenvalues 
are $\{\a,\bar\a\}$ and $\{\b,\bar\b\}$. Thus, we may diagonalize 
the two matrices $E_a$ and $E_b$ and find that 
$$
E_a=P_a\left(\begin{matrix}\a & 0\\0 & \bar\a\end{matrix}\right)P_a^{-1}\quad\text{ and }\quad
E_b=P_b\left(\begin{matrix}\b & 0\\0 & \bar\b\end{matrix}\right)P_b^{-1},
$$ where we took 
$$
P_a=\left(\begin{matrix}\a-1 & \bar\a-1\\1 & 1\end{matrix}\right)\quad\text{ and }\quad
P_b=\left(\begin{matrix}1 & 1\\\b-1 & \bar\b-1\end{matrix}\right), 
$$ as eigenvector matrices. 
We then simply calculate 
$$ 
E_a^x=P_a\left(\begin{matrix}\a^x & 0\\0 & \bar\a^x\end{matrix}\right)P_a^{-1}\quad\text{ and }\quad
E_b^y=P_b\left(\begin{matrix}\b^y & 0\\0 & \bar\b^y\end{matrix}\right)P_b^{-1},
$$ noting that for $x=0$ or for $y=0$, the expressions in the lemma produce the identity 
matrix $\left(\begin{matrix}1 & 0\\0 & 1\end{matrix}\right)$. Indeed, $U_{-1}^\a=1/r$ and 
$U_{-1}^\b=-1/r$. 
\end{proof}

\begin{theorem}\label{thm:R} Let $r\ge1$ be an integer, $\a=1+\frac{\sqrt{r^2+4}-r}2$ and 
$\b=\a+r$. Define $a(n)=\lf\a n\rf$ and $b(n)=\lf\b n\rf$. Let 
$w=\ell_1\circ\ell_2\circ\cdots\circ\ell_{x+y}$,  
where $\ell_i=a$ for $x\ge0$ values and $\ell_i=b$ for the remaining $y$ values of $i$, $1\le i\le x+y$. 
Then for all $n\ge1$ \begin{equation}\label{eq:R}
w(n)=s_{x,y}\,a(n)+t_{x,y}\,b(n)-d_w(n),
\end{equation}
where 
\begin{align}\begin{split}\label{eq:Rcoef}
&s_{x,y}=U_x^\a U_y^\b-rU_{y-1}^\b(U_x^\a-U_{x-1}^\a)=U_x^\a U_y^\b+U_{y-1}^\b(U_{x+1}^\a-2U_x^\a),\\
&t_{x,y}=U_x^\a U_y^\b+rU_{x-1}^\a(U_y^\b-U_{y-1}^\b)=U_x^\a U_y^\b+U_{x-1}^\a(U_{y+1}^\b-2U_y^\b),
\end{split} \end{align}
$(U_x^\a)$ and $(U_y^\b)$ were defined in (\ref{eq:Luc}) and $d_w$ is an integral 
and bounded function of $n$ that depends on $w$.
\end{theorem}
\begin{proof} Suppose $w(n)=s_wa(n)+t_wb(n)-d_w(n)$, where $s_w$ and $t_w$ are integers that do not depend on $n$ 
and $d_w$ is an integral and bounded function of $n$. Then, by Lemma \ref{lem:cas-r}, 
we find that 
\begin{align}\begin{split}\label{eq:ab}
wa(n)&=\big((1-r)s_w+t_w\big)a(n)+(s_w+t_w)b(n)-d_{wa}(n),\\
wb(n)&=(s_w+t_w)a(n)+\big(s_w+(r+1)t_w\big)b(n)-d_{wb}(n),
\end{split}
\end{align} where $d_{wa}(n)=(s_w+t_w)d_{a^2}(n)+d_w(a(n))$ and $d_{wb}(n)=d_w(b(n))$. 
Thus we see from (\ref{eq:ab}) that 
$$
E_a\cdot\left(\begin{matrix}s_w\\t_w\end{matrix}\right)=\left(\begin{matrix}s_{wa}\\t_{wa}\end{matrix}\right)
\quad\text{ and }\quad E_b\cdot\left(\begin{matrix}s_w\\t_w\end{matrix}\right)=\left(\begin{matrix}s_{wb}\\t_{wb}
\end{matrix}\right),
$$ where the matrices $E_a$ and $E_b$ were defined in (\ref{eq:Mat}).  

An easy induction on $x+y$ shows that for all words $w$ with $x$ letters $a$ and $y$ letters $b$ and all 
$n\ge1$, $0\le\a^x\b^yn-w(n)\le\b^{x+y}$. 
Indeed, if $\ell=a$ or $b$ and $\ell(n)=\lf\lambda n\rf$, then $0\le\a^x\b^y\ell(n)-w\ell(n)\le\b^{x+y}$, 
by the inductive hypothesis. But $\ell(n)=\lambda n-\{\lambda n\}$, so $0\le\a^x\b^y\lambda n-
w\ell(n)\le\b^{x+y}+\a^x\b^y\{\lambda n\}\le2\b^{x+y}\le\b^{x+y+1}$, as $\b>2>\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}<Ar_y-r_{y+1}<1-6\cdot10^{-5}$. Therefore, $0<Ar_y-r_{y+1}+E_y<1$ and $\lf A\t_y\rf=\s_{y+1}$. 
Since, by definition, $\t_{y+1}=\lf A\t_y\rf$, the inductive step is proved. As mentioned earlier the induction 
is well grounded as we checked that $\t_k=\s_k$, for all $k$, $0\le k\le 199$.  
\end{proof}

\begin{remark}
The four values of $\a^3r_y-r_{y+1}$ in (\ref{eq:4}) are the limit values, rounded to three 
decimals, of the fractional 
parts of $\a^3\t_y$, as $y$ increases. In fact, we found that for $y=20$, $21$, $22$ and $23$, those values are 
already, to three significant digits, equal to $0.064$, $0.938$, $0.779$ and $0.366$, respectively. 
\end{remark}

 With $\xi_y$ and $\ep_y$, respectively, defined in Lemmas \ref{lem:3} and \ref{lem:2}, we obtain the corollary 

\begin{cor} For all $y\ge0$, we find that $\xi_y=\ep_y$, i.e., 
$$
\lf(4-\a^3)\{\a^3 \t_{y+1}\}-\a^{-3}\{\a^3 \t_y\}\rf=\begin{cases}0,&\text{ if }y
\equiv0,1\text{ or }2\pmod 4;\\
-1,&\text{ if }y\equiv3\pmod 4.
\end{cases}
$$
\end{cor}

 And, in return, we also have an expression for the remainder function $e_{(y)}(1)$ of Corollary \ref{cor:N}. 

\begin{cor} For all $y\ge0$, 
$$
e_{(y)}(1)=\sum_{k=0}^{\lf(3y-14)/12\rf}N_{3y-14-12k}.
$$
\end{cor}
\begin{proof} From Corollary \ref{cor:N}, $b^y(1)=a(1)N_{3y-2}+b(1)N_{3y}-N_{3y-3}-e_{(y)}(1)$. But 
$a(1)N_{3y-2}+b(1)N_{3y}-N_{3y-3}=N_{3y-2}+3N_{3y}-N_{3y-3}=N_{3y+1}+N_{3y}+N_{3y-1}=N_{3y+2}+N_{3y}=N_{3y+3}$. 
Comparing with the expression of $\s_y$ in (\ref{eq:1}) yields the corollary since $\s_y=\t_y=b^y(1)$. 
\end{proof}


\section{The $(\a,\a^4)$ case with $\a^4-\a^3-1=0$, $\a>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}

                                                                                


.