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

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.00.0.2570}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{LastRevised=Wednesday, July 26, 2006 15:15:11}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}

\input{tcilatex}
\arraycolsep=2pt

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Complementary Equations
}
\vskip 1cm
{\large
Clark Kimberling\\
Department of Mathematics\\
University of Evansville\\
1800 Lincoln Avenue\\
Evansville, IN 47722\\
USA\\
\href{mailto:ck6@evansville.edu}{\tt ck6@evansville.edu}\\
}
\end{center}

\vskip .2 in

\begin{abstract}
Increasing sequences $a()$ and $b()$ that partition the sequence of positive
integers are called complementary sequences, and equations that explicitly
involve both $a()$ and $b()$ are called complementary equations.  This article
surveys several families of such equations, including $b(n)=a(jn)\pm r,$ $%
b(n)=a(jn)+kn,$ $b(n)=f(a(n)),$ and $b(n)=a(b(n-1))+qn+r.$
\end{abstract}

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{proposition}{Proposition}[section]
%\newtheorem{corollary}{Corollary}[section]
%\newtheorem{lemma}{Lemma}[section] 


% This file was created by EXP Version 5.0.

\section{Introduction}

Under the assumption that sequences $a$ and $b$ partition the sequence $%
N=(1,2,3,\ldots )$ of positive integers, the designation \textit{%
complementary equations}\ applies to equations such as%
\begin{equation*}
b(n)=a(a(n))+1
\end{equation*}%
in much the same way that the designations \textit{functional equations}, 
\textit{differential equations}, and \textit{Diophantine equations}\ apply
elsewhere. \ Indeed, complementary equations can be regarded as a class of
Diophantine equations.

Various pairs of complementary sequences, such as Beatty sequences 
(\cite{AlSh03,St76}), have been widely studied, as evidenced by many
entries in the \textit{Online Encyclopedia of Integer Sequences}\cite{Slo06}.
In particular, complementary sequences have been discussed extensively
by Fraenkel in connection with Beatty sequences, spectra of numbers, and
combinatorial games; see
\cite{Fr69,Fr73A,Fr73B,FrBo73,Fr75,Fr77,Fr82,Fr84,FrKi94,Fr98,FrKr04}.
See also \cite{HoRe01,Mer78}. 
However, in the literature the recognition of a single equation involving
both sequences tends to occur only parenthetically.  The purpose of this
paper is to recognize classes of such equations explicitly.

Throughout, the symbols $a$ and $b$ denote strictly increasing complementary
sequences; i.e., every number in $N$ is $a(n)$ or $b(n)$ for some $n$ in $N,$
and no term of $a$ is also a term of $b.$ \ An \textit{ordinary
complementary equation} (OCE) is defined by the form

\begin{equation}
b(n)=f(\widehat{a}(n),\widehat{b}(n),n),  \tag{1}
\end{equation}%
where%
\begin{eqnarray*}
\widehat{a}(n) &=&(a\left( 1),a\left( 2\right) ,\ldots a(p(n)\right) ),\text{
\ \ }a(p(n))<b(n), \\
\widehat{b}(n) &=&(b\left( 1),b\left( 2\right) ,\ldots b(q(n)\right) ),\text{
\ \ }b(q(n))<b(n).
\end{eqnarray*}%
That is, the $n$th term of the complement, $b,$ of $a,$ is determined as a
function, $f,$ of $n$ and terms of $a$ and $b$ that are previously defined.
\ (It is common and convenient to use time-suggestive descriptors such as 
\textit{previously}, but we note that inductive definitions do not, in fact,
depend on time.)

In some cases, an OCE (1) forces $a(1)=1$, but, as in Example 3 below, this
need not be the case. \ By decreeing an initial value, either $a(1)=1$ or
else $b(1)=1,$ the OCE must then have a unique solution $b,$ or
equivalently, $a$.

An equation involving both a sequence and its complement and which cannot be
represented in the form (1) is a \textit{partial complementary equation}
(PCE). \ Typically, a PCE determines only a part of a solution; which is to
say that there may be many solutions, as in Example 2 just below.\medskip

\textbf{Example 1.} \ The OCE $b(n)=a(a(n))+1$ has unique solution $%
a(n)=\left\lfloor n\tau \right\rfloor ,$ where $\tau =(1+\sqrt{5})/2.$ \ The
complement is given by $b(n)=\left\lfloor n\tau \right\rfloor +n,$ which is
also the unique solution of the OCE $b(n)=a(n)+n,$ an equation discussed
more generally in section 4.\bigskip

\textbf{Example 2.} \ Every solution of the equation%
\begin{equation}
b(n)=b(n-1)a(n+1)  \tag{2}
\end{equation}%
has $a(1)=1.$ \ However, the number $2$ could be either $a(2)$ or $b(1),$ so
that (2) is a PCE.\bigskip

\textbf{Example 3.} \ The OCE%
\begin{equation}
b(n)=a(n-1)+b(n-1)  \tag{3}
\end{equation}%
for $n\geq 2,$ with initial condition $b(1)=1,$ has as solution the
Hofstadter sequence A005228:%
\begin{equation*}
b=(1,3,7,12,18,26,35,45,\ldots )
\end{equation*}%
with complement $a=$ A030124.\bigskip

\textbf{Example 4.} \ Bode, Harborth, and Kimberling \cite{BoHaKi} discuss
the equation%
\begin{equation*}
b(n)=a(n-1)+a(n-2)
\end{equation*}%
with prescribed initial terms $a(1)$ and $a(2).$\bigskip 

\textbf{Example 5.} \ Another PCE is%
\begin{equation*}
a(b(n))-b(a(n))=1.
\end{equation*}%
Solutions include $b(n)=2n$ and $b(n)=\left\lfloor n\tau \right\rfloor .$%
\bigskip

In the sequel, we shall solve four types of OCEs: $\ b(n)=a(jn)\pm r,$ $%
b(n)=a(jn)+kn,$ $b(n)=f(a(n)),$ and the PCE $b(n)=a(b(n-1))+qn+r.$

\section{The step sequence of an OCE}

Suppose an OCE (1) is given. \ Because $a$ and $b$ are complementary, when
jointly ranked they form the sequence $N.$ \ The joint ranking has the form%
\begin{eqnarray*}
&&a(1),\ldots ,a(u_{1}),b\left( 1\right) ,\ldots ,b(v_{1}), \\
&&a(u_{1}+1),\ldots ,a(u_{2}),b\left( v_{1}+1\right) ,\ldots ,b(v_{2}), \\
&&a(u_{2}+1),\ldots ,a(u_{3}),b\left( v_{2}+1\right) ,\ldots
,b(v_{3}),\ldots ,
\end{eqnarray*}%
where the numbers $u_{i}$ and $v_{i}$ are nonnegative integers. \ Note that%
\begin{eqnarray*}
1 &=&a(1)<b(1), \text{ if }u_{1}>0; \\
1 &=&b(1)<a(1), \text{ if }u_{1}=0.
\end{eqnarray*}%
Each $n\geq v_{1}+1$ has a unique representation%
\begin{equation*}
n=v_{i-1}+r,\text{ \ where }1\leq r\leq v_{i}-v_{i-1},
\end{equation*}%
where $i-1=\max \{m:n\geq v_{m}\}.$

Define the \textit{step sequence} $s=(s(2),s(3),\ldots )$ by%
\begin{equation*}
s(n)=\left\{ 
\begin{array}{cc}
u_{i}-u_{i-1}+1, & \text{if }r=1; \\ 
1, & \text{if }r>1.%
\end{array}%
\right.
\end{equation*}%
Then $b$ is clearly given by%
\begin{equation}
b(n)=\left\{ 
\begin{array}{cc}
u_{1}+1, & \text{if }n=1; \\ 
b(n-1)+s(n), & \text{if }n\geq 2.%
\end{array}%
\right.  \tag{3}
\end{equation}%
In many cases, we shall see, every $b(n)$ is immediately preceded and
followed by a term of $a,$ so that $v_{i}=i$ for all $i\geq 1,$ and%
\begin{equation*}
s(n)=u_{n}-u_{n-1}+1
\end{equation*}%
for $n\geq 2.$ \ \ In the sequel, we shall concentrate on sequences $b$ of
this kind.

\section{The equations $b(n)=a(jn)\pm r$}

Consider the equation%
\begin{equation}
b(n)=a(jn)+r,  \tag{4}
\end{equation}%
where $1\leq r\leq j.$ \ In order to solve this OCE, we find inductively that%
\begin{equation*}
a(n)=\left\{ 
\begin{array}{ll}
n, & \text{if }1\leq n\,<j+r; \\ 
n+1, & \text{if }j+r\leq n<2j+r; \\ 
n+2, & \text{if }2j+r\leq n<3j+r; \\ 
\vdots & \vdots \\ 
n+q, & \text{if }qj+r\leq n<(q+1)j+r. \\ 
\vdots & \vdots%
\end{array}%
\right.
\end{equation*}%
For example, we move from $a(n)=n$ to $a(n)=n+1$ when $n=j+r$ in order to
make room for $b(1)=j+r.$ \ The inequality for which $a(n)=n+q$ is
equivalent to%
\begin{equation*}
\frac{n-j-r}{j}<q\leq \frac{n-r}{j},
\end{equation*}%
so that $q=\left\lfloor \dfrac{n-r}{j}\right\rfloor $ and $%
a(n)=n+\left\lfloor \dfrac{n-r}{j}\right\rfloor .$ \ Thus, for $n=1,$ we
have $a(jn)=j.$ \ Replacing $n$ by $jn$ gives%
\begin{equation*}
a(jn)=jn+\left\lfloor \dfrac{jn-r}{j}\right\rfloor =jn+n-1.
\end{equation*}%
To conclude, we have%
\begin{equation*}
a(jn)+r=jn+n-1+r
\end{equation*}%
for all $n\geq 1,$ so that the solution of (4) is given by%
\begin{equation*}
b(n)=(j+1)n+r-1.
\end{equation*}

The same method applies to the OCE%
\begin{equation*}
b(n)=a(jn)-r,
\end{equation*}%
where $1\leq r\leq j-1,$ giving the solution%
\begin{equation*}
b(n)=(j+1)n-r.
\end{equation*}

\section{The equation $b(n)=a(jn)+kn$}

Suppose $r$ and $s$ are positive irrational numbers satisfying Beatty's
equation \cite{Be26}:%
\begin{equation}
\frac{1}{r}+\frac{1}{s}=1.  \tag{5}
\end{equation}%
Then the sequences $a$ and $b$ given by $a(n)=\left\lfloor nr\right\rfloor $
and $b(n)=\left\lfloor ns\right\rfloor $ are a pair of complementary
sequences known as Beatty sequences (\cite{St76}, \cite{Slo06}, \cite{AlSh03}%
).

The OCE%
\begin{equation}
b(n)=a(n)+kn,  \tag{6}
\end{equation}%
where $k$ is a positive integer, occurs in Stolarsky \cite{St76} where it is
solved by means of shift operators, related to morphisms and continued
fractions (\cite{AlSh03}, \cite{St76}) and also closely related to the step
sequences of section 2. \ Sequences satisfying (6) were also studied by
Fraenkel \cite{Fr82}. \ The solution of (6) is given by the Beatty sequences%
\begin{equation}
a(n)=\left\lfloor rn\right\rfloor ,\text{ \ \ \ }b(n)=\left\lfloor
sn\right\rfloor ,  \tag{7}
\end{equation}%
where%
\begin{equation}
r=1+\frac{\sqrt{k^{2}+4}-k}{2}\text{ \ \ \ and \ \ \ }s=1+\frac{\sqrt{k^{2}+4%
}+k}{2}\text{.}  \tag{8}
\end{equation}

We wish to generalize Stolarsky's result to certain equations of the form%
\begin{equation}
b(n)=a(jn)+kn;  \tag{9}
\end{equation}%
specifically, we seek positive integers $j$ and $k$ for which the solution
is a pair of Beatty sequences. \ Write%
\begin{equation}
r=\frac{m+\sqrt{p}}{j},  \tag{10}
\end{equation}%
where $m$ and $p$ are rational numbers and $\sqrt{p}$ is irrational. \
Equation (5) then leads to%
\begin{equation}
s=\frac{j\sqrt{p}+p+jm-m^{2}}{p-(m-j)^{2}}.  \tag{11}
\end{equation}%
The desired equations%
\begin{equation*}
\left\lfloor sn\right\rfloor =\left\lfloor jrn\right\rfloor +kn
\end{equation*}%
are equivalent to%
\begin{equation}
sn-\delta _{n}=jrn-\varepsilon _{n}+kn,  \tag{12}
\end{equation}%
where the fractional parts $\delta _{n}$ and $\varepsilon _{n}$ satisfy%
\begin{equation*}
0<\delta _{n}=sn-\left\lfloor sn\right\rfloor <1\text{ \ \ \ and \ \ \ }%
0<\varepsilon _{n}=jrn-\left\lfloor jrn\right\rfloor <1
\end{equation*}%
for all $n.$ \ Dividing both sides of (12) by $n$ and taking the limit as $%
n\rightarrow \infty $ gives%
\begin{equation*}
s=jr+k.
\end{equation*}%
Thus the coefficient $j/(p-(m-j)^{2})$ of $\sqrt{p}$ on the right side of
(11) must equal the coefficient of $\sqrt{p}$ in $jr,$ which, by (10)\ is $1$%
, so that%
\begin{equation*}
j=p-(m-j)^{2},
\end{equation*}%
which implies%
\begin{equation*}
j=\frac{2m-1\pm \sqrt{4(p-m)+1}}{2}.
\end{equation*}%
In order that $j$ be an integer, $\sqrt{4(p-m)+1}$ must be an odd integer:%
\begin{equation*}
\sqrt{4(p-m)+1}=2q-1,
\end{equation*}%
so that%
\begin{equation*}
p=q^{2}-q+m.
\end{equation*}%
Substituting into (11) and simplifying gives%
\begin{equation*}
s=q+\sqrt{p}.
\end{equation*}

Thus, for given $m$ and $q$ for which $q^{2}-q+m$ is a nonsquare (below, we
shall show that it is always a nonsquare), we put%
\begin{eqnarray*}
j &=&m+q-1, \\
k &=&q-m, \\
r &=&\frac{m+\sqrt{q^{2}-q+m}}{j}, \\
s &=&q+\sqrt{q^{2}-q+m},
\end{eqnarray*}%
and have the solution (7) of the equation (9).

Instead of starting with $m$ and $q$, we can start with $j$ and $k$ to
produce%
\begin{eqnarray*}
q &=&\frac{j+k+1}{2}, \\
m &=&\frac{j-k+1}{2}, \\
\sqrt{p} &=&\frac{\sqrt{(j+k+1)^{2}-4k}}{2}.
\end{eqnarray*}%
It is this latter representation of $p$ that we now use to show that $\sqrt{p%
}$ is irrational for all positive integers $j$ and $k.$ \ It suffices to
show that $(j+k+1)^{2}-4k$ is a nonsquare. \ Let $M=j+k+1,$ and note that
for $k=0$ and $k=M-1$ we have $M^{2}-4k$ taking the values $M^{2}$ and $%
(M-2)^{2},$ respectively. \ There is only one square between those numbers,
namely $(M-1)^{2}.$ \ Therefore, if $M^{2}-4k$ is a square for some $k$
satisfing $1\leq k\leq M-2,$ then that value of $k$ must satisfy%
\begin{equation}
M^{2}-4k=(M-1)^{2}.  \tag{13}
\end{equation}%
However, (13) implies $4k=2M-1,$ a number that is both even and odd. \ As
there is no such number, $(j+k+1)^{2}-4k$ is not a square for any positive
integers $j$ and $k.$

Examples using Beatty-pair solutions of (9) are now easy to write out, as
suggested by a table:%
\begin{equation*}
\begin{tabular}{||c||c|c|c|c|c|c|c|c|c|c|}
\hline
$j$ & $1$ & $1$ & $2$ & $1$ & $2$ & $3$ & $1$ & $2$ & $3$ & $4$ \\ \hline
$k$ & $1$ & $2$ & $1$ & $3$ & $2$ & $1$ & $4$ & $3$ & $2$ & $1$ \\ \hline
$p$ & $5/4$ & $2$ & $3$ & $13/4$ & $17/4$ & $21/4$ & $5$ & $6$ & $2$ & $8$
\\ \hline
\end{tabular}%
\end{equation*}

In connection with heap games, Fraenkel \cite{Fr98} considers the extension
of (6) to the OCE%
\begin{equation*}
b(n)=ja(n)+kn,
\end{equation*}%
where $j$ and $k$ are positive integers. \ For small values of $j$ and $k,$
solutions $a$ and $b$ include the pairs (A045671, A045672), (A045681,
A045682), and (A045749, A045750), and (A045774, A045775).\bigskip 

\textbf{Example 6.} \ Taking $j=1$ and leaving $k$ arbitrary in (9) gives
(8).\bigskip

\textbf{Example 7.} \ Taking $j=k$ gives the OCE $b(n)=a(jn)+jn$ with
solution (7) using%
\begin{equation*}
r=1+\frac{\sqrt{4j^{2}+1}}{2j}\text{ \ \ \ and \ \ \ }r=\frac{2j+1+\sqrt{%
4j^{2}+1}}{2}.
\end{equation*}

\section{The OCE of a dispersion, $b(n)=f(a(n))$}

In this section, rather than starting with an OCE, we start with a certain
kind of array consisting of all the positive integers, and we derive an OCE
from it. \ Suppose $f$ and $g$ are strictly increasing complementary
sequences and that $g(1)=1.$ \ The dispersion, $D(f)=\{d(i,j)\}_{i,j\geq 1}$
of $f$ is defined \cite{Ki93} as the array having first column given by $%
d(i,1)=g(i)$ and subsequent columns given inductively by%
\begin{equation*}
d(i,j)=f(d(i,j-1)).
\end{equation*}%
We shall see next that the general dispersion $D(f)$ is naturally associated
with the OCE%
\begin{equation}
b(n)=f(a(n)),  \tag{14}
\end{equation}%
and that the dispersion provides a solution to this equation.

Note first that no member of column 1 of $D(f)$ is an image of $f,$ so that
the terms of column 1 belong to the sequence $a.$ \ Next, every member $m$
of column 2 is of the form $f(j)$ where $j$ is in $a,$ so that $m$ is in $b.$
\ Consequently, each $m^{\prime }$ in column 3 satisfies $m^{\prime }=f(m)$
for some $m$ in sequence $b.$ \ Therefore, every term of column 3 is in $a;$
otherwise, if $m^{\prime }$ were in $b,$ then $m$ would be in $a,$ a
contradiction. \ This shows that every term of column 3 is in $a.$

Continuing inductively, we conclude that the terms of the odd numbered
columns of $D(f)$ are the terms of $a,$ so that $a$ is the ordered union of
all the odd numbered columns. \ Likewise, $b$ is the ordered union of all
the even numbered columns. \ In $D(f),$ every positive integer occurs
exactly once (see \cite{Ki93} for a proof), so that every positive integer
is in $a$ or $b,$ which confirms that these are complementary
sequences.\bigskip 

\textbf{Example 8.} \ Let $f(n)=2n$ and $g(n)=2n-1.$ \ The associated OCE is 
$b(n)=2a(n).$ \ The northwest corner of the dispersion $D(f)$ is%
\begin{equation*}
\begin{tabular}{ccccccc}
$1$ & $2$ & $4$ & $8$ & $16$ & $32$ & $\cdots $ \\ 
$3$ & $6$ & $12$ & $24$ & $48$ & $96$ &  \\ 
$5$ & $10$ & $20$ & $40$ & $80$ & $160$ &  \\ 
$7$ & $14$ & $28$ & $56$ & $112$ & $224$ &  \\ 
$\vdots $ &  &  &  &  &  & $\ddots $%
\end{tabular}%
\end{equation*}%
so that $a$ is the ordered sequence of numbers%
\begin{equation*}
(2i+1)2^{2j},\text{ \ \ \ \ }i\geq 0,\text{ }j\geq 0,
\end{equation*}%
this being A003159, with complement $b=$ A036554, described as the numbers
whose binary representation ends in an odd number of zeros.\bigskip

As suggested by Example 8, the OCE%
\begin{equation*}
b(n)=ka(n),
\end{equation*}%
for $k\geq 2,$ has solution $a$ the ordered union of the numbers%
\begin{equation*}
(ki+r)k^{2j},\text{ \ \ }1\leq r\leq k-1,\text{ }i\geq 0,\text{ }j\geq 0,
\end{equation*}%
with $b$ the ordered union of the numbers $(ki+r)k^{2j+1}.$\bigskip

\textbf{Example 9.} \ Let $f(n)=2n+1$ for $n\geq 1,$ let $g(1)=1$ \ and $%
g(n)=2n$ for $n\geq 2.$ \ The associated OCE is $b(n)=2a(n)+1.$ \ The
northwest corner of the dispersion $D(f)$ is%
\begin{equation*}
\begin{tabular}{ccccccc}
$1$ & $3$ & $7$ & $15$ & $31$ & $63$ & $\cdots $ \\ 
$2$ & $5$ & $11$ & $23$ & $47$ & $95$ &  \\ 
$4$ & $9$ & $19$ & $39$ & $79$ & $159$ &  \\ 
$6$ & $13$ & $27$ & $55$ & $111$ & $223$ &  \\ 
$\vdots $ &  &  &  &  &  & $\ddots $%
\end{tabular}%
\end{equation*}%
so that $a$ is the ordered sequence of numbers%
\begin{equation*}
2^{2j+1}-1\text{ \ \ and \ \ }(2i+1)2^{2j}-1,\text{ \ \ \ \ }i\geq 1,\text{ }%
j\geq 0,
\end{equation*}%
and $b$ is the ordered sequence of numbers%
\begin{equation*}
2^{2j+2}-1\text{ \ \ and \ \ }(2i+1)2^{2j+1}-1,\text{ \ \ \ \ }i\geq 1,\text{
}j\geq 0.
\end{equation*}

It is natural to ask what OCEs are associated with well-known dispersions. \
In the next examples, we answer this question for the Wythoff array, the
Wythoff difference array, the Stolarsky array, and the inverse Wythoff
array.\bigskip

\textbf{Example 10.} \ Column 1 of the Wythoff array $W=\{w(i,j)\}$ is given 
\cite{SlClass} by%
\begin{equation*}
w(i,1)=\left\lfloor \left\lfloor i\tau \right\rfloor \tau \right\rfloor ,
\end{equation*}%
and the ordered complement of column 1, written as an increasing sequence,
is given by%
\begin{equation*}
f(n)=\left\lfloor (n+1)\tau \right\rfloor -1.
\end{equation*}%
The associated OCE is therefore%
\begin{equation*}
b(n)=\left\lfloor (a(n)+1)\tau \right\rfloor -1.
\end{equation*}%
Its solution $a$ is the ordered union of odd numbered columns of $W,$ so
that $a$ is simply the lower Wythoff sequence, A000201. \ The complement, $b,
$ is the rest of $W,$ which as an increasing sequence is the upper Wythoff
sequence, A001950. \ Initial terms are given by%
\begin{equation*}
a=(1,3,4,6,8,9,11,12,\ldots ),\text{ \ \ \ \ }b=(2,5,7,10,13,15,18,20,\ldots
).
\end{equation*}%
Fraenkel and Kimberling \cite{FrKi94} discuss Example 10 in greater
detail.\bigskip 

\textbf{Example 11.} \ The Wythoff difference array, $D=\{d(i,j)\},$ given
by A080164, is the dispersion of the upper Wythoff sequence, which, when
written in increasing order, is given by%
\begin{equation*}
f(n)=\left\lfloor (\tau +1)n\right\rfloor .
\end{equation*}%
The associated OCE is therefore%
\begin{equation*}
b(n)=\left\lfloor (\tau +1)a(n)\right\rfloor .
\end{equation*}%
Its solution from columns of $D$ is given by initial terms as follows:%
\begin{equation*}
a=(1,3,4,5,6,8,9,11,12,\ldots ),\text{ \ \ \ \ }b=(2,7,10,13,15,20,\ldots ).
\end{equation*}

\textbf{Example 12.} \ The inverse Wythoff array, $X=\{x(i,j)\},$ has first
column given by%
\begin{equation*}
x(i,1)=s(n)=\left\{ 
\begin{tabular}{ll}
$1$, & if $i=1;$ \\ 
$\left\lfloor i\tau \right\rfloor -1$, & if $i>1$%
\end{tabular}%
\right. 
\end{equation*}%
and ordered complement of column 1 given by%
\begin{equation*}
f(n)=\left\lfloor (n+1)\tau \right\rfloor +n.
\end{equation*}%
(The definition of the inverse of a dispersion is given in \cite{Ki93}). \
The associated OCE is%
\begin{equation*}
b(n)=\left\lfloor (a(n)+1)\tau \right\rfloor +a(n).
\end{equation*}%
Its solution from columns of $X$ is given by initial terms as follows:%
\begin{equation*}
a=(1,2,3,5,7,8,10,11,12,13,\ldots ),\text{ \ \ \ \ }%
b=(4,6,9,14,19,22,27,30,33,35,\ldots ).
\end{equation*}

\section{The form $b(n)=a(b(n-1))+qn+r$}

We begin with the OCE%
\begin{equation}
b(n)=a(b(n-1))+1.  \tag{15}
\end{equation}%
If $a(1)=1,$ the solution is%
\begin{equation*}
b(n)=\frac{n^{2}+n}{2}+1,
\end{equation*}%
whereas if $b(1)=1,$ the solution is%
\begin{equation}
b(n)=\frac{n^{2}+n}{2}.  \tag{16}
\end{equation}%
We shall prove the latter, starting with a lemma closely related to
(3).\bigskip

\textbf{Lemma.} \ \textit{Suppose }$a$\textit{\ and }$b$\textit{\ satisfy
(15) and the initial condition }$b(1)=1$\textit{. \ Then}%
\begin{equation*}
a(m+1)=\left\{ 
\begin{tabular}{ll}
$a(m)+2$, & if $m=b(k)$ for some $k;$ \\ 
$a(m)+1$, & otherwise.%
\end{tabular}%
\right. 
\end{equation*}%
\medskip \textit{Proof.} \ Because $b(1)=1,$ we have $a(1)\geq 2,$ so that $%
b(2)\geq 3$, by (15). \ As a first step in an induction proof, we therefore
have $b(2)-b(1)\geq 2.$ \ Assume for arbitrary $k\geq 2$ that $%
b(k)-b(k-1)\geq 2.$ \ Then, using (15),%
\begin{eqnarray*}
b(k+1)-b(k) &=&a(b(k))-a(b(k-1)) \\
&\geq &b(k)-b(k-1)\geq 2.
\end{eqnarray*}%
Thus, for every $k\geq 2,$ the numbers $b(k)-1$ and $b(k)+1$ are terms of
the sequence $a.$ \ As every positive integer is in exactly one of the
sequences $a$ and $b,$ we have $a\left( m+1\right) =a\left( m\right) +2$ if $%
a(m)$ is in $b$ and $a\left( m+1\right) =a\left( m\right) +1$ otherwise. \ \
\ \ \ \ \ \ \ $\blacksquare $

Now, we shall prove that (15), with the intial condition $b(1)=1,$ implies
(16). \ By (15),%
\begin{equation*}
b(2)=a(b(1))+1=a(1)+1\geq 3,
\end{equation*}
so that $2$ cannot be $b(2)$ and must therefore be $a(1).$ \ Then $%
b(2)=a(b(1))+1=a(1)+1=3.$ \ As a two-part induction hypothesis, assume for
arbitrary $k\geq 1$ these two equations:%
\begin{eqnarray}
b(k) &=&\frac{k(k+1)}{2},  \TCItag{17} \\
a(b(k)) &=&b(k)+k.  \TCItag{18}
\end{eqnarray}%
Then%
\begin{eqnarray*}
b(k+1) &=&a(b(k))+1 \\
&=&b(k)+k+1\text{ by (18)} \\
&=&\frac{(k+1)(k+2)}{2}\text{ by (17)},
\end{eqnarray*}%
and it remains to be proved that%
\begin{equation}
a(b(k+1))=b(k+1)+k+1.  \tag{19}
\end{equation}%
We have%
\begin{eqnarray*}
a(b(k)+1) &=&a(b(k))+2\text{ by the lemma} \\
&=&b(k)+k+2\text{ by (18).}
\end{eqnarray*}%
Also by the lemma,%
\begin{eqnarray}
a(b(k)+2) &=&a(b(k)+1)+1  \notag \\
a(b(k)+3) &=&a(b(k)+2)+1=a(b(k)+1)+2  \notag \\
&&\vdots  \notag \\
a(b(k)+k) &=&a(b(k)+k-1)+1=a(b(k)+1)+k-1  \notag \\
a(b(k)+k+1) &=&a(b(k)+k)+1=a(b(k)+1)+k.  \TCItag{20}
\end{eqnarray}%
Now,%
\begin{eqnarray*}
a(b(k)+1) &=&a(b(k))+2\text{ by the lemma} \\
&=&b(k+1)+1\text{ by (15),}
\end{eqnarray*}%
so that%
\begin{equation*}
a(b(k)+1)+k=b(k+1)+k+1,
\end{equation*}%
which by (20) implies%
\begin{equation*}
a(b(k)+k+1)=b(k+1)+k+1,
\end{equation*}%
and the desired (19) now follows from the fact, already proved, that $%
b(k)+k+1=b(k+1).$

(Note that (18) is a PCE; one solution is given by (17); another, by $%
b(n)=3n-2.$)\bigskip

Similar inductive proofs can be given for various OCEs, including the
following:%
\begin{eqnarray*}
\text{Equation}\text{: \ } &&b(n)=a(b(n-1))+r,\text{ where }r\geq 1 \\
\text{Initial value}\text{: \ } &&b(1)=1 \\
\text{Solution}\text{: } &&b(n)=(r-1)(n-1)+\frac{n(n+1)}{2}.
\end{eqnarray*}%
\begin{eqnarray*}
\text{Equation} &\text{:}&\text{ \ }b(n)=a(b(n-1))+r,\text{ where }r\geq 1 \\
\text{Initial value} &\text{:}&\text{ \ }a(1)=1 \\
\text{Solution} &\text{:}&\text{ \ }b(n)=rn+\frac{n^{2}-n+2}{2}.
\end{eqnarray*}%
\begin{eqnarray*}
\text{Equation} &\text{:}&\text{ \ }b(n)=a(b(n-1))+qn,\text{ where }q\geq 1
\\
\text{Initial value} &\text{:}&\text{ \ }b(1)=1 \\
\text{Solution} &\text{:}&\text{ }b(n)=\frac{q(n^{2}+n+2)+n^{2}-n+2}{2}.
\end{eqnarray*}%
\begin{eqnarray*}
\text{Equation} &\text{:}&\text{ \ }b(n)=a(b(n-1))+qn,\text{ where }q\geq 1
\\
\text{Initial value} &\text{:}&\text{ \ }a(1)=1 \\
\text{Solution} &\text{:}&\text{ }b(n)=\frac{q(n^{2}+n)+n^{2}-n+2}{2}.
\end{eqnarray*}%
\begin{eqnarray*}
\text{Equation} &\text{:}&\text{ \ }b(n)=a(b(n-1))+qn+r,\text{ where }q\geq
1,\text{ }r\geq 1 \\
\text{Initial value} &\text{:}&\text{ \ }b(1)=1 \\
\text{Solution} &\text{:}&\text{ \ }b(n)=\frac{q(n^{2}+n+2)+n^{2}+(r+1)n-2r+2%
}{2}.
\end{eqnarray*}%
\begin{eqnarray*}
\text{Equation} &\text{:}&\text{ \ }b(n)=a(b(n-1))+qn+r,\text{ where }q\geq
1,\text{ }r\geq 1 \\
\text{Initial value} &\text{:}&\text{ \ }a(1)=1 \\
\text{Solution} &\text{:}&\text{ \ }b(n)=\frac{q(n^{2}+n)+n^{2}+(2r-1)n+2}{2}%
.
\end{eqnarray*}%
To summarize, if $q\geq 0$ and $r\geq 0$ and $q$ and $r$ are not both $0,$
and if an initial value, either $a(1)=1$ or $b(1)=1$ is assumed, then the
equation%
\begin{equation*}
b(n)=a(b(n-1))+qn+r
\end{equation*}%
holds for a unique second-degree polynomial in $n.$ \ Several special cases
are tabulated here, along with three examples in which $r<0.\medskip $

\begin{center}
$%
\begin{tabular}{|l|c|c|c|}
\hline
${\small b(n)-a(b(n-1)=}$ & \textbf{Initial} & \textbf{Solution} & \textbf{%
Name} \\ \hline
\multicolumn{1}{|c|}{$1$} & \multicolumn{1}{|l|}{${\small a(1)=1}$} & $%
(n^{2}+n+2)/2$ & \multicolumn{1}{|l|}{\small A000124, Hogben's c. p. nos.}
\\ \hline
\multicolumn{1}{|c|}{$2$} & \multicolumn{1}{|l|}{${\small a(1)=1}$} & $%
(n^{2}+3n+2)/2$ & \multicolumn{1}{|l|}{\small A000217, triangle numbers} \\ 
\hline
\multicolumn{1}{|c|}{$n$} & \multicolumn{1}{|l|}{${\small b(1)=1}$} & $%
{\small n}^{2}$ & \multicolumn{1}{|l|}{\small A000290, square numbers} \\ 
\hline
\multicolumn{1}{|c|}{$2n+2$} & \multicolumn{1}{|l|}{${\small a(1)=1}$} & $%
(3n^{2}+5n+2)/2$ & \multicolumn{1}{|l|}{\small A000326, pentagonal numbers}
\\ \hline
\multicolumn{1}{|c|}{$3n+2$} & \multicolumn{1}{|l|}{${\small a(1)=1}$} & $%
{\small 2n}^{2}{\small +3n+1}$ & \multicolumn{1}{|l|}{\small A000384,
hexagonal numbers} \\ \hline
\multicolumn{1}{|c|}{$2n+1$} & \multicolumn{1}{|l|}{${\small a(1)=1}$} & $%
{\small 2n}^{2}{\small +2n+1}$ & \multicolumn{1}{|l|}{\small A001844,
centered square nos.} \\ \hline
\multicolumn{1}{|c|}{$n+1$} & \multicolumn{1}{|l|}{${\small b(1)=1}$} & $%
{\small n}^{2}{\small +n-1}$ & \multicolumn{1}{|l|}{\small A028387} \\ \hline
\multicolumn{1}{|c|}{$n-1$} & \multicolumn{1}{|l|}{${\small b(1)=1}$} & $%
{\small n}^{2}{\small -n+1}$ & \multicolumn{1}{|l|}{\small A002061, central
polygonal nos.} \\ \hline
\multicolumn{1}{|c|}{$3n-1$} & \multicolumn{1}{|l|}{${\small a(1)=1}$} & $%
{\small 2n}^{2}{\small +1}$ & \multicolumn{1}{|l|}{\small A058331} \\ \hline
\multicolumn{1}{|c|}{$3n-2$} & \multicolumn{1}{|l|}{${\small b(1)=1}$} & $%
{\small 2n}^{2}{\small -1}$ & \multicolumn{1}{|l|}{\small A000384, hexagonal
numbers} \\ \hline
\end{tabular}%
$\bigskip
\end{center}

\begin{thebibliography}{99}
\bibitem{AlSh03} J.-P. Allouche and J. Shallit, \textit{Automatic Sequences}%
, Cambridge University Press, 2003.

\bibitem{Be26} S. Beatty, Problem 3173, {\it Amer. Math. Monthly}
{\bf 33} (1926) 159;
{\bf 34} (1927) 159.

\bibitem{BoHaKi} J.-P. Bode, H. Harborth, and C. Kimberling, Complementary
Fibonacci sequences,\ forthcoming.

\bibitem{Fr69} A. S. Fraenkel, The bracket function and complementary sets
of integers, \textit{Canadian J. Math.} {\bf 21} (1969), 6--27.

\bibitem{Fr73A} A. S. Fraenkel, Complementing and exactly covering
sequences, \textit{J. Combinatorial Theory Ser. A } {\bf 14} (1973), 8--20.

\bibitem{Fr73B} A. S. Fraenkel, A Characterization of exactly covering
congruences, \textit{Discrete Math.} {\bf 4} (1973), 359--366.

\bibitem{FrBo73} A. S. Fraenkel and I. Borosh, A generalization of Wythoff's
game, \textit{J. Combinatorial Theory Ser. A} {\bf 5} (1973), 175--191.

\bibitem{Fr75} A. S. Fraenkel, Further characterizations and properties of
exactly covering congruences, \textit{Discrete Math.} {\bf 12} (1975), 93--100.

\bibitem{Fr77} A. S. Fraenkel, Complementary systems of integers, \textit{%
Amer. Math. Monthly } {\bf 84} (1977), 114--115.

\bibitem{Fr82} A. S. Fraenkel, How to beat your Wythoff games' opponents on
three fronts, \textit{Amer. Math. Monthly } {\bf 89} (1982), 353--361.

\bibitem{Fr84} A. S. Fraenkel, Wythoff games, continued fractions, cedar
trees and Fibonacci searches, \textit{Theoret. Comput. Sci. } {\bf 29} (1984),
49--73.

\bibitem{FrKi94} A. S. Fraenkel and C. Kimberling, Generalized Wythoff
arrays, shuffles and interspersions, \textit{Discrete Math. } {\bf 126} (1994),
137--149.

\bibitem{Fr98} A. S. Fraenkel, Heap games, numeration systems and sequences, 
\textit{Ann. Combinatorics} {\bf 2} (1998), 197--210.

\bibitem{FrKr04} A. S. Fraenkel and D. Krieger, The structure of
complementary sets of integers: \ a $3$-shift theorem, \textit{Int. J. Pure
Appl. Math. } {\bf 10} (2004), 1--49.

\bibitem{Guy94} R. K. Guy, Max and Mex Sequences, \textit{Unsolved Problems
in Number Theory,} 2nd ed., Springer-Verlag, New York (1994), 227--228,
Problem 27.

\bibitem{HoRe01} A. Holshouser and H. Reiter, A generalization of Beatty's
theorem, \textit{Southwest J. Pure Appl. Math. } (2001), 24--29.

\bibitem{Ki93} C. Kimberling, Interspersions and dispersions,\ \textit{Proc.
Amer. Math. Soc.} {\bf 117} (1993), 313--321.

\bibitem{Mer78} A. McD. Mercer, Generalized Beatty sequences, {\it Internat. J.
Math. Sci.} {\bf 1} (1978), 525--528.

\bibitem{Slo06} N. J. A. Sloane,
\href{http://www.research.att.com/~njas/sequences}{\textit{The On-Line 
Encyclopedia of Integer Sequences}}.

\bibitem{SlClass} N. J. A. Sloane, \href{http://www.research.att.com/~njas/sequences/classic.html}{Classic Sequences In \textit{The On-Line
Encyclopedia of Integer Sequences}: \ (Part 1:) \ The Wythoff Array and The
Para-Fibonacci Sequence}.

\bibitem{St76} K. B. Stolarsky, Beatty sequences, continued fractions, and
certain shift operators, \textit{Canadian Math. Bull.} {\bf 19} (1976)
473--482.\bigskip 
\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B37.

\noindent \emph{Keywords: } 
Beatty sequence, complementary equation, complementary
sequences, dispersion, inverse, polygonal numbers, Stolarsky array, Wythoff
array, Wythoff difference array, Wythoff sequences.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000124}
\seqnum{A000201}
\seqnum{A000217}
\seqnum{A000290}
\seqnum{A000326}
\seqnum{A000384}
\seqnum{A001844}
\seqnum{A001950}
\seqnum{A002061}
\seqnum{A003159}
\seqnum{A005228}
\seqnum{A028387}
\seqnum{A036554}
\seqnum{A045671}
\seqnum{A045672}
\seqnum{A045681}
\seqnum{A045749}
\seqnum{A045750}
\seqnum{A045774}
\seqnum{A045775}
\seqnum{A058331} and
\seqnum{A080164}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  May 16 2006;
Revised versions received July 26 2006; October 11 2006.
Published in {\it Journal of Integer Sequences}, December 30 2006.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}