\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
%\input{tcilatex}

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

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf Complementary Equations and \\
\vskip .15in
Wythoff Sequences
}
\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}
The lower Wythoff sequence $a=(a(n))$ and upper Wythoff sequence $b=(b(n))$
are solutions of many complementary equations $f(a,b)=0$.  Typically, 
$f(a,b)$ involves composites such as $a(a(n))$ and $a(b(n))$, and each such
sequence is treated as a binary word (e.g., $aa$ and $ab$).  Conversely,
each word represents a sequence and, as such, is a linear combination of 
$a,b,$ and $1,$ in which the coefficients of $a$ and $b$ are consecutive
Fibonacci numbers.  For example, $baba=3a+5b-6$.
\end{abstract}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{examp}[theorem]{\small Example}
\newenvironment{example}{\begin{examp}\normalfont\small\quad}{\normalsize\end{examp}}



%\usepackage{amssymb}
%\usepackage{amsmath}


%\arraycolsep=2pt

%\begin{document}


\section{Introduction}

An example of a complementary equation is%
\begin{equation}
a(a(n))=b(n)-1,  \label{t1}
\end{equation}%
where it is given that the sequences $a$ and $b$ are complementary---that
is, they are strictly increasing sequences of positive integers, and every
positive integer is in exactly one of the sequences. \ Given the initial
value $a(1)=1,$ equation (\ref{t1}) has as a unique solution the lower Wythoff
sequence, $a(n)=\left\lfloor \tau n\right\rfloor ,$ or equivalently, the
upper Wythoff sequence, $b(n)=\left\lfloor \tau ^{2}n\right\rfloor ,$ where $%
\tau =(1+\sqrt{5})/2.$

Equation (\ref{t1}) can be abbreviated as $aa=b-1.$ \ Here, the concatenation $aa$
(which will also be written as $a^{2}$) represents composition, and the
reduced notation provides a convenient way to express complementary
equations, such as $ab=a+b,$ $ba=a+b-1,$ and $b^{2}=a+2b.$ \ The Wythoff
sequences are solutions of these equations. \ The main purpose of this
article is to show that \textit{every} word of the sort suggested by $a^{2},$
$ab,$ $ba$, and $b^{2}$ lends itself to a simple complementary equation
having Wythoff solutions.

Suppose%
\begin{equation*}
w=l_{1}l_{2}\cdots l_{k}
\end{equation*}%
is a word on the two-symbol alphabet $\{a,b\}.$ \ We shall use $w$ to denote
not only the word but also the sequence $(w(n))$ defined as $w=w_{k},$ where%
\begin{equation*}
w_{1}(n)=l_{1}(n),\text{ \ \ \ \ \ }w_{2}(n)=w_{1}(l_{2}(n)),\text{ \ \ \ \ }%
\ldots ,\text{ \ \ \ \ }w_{k}(n)=w_{k-1}(l_{k}(n)).
\end{equation*}%
Call $k=k(w)$ the \textit{length} of $w.$ \ Let $m=m(w)$ be the number of
occurrences of the letter $b$ in $w,$ and call $m$ the \textit{weight} of $%
w. $

Regarding notation, set braces $\{$ $\}$ denote fractional parts as well as
sets; $N$ denotes the set of positive integers, and the Fibonacci sequence $%
(F_{n})$ is defined by $F_{1}=1,$ $F_{2}=1,$ and $F_{n}=F_{n-1}+F_{n-2}$ for 
$n\geq 3.$

In the following four lemmas, $a$ and $b$ denote the Wythoff sequences. \
These symbols may also be regarded as representing a general pair of
complementary sequences defining a complementary equation; in this case,
given the initial value $a(1)=1,$ a solution of the equation is the Wythoff
solution, but there are, for some of the equations, also other solutions.

Possibly these lemmas all appear in other settings, but proofs are included
here for the sake of completeness.

\begin{lemma}
\label{L:1}
$a^{2}=b-1.$
\end{lemma}

\begin{proof}
For every $n$ in $N,$%
\begin{equation*}
0<(\tau -1)\{\tau n\}<1,
\end{equation*}%
so that%
\begin{eqnarray*}
-1 &=&\left\lfloor \{\tau n\}-\tau \{\tau n\}\right\rfloor  \\
&=&\left\lfloor \tau n-\left\lfloor \tau n\right\rfloor -\tau \{\tau
n\}\right\rfloor  \\
&=&\left\lfloor \tau n-\tau \{\tau n\}\right\rfloor -\left\lfloor \tau
n\right\rfloor ,
\end{eqnarray*}%
so that $\left\lfloor \tau n\right\rfloor =\left\lfloor \tau n-\tau \{\tau
n\}\right\rfloor +1.$ \ Then using $b(n)=\left\lfloor \tau n\right\rfloor +n,
$%
\begin{eqnarray*}
b(n) &=&\left\lfloor \tau n+n-\tau \{\tau n\}\right\rfloor +1 \\
&=&\left\lfloor \tau ^{2}n-\tau \{\tau n\}\right\rfloor +1 \\
&=&\left\lfloor \tau (\tau n-\{\tau n\}\right\rfloor +1 \\
&=&\left\lfloor \tau \left\lfloor \tau n\right\rfloor \right\rfloor +1 \\
&=&a(a(n))+1.
\end{eqnarray*}
\end{proof}

\begin{lemma}
\label{L:2}
$ab=a+b.$
\end{lemma}

\begin{proof}
Adapting a proof in\textbf{\ }\cite{FrK}, for every $n$ in $N$ we have%
\begin{eqnarray*}
a(b(n)) &=&\left\lfloor \tau \left\lfloor \tau ^{2}n\right\rfloor
\right\rfloor  \\
&=&\left\lfloor \tau n+\tau \left\lfloor \tau n\right\rfloor \right\rfloor 
\\
&=&n+\left\lfloor 2\tau n-\tau n-n+\tau \left\lfloor \tau n\right\rfloor
\right\rfloor  \\
&=&2\left\lfloor \tau n\right\rfloor +n+\left\lfloor 2\tau n-2\left\lfloor
\tau n\right\rfloor -\tau n-n+\tau \left\lfloor \tau n\right\rfloor
\right\rfloor  \\
&=&\left\lfloor \tau n\right\rfloor +\left\lfloor \tau ^{2}n\right\rfloor
+\left\lfloor 2\tau n-2\left\lfloor \tau n\right\rfloor -\tau ^{2}n+\tau
\left\lfloor \tau n\right\rfloor \right\rfloor  \\
&=&a(n)+b(n),
\end{eqnarray*}%
because%
\begin{equation*}
\left\lfloor 2\tau n-2\left\lfloor \tau n\right\rfloor -\tau ^{2}n+\tau
\left\lfloor \tau n\right\rfloor \right\rfloor =\left\lfloor (2-\tau )\{\tau
n\}\right\rfloor =0.
\end{equation*}
\end{proof}

\begin{lemma}
\label{L:3}
$ba=a+b-1.$
\end{lemma}

\begin{proof}
For every $n$ in $N,$%
\begin{eqnarray*}
b(a(n)) &=&b(\left\lfloor \tau n\right\rfloor )=\left\lfloor \tau
\left\lfloor \tau n\right\rfloor \right\rfloor +\left\lfloor \tau
n\right\rfloor  \\
&=&a(a(n))+a(n),
\end{eqnarray*}%
and now Lemma \ref{L:1} applies.
\end{proof}

\begin{lemma}
\label{L:4}
$b^{2}=a+2b.$
\end{lemma}

\begin{proof}
Using Lemma \ref{L:2},%
\begin{equation*}
b(b(n))=a(b(n))+b(n)=a(n)+b(n)+b(n).
\end{equation*}%
Lemmas \ref{L:1}-\ref{L:4} show the four words $w$ of length $2$ as sequences which, as
solutions of complementary equations, are simple linear combinations of $a,b,
$ and $1.$ \ This result will be extended to longer words in the next
section.
\end{proof}

\section{Main Theorem on Wythoff sequences}

Lemmas \ref{L:1}-\ref{L:4}  enable a proof that \textit{every} word, as a
sequence, is a linear combination of $a,b,$ and $1$ in which the
coefficients of $a$ and $b$ are consecutive Fibonacci numbers.

\begin{theorem}
\label{T:5}
Let $w=l_{1}l_{2}\cdots l_{k}$ with length $k\geq 2$ and weight $m.$ \ Then,
as a sequence,%
\begin{equation}
w=F_{k+m-2}a+F_{k+m-1}b-c,  \label{t2}
\end{equation}%
where $c\geq 0,$ invariant of $n,$ is given by%
\begin{equation*}
c=F_{k+m+1}-w(1).
\end{equation*}
\end{theorem}

\begin{proof}
For $k=2$, there are four words $w$, namely $a^{2},ab,ba,b^{2},$ and by
Lemmas \ref{L:1}-\ref{L:4}, the complementary equation (\ref{t2}) holds for each of these. \ As an
induction hypothesis, assume for arbitrary $k\geq 2$ and every word%
\begin{equation}
w=l_{1}l_{2}\cdots l_{k}  \label{t3}
\end{equation}%
that (\ref{t2}) holds. \ Let%
\begin{equation*}
w^{\prime }=l_{1}l_{2}\cdots l_{k}l_{k+1}
\end{equation*}%
be an arbitrary word of length $k+1,$ and let $k^{\prime }$ and $m^{\prime }$
denote the length and weight of $w^{\prime }$.\medskip 

\textit{Case 1.} $\ l_{k+1}=a,$ so that $k^{\prime }=k+1$ and $m^{\prime }=m.
$ \ We have $w^{\prime }=wa$ where $w$ is as in (\ref{t3}). \ The induction
hypothesis is that%
\begin{equation*}
w(\upsilon )=F_{k+m-2}a(\upsilon )+F_{k+m-1}b(\upsilon )-c
\end{equation*}%
for every $\upsilon $ in $N.$ \ Thus for any $n$ in $N,$ we put $\upsilon
=a(n):$%
\begin{equation*}
w^{\prime }(n)=w(a(n))=F_{k+m-2}a(a(n))+F_{k+m-1}b(a(n))-c,
\end{equation*}%
so that%
\begin{eqnarray*}
w^{\prime } &=&F_{k+m-2}a^{2}+F_{k+m-1}ba-c \\
&=&F_{k+m-2}(b-1)+F_{k+m-1}(a+b-1)-c \\
&=&F_{k+m-1}a+F_{k+m}b-c-F_{k+m} \\
&=&F_{k^{\prime }+m^{\prime }-2}a+F_{k^{\prime }+m^{\prime }-1}b-c-F_{k+m}.
\end{eqnarray*}%
\ \textit{Case 2.} $l_{k+1}=b,$ so that $k^{\prime }=k+1,$ $m^{\prime }=m+1$
and $w^{\prime }=wb,$ and%
\begin{equation*}
w^{\prime }(n)=w(b(n))=F_{k+m-2}a(b(n))+F_{k+m-1}b(b(n))-c,
\end{equation*}%
which is%
\begin{eqnarray*}
w^{\prime } &=&F_{k+m-2}ab+F_{k+m-1}b^{2}-c \\
&=&F_{k+m-2}(a+b)+F_{k+m-1}(a+2b)-c \\
&=&F_{k+m}a+F_{k+m+1}b-c \\
&=&F_{k^{\prime }+m^{\prime }-2}a+F_{k^{\prime }+m^{\prime }-1}b-c.
\end{eqnarray*}%
Thus, (\ref{t2}) is proved, and clearly $c$ is invariant of $n.$ \ Put $n=1$ to
find from (\ref{t2}) that%
\begin{eqnarray*}
c &=&-w(1)+a(1)F_{k+m-2}+b(1)F_{k+m-1} \\
&=&F_{k+m+1}-w(1).
\end{eqnarray*}%
That $c\geq 0$ follows inductively from the observations that $c\geq 0$ in
each of Lemmas \ref{L:1}-\ref{L:4} and that in both cases above, as we pass from $w$ to $%
w^{\prime },$ the constant $c$ passes to a new constant $c^{\prime }\geq c.$
\end{proof}

\section{Tables and examples}

\begin{equation*}
\begin{tabular}{|l|l|l|}
\hline
\multicolumn{3}{|c|}{Table 1. Words of length 2} \\ \hline\hline
$aa=b-1$ &  & $ba=a+b-1$ \\ \hline
$ab=a+b$ &  & $bb=a+2b$ \\ \hline
\end{tabular}%
\end{equation*}%
Sequences in \cite{OEIS} corresponding to the words in Table 1 are \seqnum{A003622},
\seqnum{A003623}, \seqnum{A035336}, and \seqnum{A101864}, respectively.\bigskip

\begin{equation*}
\begin{tabular}{|l|l|l|}
\hline
\multicolumn{3}{|c|}{Table 2. Words of length 3} \\ \hline\hline
$aaa=a+b-2$ &  & $abb=2a+3b$ \\ \hline
$aab=a+2b-1$ &  & $bab=2a+3b-1$ \\ \hline
$aba=a+2b-2$ &  & $bba=2a+3b-3$ \\ \hline
$baa=a+2b-3$ &  & $bbb=3a+5b$ \\ \hline
\end{tabular}%
\end{equation*}%
Sequences in \cite{OEIS} corresponding to the words in Table 2 are \seqnum{A134859},
\seqnum{A134864}, \seqnum{A035337}, \seqnum{A134861}, \seqnum{A134862}, \seqnum{A134863},
\seqnum{A035338}, and \seqnum{A134864},
respectively.\bigskip

\begin{equation*}
\begin{tabular}{|l|c|l|}
\hline
\multicolumn{3}{|c|}{Table 3. Words of length 4} \\ \hline\hline
$aaaa=a+2b-4$ &  & $abba=3a+5b-5$ \\ \hline
$aaab=2a+3b-2$ &  & $baba=3a+5b-6$ \\ \hline
$aaba=2a+3b-4$ &  & $bbaa=3a+5b-8$ \\ \hline
$abaa=2a+3b-5$ &  & $abbb=5a+8b$ \\ \hline
$baaa=2a+3b$ &  & $babb=5a+8b-1$ \\ \hline
$aabb=3a+5b-1$ &  & $bbab=5a+8b-3$ \\ \hline
$abab=3a+5b-2$ &  & $bbba=5a+8b-8$ \\ \hline
$baab=3a+5b-3$ &  & $bbbb=8a+13b$ \\ \hline
\end{tabular}%
\end{equation*}%
\medskip

\begin{example}
$a^{k}=F_{k-2}a+F_{k-1}b-F_{k+1}+1$ for all $k$ in $N.$\medskip 
\end{example}

\begin{example}
$b^{k}=F_{2k-2}a+F_{2k-1}b$ for all $k$ in $N.$\medskip 
\end{example}

\section{The constant $c$}

The constant $c$ in Theorem \ref{T:5} is not easily written out in general.
\ However, we can gain some insights using the following theorem.\bigskip 

\begin{theorem}
\label{T:6}
Suppose, as in Theorem \ref{T:5}, that%
\begin{equation*}
w=F_{k+m-2}a+F_{k+m-1}b-c.
\end{equation*}%
Then for $i\geq 0,$%
\begin{eqnarray}
wa^{2i} &=&F_{k+m+2i-2}a+F_{k+m+2i-1}b-c-\overset{i}{\underset{h=1}{\sum }}%
F_{k+m+2h}  \label{t4} \\
wa^{2i+1} &=&F_{k+m+2i-1}a+F_{k+m+2i}b-c-F_{k+m+2i}-\overset{i}{\underset{h=1%
}{\sum }}F_{k+m+2h}  \label{t5} \\
wb^{i} &=&F_{k+m+2i-2}a+F_{k+m+2i-1}b-c.  \label{t6}
\end{eqnarray}%
$\medskip $
\end{theorem}

\begin{proof}
Each equation is easily proved by induction on $i.\medskip $
\end{proof}

As every word is a concatenation of subwords covered by (\ref{t4})-(\ref{t6}), it follows
that the constant $c$ in (\ref{t2}) is a sum of Fibonacci numbers, each appearing
at most twice, as in (\ref{t5}), where $F_{k+m+2i}$ occurs twice.$\medskip $

\begin{corollary}
\label{C:7}
\textbf{\ }Suppose $w$ is a word. \ In the representation (\ref{t2}), $c=0$ if and
only if $w=b^{i+1}$ or $w=ab^{i}$ for some $i\geq 1.$
\end{corollary}

\begin{proof}
The assertion is clearly true for words of length $1.$ \ By Lemmas \ref{L:1}-\ref{L:4},
among words of length 2, we have $c=0$ only for $w=b^{2}$ and $w=ab.$ \ The
remaining cases now follow from (\ref{t6}).
\end{proof}

\section{Columns of the Wythoff array}

Let $W$ denote the Wythoff array \cite{AS,SloCl,MW}, for
which the entry in row $n$, column $h,$ is%
\begin{equation*}
W(n,h)=(n-1)F_{h}+\left\lfloor n\tau \right\rfloor F_{h+1}.
\end{equation*}%
Words $w,$ taken as sequences, have close connections to columns of $W.$%
\medskip

\begin{theorem}
\label{T:8}
Column $h$ of $W$ is given by%
\begin{equation*}
w_{h}:=\left\{ \text{%
\begin{tabular}{ll}
$ab^{(h-1)/2}a$ & if $h$ is odd \\ 
$b^{h/2}a$ & if $h$ is even.%
\end{tabular}%
}\right. 
\end{equation*}%
\medskip 
\end{theorem}

\begin{proof}
By Theorem \ref{T:5}, for all $h$ and $n$ in $N,$%
\begin{eqnarray*}
w_{h}(n) &=&F_{h-1}a(n)+F_{h}b(n)-F_{h} \\
&=&F_{h-1}\left\lfloor n\tau \right\rfloor +F_{h}(\left\lfloor n\tau
\right\rfloor +n-1) \\
&=&(F_{h-1}+F_{h})\left\lfloor n\tau \right\rfloor +(n-1)F_{h} \\
&=&(n-1)F_{h}+\left\lfloor n\tau \right\rfloor F_{h+1} \\
&=&W(n,h).
\end{eqnarray*}%
The next theorem tells that the sequences in Corollary \ref{C:7} are ordered unions
of columns of $W.$\medskip 
\end{proof}

\begin{theorem}
\label{T:9}
For all $h$ in $N,$%
\begin{equation*}
ab^{h-1}=\text{ordered }{\Large \cup }\{w_{2j-1}:\text{ \ }j=h,h+1,h+2,...\}
\end{equation*}%
and%
\begin{equation*}
b^{h}=\text{ordered }{\Large \cup }\{w_{2j}:\text{ \ }j=h,h+1,h+2,...\}.
\end{equation*}
\end{theorem}

Proof of Theorem \ref{T:9} is left to the reader, who may wish to prove
also, regarding all words not covered by Theorems \ref{T:8} and \ref{T:9},
that every word $a^{2}w^{\prime },$ as a sequence, is a subsequence of
column 1 of $W,$ that every $baw^{\prime }$ is a subsequence of column 2,
that every $abaw^{\prime }$ is a subsequence of column 3, that every $%
bbaw^{\prime }$ is a subsequence of column 4, and so on.

\section{Concluding remarks}

Some complementary equations having Wythoff solutions have been presented. 
Others, such as $ab-ba=1,$ can be written easily by inspecting Tables 1-3. 
Most of these equations have not only the Wythoff solutions, but also
others.  For example, the equation $ab=a+b$ has the sequence $(2n-1)$ as a
solution.  One wonders if \textit{general} solutions can be obtained for
this and other complementary equations, and not only for the initial value $%
a(1)=1$.  The interested reader may wish to consult \cite{AS} (especially
Chapters 7 and 9) and \cite{Fr69,Fr73,Fr77,FrK,Kim}.

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

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

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

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

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

\bibitem{Kim} C. Kimberling, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Kimberling/kimberling26.html}{Complementary equations}, \textit{J. Integer
Sequences} {\bf 10} (2007),  Article 07.1.4.

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

\bibitem{SloCl} N. J. A. Sloane, \textit{Classic sequences,}  \\
\href{http://www.research.att.com/~njas/sequences/classic.html}{\tt http://www.research.att.com/\symbol{126}njas/sequences/classic.html} .

\bibitem{MW} E. Weisstein, MathWorld,
\href{http://mathworld.wolfram.com/}{\tt http://mathworld.wolfram.com/} .
\end{thebibliography}



\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } complementary equation, complementary sequences,
Fibonacci numbers, golden ratio, Wythoff array, Wythoff sequence.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000201},
\seqnum{A001950},
\seqnum{A003622},
\seqnum{A003623},
\seqnum{A035336},
\seqnum{A035337},
\seqnum{A035338},
\seqnum{A035513},
\seqnum{A101864},
\seqnum{A134859},
\seqnum{A134860},
\seqnum{A134861},
\seqnum{A134862},
\seqnum{A134863}, and
\seqnum{A134864}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 27 2007;
revised version received  July 21 2008.
Published in {\it Journal of Integer Sequences}, August 3 2008.

\bigskip
\hrule
\bigskip

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


\end{document}