\documentclass[12pt,reqno]{article}

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

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

\begin{document}

\begin{center}
\includegraphics[width=4in]{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 Van der Laan Sequences and a \\
\vskip .11in
Conjecture on Padovan Numbers} \vskip 1cm \large
David Nacin\\
Department of Mathematics\\
William Paterson University\\
Wayne, NJ   07470 \\
USA\\
\href{mailto:nacind@wpunj.edu}{\tt nacind@wpunj.edu}
\end{center}
\vskip .2 in


\begin{abstract}
The Padovan sequence has the property that the largest of any four
consecutive terms equals the sum of the two smallest.  We examine when
sequences with this property can merge with multiples of the Padovan
sequence, and show that any increasing sequence with this property is
a linear combination of Padovan sequences.  We then show that linear
combinations of Fibonacci numbers arise when we weaken the condition to
sequences that increase following certain permutation patterns.
\end{abstract}


\section{Introduction}

The Padovan sequence $p(n)$ is defined by $p(0)=1,$ $p(1)=p(2)=0,$ and $$p(n) = p(n-2) + p(n-3)$$ for all $n \geq 2$.  Beginning with $$1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151,  \ldots,$$ it is sequence \seqnum{A000931} in the On-Line Encyclopedia of Integer Sequences (OEIS) \cite{oeis}.  It arises as a solution to many counting problems and also as the side lengths of the spiral of equilateral triangles shown in Figure \ref{pad}, in a similar construction to the famous spiral of squares that generates the Fibonacci sequence \seqnum{A000045} \cite{spiral}. 
\begin{figure}[ht]
    \centering
    \includegraphics[width = .6\textwidth]{pad01.pdf} 
    \caption{The Padovan sequence from a spiral of equilateral triangles.}
    \label{pad}
\end{figure}
 
The following conjecture was found in the OEIS entry for this sequence.
\begin{conjecture}
If a sequence of non-negative integers has the property that the largest of any four consecutive terms equals the sum of the two smallest then the sequence is either identically zero or merges with the present sequence or an integer multiple of it (such as \seqnum{A291289}) after a finite number of steps. This must be a well-known property, and it would be nice to have a reference.
\end{conjecture} 
For convenience, from here on we refer to any non-negative sequence with this property as being \textit{Van der Laan}.  The Padovan sequence was discovered by its creator, the Dutch architect, mathematician, and Benedictine monk, Hans van der Laan in his studies of the ratios that he felt marked the boundaries of human perception \cite{RichardPadovan}.  

The conjecture is false. Counterexamples include \seqnum{A177704}:
$$1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2, \ldots$$
and \seqnum{A328943}:
$$2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,  \ldots.$$ 
Restricting the conjecture to unbounded sequences still leads to counterexamples such as \seqnum{A321341}:
$$2,2,1,3,3,   4,1,4,    5,5,1,6,6,   7,1,7,   8,8,1,9,9,   10,1,10, 11,11,1,12,12,  \ldots$$
and  \seqnum{A321664}:
$$0, 1, 1, 1, 2, 1, 2, 3, 2, 4, 5, 3, 7, 8, 5, 12, 13, 8, 20, 21, 13, 33, 34, 21, 54,55, 34,  \ldots \ .$$
The former shows an example that is not only unbounded but contains every natural number and is equal to one infinitely often.  The latter sequence is glued together from three copies of the Fibonacci sequence, one of which has been shifted down by one.

These sequences lead to more questions that we begin to address next.  

\begin{itemize}
\item Which increasing Van der Laan sequences merge with multiples of the Padovan sequence?
\item Can we classify all increasing Van der Laan sequences in some way?
\item What about Van der Laan sequences such as \seqnum{A321664}, which are close to increasing in some way?
\item Is there a Van der Laan sequence consisting of only Fibonacci numbers?
\item Do the Fibonacci numbers arise here in any sort of natural way?
\end{itemize}

\section{Increasing Van der Laan sequences}

If a Van der Laan sequence is increasing then any four consecutive terms must begin with the two smallest and end in the largest. The sequence must then satisfy the same recurrence as the Padovan numbers 
\begin{equation}
a(n) = a(n-2) + a(n-3) \label{sameaspad}
\end{equation}
for all values of $n$ where the sequence is defined.  If any three consecutive terms share a common factor then the entire sequence shares that factor.  In fact, no such sequence can merge with a multiple of the Padovan sequence without the entire sequence being a multiple of the Padovan sequence.  If the sequence $a(n)$ merges with an integer multiple of the Padovan sequence, it satisfies $$a(i) = cp(i+k)$$ for some constant integer $c$ and for all $i>n$.  Then $$a(n) = a(n+3) - a(n+1) = cp(n+3+k) - cp(n+1+k) = cp(n+k),$$ and by well ordering, it must satisfy the relation for all $i$.  We have shown the following:
\begin{proposition}
The only increasing Van der Laan sequences that merge with multiples of the Padovan sequence are the multiples of the Padovan sequence.
\end{proposition}

Note that it is perfectly possible for a non-increasing Van der Laan sequence to merge with the Padovan sequence.  The sequence 
$$4, 3, 2, 2, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151,  \ldots$$
is one such example.

It is not hard to find all increasing Van der Laan sequences.  The following proposition follows directly by induction, Eq.~\eqref{sameaspad}, and the first three entries of the sequence.
\begin{proposition}
Any increasing Van der Laan sequence $a(n)$ is of the form
$$a(n) = \alpha p(n-1) + \beta p(n+1) + \gamma p(n)$$
for all $n \geq 1$, where $\alpha \leq \beta \leq \gamma$ and
$p(n)$ is the Padovan sequence.
\end{proposition}

Setting $\alpha=\beta=\gamma=1$ in this lemma gives us the original Padovan sequence.  It allows us to restate the original conjecture that inspired this paper as follows.

\begin{quote}
If an \textit{increasing} sequence of non-negative integers has the property that the largest of any four consecutive terms equals the sum of the two smallest, then the sequence is a linear combination of three  copies of the Padovan sequence.
\end{quote}

\section{Permutation pattern increasing sequences}

Let us return our attention to the ``mostly Fibonacci'' counterexample 
$$0, 1, 1, 1, 2, 1, 2, 3, 2, 4, 5, 3, 7, 8, 5, 12, 13, 8, 20, 21, 13, 33, 34, 21, 54, 55, 34,  \ldots$$
which is not increasing but instead follows an ``up-up-down'' pattern.  
It can be defined on the non-negative integers by
$$\begin{array}{lcl}
a(3n)& = &f(n+2)-1 \\
a(3n+1)& = &f(n+2) \\
a(3n+2)& = &f(n+1),\\
 \end{array} $$ 
where $f(n)$ is the standard Fibonacci sequence defined by $$f(0) = 0, f(1) = 1,f(n+2) = f(n+1) + f(n).$$  This sequence is Van der Laan, contains two disjoint copies  and one shifted copy of the Fibonacci numbers, and has a strict up-up-down pattern in the sense that $$f(3n-1) \leq f(3n) \leq f(3n+1),$$ $$f(3n+1) \geq f(3n+2).$$  To define things precisely, we will borrow some terminology from permutation patterns. 
\begin{figure}[ht]
    \centering
    \includegraphics[height = .31\textheight]{pp00.pdf} 
    \caption{A $(2,3,1)$-increasing sequence.}
\end{figure}

\begin{definition}
Let $\sigma$ be any permutation of $[m] = \{1, 2, \ldots, m\}$ and $\sigma(i)$ be the $i^{\textrm{th}}$ entry of $\sigma$.  Then a series $a(n)$ is \textit{$\sigma$-increasing} if for any non-negative integer $k$ and and $i \neq j$ in $[m]$, then 
\begin{itemize}
\item $a(mk+i) \leq a(mk+j)$ if and only if $\sigma(i)<\sigma(j)$   
\item $a(mk+i) \leq a(ml+j)$ if $k < l$.
\end{itemize}
\end{definition}

For example, our Fibonacci counterexample above is $(2,3,1)$-increasing because $a(3k+1)$ is greater than or equal to  $a(3k)$ and $a(3k+2)$ for all $k$ and $a(3k) \geq a(3k+2)$ and each group $a(3k),a(3k+1),a(3k+2)$ is greater than or equal to the three previous consecutive terms.  Our inequalities for $a(n)$ are intentionally not strict, as this makes things slightly more general.

The appearance of some form of Fibonacci numbers in sequences like this is not just the result of careful design, but inevitable to a certain extent.  Beginning the Fibonacci sequence at index $-1$ so $f(-1)=1, f(0)=0, f(n+2)=f(n+1)+f(n)$, we get the following proposition.
\begin{proposition}
Every $(2,3,1)$-increasing Van der Laan sequence is of the form
$$\begin{array}{lcl}
a(3n+1)& = &\alpha + \beta (f(n+1)-1)+ \gamma f(n) \\
a(3n+2)& = &\beta f(n+1)+ \gamma f(n) \\
a(3n+3)& = &\beta f(n)+ \gamma f(n-1)\\
 \end{array} $$ 
for some $\beta \geq \alpha \geq \gamma$ and all $n \geq 0$.
\end{proposition}


\begin{proof}
For any $k \geq 1$, both $$a(3k) \leq a(3k-1) \leq a(3k+1) \leq (3k+2)$$ and 
$$a(3k) \leq a(3k+3) \leq a(3k+1) \leq (3k+2)$$ are sets of consecutive numbers with largest 
term $a(3k+2)$, so their smallest two terms must be equal.  This implies $$a(3k)+a(3k-1)=a(3k)+a(3k+3)$$
and thus $a(3k-1)=a(3k+3)$.   

Our sequence thus follows the pattern shown in Figure \ref{a(3k+3)}.  This together with the $(2,3,1)$-increasing condition tells us that 
$$\begin{array}{lcl}
a(3k+1)& = & a(3k-2)+a(3k) \\
a(3k+2)& = &a(3k-1)+a(3k) \\
a(3k+3)& = &a(3k-1)\\
\end{array} $$ for all $k>1$.
 
\begin{figure}[ht]
    \centering
    \includegraphics[height = .26\textheight]{pp01.pdf} 
    \caption{A $(2,3,1)$-increasing sequence with $a(3k-1)=a(3k+3)$ for all $k \geq 1$.}
    \label{a(3k+3)}
\end{figure}

The full result now follows from induction together with the fact that any $(2,3,1)$-increasing sequence begins with three terms that can be written in the form $$a(1)=\alpha + \beta (f(1)-1), a(2)=\beta f(1), a(3)=\gamma f(-1)$$ for some $\alpha, \beta, \gamma$.
\end{proof}

The series in the beginning of this section has some Fibonacci numbers appearing directly, because it is the case where $a=b=c=1$.  We can actually use this to answer one of our main questions.  Although we cannot let $\beta$ be zero to remove the $f(n+1)-1$ term, without setting $\alpha$ and $\gamma$ to zero as well, if we set $\alpha = \beta = 1$ and $\gamma = 0$ we get sequence \seqnum{A327035}
$$1, 1, 0, 1, 1, 1, 2, 2, 1, 3, 3, 2, 5, 5, 3, 8, 8, 5, 13, 13, 8, 21, 21, 13, 34, 34, 21, \ldots, $$
which is composed entirely of Fibonacci numbers.

At this point we might ask what happens in the other permutation pattern increasing cases as well.  Before we jump to the other order three permutations, we can ask what happens for the two order two permutations.  The permutation $(1,2)$ just gives the increasing case from the previous section leaving us with one more order two case to consider.  
\begin{proposition}
The only $(2,1)$-increasing Van der Laan sequence is the zero sequence. \label{just(2,1)}
\end{proposition}
\begin{proof}
\begin{figure}[ht]
    \centering
    \includegraphics[height = .21\textheight]{pp02.pdf} 
    \caption{A $(2,1)$-increasing sequence.}
    \label{(2,1)-inc}
\end{figure}
As shown in Figure \ref{(2,1)-inc}, for all $k \geq 1$,
$$a(2k) \leq a(2k+2) \leq a(2k+1) \leq a(2k+3)$$
and
$$a(2k+2) \leq a(2k+1) \leq a(2k+4) \leq a(2k+3)$$
are both sets of consecutive terms with highest term $a(2k+3)$.  Therefore $$a(2k) + a(2k+2) = a(2k+2) + a(2k+1),$$ which shows that $a(2k) = a(2k+1)$.  Since $$a(2k+1) \geq a(2k-1) \geq a(2k)$$ we can conclude that $$a(2k+1) = a(2k-1) = a(2k).$$  This shows the sequence is constant, and the Van der Laan condition implies it must be identically zero.
\end{proof}

Aside from a first term, the $(1,3,2)$ and $(2,1,3)$-increasing cases are both equivalent up to a shift in index, as we can see in Figure \ref{2eq}.  However, together with the $(3,1,2)$-increasing case, all three are identical to the zero case.  The proofs are basically the same as Proposition \ref{just(2,1)}.  This leaves one case left, that of $(3,2,1)$-increasing sequences.  
\begin{proposition}
Every $(3,2,1)$-increasing Van der Laan sequence is of the form
$$\begin{array}{lcl}
a(3n+1)& = & \alpha f(n+1) + \beta f(n)\\
a(3n+2)& = & \alpha f(n+1) + \beta f(n) \\
a(3n+3)& = & \alpha f(n) + \beta f(n-1)\\
 \end{array} $$ 
for some $\alpha \geq \beta$ and all $n \geq 0$.
\end{proposition}

\begin{figure}[ht]
    \centering
    \includegraphics[height = .21\textheight]{pp03.pdf} 
    \caption{The $(1,3,2)$ and $(2,1,3)$-increasing cases.}
    \label{2eq}
\end{figure}

We leave out the proof of this result since it is a slightly easier
version of the same argument done for the $(2,3,1)$-increasing case.
In fact, the final result here is simply the case where $\alpha = \beta$
in the result of that theorem.

In conclusion, for any permutation $\alpha$ of degree three or less, an $\alpha$-increasing Van der Laan sequence must be either increasing, and hence a linear combination of three Padovan sequences, a linear combination of Fibonacci sequences with one possible shifted by a constant, or identically zero.  Perhaps more importantly, we see that the Fibonacci sequence arises in a natural way when examining Van der Laan sequences with different growth patterns. 

\begin{thebibliography}{9}
\bibitem{spiral} T. Edgar and D. Nacin, A visual tour of identities for the Padovan sequence,
\textit{Math. Intelligencer} \textbf{44} (2022), 111--118.

\bibitem{RichardPadovan} R. Padovan, Dom Hans van der Laan and the
plastic number, \textit{Nexus IV: Architecture and Mathematics}, Kim
Williams Books, 2002, pp.\ 181--193.

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

\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary 11B39;
 Secondary 05A05, 11B83, 11B37, 00A08.

\noindent \emph{Keywords:}  Padovan number, Fibonacci number, permutation pattern.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A000931},
\seqnum{A177704},
\seqnum{A291289},
\seqnum{A321341},
\seqnum{A321664},
\seqnum{A327035}, and
\seqnum{A328943}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 10 2022;
revised version received December 27 2022.  
Published in {\it Journal of Integer Sequences}, December 30 2022.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

