\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{csquotes}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

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

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\Mod}[1]{\ (\mathrm{mod}\ #1)}

\DeclareMathOperator{\mex}{mex}

\begin{document}

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

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE \bf Complementary Equations with \\
\vskip .1in 
Advanced Subscripts}
\vskip 1cm
\Large
Clark Kimberling\\
Department of Mathematics\\
University of Evansville\\
Evansville, IN 47722\\
USA\\
\href{mailto:ck6@evansville.edu}{\tt ck6@evansville.edu}

\vskip 1cm
\Large
Peter J. C. Moses\\
Engineering Division, Moparmatic Co.\\
Astwood Bank, Nr. Redditch\\
Worcestershire, B96 6DT\\
UK\\
\href{mailto:moparmatic@gmail.com}{\tt moparmatic@gmail.com}
\end{center}

\vskip .2in

\begin{abstract}
This paper discusses complementary equations, such as $a_n=b_n+b_{2n}$, in which $(a_n)$ and $(b_n)$ are strictly increasing complementary sequences for which, in addition to the subscript $n$, at least one subscript in advance of $n$, such as $n+1$ or $2n$, occurs.  Some of the equations are solved with proofs, and others are presented as conjectures or examples based on 
{\tt Mathematica} programs that appear in the final section of the paper.
\end{abstract}

\section{Introduction}\label{intro}
Let $\N=\{1,2,\ldots\}$ and $\N_0=\N \cup \{0\}$.  Many sequences $(a_n)$ in $\N$ are defined by an equation that tells how to determine each term from preceding terms; e.g., the Fibonacci sequence, $(F_n),$ arises from the equation $F_n=F_{n-1}+F_{n-2},$ starting with $F_1=1$ and $F_2=1$.  Less familiar are sequences generated by a \textit{complementary equation}---that is, an equation that refers to both $(a_n)$ and its complement in $\N$.

In this paper, $a=(a_n)$ denotes an increasing sequence in $\N$ such that the complement in $\N$ of the set $A=\{a_n: n \geq 0 \}$ is infinite. We write the complement as $B$ and denote by $b=(b_n)$ the sequence of numbers in $B$ in increasing order.  A classic example of a complementary equation is
$$b_n=a_n+n \text{ where } a_1=1,$$
with solution given by
$$a_n=\lfloor n\tau \rfloor, \hspace{5mm} b_n=n+\lfloor n\tau \rfloor,$$
where $\tau = (1+\sqrt{5})/2$, the golden ratio.  The sequences $(a_n)$ and $(b_n)$ are the lower and upper Wythoff sequences, \seqnum{A000201} and \seqnum{A001500} in the {\it On-line Encyclopedia of Integer Sequences} \cite{OEIS}; also see \cite{Kim1} and \cite{Kim2}.

\section{Advanced subscripts}\label{AdvSub}

It may seem surprising that complementary equations with advanced subscripts, such as $a_n=b_n+b_{2n},$ make sense, since $2n$ comes after $n$. The first theorem will show that, with initial value $b_0=1,$ this equation and many others 
make sense and have unique solutions.

\begin{theorem}\label{exist}
Suppose that $f:\N^2 \rightarrow \N$ satisfies $f(1,1) \geq 2$ and
$$f(m+1,n) \geq \\
f(m,n)+1 \text{ and } f(m,n+1) \geq f(m,n)+1$$
for all $(m,n) \in \N^2$. If $g,h:\N_0 \rightarrow \N$ are strictly increasing functions, then the complementary equation
\begin{equation}\label{eq:af}
a_n=f(b_{g(n)},b_{h(n)}), \text{ with } b_0=1,
\end{equation}
has a unique solution.
\end{theorem}

\begin{proof}
We assume that a solution $(a,b)=((a_n),(b_n))$ exists and then confirm inductively that it is uniquely determined; that is, a solution is generated inductively by (\ref{eq:af}), and it is unique. For $n \geq 0$,
\begin{align*}
f(b_{g(n)},b_{h(n)}) &\geq f(b_{g(n)},b_{h(n)}-1)+1  \\
&\geq f(b_{g(n)},b_{h(n-1)})+1 \\
&\geq f(b_{g(n)}-1,b_{h(n-1)})+2 \\
&\geq f(b_{g(n-1)},b_{h(n-1)})+2,
\end{align*}
so that
\begin{equation}\label{eq:adiff}
a_n-a_{n-1} \geq 2.
\end{equation}

Since $b_0=1$, we have $a_0=f(b_0,b_0)=f(1,1) \geq 2$. Then (\ref{eq:adiff}) implies $a_1 \geq a_0+2$, so that by complementation, the numbers $b_i$ are uniquely determined as the consecutive integers in $[a_0+1,a_1-1]$, and inductively, the set of $b_i$ are uniquely determined as the consecutive integers in $[a_n+1,a_{n+1}-1]$, for all $n \geq 0$.
\end{proof}

Following is a list of some complementary equations to which Theorem \ref{exist} applies:
\begin{align*}
a_n &= 2b_n,\\
a_n &= b_n+b_{n+2},\\
a_n &= 3b_n+2b_{n+2}-5,\\
a_n &= 2b_n+b_{2n}+1, \\
a_n &= b^2_n+2b_{n+1}, \\
a_n &= b_{\lfloor n/2 \rfloor}+b_{\lfloor 3n/2 \rfloor},\\
a_n &= b_n b_{n+1}+1, \\
a_n &= b^2_n+b^2_{n+1}.
\end{align*}

The method of proof suggests that Theorem \ref{exist} could be extended to cover many more types of equations with advanced subscripts, such as these:
\begin{align*}
a_n &= a_{n-1}+b_{n+1}, \\
a_n &= b_n+b_{n+1}+b_{n+2}, \\
a_n &= b_{n+1}+n+1,\\
a_n &= b_n+b_{2n}+b_{3n}+b_{4n}-1.
\end{align*}

It appears that for many complementary equations, exact formulas for solutions are elusive and that generating the sequences depends on the $\mex$ function (\textbf{m}inimal \textbf{ex}cludant), which has been described as \enquote{unwieldy} \cite{Fr&P}.  Accordingly, aside from multi-case proofs for certain simple-looking equations (in Sections~\ref{AdvSub} and \ref{compeq2}), we rely on 
{\tt Mathematica} programs, as shown in Section~\ref{programs}, to generate sequences that reveal both expected and unexpected results, leading to examples and conjectures based on experimentation.

\section{The equation $a_n=b_{2n}+b_{4n}$, where $b_0=1$}\label{compeq1}
In this section, we consider equations $a_n=b_{hn}+b_{khn}$, where $h \geq 2$. (A different method applies to the case $h=1$, as in Section~\ref{compeq3}). First, we consider the special case $a_n=b_{2n}+b_{4n}$, and then we state conjectures for general $h$ and $k$.

\begin{lemma}\label{lemma}
Suppose that a sequence $\beta$ is given by
\begin{equation}\label{eq:beta}
\beta_n=r(m(n))+21\lfloor{n/18}\rfloor,
\end{equation}
where $m(n)=n-18\lfloor{n/18}\rfloor$ and

\begin{equation*}
r(m)=\begin{cases}
1, & \text{if $m = 0$}; \\
m+2, & \text{if $1 \leq m \leq 7$}; \\
m+3, & \text{if $8 \leq m \leq 13$}; \\
m+4, & \text{if $14 \leq m \leq 17$}.
\end{cases}
\end{equation*}

Then
\begin{equation*}
\beta_{2n+2}-\beta_{2n} =
\begin{cases}
3, & \text{if $n \equiv 0\Mod{3} $}; \\
2, & \text{if $n \not\equiv 0\Mod{3} $}
\end{cases}
\end{equation*}
and
\begin{equation*}
\beta_{4n+4}-\beta_{4n} =
\begin{cases}
4 & \text{if $n \equiv 2\Mod{3} $}; \\
5 & \text{if $n \not\equiv 2\Mod{3} $}.
\end{cases}
\end{equation*}
\end{lemma}

\begin{proof}
For $0 \leq n \leq 17$, we have $m(n)=n$, and values of $r(n)$ as shown in 
Table~\ref{Table1}.

\begin{table}[H]
\begin{center}
\resizebox{.95\textwidth}{!}{
\begin{tabular}{| c | c c c c c c c c c c c c c c c c c c |}
\hline
$n=m(n)$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\
\hline
$r(n)$ & 1 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 11 & 12 & 13 & 14 & 15 & 16 & 18 & 19 & 20 & 21 \\
\hline
\end{tabular}
}
\caption{Values of $r(n)$\label{Table1}}
\end{center}
\end{table}

By (\ref{eq:beta}) we have
\begin{equation*}
\beta_{2n+2}-\beta_{2n}=r(m(2n+2))-r(m(2n))+21\left(\left\lfloor\frac{n+1}{9}\right\rfloor-\left\lfloor\frac{n}{9}\right\rfloor\right),
\end{equation*}
which leads to cases, first for $\beta_{2n+2}-\beta_{2n}$ (Cases 1.1 and 1.2), then for $\beta_{4n+4}-\beta_{4n}$.

\bigskip
\noindent\textbf{Case 1.1:}  $\lfloor\frac{n+1}{9}\rfloor-\lfloor\frac{n}{9}\rfloor=0$.  Here, $m(2n+2)-m(2n)=2$, so that
$$\beta_{2n+2}-\beta_{2n}=r(m(2n+2))-r(m(2n)),$$
which, as in Table~\ref{Table1}, is $3$ if $n \equiv 0\Mod{3} $ and $2$ otherwise.

\bigskip\noindent
\textbf{Case 1.2:}  $\lfloor\frac{n+1}{9}\rfloor-\lfloor\frac{n}{9}\rfloor=1$.  Here, $n$ must be of the form $9j-1$, so that $m(2n)=m(18j-2)=16$ and $m(2n+2)=m(18j)=0$.  Then
$$\beta_{2n+2}-\beta_{2n}=r(0)-r(16)+21=2,$$
as required, since $n \equiv 2 \Mod{3}$.

\bigskip\noindent
\textbf{Case 2.1:} $\lfloor\frac{2n+2}{9}\rfloor-\lfloor\frac{2n}{9}\rfloor=0$.  Here, $m(4n+4)-m(4n)=4$, so that
$$\beta_{4n+4}-\beta_{4n}=r(m(4n+4))-r(m(4n)),$$
which, as in Table \ref{Table1}, is $4$ if $n \equiv 2 \Mod{3} $ and $5$ otherwise.

\bigskip\noindent
\textbf{Case 2.2:} $\lfloor\frac{2n+2}{9}\rfloor-\lfloor\frac{2n}{9}\rfloor=1$.  We recognize two exhaustive subcases:

\bigskip\noindent
\textbf{Subcase 2.2.1:} $2n=7+9j$ for some $j$, so that $2n+2=9(j+1)$. Here, $m(4n)=14$ and $m(4n+4)=0$, whence
$$\beta_{4n+4}-\beta_{4n}=r(0)-r(14)+21=1-18+21=4,$$
as required, since $n \equiv 2 \Mod{3} $.

\bigskip\noindent
\textbf{Subcase 2.2.2:} $2n=8+9j$ for some $j$, so that  $2n+2=1+9(j+1)$. Then $m(4n)=16$ and $m(4n+4)=2$, whence
$$\beta_{4n+4}-\beta_{4n}=r(3)-r(16)+21=4-20+21=5,$$
as required, since $n \equiv 1 \Mod{3} $.
\end{proof}

We are now ready for the main theorem of this section.

\begin{theorem}\label{thm1}
Let $a=(a_n)$ and $b=(b_n)$ be the strictly increasing complementary sequences determined by the equation
\begin{equation}\label{eq:main1}
a_n=b_{2n}+b_{4n}, \text{ where } b_0=1.
\end{equation}
Then
\begin{equation}\label{eq:maincases}
a_n = \begin{cases}
2 + 21\lfloor n/3 \rfloor, & \text{if $m \equiv 0\Mod{3}$};  \\
10 + 21\lfloor n/3 \rfloor, & \text{if $m \equiv 1\Mod{3}$}; \\
17 + 21\lfloor n/3 \rfloor, & \text{if $m \equiv 2\Mod{3}$}.
\end{cases}
\end{equation}
\end{theorem}

\begin{proof}
Since $b_0=1$, we have $a_0=2$ by (\ref{eq:main1}), and since $a$ and $b$ are strictly increasing and complementary, we have
$$2 < b_1 < b_2 < b_3 < b_4,$$
which implies that $b_i=2+i$ for $i=1,\ldots, 4$. Equation (\ref{eq:main1}) implies $a_1=b_2+b_4=4+6=10$, so that $b_i=3+i$ for $i=5,6,7$.  Then $a_2=b_4+b_8 \geq 6+10=16$, and $a_2=6+11=17$.  Thus, (\ref{eq:maincases}) is established for $n=0,1,2$.  Before assuming (\ref{eq:maincases}) as an induction hypothesis, we note that 
$$a_3=b_6+b_{12} = 8+15 = 23$$
implies $b_{13}=16$ and $b_i=4+i$ for $i=14,\ldots, 17$, so that, in regard to the sequence $\beta_n$ in Lemma \ref{lemma}, we have $b_n=\beta_n$ for $n=0,\ldots,17$.  Moreover, since $b$ is the complement of $a$, we have, for $n=0,\ldots 17$,
\begin{equation}\label{eq:label4}
b_n=r(m(n))+21\lfloor n/18 \rfloor,
\end{equation}
where $m(n)=n-18\lfloor n/18 \rfloor$ and
\begin{equation*}
r(m) = \begin{cases}
1, & \text{if $m = 0$}; \\
m+2, & \text{if $1 \leq m \leq 7$}; \\
m+3, & \text{if $8 \leq m \leq 13$}; \\
m+4, & \text{if $14 \leq m \leq 17$}.
\end{cases}
\end{equation*}

For use below, we note that (\ref{eq:main1}) implies
\begin{equation}\label{eq:main2}
a_{n+1}=a_n+b_{4n+4}-b_{4n}+b_{2n+2}-b_{2n}
\end{equation}
for $n \geq 0$. Now, as an induction hypothesis, assume that (\ref{eq:maincases}) holds for arbitrary $n \geq 2$. We have three cases, according as $n \equiv 0,1,2 \Mod{3}$.

\bigskip\noindent
\textbf{Case 1:} $n \equiv 0\Mod{3}$.  Here, $a_n=2+21\lfloor n/3 \rfloor$, and by Lemma \ref{lemma}, $b_{2n+2}-b_{2n}=3$ and $b_{4n+4}-b_{4n}=5$, so that by (\ref{eq:main2}),
$$a_{n+1}=a_n+8=10+21 \lfloor n/3 \rfloor = 10+21 \lfloor (n+1)/3 \rfloor.$$
By complementation, we also have (\ref{eq:label4}) for the numbers $b_i$ required for the following proof for Case 2.

\bigskip\noindent
\textbf{Case 2:} $n \equiv 1\Mod{3}$. Here, $b_{2n+2}-b_{2n}=2$ and $b_{4n+4}-b_{4n}=5$, so that
$$a_{n+1}=a_n+7=17+21 \lfloor n/3 \rfloor = 17+21 \lfloor (n+1)/3 \rfloor.$$
By complementation, we also have (\ref{eq:label4}) for the numbers $b_i$ required for the following proof for Case 3.

\bigskip\noindent
\textbf{Case 3:} $n \equiv 2\Mod{3}$. Here, $b_{2n+2}-b_{2n}=2$ and $b_{4n+4}-b_{4n}=4$, so that
$$a_{n+1}=a_n+6=23+21 \lfloor n/3 \rfloor = 2+(21+21 \lfloor n/3 \rfloor).$$
By complementation, we also have (\ref{eq:label4}) for the numbers $b_i$ required for the next application of the proof for Case 1, so that by the principle of mathematical induction, (\ref{eq:maincases}) holds for all $n \geq 0$.
\end{proof}

\begin{corollary}\label{corrr}
The sequence $(b_n)$ in Theorem \ref{thm1} is identical to the sequence $(\beta_n)$ in Lemma \ref{lemma}.
\end{corollary}

\begin{proof}
A proof is included in the proof of Theorem \ref{thm1}.
\end{proof}

\begin{corollary}\label{corrrr}
The sequence $a$ in Theorem \ref{thm1} satisfies the recurrence
$$a_{n+4}=a_{n+3}+a_{n+1}-a_n.$$
\end{corollary}

\begin{proof}
We shall make repeated use of Corollary \ref{corrr}.  Let
$$B_2=b_{2n+2}-b_{2n}, \hspace{0.3cm} B_4=b_{4n+4}-b_{4n}, \hspace{0.3cm} B_8=b_{2n+8}-b_{2n+6},\hspace{0.3cm} B_{16}=b_{4n+16}-b_{4n+12},$$
so that
$$a_{n+4}-a_{n+3}=B_{16}+B_8 \text{ and } a_{n+1}-a_n=B_4+B_2.$$
There are three cases:

\bigskip\noindent
\textbf{Case 1:} $n \equiv 0 \Mod{3}$.
\begin{align*}
B_{16} &=v\beta_{4m+4}-\beta_{4m} \text{ for } m=n+3, \text{ so that } m \equiv 0 \Mod{3}, \text{ and } B_{16}=5. \\
B_8 &= \beta_{2m+2}-\beta_{2m} \text{ for } m=n+3, \text{ so that } m \equiv 0 \Mod{3}, \text{ and } B_8=3. \\
B_4 &= \beta_{2m+4}-\beta_{4m} \text{ for } m=n, \text{ so that } m \equiv 0 \Mod{3}, \text{ and } B_4=5. \\
B_2 &= \beta_{2m+2}-\beta_{2m} \text{ for } m=n, \text{ so that } m \equiv 0 \Mod{3}, \text{ and } B_2=3.
\end{align*}

\bigskip\noindent
\textbf{Case 2:} $n \equiv 1 \Mod{3}$.
\begin{align*}
B_{16} &= \beta_{4m+4}-\beta_{4m} \text{ for } m=n+3, \text{ so that } m \equiv 1 \Mod{3}, \text{ and } B_{16}=5. \\
B_8 &= \beta_{2m+2}-\beta_{2m} \text{ for } m=n+3, \text{ so that } m \equiv 1 \Mod{3}, \text{ and } B_8=3. \\
B_4 &= \beta_{2m+4}-\beta_{4m} \text{ for } m=n, \text{ so that } m \equiv 1 \Mod{3}, \text{ and } B_4=5. \\
B_2 &= \beta_{2m+2}-\beta_{2m} \text{ for } m=n, \text{ so that } m \equiv 1 \Mod{3}, \text{ and } B_2=3.
\end{align*}

\bigskip\noindent
\textbf{Case 3:} $n \equiv 2 \Mod{3}$.
\begin{align*}
B_{16} &= \beta_{4m+4}-\beta_{4m} \text{ for } m=n+3, \text{ so that } m \equiv 2 \Mod{3}, \text{ and } B_{16}=4. \\
B_8 &= \beta_{2m+2}-\beta_{2m} \text{ for } m=n+3, \text{ so that } m \equiv 2 \Mod{3}, \text{ and } B_8=2. \\
B_4 &= \beta_{2m+4}-\beta_{4m} \text{ for } m=n, \text{ so that } m \equiv 2 \Mod{3}, \text{ and } B_4=4. \\
B_2 &= \beta_{2m+2}-\beta_{2m} \text{ for } m=n, \text{ so that } m \equiv 2 \Mod{3}, \text{ and } B_2=2.
\end{align*}

In all the cases,
$$B_{16}+B_8=B_4+B_2,$$
which is equivalent to
$$a_{n+4}-a_{n+3}=a_{n+1}-a_n.$$
\end{proof}

Next, we give a conjecture based on Program \ref{Program1}, which was used to generated Table \ref{Table2}.
\begin{conjecture}\label{conjA}
Let $a=(a_n)$ and $b=(b_n)$ be the strictly increasing complementary sequences determined by the equation
$$a_n=b_{hn}+b_{khn},$$
where $h \geq 2$, $k \geq 2$, and $b_0=1$. Then $a$ is a linear recurrence sequence given by
$$a_n=a_{n-1}+a_{n-k-1}-a_{n-k-2}$$
with initial terms
$$a_0=2, \hspace{.3cm} a_1=h(k+1)+4, \hspace{.3cm} a_2=2h(k+1)+5, \ldots , \hspace{.3cm} a_k=kh(k+1)+k+3.$$
The sequence $a$ consists of the positive integers congruent modulo $(k+1)(2k+h+1)$ to the numbers in $\{a_0,a_1,\ldots , a_k\}$, and the sequence $b$ satisfies the linear recurrence
$$b_n = b_{n-1}+b_{n-m}-b_{n-m-1}, \text{ where } m=(k+2)hk+h-5.$$
\end{conjecture}

\begin{table}[H]
\begin{center}
\resizebox{.95\textwidth}{!}{
\begin{tabular}{| c | c c c c c c c c c c c c c c |}
\hline
$n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
$a_n=b_{2n}+b_{4n}$ & 2 & 10 & 17 & 23 & 31 & 38 & 44 & 52 & 59 & 65 & 73 & 80 & 86 & 94  \\
$a_n=b_{2n}+b_{6n}$ & 2 & 12 & 21 & 30 & 38 & 48 & 57 & 66 & 74 & 84 & 93 &102 & 110 & 120  \\
$a_n=b_{2n}+b_{8n}$ & 2 & 14 & 25 & 36 & 47 & 57 & 69 & 80 & 91 & 102 & 112 & 124 & 135 & 146  \\
$a_n=b_{3n}+b_{6n}$ & 2 & 13 & 23 & 32 & 43 & 53 & 62 & 73 & 83 & 92 & 103 & 113 & 122 & 133  \\
$a_n=b_{3n}+b_{9n}$ & 2 & 16 & 29 & 42 & 54 & 68 & 81 & 94 & 106 & 120 & 133 & 146 & 158 & 172  \\
$a_n=b_{4n}+b_{8n}$ & 2 & 16 & 29 & 41 & 55 & 68 & 80 & 94 & 107 & 119 & 133 & 146 & 158 & 172  \\
\hline
\end{tabular}
}
\caption{First fourteen terms, $a_n=b_{hn}+b_{khn}, b_0=1$\label{Table2}}
\end{center}
\end{table}

In the next section we extend our earlier attention to the special case $a_n=b_{2n}+b_{4n}$ by adding a nonzero constant to the right-hand side.

\section{The equation $a_n=b_{2n}+b_{4n}+c$, where $b_0=1$}\label{compeq2}
Theorem \ref{thm1} gives a precise solution of $a_n=b_{2n}+b_{4n}$, with $b_0=1$, and Corollary \ref{corrrr} shows that $(a_n)$ is more \enquote{regular} than might be thought
if (\ref{eq:maincases}) were the only representations.  We shall see, however, that this sort of regularity does not extend to equations of the form $a_n=b_{2n}+b_{4n}+c$ when $c \geq 1$.

\begin{theorem}\label{thmc}
Let $a=(a_n)$ and $b=(b_n)$ be the strictly increasing complementary sequences determine by the equation
$$a_n=b_{2n}+b_{4n}+1, \text{ where } b_0=1.$$
Then
\begin{equation}\label{eq:3or4}
a_n = 7n +\begin{cases}
3, & \text{if $n \equiv 0\Mod{3} $}; \\
3 \text{ or } 4, & \text{if $n \not\equiv 0\Mod{3} $}.
\end{cases}
\end{equation}
\end{theorem}

\begin{proof}
We have \cite{IB1} inductively
$$b_{6n+3} \geq 7n+5 \text{ and } b_{6n+1} \leq 7n+2,$$
so that
\begin{equation}\label{eq:t1}
t+\lfloor(t+3)/6\rfloor+1 \leq b_t \leq t+ \lceil(t-1)/6\rceil+1
\end{equation}
for $t=6k+3,\ldots,6k+7$. Thus, $b_t=t+\lceil (t-1)/6)\rceil+1$ except for
$$7k+3 \leq b_{6k+2} \leq 7k+4.$$
Consequently, $7n+3 \leq a_n \leq 7n+4$, as desired.
\end{proof}

To illustrate the \enquote{irregularity} of (\ref{eq:3or4}) when $n \not\equiv 0\Mod{3}$, let $r=(r_n)$ be the increasing sequence of numbers $n$ for which $a_n=7n+4$:
\begin{equation}\label{eq:differences}
r=(1,5,7,10,13,14,17,19,23,25,28,32,34,37,41,44,46,47,49,50, \ldots ).
\end{equation}

\begin{conjecture}\label{conjB}
The sequence $r$ is not linearly recurrent, and
$$\{a_n-a_{n-1}: n \geq 1\}=\{1,2,3,4,5\}.$$
\end{conjecture}

The five differences shown in \ref{eq:differences} all occur as $n$ ranges from $1$ to $28$. No other difference occurs as $n$ ranges up to $10000$. Similar mysteries are found for other choices of $c$.  Initial terms of $(a_n)$ are shown in Table \ref{Table3}, which was used to construct Table \ref{Table3}. Looking ahead, it appears that the sequences $(a_n)$ are much more \enquote{regular} for $c \in \{2,3,5\}$, than for some other values of $c$; see Conjectures \ref{conjC}-\ref{conjE}.

\begin{table}[H]
\begin{center}
\resizebox{.95\textwidth}{!}{
\begin{tabular}{| c | c c c c c c c c c c c c c c |}
\hline
$n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
$a_n=b_{2n}+b_{4n}+0$ & 2 & 10 & 17 & 23 & 31 & 38 & 44 & 52 & 59 & 65 & 73 & 80 & 86 & 94  \\
$a_n=b_{2n}+b_{4n}+1$ & 3 & 11 & 17 & 24 & 31 & 39 & 45 & 53 & 59 & 66 & 74 & 80 & 87 & 95  \\
$a_n=b_{2n}+b_{4n}+2$ & 4 & 11 & 18 & 25 & 32 & 39 & 46 & 53 & 60 & 67 & 74 & 81 & 88 & 95  \\
$a_n=b_{2n}+b_{4n}+3$ & 5 & 12 & 19 & 26 & 33 & 40 & 47 & 54 & 61 & 68 & 75 & 82 & 89 & 96  \\
$a_n=b_{2n}+b_{4n}+4$ & 6 & 12 & 19 & 27 & 34 & 41 & 48 & 54 & 62 & 69 & 75 & 82 & 90 & 96  \\
$a_n=b_{2n}+b_{4n}+5$ & 7 & 13 & 20 & 28 & 34 & 41 & 49 & 55 & 62 & 70 & 76 & 83 & 91 & 97  \\
$a_n=b_{2n}+b_{4n}+6$ & 8 & 14 & 21 & 28 & 35 & 42 & 50 & 56 & 63 & 71 & 77 & 84 & 92 & 98  \\
$a_n=b_{2n}+b_{4n}+7$ & 9 & 15 & 22 & 28 & 36 & 43 & 50 & 57 & 64 & 70 & 78 & 85 & 92 & 99  \\
$a_n=b_{2n}+b_{4n}+8$ & 10 & 16 & 22 & 29 & 36 & 44 & 50 & 58 & 65 & 71 & 79 & 86 & 92 & 100  \\
\hline
\end{tabular}
}
\caption{$a_n=b_{2n}+b_{4n}+c, \text {for } c=0,1,\ldots,8$\label{Table3}}
\end{center}
\end{table}

With one exception, the data in Table~\ref{Table3}, generated by Program \ref{Program2}, show nondecreasing columns. It turns out that this exception is indicative of many others.  In order to describe them, we introduce some notation:
for each $c \geq 1$ and the equations
\begin{equation}\label{eq:two}
a_n=b_{2n}+b_{4n}+c \text{ and } a^*_n=b^*_{2n}+b^*_{4n}+c+1, \text{where } b_0=b^*_0=1,
\end{equation}
throughout this section let
\begin{align*}
N &= \text{an upper bound for $n$, depending on context};\\
m(c) &= \min\{a^*_n-a_n\} \text{ for } 0 \leq n \leq N=5000; \\
M(c) &= \max\{a^*_n-a_n\} \text{ for } 0 \leq n \leq N=5000; \\
T(c,i) &= \text{sequence of indices } n \text{ for which } a^*_n-a_n = i;\\
\Delta(c,i) &= \text{set of distinct differences in } T(c,i).
\end{align*}
The choice of $N$ varies as an experimental upper bound when sampling various (presumably) unbounded sequences.

Note that the sets $T(c,i)$ for $i=m(c),\ldots,M(c)$ partition $\N_0$. We shall refer to $m,M,T,$ and $\Delta$ in the following examples, which show various sorts of unwieldiness that appear when comparing the sequences $(a_n)$ and $(a^*_n)$ given by (\ref{eq:two}).

\begin{example}\label{ExA}
For $c=0$, we have $m(c)=0, M(c)=1$, and
\begin{align*}
T(0,0) &= (2,4,8,11,16,20, \ldots); \hspace{.5cm} \Delta(0,0) = \{1,2,3,4,5,7,8,9,10,12,13\}; \\
T(0,1) &= (0,1,3,5,6,7,9, \ldots); \hspace{.7cm} \Delta(0,1) = \{1,2,3\}. \\
\end{align*}
\end{example}
In Example \ref{ExA}, $\Delta(0,0)$ consists of $11$ integers in the interval $[1,13]$, with $6$ and $11$ missing.  Table~\ref{Table4}, generated by Program \ref{Program3}, shows the frequency of each difference $a^*_n-a_n$, for $n$ up to $N=10000$.

\begin{table}[H]
\begin{center}
\begin{tabular}{| c c c c c c c c c c c c c |}
\hline
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
316 & 581 & 737 & 461 & 188 & 0 & 45 & 129 & 129 & 23 & 0 & 8 & 53 \\
\hline
\end{tabular}
\caption{Frequencies of differences in $\Delta(0,0), n=1,2,\ldots,N=10000$\label{Table4}}
\end{center}
\end{table}

\begin{example}\label{ExB}
For $c=1$, we have $m(c)=0, M(c)=1$, and
\begin{align*}
T(1,0) &= (1,5,7,10,13,14,17,19 \ldots), \\
& \Delta(1,0) = \{1,2,3,4,5\}; \\
T(1,1) &= (0,2,3,4,6,8,9,11,12 \ldots), \\
& \Delta(1,1) = \{1,2,3\}. \\
\end{align*}
\end{example}

\begin{example}\label{ExC}
For $c=2$, we have $m(c)=M(c)=1$, so that $T(2,1)=\N_0$ and $\Delta(2,1)=\{1\}$.
\end{example}
Regarding Example \ref{ExC}, we pose this question: \textit{is $2$ the only value of $c$ for which $m(c)=M(c)$?} (Program \ref{Program3}, with $c=2$ in the first instance and $c=3$ in the second, confirms that $a^*_n-a_n=1$ for $n$ up to $N=10000$).

In connection with Table \ref{Table4}, the difference $a^*_n-a_n$ is never $6$ or $11$ for $N=10000$, and is $12$ relatively rarely; indeed, the least $n$ for which $a^*_n-a_n=12$ is $n=1325$.

\begin{example}\label{ExD}
For $c=6$, we have $m(c)=-1, M(c)=1$, and
\begin{align*}
T(6,-1) &= (9,18,24,27,36,45,48 \ldots), \\
& \Delta(6,-1) = \{3,6,9\}; \\
T(6,0) &= (3,6,12,31,33,39,51 \ldots), \\
&  \Delta(6,0) \text{ (see note below)}; \\
T(6,1) &= (0,1,2,4,5,7,8,10, \ldots), \\
&  \Delta(6,1) = \{1,2\}. \\
\end{align*}
\end{example}
It appears that $\Delta(6,0)$ is a much larger set, for large $n$, than all other sampled $\Delta(c,i)$.  Indeed, it seems possible that if $n$ is not restricted to an upper bound, then $\Delta(6,0)$ is infinite, as suggested by the following data, in which \enquote{newcomers} are bolded:
\begin{align*}
\text{For } n &= 1,\ldots,N=6000,\\
T(6,0) &= \{3,6,9,12,18,24,27,36,39,42,48,51,54,57,66,75,81,93,99, \\
& 111,117,120,123,156,162,198,237,279,354,360,480,531,660 \}.\\
\text{For } n &= 1,\ldots,N=12000, \\
T(6,0) &= \{3,6,9,12,18,24,27,36,39,42,48,51,54,57,66,75,81,93,99,\\
& 111,117,120,123,156,162,\textbf{171},\textbf{180},198,237,279,354,360,480,\\
& 531,660,\textbf{711},\textbf{849},\textbf{1065} \}.\\
\text{For } n &= 1,\ldots,N=16000,\\
T(6,0) &= \{3,6,9,12,18,24,27,36,39,42,48,51,54,57,66,75,81,93,99,\\
& 111,117,120,123,156,162,171,\textbf{174},180,198,\textbf{225},237,\textbf{270},279,\\
& 354,360,480,531,660,711,849,\textbf{1062},1065,\textbf{1092} \}.
\end{align*}


\begin{example}\label{ExE}
For $c=9$, we have $m(c)=-1, M(c)=2$, and
\begin{align*}
T(9,-1) &= (6), \Delta(9,-1) = \text{(empty)}; \\
T(9,0) &= (8,10,11,13,16,20, \ldots), \Delta(9,0) = \{1,2,3,4,6,7\}; \\
T(9,1) &= (0,1,2,3,4,5,6,7,9, \ldots), \Delta(9,1) = \{1,2,3\}; \\
T(9,2) &= (20), \Delta(9,2) = \text{(empty)}.
\end{align*}
\end{example}
In Example \ref{ExE}, $T(9,-1)=(6)$ comes from $a^*_6-a_6=44-45=-1$, and $T(9,2)=(2,0)$ comes from $a^*_{20}-a_{20}=144-142=2$.  Otherwise, for $0 \leq n \leq N=5000$, we have $0 \leq a^*_n-a_n \leq 1$.

For $0 \leq n \leq N=5000$, and perhaps for all $n>N=5000$,
\begin{align*}
& (m(c),M(c))=(0,1) \text{ for } c = 0,1,3,4,5,7,8,10,11,12,13,15,16,17,24,25, \\
& \hspace{6cm} 27,28,32,33,36,48,50,56,57; \\
& (m(c),M(c))=(-1,1) \text{ for } c = 6,14,18,19,20,21,23,26,34,37,39,40,44, \\
& \hspace{6cm} 45,47,55,58; \\
& (m(c),M(c))=(-1,2) \text{ for } c = 9,29,30,31,35,38,41,42,43,49,51,52,53, \\
& \hspace{6cm} 54,59,60; \\
& (m(c),M(c))=(-1,3) \text{ for } c = 22,46. 
\end{align*}
The next three conjectures, based on $N=10000$, suggest that $a^*_n-a_n$ is \enquote{regular} for $c=2,3,5$, (whereas, it appears, the regularity does not extend to $c=4$ or $c=6$).

\begin{conjecture}\label{conjC}
Suppose that $c \geq 0$, and let $(a_n)$ and $(\hat{a}_n)$ be solutions of
$$a_n=b_{2n}+b_{4n} \text{ and } \hat{a}_n=\hat{b}_{2n}+\hat{b}_{4n}+2,$$
respectively.  Then
\begin{equation*}
\hat{a}_n-a_n =
\begin{cases}
2, & \text{if $n \equiv 0\Mod{3} $}; \\
1, & \text{if $n \not\equiv 0\Mod{3} $}.
\end{cases}
\end{equation*}
\end{conjecture}

\begin{conjecture}\label{conjD}
Suppose that $c \geq 0$, and let $(a_n)$ and $(\hat{a}_n)$ be solutions of
$$a_n=b_{2n}+b_{4n} \text{ and } \hat{a}_n=\hat{b}_{2n}+\hat{b}_{4n}+3,$$
respectively.  Then
\begin{equation*}
\hat{a}_n-a_ n=
\begin{cases}
3, & \text{if $n \equiv 0\Mod{3} $}; \\
2, & \text{if $n \not\equiv 0\Mod{3} $}.
\end{cases}
\end{equation*}
\end{conjecture}

\begin{conjecture}\label{conjE}
Suppose that $c \geq 0$, and let $(a_n)$ and $(\hat{a}_n)$ be solutions of
$$a_n=b_{2n}+b_{4n} \text{ and } \hat{a}_n=\hat{b}_{2n}+\hat{b}_{4n}+5,$$
respectively.  Then
\begin{equation*}
\hat{a}_n-a_n =
\begin{cases}
5, & \text{if $n \equiv 0\Mod{3} $}; \\
3, & \text{if $n \not\equiv 0\Mod{3} $}.
\end{cases}
\end{equation*}
\end{conjecture}

\section{The equation $a_n=b_n+b_{2n}$}\label{compeq3}
In contrast to results in Section~\ref{compeq1}, we find less \enquote{regularity} in the present section.


\begin{theorem}\label{nand2nd}
The solution of the complementary equation $a_n=b_n+b_{2n}$, with $b_0=1$, satisfies the following conditions for all $n \geq 0$ and $i \geq 0$:
\begin{align*}
4n+2 \leq a_n &\leq 4n+3, \\
 b_{3i} &= 4i+1, \\
4i+2 \leq b_{3i+1} &\leq 4i+3, \\
b_{3i+2} &= 4i+4.
\end{align*}
\end{theorem}

\begin{proof}
We paraphrase a proof given in MathOverflow \cite{IB}.  Clearly the inequality
\begin{equation}\label{eq:induct}
4n+2 \leq a_n \leq 4n+3
\end{equation}
holds for $n \in \{0,1,2\}$.  We assume (\ref{eq:induct}) as an induction hypothesis for $n \geq 2$. For convenience the phrase \enquote{is in $a$} will refer to terms of the sequence $a$, and likewise for $b$. We have three cases.

\bigskip\noindent
\textbf{Case 1:} $n=3i$.  By the induction hypothesis,
\begin{equation}\label{eq:A*}
4i-2 \leq a_{i-1} \leq 4i-1,
\end{equation}
so that the number of terms $a_m$ that are $\leq 4i-1$ is $i$. (Specifically, these $i$ numbers are $a_0,a_1,\ldots,a_{i-1}$.)  Since every integer in $[1,4i-1]$ is in $a$ or $b$, the number of terms $b_m$ that are $\leq 4i-1$ is $(4i-1)i-i=3i-1$. By (\ref{eq:A*}), the numbers $4i$ and $4i+1$ are also in $b$, so that the number of terms $b_m$ in $[1,4i+1]$ is $3i+1$.  These numbers are $b_0,b_1,\ldots,b_{3i}$, so that $b_{3i}=4i+1$.

\bigskip\noindent
\textbf{Case 2:} $n=3i+1$.  By the induction hypothesis,
\begin{equation*}
4i+2 \leq a_i \leq 4i+3,
\end{equation*}
and $a_{i+1} \geq 4i+6$, so that there are exactly $i+1$ terms $a_m$ in $[1,4i+3]$.  Therefore, there are exactly $4i+5-(i+1)=3i+4$ terms $b_m$ that are $\leq 4i+5$, specifically,
$b_0,b_1,\ldots b_{3i+3}$. By the induction hypothesis,

\begin{equation}\label{eq:A**}
4i+6 \leq a_{i+1} \leq 4i+7,
\end{equation}
so that there are at most $i+1$ terms $a_m$ in $[1,b_{i+3}]$.  (Otherwise, $a_{i+1} \in [1,b_{i+3}]$, so that $a_{i+1} \leq b_{3i+3}$, contrary to the already proved inequality $b_{3i+3} \leq 4i+5 < a_{i+1}$). Since $b_{3i+3} \leq 4i+5$, and since, by (\ref{eq:A**}), $4i+4$ and $4i+5$ are in $b$, we have $b_{3i+2}=4i+4$ and $b_{3i+3}=4i+5$, so that

\begin{equation}\label{eq:A***}
b_{3i+1} \leq 4i+3.
\end{equation}

We turn now to a proof that $b_{3i+1} \geq 4i+2$. Every integer in $[1,4i]$ is in $a$ or $b$, and since (by the induction hypothesis) $a_{i-1} \leq 4i-1$, there are at least $i$ terms $a_m$ that are $ \leq 4i-1$, hence at most $(4i-1)-i=3i-1$ terms $b_m$ in $[1,4i-1]$. Since
$$ a_{i-1} \leq 4i-1 < 4i+2 \leq a_i,$$
the numbers $4i$ and $4i+1$ are in $b$. There are, therefore, at most $3i+1$ terms $b_m$ in $[1,4i+1]$.  We have
$$b_0 < b_1 < b_2 < \cdots b_{3i} \leq 4i+1$$
and $b_{3i+1} > 4i+1$.  Thus, $b_{3i+1} \geq 4i+2$.

\bigskip\noindent
\textbf{Case 3:} $n=3i+2$.  By the induction hypothesis, $a_{i+1} \geq 4i+6$, so that, since
$$ 4i+2 \leq a_i \leq 4i+3,$$
the number of terms $a_m$ that are $\leq 4i+3$ is $i+1$.  Since every integer in $[1,4i+3]$ is in $a$ or $b$, the number of terms $b_m$ that are $\leq 4i+3$ is $4i+3-(i-1)=3i+2$. The induction hypothesis implies
$$a_i \leq 4i+3 < 4i+6 < a_{i+1},$$
so that $4i+4$ is in $b$.  We have thus counted a total of $3i+3$ terms $b_m$ in $[1,4i+4]$; they are
$$b_0, b_1,\ldots , b_{3i+2},$$
so that $b_{3i+2}=4i+4$.

We now finish the induction for establishing (\ref{eq:induct}):
\begin{align*}
4(k+1)+\frac{10}{3} &= \frac{4(k+1)+5}{3}+\frac{4(2k+2)+5}{3} \\
&\geq b_{k+1}+b_{2k+2} \\
&= a_{k+1} \\
&\geq  \frac{4(k+1)+2}{3}+\frac{4(2k+2)+2}{3} \\
&= 4(k+1)+\frac{4}{3}.
\end{align*}
Since $a_{k+1}$ is an integer, the inequality
$$4(k+1)+\frac{10}{3} \geq a_{k+1} \geq 4(k+1)+\frac{4}{3}$$
implies
$$4(k+1)+2 \leq a_{k+1} \leq 4(k+1)+3.$$
\end{proof}

The irregular subsequence of the sequence
$$b = (1,3,4,5,6,8,9,11,12,13,15,16,17,19,20,21,22,24,25,27, \ldots$$
in Theorem \ref{nand2nd} is
\begin{equation}\label{eq:ess}
s(i):=(b_{3i+1})=(3,6,11,15,19,22,27,30,35,39,42,47,51,54,67, \ldots ),
\end{equation}
for which $4i+2 \leq s(i) \leq 4i+3$; indeed,
\begin{equation*}
s_i = \begin{cases}
4i+2, & \text{if } i = 2,6,8,11,14,15,18,20,24,26,29,33,35,38,42, \ldots \\
4i+3, & \text{if } i = 1,3,4,5,7,9,10,12,13,16,17,19,21,22,23,25, \ldots .
\end{cases}
\end{equation*}

Following are two conjectures based on Program \ref{Program4}, with $n$ ranging from $1$ to $50000$.
\begin{conjecture}\label{conjF}
The difference sequence of the above sequence
$$(2,6,8,11,14,15,18, \ldots)$$
has only five distinct terms: $1,2,3,4,5$.
\end{conjecture}
The least $n$ for which all five differences occur in Conjecture \ref{conjF} is $111$.


\begin{conjecture}\label{conjG}
The limiting proportion of $s_i$'s of the form $4i+2$ is $2/5$.
\end{conjecture}

\section{The equation $a_n=ub_n+vb_{n+k}+c$}\label{compeq4}
The preceding sections show that some complementary equations with advanced subscripts are easily solved, whereas others involve a multitude of cases and irregularities.  Here we consider equations of the form
\begin{equation}\label{eq:eqq}
a_n=ub_n+vb_{n+k}+c, \text{ where } b_0=1,
\end{equation}
where $u, v,$ and $c$ are integers satisfying $k \geq 1$ and $1 \leq u \leq v$, and we find the same sort of regularities and irregularities.  Let
$$x=\lim_{n\to\infty}{a_n/n} \text{ and } y=\lim_{n\to\infty}{b_n/n}.$$
Then (\ref{eq:eqq}) together with $1/x+1/y=1$, yields
$$x=u+v+1 \text{ and } y=(u+v+1)/(u+v).$$

Table \ref{Table5}, generated by Program \ref{Program5}, shows in columns 4 and 5 the minimum and maximum values of $a_n-(u+v+1)n$ for $n=0,1,\ldots, 100000$. Also, Table \ref{Table5} indicates that for $u=v=1$,
$$\max\{a_n-3n\}=a_0=k+2,$$
but that the sequence $(m(n))=(\min\{a_n-3n\})$ is not so predictable, as indicated by its first $22$ terms:
$$3,3,4,4,5,6,6,7,8,8,9,10,10,11,11,12,13,13,14,14,15,16.$$
\begin{table}[H]
\begin{center}
\begin{tabular}{|cccrcc|}
\hline
$u$ & $v$ & $k$ & $\min$ & $\max$ & $a_0$ \\
\hline
$1$ & $1$ & $1$ & $3$ & $3$ & $3$ \\
$1$ & $2$ & $1$ & $-1$ & $10$ & $5$ \\
$1$ & $3$ & $1$ & $-3$ & $15$ & $7$ \\
$1$ & $4$ & $1$ & $-5$ & $18$ & $9$ \\
$1$ & $5$ & $1$ & $-5$ & $23$ & $11$ \\
$2$ & $1$ & $1$ & $-1$ & $9$ & $4$ \\
$3$ & $1$ & $1$ & $-3$ & $13$ & $5$ \\
$4$ & $1$ & $1$ & $-6$ & $15$ & $6$ \\
$5$ & $1$ & $1$ & $-6$ & $19$ & $7$ \\
$2$ & $3$ & $1$ & $-6$ & $17$ & $8$ \\
$3$ & $2$ & $1$ & $-6$ & $16$ & $7$ \\
$2$ & $2$ & $1$ & $-3$ & $14$ & $6$ \\
$3$ & $3$ & $1$ & $-5$ & $21$ & $9$ \\
$1$ & $1$ & $2$ & $3$ & $4$ & $4$ \\
$1$ & $1$ & $3$ & $4$ & $5$ & $5$ \\
$1$ & $1$ & $4$ & $4$ & $6$ & $6$ \\
$1$ & $1$ & $5$ & $5$ & $7$ & $7$ \\
$1$ & $1$ & $6$ & $6$ & $8$ & $8$ \\
$1$ & $1$ & $7$ & $6$ & $9$ & $9$ \\
\hline
\end{tabular}
\caption{$a_n=ub_n+vb_{n+k}, b_0=1$\label{Table5}}
\end{center}
\end{table}

As already noted, Table \ref{Table5} and further explorations suggest that if $u>1$ or $v>1$, then both $\min$ and $\max$ are unbounded. Taking $(u,v,k)=(1,2,1)$ as an example, we have $(\min,\max)= (-1,10)$
when $N=100000$. The appearance of $(N,m,M)$ in the following list means that as $n$ ranges from $1$ to $N$, the minimal and maximal differences $a_n-(u+v+1)n$ are $m$ and $M$:
\begin{align*}
& (100,2,7), (300,1,7), (600,1,7), (700,1,8), \\ 
& (1900,1,8), (2000,0,8), (5000,0,8), (6000,0,9),\\
& (20000,-1,9), (10000,-1,10), (200000,-2,10)
\end{align*} 

Theorem \ref{exist}, with $f(x,y)=ux+vy+c$, ensures a unique solution of (\ref{eq:eqq}) if $c \geq 2-u-v$.  This is the case, for example, for the equation $a_n=b_n+2b_{n+1}+c$ when $c=-1$.  It is easy to check, however, that this equation also has a unique solution for $c=-2$, but not for $c=-3$.  This example raises a question to which we respond with another conjecture:

\begin{conjecture}\label{conjH}
The equation (\ref{eq:eqq}), where $b_0=1$, has a unique solution if and only if
\begin{equation*}
c \geq 2-u-v+k-vk.
\end{equation*}
\end{conjecture}

Results shown in Table \ref{Table5} and experimentation suggest that if $(u,v)=(1,1)$, then $\min\{a_n-(u+v+1)n\}$ and $\max\{a_n-(u+v+1)n\}$ are as indicated in Table \ref{Table5} and that otherwise, both are unbounded.

We turn now to equations in which $c \neq 0$. Indeed, we take $c$ to be the least value for which the equation (\ref{eq:eqq}) has a solution; i.e., $c = 2-u-v+k-vk$. Table \ref{Table6}, generated by Program \ref{Program6}, shows the minimum and maximum values of $a_n-(u+v+1)n$ for $n=0,1,\ldots, 100000$.
\begin{table}[H]
\begin{center}
\begin{tabular}{|cccrrcc|}
\hline
$u$ & $v$ & $k$ & $c$ & $\min$ & $\max$ & $a_0$ \\
\hline
$1$ & $2$ & $1$ & $-2$ & $-2$ & $9$ & $3$ \\
$1$ & $2$ & $2$ & $-3$ & $-1$ & $10$ & $4$ \\
$1$ & $2$ & $3$ & $-4$ & $0$ & $10$ & $5$ \\
$2$ & $1$ & $1$ & $-1$ & $-2$ & $8$ & $3$ \\
$2$ & $2$ & $1$ & $-3$ & $-5$ & $12$ & $3$ \\
$2$ & $2$ & $2$ & $-4$ & $0$ & $9$ & $4$ \\
$2$ & $1$ & $3$ & $-1$ & $0$ & $10$ & $5$ \\
$3$ & $3$ & $1$ & $-6$ & $-9$ & $17$ & $3$ \\
$3$ & $3$ & $2$ & $-8$ & $-5$ & $15$ & $4$ \\
$3$ & $3$ & $3$ & $-10$ & $-1$ & $13$ & $5$ \\
\hline
\end{tabular}
\caption{$a_n=ub_n+vb_{n+k}+c, b_0=1$\label{Table6}}
\end{center}
\end{table}

As might be expected from the discussion about Table \ref{Table5}, it appears likely that minimum and maximum values represented in columns $5$ and $6$ of Table \ref{Table6} are unbounded. 

\section{{\tt Mathematica} programs}\label{programs}

The examples and conjectures in the preceding sections are based on six 
{\tt Mathematica programs} in which the parameters $h,k,c,u,v,$ and $z$ can be varied. Each program depends on the $\mex$ function mentioned near the end of Section~\ref{AdvSub}.

\subsection{Program for Table \ref{Table2}}\label{Program1}
The parameters $z,c,h,k$ are set by the first two lines of code.  Keep $c=0$. Decrease $z$ to $100$ for a first run. To see row 4 of Table \ref{Table2}, for example, use $h=3$ and $k=6$. When experimenting, use larger $z$ for larger $h$ and $k$.
\begin{verbatim}
z = 1000; c = 0;
h = 2; k = 4;
mex[list_, start_] := (NestWhile[# + 1 &, start, 
MemberQ[list, #] &]);
a = {}; b = {1}; AppendTo[a, c + mex[Flatten[{a, b}], 1]];
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
  AppendTo[a, c + Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
"Sequence (a(n)), from a(n)=a(h*n)+b(k*n):"
a ; Take[a, 100]
\end{verbatim}

\subsection{Program for Table \ref{Table3}}\label{Program2}
The parameters are set to generate row 7 of Table~\ref{Table3}. When experimenting, use larger $z$ for larger $h$, $k$, and $c$.
\begin{verbatim}
z = 1000;
h = 2; k = 4; c = 6;
mex[list_, start_] := (NestWhile[# + 1 &, start, 
MemberQ[list, #] &]);
a = {}; b = {1}; AppendTo[a, c + mex[Flatten[{a, b}], 1]];
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
  AppendTo[a, c + Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
"Sequence (a^*(n)), from a(n)=a(h*n)+b(k*n)+c, where c = 1:"
a ; Take[a, 100]
\end{verbatim}

Data supporting Conjecture \ref{conjB} can be obtained by adding the following lines at the end of this program:
\begin{verbatim}
r = Select[Range[400], Mod[a[[# + 1]], 7] ==4 &] 
(* r is the sequence just before Conjecture 8. *)
d = Differences[s]
Union[d]
\end{verbatim}


\subsection{Program for Table \ref{Table4}}\label{Program3}
The parameters are set to show frequencies $27,61,73,\ldots$, with $z=1000$. The runtime is considerably longer for $z=10000$, as in Table \ref{Table4}.
\begin{verbatim}
z = 1000; c = 0;
mex[list_, start_] := (NestWhile[# + 1 &, start, 
MemberQ[list, #] &]);
h = 2; k = 4; a = {}; b = {1};
AppendTo[a, c + mex[Flatten[{a, b}], 1]];
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
  AppendTo[a, c + Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
"Sequence (a(n)), from a(n)=a(h*n)+b(k*n)+c, where c = 0:"
a; a1 = a; Take[a, 50]
c = 1; a = {}; b = {1};
AppendTo[a, c + mex[Flatten[{a, b}], 1]]; 90
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
  AppendTo[a, c + Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
"Sequence (a^*(n)), from a(n)=a(h*n)+b(k*n)+c"
a ; Take[a, 50]
"Distinct differences, a(n)^* - a(n):"
Union[a - a1]
p = Differences[Flatten[Position[a - a1, 0]]]; Take[ p, 100]
"Number of occurrences of each difference:"
t = Table[Count[p, k], {k, 1, 13}]
\end{verbatim}

\subsection{Program for Conjectures \ref{conjF} and \ref{conjG}}\label{Program4}
The parameters are set to output the sequence on Conjecture \ref{conjF}. The code can be easily extended to support Conjecture \ref{conjG}.
\begin{verbatim}
mex[list_, start_] := (NestWhile[# + 1 &, start, 
MemberQ[list, #] &]);
h = 1; k = 2; a = {}; b = {1}; z = 2000;
AppendTo[a, mex[Flatten[{a, b}], 1]];
Do[Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
  AppendTo[a, Last[b] + b[[1 + (Length[b] - 1)/k h]]], {z}];
Take[b, 50]
bb = b; Clear[b];(*next,re-index b with offset 0*)
b[n_] := bb[[n + 1]]; u = Table[b[3 i + 1], 
{i, 0, -1 + Length[bb]/3}];
Take[u, 100]
t = Mod[u, 4]; p = Flatten[Position[t, 2]];
Take[p, 100]
d = Differences[p];
Union[d] (* set of distinct differences *)
\end{verbatim}

\subsection{Program for Table \ref{Table5}}\label{Program5}
The parameters $u,v,k,c,$ and $z$ are set to show $\{0,9\}$ as minimal and maximal differences; to get $\{-1,10\}$,m as in row 2 of Table \ref{Table5}, use $z=100000$, and wait.
\begin{verbatim}
z = 10000;
mex[list_, start_] := (NestWhile[# + 1 &, start, 
MemberQ[list, #] &]);
 {u, v, k, c} = {1, 2, 1, 0}; {a, b} = {{}, {1}};
Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}];
AppendTo[a, u b[[1]] + v b[[k + 1]] + c];
Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]];
  AppendTo[a, u b[[n]] + v b[[k + n]] + c], {n, 2, z}];
Take[a, 60];
Take[b, 60];
Intersection[a, b];
aa[n_] := a[[n + 1]];
t = Table[aa[n] - (u + v + 1) n, {n, 0, z - 2}];
{Min[t], Max[t]}
\end{verbatim}

\subsection{Program for Table \ref{Table6}}\label{Program6}
The parameters $u,v,k,c,$ and $z$ are set to show $\{-1,8\}$ as minimal and maximal differences; to get $\{-2,9\}$,m as in row 1 of Table \ref{Table6}, use $z=100000$, and wait.
\begin{verbatim}
z = 10000;
mex[list_, start_] := (NestWhile[# + 1 &, start, 
MemberQ[list, #] &]);
 {u, v, k, c} = {1, 2, 1, -2}; {a, b} = {{}, {1}};
Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]], {k}]
AppendTo[a, u b[[1]] + v b[[k + 1]] + c];
Do[AppendTo[b, mex[Flatten[{a, b}], Last[b]]];
  AppendTo[a, u b[[n]] + v b[[k + n]] + c], {n, 2, z}];
Take[a, 60]
Take[b, 60]
Intersection[a, b]
aa[n_] := a[[n + 1]];
t = Table[aa[n] - (u + v + 1) n, {n, 0, z - 2}];
{Min[t], Max[t]}
Flatten[Position[t, Min[t]]]
Flatten[Position[t, Max[t]]]
\end{verbatim}

\section{Acknowledgments}
We thank the referee for their valuable comments and suggestions. We also thank Neil J. A. Sloane and the many contributors to the 
{\it On-line Encyclopedia of Integer Sequences}. 

\begin{thebibliography}{99}

\bibitem{IB} Ilya Bogdanov, Answer for \enquote{Simple-looking sequences
$A$ and $B$ defined by a complementary equation}, 2019. Available at
\url{https://tinyurl.com/1j1zv6u5}.

\bibitem{IB1} Ilya Bogdanov, Answer for \enquote{Difference of
two integer sequences: all zeros and ones?}, 2019. Available at
\url{https:tinyurl.com/5yu5hddw}.

\bibitem{Fr&P} A. Fraenkel and U. Peled, Harnessing the unwieldy MEX function, in \textit{Games of No Chance 4,} Richard J. Nowakowski, editor, 
Mathematical Sciences Research Institute Publications 63, 
Cambridge University Press, 2007, pp.~77--94.

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

\bibitem{Kim2} C. Kimberling, Complementary equations and Wythoff
sequences, \textit{J. Integer Sequences}, 
{\bf 11} (2008), \href{https://cs.uwaterloo.ca/journals/JIS/VOL11/Kimberling/kimberling719a.html}{Article 08.3.3}.

\bibitem{OEIS} N. J. A.  Sloane et al., \textit {The On-Line Encyclopedia of Integer Sequences}, 2020.  Available at
\url{https://oeis.org/}.

\end{thebibliography}

\bigskip
\hrule\bigskip
\noindent 2010 \textit{Mathematics Subject Classification}:
Primary 11B37.

\noindent \textit{Keywords: }
complementary equation, complementary sequence.

\noindent (Concerned with sequences
\seqnum{A304799},
\seqnum{A304800},
\seqnum{A304801},
\seqnum{A304802},
\seqnum{A304803},
\seqnum{A304804},
\seqnum{A304805},
\seqnum{A304806},
\seqnum{A304807},
\seqnum{A304808},
\seqnum{A304809},
\seqnum{A304810},
\seqnum{A304811},
\seqnum{A304812},
\seqnum{A304813},
\seqnum{A304814},
\seqnum{A304815},
\seqnum{A304816},
\seqnum{A309156}, and
\seqnum{A326661}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  December 2 2020;
revised version received  February 6 2021.
Published in {\it Journal of Integer Sequences}, February 6 2021.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


