\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{xcolor}
\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}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{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}
\newcommand\be{\begin{equation}}
\newcommand\ee{\end{equation}}
\newcommand\bn{\begin{eqnarray}}
\newcommand\en{\end{eqnarray}}
\newcommand\bns{\begin{eqnarray*}}
\newcommand\ens{\end{eqnarray*}}
\renewcommand*{\thefootnote}{\fnsymbol{footnote}}
\begin{center}
\vskip 1cm{\LARGE{\bf An Approach to the Construction of Linear \\
\vskip .1in
Divisibility Sequences of Higher Orders} }
\vskip 1cm
\large
Tian-Xiao He\\
Department of Mathematics\\
Illinois Wesleyan University\\
Bloomington, IL 61702\\
USA\\
\href{mailto:the@iwu.edu}{\tt the@iwu.edu} \\
\ \\
Peter J.-S. Shiue\footnote{This work was completed while on sabbatical leave from the University of Nevada, Las Vegas, and the author would like to thank UNLV for its support.}
\\
Department of Mathematical Sciences\\
University of Nevada, Las Vegas\\
Las Vegas, NV 89154-4020\\
USA\\
\href{mailto:shiue@unlv.nevada.edu}{\tt shiue@unlv.nevada.edu} \\
\end{center}
\vskip .2 in
\renewcommand*{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}
\begin{abstract}
We present a unified approach to construct divisibility sequences of higher orders by using divisibility sequences of order $2$.
\end{abstract}
\section{Introduction}
Let ${\mathbb Z}$ be the ring of integers. A sequence $( a_{n})_{n\geq 0}$ of elements in ${\mathbb Z}$ is called a divisibility sequence (DS for abbreviation) if $m|n$ implies $a_m|a_n$. In this paper, we discuss DSs that are recursive sequences $(a_n)$ satisfying linear homogeneous recurrence relations with constant coefficients, which are called linear divisibility sequences (LDSs for abbreviation). A well-known example is the sequence of Fibonacci numbers. It has long been an open question whether all divisibility sequences are, essentially, just termwise products of second order recursive sequences generalizing the Fibonacci numbers. Some earlier discussion about the question can be found in Ward \cite{War}. B\'ezivin, Peth\"o, and van der Poorten \cite{BPP} characterize all divisibility sequences by employing the factorization theory for exponential polynomials and a deep arithmetic result on the Hadamard quotient of rational functions. Some interesting results of divisibility sequences of order $3$ and $4$ can be found in Hall \cite{Hal} and Williams and Guy \cite{WG, WG15}, respectively. In this paper, we will present a different unified approach to construct LDSs of higher order by using LDSs of order $2$. Of course, we are aware that in literature the notion ``divisibility sequence" need not entail that the sequence is a recursive sequence. However, we prefer to follow the original definition to limit the LDS in the ring of linear homogeneous recursive sequences.
We present a necessary and sufficient condition for a second order LDS in the next section. Then, a large class of the second order number and polynomial divisibility sequences are given. In Section $3$, we will give a unified approach to construct higher order LDSs by using second order LDSs and the Hadamard product of sequences (see, for example, Everest, Poorten, Shparlinski, and Ward \cite [p.\ 65] {EPSW}), namely, $(a_n)\ast(b_n)=(a_nb_n)$.
\section{Second order linear divisibility sequences}
In this section, we discuss the conditions that make a second order linear homogeneous recursive sequence $( a_n)$ an LDS. Here, a number sequence $( a_n)$ is called linear homogeneous recursive sequence of order $2$, if it satisfies the following linear homogenous recurrence relation of order $2$:
\be\label{1.1}
a_n=pa_{n-1}+qa_{n-2}, \quad n\geq 2,
\ee
for a constant $p$, a nonzero constant $q$, and initial conditions $a_0$ and $a_1$. Mansour \cite{Man} call the sequence defined by \eqref{1.1} a Horadam sequence, which was introduced in 1965 by Horadam \cite{Hor}. Mansour \cite{Man} also obtain the generating functions for powers of a Horadam sequence. A survey on the Horadam sequences is given by Larcombe, Bagdasar, and Fennessey \cite{LBF}. For the sake of readers' convenience, we prove the following theorem of the second order LDSs by using our results in \cite{HS}.
\begin{theorem}\label{thm:1.1}
Let $( a_n)$ be a second order linear homogeneous recursive sequence defined by \eqref{1.1} with an arbitrary $a_1$. Then $(a_n)$ is an LDS if and only if the initial condition $a_0=0$, while the initial condition $a_{1}$ is arbitrary.
\end{theorem}
\begin{proof}
Let $\alpha$ and $\beta$ be two roots of the characteristic polynomial $x^2-px-q$ of $( a_n)$. They may be the same. From \cite{HS}, we have the expression of $a_n$ in terms of $\alpha$ and $\beta$:
\be\label{1.2-1}
a_n=\begin{cases} \left( \frac{a_1-\beta a_0}{\alpha -\beta}\right)\alpha^n-\left( \frac{a_1-\alpha a_0}{\alpha -\beta}\right)\beta^n, & \text{if $\alpha\not= \beta;$}\\
na_1 \alpha^{n-1}-(n-1)a_0\alpha^n, & \text{if $ \alpha=\beta.$}
\end{cases}
\ee
Particularly, for $a_0=0$, we have
\be\label{1.2}
a_n=\begin{cases} \frac{a_1}{\alpha -\beta}\left(\alpha^n-\beta^n\right), & \text{if $\alpha\not= \beta$};\\
na_1 \alpha^{n-1}, & \text{if $\alpha=\beta$}.\end{cases}
\ee
It is easy to check that $m|n$ implies $a_m|a_n$. Hence, $( a_n)$ is an LDS, which proves the sufficiency.
For the necessity, we consider a second order linear homogenous recursive sequence $( F_{n})$, where $F_n=F_{n-1}+F_{n-2}$ with initial conditions $F_0=F_1=1$. It is obvious that $(F_n)$ is not an LDS, as for instance $F_2=2$ is not a divisor of $F_4=5$. From \eqref{1.2-1}, if $a_n$ is an LDS and $\alpha, \beta \not=0$, then $a_1|a_2$ implies
\[
\left. a_1\right| \left( a_1(\alpha+\beta)-a_0\alpha\beta\right).
\]
Consequently, $a_0=0$ for an arbitrary $a_1$. Similarly, for other cases one can show that a second order linear homogenous recursive sequence $( a_n)$ defined by \eqref{1.1} with an arbitrary $a_1$ is an LDS, and its initial condition $a_0$ must be zero.
\end{proof}
%\qed
\begin{remark}\label{rem:1}
In the articles by Florez, Higuita, and Mukherjees \cite{FHM}, Hilton, Pedersen, Vrancken \cite{HPV}, Hoggatt and Bicknell-Johnson \cite{HB}, and McDaniel \cite{Mcd}, the GCD properties of Fibonacci numbers and polynomials, Lucas numbers, the Morgan-Voyce polynomials, the Chebyshev polynomials, and more general polynomials are studied, in which the condition of that the first initial condition of the recurrence relation must be zero is not needed. Here elements in a GCD set is a recursive sequence $\{a_n\}$ satisfying $\gcd(a_n,a_m)=a_{\gcd(n,m)}$. The collection of all LDS is a subset of GCD set because a (recursive) LDS sequence $\{a_n\}$ has the property that $n|m$ implies $a_n|a_m$ means $\gcd(a_n,a_m)=a_n=a_{\gcd(n,m)}$. Hence, the set of LDS is the subset of GCD set characterized by $a_0=0$.
\end{remark}
\medbreak
\begin{example}\label{Example 1}
From Theorem \ref{thm:1.1}, the Fibonacci number sequence $(F_n),$ where $F_{n}=F_{n-1}+F_{n-2}$ ($n\geq 2$) with initial conditions $F_0=0$ and $F_1=1$, the Pell number sequence $( P_{n})$, where $P_n=2P_{n-1}+P_{n-2}$ ($n\geq 2$) with initial conditions $P_0=0$ and $P_1=1$, and the Mersenne number sequence $( M_{n})$, where $M_n=3M_{n-1}-2M_{n-2}$ ($n\geq 2$) with the initial conditions $M_0=0$ and $M_1=1$ are LDSs.
\end{example}
\medbreak
Based on Theorem \ref{thm:1.1} and equation \eqref{1.2}, we consider a class of the LDS $(w_{n})$ defined by
\be\label{1.3}
w_{n}=c\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},
\ee
where $c$, $\alpha$, and $\beta$ are constants, and $\alpha\not= \beta$. We have the following result.
\begin{theorem}\label{thm:1.2}
Let $\alpha$ and $\beta$ be distinct real (or complex) numbers, and let sequence $( w_{n})$ be defined by \eqref{1.3}. Then $( w_{n})$ is a second order linear homogenous recursive sequence with $w_{0}=0$ and $w_{1}=c$. Also, $(w_{n})$ is an LDS of order $2$.
\end{theorem}
\begin{proof}
From \eqref{1.2}, we know that $( w_{n})$ is a linear homogeneous recursive sequence with initial values $w_{0}=0$ and $w_{1}=c$, and the recurrence relation $w_{n+2}=(\alpha+\beta)w_{n+1}-\alpha\beta w_{n}$. Since $w_{0}=0$, $(w_{n})$ is an LDS.
\end{proof}
\begin{example}\label{Example 2} It is obvious that all sequences shown in Example \ref{Example 1} belong to the class $( w_{n})$. Particularly, the alternative form $( w_{n})$ of the Fibonacci sequence $( F_{n})$ is the Binet formula:
\[
F_{n}=\frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2}\right)^{n}-\left( \frac{1-\sqrt{5}}{2}\right)^{n}\right).
\]
\end{example}
\medbreak
\begin{remark}\label{Rem:2} Let $D=p^2+4q$, where $p$ and $q$ are the coefficients of the recurrence relation \eqref{1.1}, and let $\left( \frac{D}{r}\right)$ be the Legendre symbol, i.e.,
\[
\left( \frac{D}{r}\right)\equiv D^{(r-1)/2}\,\, (\mbox{mod}\, r),
\]
where $r$ is any odd prime. From Euler's criterion, $\left( \frac{D}{r}\right)=-1$ if there is no integer $x$ such that $D\equiv x^2\,\, (\mbox{mod}\, r)$, otherwise $\left( \frac{D}{r}\right)=1$. Niven, Zuckerman, and Montgomery \cite[p.\ 202 and p.\ 205] {NZM} give the following results of $( a_n)$ defined by \eqref{1.1} with $a_0=0$ and $a_1=1$:
\begin{enumerate}
\item[(1)] If $\left( \frac{D}{r}\right)=-1$, then $r| a_{r+1}$.
\item[(2)] If $\left( \frac{D}{r}\right)=1$, then $a_{r+1}\equiv p\,\, (\mbox{mod}\, r)$.
\item[(3)] If $\left( \frac{D}{r}\right)=1$, then $ qa_{r-1}\equiv 0\,\, (\mbox{mod}\,r)$.
\item[(4)] $a_r\equiv \left( \frac{D}{r}\right)\,\, (\mbox{mod}\, r)$.
\end{enumerate}
Thus, for $k\in {\mathbb N}$ we have the following results on the divisibility of $( w_n)$ shown in \eqref{1.3} with $c=1$, accordingly:
\begin{enumerate}
\item[(1)] If $\left( \frac{D}{r}\right)=-1$, then $r| w_{k(r+1)}$.
\item[(2)] If $\left( \frac{D}{r}\right)=1$ and $p\equiv 0\,\, (\mbox{mod}\, r)$, then $r|w_{k(r+1)}$.
\item[(3)] If $\left( \frac{D}{r}\right)=1$ and $\gcd(q,r)=1$, then $ r|w_{k(r-1)}$.
\item[(4)] If $r|D$, then $r|w_{kr}$.
\end{enumerate}
\end{remark}
\medbreak
The result shown in Theorem \ref{thm:1.2} has a higher order analogy. For instance, Roettger \cite{Roe} and M\"ulcer, Roettger, and Williams \cite{MRW} use the third order linear homogenous recurrence relation with the characteristic polynomial $x^{3}-P_{1}x^{2}+P_{2}x-P_{3}$ to construct the following order $6$ LDS
\[
C_{n}=\left( \frac{\alpha^{n}-\beta^{n}}{\alpha -\beta}\right)\left( \frac{\beta^{n}-\gamma^{n}}{\beta -\gamma}\right)\left( \frac{\gamma^{n}-\alpha^{n}}{\gamma -\alpha}\right),
\]
where $\alpha$, $\beta$, and $\gamma$ are the roots of $x^{3}-P_{1}x^{2}+P_{2}x-P_{3}$. The results for $C_{n}$ is stated more generally in \cite[Section 1.3] {BPP}.
\section{Higher order divisibility sequences}
If an LDS satisfies a linear recurrence relation of order $r$, we call it an LDS of order $r$. Here, $r$ is the degree of the characteristic polynomial of the recurrence. The best known example of such a sequence of order $2$ is the Lucas sequence. In Section $2$, we present some general results on the LDSs of order $2$ and many examples. In this section we use LDSs of order $2$ and the Hadamard product of sequences to discuss higher order LDSs. Some algebraic structure of linearly recursive sequences under the Hadamard product can be found in Larson and Taft \cite{LT}.
Let $( a_n)$ be an $r$th order linear homogeneous recursive sequence satisfying
\be\label{2.1}
c_0a_n+c_1a_{n-1}+\cdots +c_ra_{n-r}=0
\ee
for $1\leq r\leq n$ with $c_0, c_r\not= 0$. If $(\alpha_k)^r_{k=1}$ are the distinct roots of the characteristic equation
\be\label{2.2}
P_r(x)=c_0x^r+c_1x^{r-1}+\cdots +c_{r-1}x+c_r=0,
\ee
then
\be\label{2.3}
a_n=A_1(\alpha_1)^n+A_2(\alpha_2)^n+\cdots +A_r(\alpha_r)^n,
\ee
where $A_k$ are determined by the $( c_k)$ and the initial conditions. Hence, if $(a_n)$ is known, then the characteristic polynomial of $( a_n)$ can be written as
\be\label{2.4}
P_r(x)=c_0(x-\alpha_1)(x-\alpha_2)\cdots (x-\alpha_r),
\ee
which is equivalent to the linear homogeneous recurrence relation \eqref{2.1}. Based on this observation, we give a unified approach of the construction of higher order linear homogeneous recursive sequences. We start from the fourth order linear homogeneous recursive sequences.
\begin{theorem}\label{thm:2.1}
Let $(a_n)$ and $( b_n)$ be two second order linear homogenous recursive sequences defined by \eqref{1.1} with initials $a_0=b_0=0$ and arbitrary initials $a_{1}$ and $b_{1}$ as well as different recursive coefficient pairs $(p_1, q_1)$ and $(p_2,q_2)$. Suppose the roots of the equation $x^2-p_1x-q_1=0$, denoted by $\alpha_1$ and $\beta_1$, are distinct, and the roots $\alpha_2$ and $\beta_2$ of the equation and $x^2-p_2x-q_2=0$ are distinct. Then the sequence $(a_nb_n)$ is a fourth order LDS with initial conditions $a_ib_i$, $0\leq i\leq 3$, where $a_0b_0=0$.
\end{theorem}
\begin{proof}
Sequences $( a_n)$ and $( b_n)$ are LDSs by Theorem \ref{thm:1.1}. We may use \eqref{1.2} to write $a_{n}b_{n}$ as the following expressions based on the different type of the roots of the characteristic equations $x^2-p_1x-q_1=0$ and $x^2-p_2x-q_2=0$ of the sequences $(a_{n})$ and $(b_{n})$, respectively.
\[
a_nb_n= \begin{cases}\frac{a_1}{\alpha_1 -\beta_1}\left(\alpha^n_1-\beta^n_1\right)\frac{b_1}{\alpha_2 -\beta_2}\left(\alpha^n_2-\beta^n_2\right), & \text{if $\alpha_1\not= \beta_1, \alpha_2\not= \beta_2$}; \\
\frac{na_1b_1}{\alpha_1 -\beta_1}\left(\alpha^n_1-\beta^n_1\right)\alpha_2^{n-1}, & \text{if $\alpha_1\not= \beta_1, \alpha_2= \beta_2$};\\
\frac{na_1b_1}{\alpha_2 -\beta_2}\left(\alpha^n_2-\beta^n_2\right)\alpha_1^{n-1}, & \text{if $\alpha_1= \beta_1, \alpha_2\not= \beta_2$};\\
n^2a_1b_1\alpha_1^{n-1}\alpha_2^{n-1}, & \text{if $\alpha_1= \beta_1, \alpha_2= \beta_2$}.\\
\end{cases}
\]
Clearly, $( a_n b_n)$ is also an LDS. Furthermore, we have
\bns
&&a_nb_n=\frac{a_1b_1}{(\alpha_1 -\beta_1)(\alpha_2-\beta_2)}\left(\alpha^n_1-\beta^n_1\right)\left(\alpha^n_2-\beta^n_2\right)\\
&&=\frac{a_1b_1}{(\alpha_1 -\beta_1)(\alpha_2-\beta_2)}\left( (\alpha_1\alpha_2)^n-(\alpha_1\beta_2)^n-(\alpha_2\beta_1)^n+(\beta_1\beta_2)^n\right).
\ens
Hence, the sequence $(a_nb_n)$ satisfies a linear homogenous recurrence relation with the characteristic equation
\bn\label{2.4-2}
&&(x-\alpha_1\alpha_2)(x-\alpha_1\beta_2)(x-\beta_1\alpha_2)(x-\beta_1\beta_2)\nonumber\\
&=& x^{4}-p_{1}p_{2}x^{3}-(p_{1}^{2}q_{2}+p_{2}^{2}q_{1}+2q_{1}q_{2})x^{2}-p_{1}p_{2}q_{1}q_{2}x+q_{1}^{2}q_{2}^{2}=0,\nonumber\\
\en
which implies that $( a_nb_n)$ is a fourth order linear homogeneous recursive sequence with initial conditions $a_ib_i$, $0\leq i\leq 3$, where $a_0b_0=0$.
\end{proof}
\medbreak
\begin{example}\label{Example 3}
Let $( F_n)$, $(P_n)$, and $(M_n)$ be the Fibonacci number sequence, the Pell number sequence, and the Mersenne number sequence, respectively. From Theorem \ref{thm:2.1} and Example \ref{Example 1}, all of the following sequences are fourth order LDSs:
\[
( F_nP_n), \quad ( F_nM_n),\quad and \quad ( P_nM_n)
\]
with characteristic equations $x^{4}-2x^{3}-7x^{2}-2x+1=0$, $x^{4}-3x^{3}-3x^{2}+6x+4=0$, and $x^{4}-6x^{3}+3x^{2}+12x+4=0$, and initial conditions $F_iP_i$, $F_iM_i$, and $P_iM_i$, $0\leq i\leq 3$, respectively.
\end{example}
\medbreak
Using a similar argument, one may construct high even order LDSs, such as a sixth order LDS, $( F_nP_nM_n)_{n\geq 0}$.
We now consider the construction of high odd order LDSs based on the following result.
\begin{theorem}\label{thm:2.2}
Let $(a_n)$ be a second order linear homogenous recursive sequence defined by \eqref{1.1} with initial conditions $a_0=0$ and $a_1=1$. Suppose the roots of the characteristic equation $x^2-px-q=0$ of $( a_n)$ are distinct and denoted by $\alpha$ and $\beta$. Then the sequence $(a_n^2)$ is a third order LDS with the characteristic equation
\be\label{2.4-3}
x^3-(p^2+q)x^2-q(p^2+q)x+q^3=0
\ee
with initial conditions $a_0^2=0$, $a_1^2$, and $a_2^2$.
\end{theorem}
\begin{proof}
Equation \eqref{1.2} implies
\[
a_n^2=\frac{(\alpha^{n}-\beta^{n})^{2}}{(\alpha-\beta)^2}=\frac{1}{(\alpha-\beta)^2} \bigl( (\alpha^2)^n-2(\alpha\beta)^n+(\beta^2)^n\bigr)
\]
for $n\geq 2$. Thus, \eqref{2.3} and \eqref{2.4} imply the following characteristic polynomial
\bns
&&(x-\alpha^2)(x-\alpha\beta)(x-\beta^2)\\
&=&x^3-((\alpha+\beta)^2-\alpha\beta)x^2+\alpha\beta(\alpha^2+\beta^2+\alpha\beta)x-(\alpha\beta)^3\\
&=&x^3-(p^2+q)x^2-q(p^2+q)x+q^3.
\ens
Recall that $\alpha\beta=-q$ and $\alpha+\beta=p$. We have that $(w_n=a_n^2)$ is an LDS satisfying the third linear homogeneous recurrence relation
\[
w_{n+3}=(p^2+q)w_{n+2}+q(p^2+q)w_{n+1}-q^3w_n, \quad q\not=0.
\]
The above recurrence relation is linear homogeneous because the powers of the sequences are $1$ and it has no constant term, which completes the proof.
\end{proof}
\medbreak
\begin{example}\label{Example 4}
Let $( F_n)$, $(P_n)$, and $(M_n)$ be the Fibonacci number sequence, the Pell number sequence, and the Mersenne number sequence, with initial conditions $F_{0} = 0$ and $F_{1} = 1$, initial conditions $P_{0} = 0$ and $P_{1} = 1$, and the initial conditions $M_{0} =0$ and $M_{1} =1$, respectively. Then $( w_n=F_n^2)$ is a third order LDS satisfying the linear homogeneous recurrence relation
\[
w_{n+3}=2w_{n+2}+2w_{n+1}-w_n
\]
with initial conditions $w_0$, $w_1$, and $w_2$. The sequence $( u_n=P_n^2)$ is a third order LDS with linear homogeneous recurrence relation
\[
u_{n+3}=5u_{n+2}+5u_{n+1}-u_n
\]
with initial conditions $u_0$, $u_1$, and $u_2$. The sequence $( v_n=M_n^2)$ is a third order LDS satisfying the linear homogeneous recurrence relation
\[
v_{n+3}=7v_{n+2}-14v_{n+1}+8v_n
\]
with initial conditions $v_0$, $v_1$, and $v_2$.
\end{example}
Similarly, we may construct higher odd order LDSs, such as a fifth order LDS, $( F_n^2P_n)$. An analogy of Theorem \ref{thm:2.2} is shown below.
\begin{theorem}\label{thm:2.2-2}
Let $(a_n)$ be a second order linear homogenous recursive sequence defined by \eqref{1.1} with initial conditions $a_0=0$ and $a_1=1$. Suppose the roots of the characteristic equation $x^2-px-q=0$ of $( a_n)$ are distinct and denoted by $\alpha$ and $\beta$. Then the sequence $(a_n^3)$ is a fourth order LDS with the characteristic equation
\be\label{2.4-4}
x^4-p(p^2+2q)x^3-q\bigl((p^2+2q)^2-2q^2-p^2q\bigr)x^2+pq^3(p^2+2q)x+q^6=0
\ee
with initial conditions $a_0^3=0$ and $a_i^3$, $1\leq i\leq 3$.
\end{theorem}
\begin{proof}
Similar to the proof of Theorem \ref{thm:2.2}, Equation \eqref{1.2} implies
\[
a_n^3=\frac{(\alpha^{n}-\beta^{n})^{3}}{(\alpha-\beta)^3}=\frac{1}{(\alpha-\beta)^3} \bigl( (\alpha^3)^n-3(\alpha^2\beta)^n+
3(\alpha \beta^2)^n-(\beta^3)^n\bigr)
\]
for $n\geq 2$. Thus, \eqref{2.3} and \eqref{2.4} imply the following characteristic polynomial
\bns
&&(x-\alpha^3)(x-\alpha^2 \beta)(x-\alpha\beta^2)(x-\beta^3)\\
&=&x^4-[\alpha^3+\alpha\beta(\alpha+\beta)+\beta^3]x^3+\alpha\beta[\alpha^4+\alpha\beta(\alpha+\beta)^2+\beta^4]x^2\\
&&-\alpha^3\beta^3[\alpha^2(\alpha+\beta)+\beta^2(\alpha+\beta)]x+(\alpha\beta)^6\\
&=&x^4-(\alpha+\beta)(\alpha^2+\beta^2)x^3+\alpha\beta\bigl((\alpha^2+\beta^2)^2-2(\alpha\beta)^2+\alpha\beta(\alpha+\beta)^2\bigr)x^2\\
&& -(\alpha\beta)^3(\alpha+\beta)(\alpha^2+\beta^2)x+(\alpha\beta)^6\\
&=&x^4-p(p^2+2q)x^3-q\bigl((p^2+2q)^2-2q^2-p^2q\bigr)x^2+pq^3(p^2+2q)x+q^6.
\ens
Recall that $\alpha\beta=-q$ and $\alpha+\beta=p$. We have that
$(w_n=a_n^3)$ is an LDS satisfying the third order linear homogeneous recurrence relation
\bns
w_{n+4}&=&p(p^2+2q)w_{n+3}+q[(p^2+2q)^2-2q^2-p^2q]w_{n+2}\\
&&-pq^3(p^2+2q)w_{n+1}-q^6w_n.
\ens
The proof is complete.
\end{proof}
\begin{example}\label{Example 5}
Let $( F_n)$, $(P_n)$, and $(M_n)$ be the Fibonacci number sequence, the Pell number sequence, and the Mersenne number sequence, with initial conditions $F_{0} = 0$ and $F_{1} = 1$, initial conditions $P_{0} = 0$ and $P_{1} = 1$, and the initial conditions $M_{0} =0$ and $M_{1} =1$, respectively. Then $( w_n=F_n^3)$ is a fourth order LDS satisfying the linear homogeneous recurrence relation
\[
w_{n+4}=3w_{n+3}+6w_{n+2}-3w_{n+1}-w_n
\]
with initial conditions $w_0$, $w_1$, $w_2$, and $w_3$. The sequence $( u_n=P_n^3)$ is a fourth order LDS with linear homogeneous recurrence relation
\[
u_{n+4}=12u_{n+3}+30u_{n+2}-12u_{n+1}-u_n
\]
with initial conditions $u_0$, $u_1$, $u_2$, and $u_3$. The sequence $( v_n=M_n^3)$ is a fourth order LDS satisfying linear homogeneous recurrence relation
\[
v_{n+4}=15v_{n+3}-70v_{n+2}+120v_{n+1}-64v_n
\]
with initial conditions $v_0$, $v_1$, $v_2$, and $v_3$.
\end{example}
Bala \cite{Bal} showed the following fourth order LDS given by Williams and Guy, $W_n=W_n(P_1,P_2,Q)$ with integer parameters $P_1$, $P_2$, and $Q$:
\be\label{2.5}
W_n=\frac{t_n(\alpha, Q)-t_n(\beta, Q)}{\alpha-\beta},\quad n\geq 1,
\ee
where $\alpha+\beta=P_1$, $\alpha \beta=-P_2$, and $t_n(x,Q)$ denote the $n$th monic Dickson polynomial of the first kind with parameter $Q$. The first few monic Dickson polynomials are
\bns
&&t_0(x,Q)=2,\\
&&t_1(x,Q)=x,\\
&&t_2(x,Q)=x^2-2Q,\\
&&t_3(x,Q)=x^3-3xQ,\\
&&\vdots
\ens
The recurrence equation for the sequence $W_n$ is
\be\label{2.6}
W_n=P_1W_{n-1}+(P_2-2Q)W_{n-2}+P_1QW_{n-3}-Q^2W_{n-4},
\ee
where the initial conditions can be found by using the Dickson polynomials shown above, namely,
\bns
&&W_0=\frac{t_0(\alpha, Q)-t_0(\beta, Q)}{\alpha-\beta}=\frac{2-2}{\alpha-\beta}=0,\\
&&W_1=\frac{t_1(\alpha, Q)-t_1(\beta, Q)}{\alpha-\beta}=\frac{\alpha-\beta}{\alpha-\beta}=1,\\
&&W_2=\frac{t_2(\alpha, Q)-t_2(\beta, Q)}{\alpha-\beta}=\frac{\alpha^2-\beta^2}{\alpha-\beta}=\alpha+\beta=P_1,\\
&&W_3=\frac{t_3(\alpha, Q)-t_3(\beta, Q)}{\alpha-\beta}=\frac{\alpha^3-\beta^3}{\alpha-\beta}-3Q\\
&&\qquad =(\alpha+\beta)^2-\alpha\beta-3Q=P_1^2+P_2-3Q.\\
\ens
Hence, we establish the following result.
\begin{theorem}\label{thm:2.3}
The Williams and Guy fourth order LDS $(W_n)$ defined in \eqref{2.5} by using the second order characteristic equation $x^2-P_1x-P_2=0$ and the Dickson polynomial sequence of the first kind with parameter $Q$ is equivalent to our fourth order LDS shown in Theorem \ref{thm:2.1}.
\end{theorem}
\begin{proof}
From their recurrence relation \eqref{2.6}, we obtain the characteristic equation of $( W_n)$ as
\be\label{2.7}
x^4-P_1x^3-(P_2-2Q)x^2-P_1Qx+Q^2=0.
\ee
Comparing \eqref{2.7} and the characteristic equation \eqref{2.4-2},
\[
x^{4}-p_{1}p_{2}x^{3}-(p_{1}^{2}q_{2}+p_{2}^{2}q_{1}+2q_{1}q_{2})x^{2}-p_{1}p_{2}q_{1}q_{2}x+q_{1}^{2}q_{2}^{2}=0,
\]
of the fourth order LDS shown in Theorem \ref{thm:2.1}, we know they are equivalent when
\bns
&&P_1=p_1p_2,\\
&&P_2=p_1^2q_2+p_2^2q_1+4q_1q_2,\\
&&Q=q_1q_2,
\ens
where $p_i=\alpha_i+\beta_i$ and $q_i=-\alpha_i\beta_i$, $i=1$ and $2$. Furthermore,
\bns
&&W_1=1=a_1b_1,\\
&&W_2=P_1=p_1p_2=(\alpha_1+\beta_1)(\alpha_2+\beta_2)=\frac{\alpha_1^2-\beta_1^2}{\alpha_1-\beta_1}
\frac{\alpha_2^2-\beta_2^2}{\alpha_2-\beta_2}=a_2b_2,\\
&&W_3=P_1^2+P_2-3Q=(p_1p_2)^2+p_1^2q_2+p_2^2q_1+4q_1q_2-3q_1q_2\\
&&\qquad =(p_1^2+q_1)(p_2^2+q_2)=\left( (\alpha_1+\beta_1)^2-\alpha_1\beta_1\right)\left( (\alpha_2+\beta_2)^2-\alpha_2\beta_2\right)\nonumber\\
&&\qquad =\frac{\alpha_1^3-\beta_1^3}{\alpha_1-\beta_1}\frac{\alpha_2^3-\beta_2^3}{\alpha_2-\beta_2}
=a_3b_3.
\ens
Hence $(a_nb_n)=(W_n)$, completing the proof of the theorem.
\end{proof}
\begin{remark}\label{Rem: 3} In an attempt to extend the second order linear divisibility sequences to sequences of order 4, it becomes necessary to examine odd and even divisibility sequences. Williams and Guy \cite{WG15} produce some conditions under which certain divisibility sequences of order 4 will be either even or odd.
\end{remark}
\begin{remark}\label{Rem: 4} Recently, B. Torrence and R. Torrence \cite{TT} point out that if $( a_n)$ is any sequence satisfying the recurrence $a_{n+1}=a_n+a_{n-1}$, then
\be\label{2.8}
a_{n+2} = 3a_n-a_{n-2},
\ee
which can be simply proved by substituting $a_{n+2}=a_{n+1}+a_n=2a_n+a_{n-1}$ on the left-hand side and reducing it to $a_{n}=a_{n-1}+a_{n-2}$. The Fibonacci and Lucas number sequences, $( F_n)$ and $(L_n)$, satisfy $a_{n+1}=a_n+a_{n-1}$. Consequently, they also satisfy \eqref{2.8}. Thus $(F_n)$ with $F_{0}=0$ can be considered as an LDS of order $4$. Thus, the recurrence relation \eqref{2.8} inspires a way to lift the order of an LDS. We now extend this idea to lift an LDS to any order. For instance, from $a_{n+2}=a_{n+1}+a_{n}$, we have
\[
a_{n+3}=a_{n+2}+a_{n+1}=2a_{n+1}+a_{n},
\]
which implies that $(F_{n})$ with $F_{0}=0$ is an LDS of order $3$. From $a_{n+3}=2a_{n+1}+a_{n}$ we can also obtain
\[
a_{n+4}=2a_{n+2}+a_{n+1}= 2a_{n+2}+(a_{n+2}-a_{n})=3a_{n+2}-a_{n},
\]
which is \eqref{2.8}. This process can continue to lift an LDS satisfying $a_{n+2}=a_{n+1}+a_{n}$ with $a_{0}=0$ to any order.
\end{remark}
\begin{remark}\label{Rem:5} For Fibonacci sequence $(F_{n})$, Brualdi \cite[p.\ 258] {Bru} mention the following fifth order LDS, which can be derived from the second order linear recurrence relation.
\[
F_{n}=5F_{n-4}+3F_{n-5},
\]
where $F_{0}=0$, $F_{1}=1$, $F_{2}=1$, $F_{3}=2$, and $F_{4}=3$. It can be seen from the above formula that $5| F_{n}$ if and only if $5|n$. Similarly, $2|F_{n}$ if and only if $3|n$, $3|F_{n}$ if and only if $4|n$, and $4|F_{n}$ if and only if $6|n$.
\end{remark}
\section{Polynomial divisibility sequences}
Similar to number LDSs, we may define polynomial LDSs. Polynomial LDSs are recursive polynomial sequences $(a_n (x))$ satisfying linear homogeneous recurrence relations with constant coefficients, with the property that whenever $m|n$, then $a_m(x)|a_n(x)$. We now start from the second order divisibility polynomial sequences, i.e., divisibility polynomial sequences satisfying linear homogeneous recurrence relations of the second order. If the coefficients of the linear recurrence relation of a function sequence $( a_n(x))$ of order $2$ are real or complex-value functions of variable $x$, i.e.,
\be\label{3.1}
a_n(x)=p(x) a_{n-1}(x)+ q(x) a_{n-2}(x),
\ee
where $p^2(x)+4q(x)\geq 0$ is assumed, we obtain a function sequence of order $2$ with initial conditions $a_0(x)$ and $a_1(x)$. In particular, if all of $p(x)$, $q(x)$, $a_0(x)$ and $a_1(x)$ are polynomials, then the corresponding sequence $(a_n(x))$ is a polynomial sequence of order $2$. Denote the solutions of
\[
t^2- p(x) t-q(x)=0
\]
by $\alpha (x)$ and $\beta(x)$. Then
\be\label{3.2}
\alpha(x)= \frac{1}{2}( p(x)+\sqrt{p^2(x)+4q(x)}), \beta (x)= \frac{1}{2}( p(x)-\sqrt{p^2(x)+4q(x)}).
\ee
Similar to Theorem \ref{thm:1.1}, we have
\begin{theorem}\label{thm:3.1}
Let $( a_n(x))$ be a second order linear homogeneous recursive polynomial sequence defined by \eqref{3.1}. Then $(a_n(x))$ is a divisibility sequence if and only if the initial condition $a_0(x)=0$, while the initial condition $a_{1}(x)$ is arbitrary.
\end{theorem}
\begin{proof}
Let $( a_n(x))$ be a sequence of order $2$ satisfying the linear recurrence relation (\ref{3.1}). Then by \cite{HS} we have
\[
a_n(x)=\begin{cases}\left( \frac{a_1(x)-\beta(x) a_0(x)}{\alpha (x)-\beta (x)}\right) \alpha^n(x)- \left(\frac{a_1(x)-\alpha(x) a_0(x)}{\alpha(x)-\beta(x)}\right) \beta^n(x), & \text{if $\alpha(x)\not= \beta(x)$};\\
na_1(x) \alpha^{n-1}(x)-(n-1)a_0(x)\alpha^{n}(x), & \text{if $\alpha (x)=\beta(x)$},\end{cases}
\]
where $\alpha(x)$ and $\beta(x)$ are shown in (\ref{3.2}). If $a_0(x)=0$, then
\be\label{3.3}
a_n(x)=\begin{cases} \frac{a_1(x)}{\alpha (x)-\beta (x)} \left(\alpha^n(x)- \beta^n(x)\right), & \text{if $\alpha(x)\not= \beta(x)$};\\
na_1(x) \alpha^{n-1}(x), &\text{if $\alpha (x)=\beta(x)$},\end{cases}
\ee
which implies that $( a_n(x))$ is a divisibility sequence. The sufficiency is proved. Conversely, we may prove the necessity.
\end{proof}
\begin{example}\label{Example 6}
Some second order polynomial LDSs can be found in various literature. For instance, Webb and Parberry \cite{WP} show that the second order linear homogeneous recursive polynomial sequence $( P_{n}(x) )$ defined by
\[
P_{n}(x)=x P_{n-1}(x)+P_{n-2}(x), \quad n\geq 2
\]
with $P_0(x)=0$ and $P_1(x)=1$ is an LDS. $( P_{n}(x))$ is the Fibonacci polynomial sequence. Obviously, when $x=1$ and $x=2$, the sequences $( P_{n}(1)=F_{n})$ and $( P_{n}(2)=P_{n})$ are the Fibonacci number sequence and the Pell number sequence, respectively.
\end{example}
Hoggatt Jr., Bicknell, and King \cite{HBK} and Koshy \cite[p.\ 461] {Kos} show the second order divisibility polynomial sequence $( P_{n}(x))$ defined by
\[
P_{n}(x)=x P_{n-1}(x)-P_{n-2}(x), \quad n\geq 2,
\]
where $P_0(x)=0$ and $P_1(x)=1$. Schur \cite[p.\ 17]{Sch} suggest the modification of the degree of Dickson polynomials $E^\ast_n(x,a)$ as follows:
\[
E^\ast_{n+1}(x,a)=2xE^\ast_n(x,a)-aE^\ast_{n-1}(x,a)
\]
with the initial conditions $E^\ast_0(x,a)=0$ and $E^\ast_1(x,a)=1$, which can also be seen in Lidl, Mullen, and Turnwald \cite[p. \ 17 ]{LMT}. Then $( E_{n}^{\ast}(x,a))$ is a second order divisibility polynomial sequence.
The above results on the linear homogeneous recursive polynomial sequence of one variable can be easily extended to the case of multivariate polynomials. Hence, a divisibility multivariate polynomial sequence can be defined similarly. For instance, Hoggatt and Long \cite{HL} present a bivariate second order divisibility polynomial sequence $( U_{n}(x,y))$, whose elements can be written as
\[
U_{n}(x,y)=x U_{n-1}(x,y)+yU_{n-2}(x,y), \quad n\geq 2,
\]
where $U_0(x,y)=0$ and $U_1(x,y)=1$.
We may use \eqref{3.1} to define the linear homogeneous recursive multivariate polynomial sequence, in which the only change is to consider all functions $a_{n}(x)$, $p(x)$, $q(x)$, as well as the corresponding root functions $\alpha(x)$ and $\beta(x)$ as the mappings from ${\mathbb R}^{n}$ to ${\mathbb R}$. As an analogy to Theorems \ref{thm:2.1} and \ref{thm:2.2}, we have the following results.
\begin{theorem}\label{thm:3.2}
Let $(a_n(x))$ and $( b_n(x))$ be two second order linear homogenous recursive polynomial sequences defined by \eqref{3.1} of $n$ variables with initial zero condition $a_0(x)=b_0(x)=0$ and arbitrary $a_{1}(x)$ and $b_{1}(x)$ as well as different recursive coefficient pairs $(p_1(x), q_1(x))$ and $(p_2(x),q_2(x))$. Suppose the roots of the equation $t^2-p_1(x)t-q_1(x)=0$ are distinct and denoted by $\alpha_1(x)$ and $\beta_1(x)$, and the roots $\alpha_2(x)$ and $\beta_2(x)$ of the equation and $t^2-p_2(x)t-q_2(x)=0$ are distinct. Then the sequence $(a_n(x)b_n(x))$ is a fourth order LDS with initial conditions $a_i(x)b_i(x)$, $0\leq i\leq 3$, where $a_0(x)b_0(x)=0$.
\end{theorem}
\begin{theorem}\label{thm:3.3}
Let $(a_n(x))$ be a second order linear homogenous recursive polynomial sequence defined by \eqref{3.1} with the initial zero condition $a_0(x)=0$ and arbitrary condition $a_{1}(x)$. Suppose the roots of the characteristic equation $t^2-p(x)t-q(x)=0$, $q(x)\not= 0$, of $( a_n(x))$ are distinct and denoted by $\alpha(x)$ and $\beta(x)$. Then the sequence $(a_n(x)^2)$ is a third order LDS with initial conditions $a_0^2(x)=0$, $a_1^2(x)$, and $a_2^2(x)$.
\end{theorem}
The proofs of Theorems \ref{thm:3.2} and \ref{thm:3.3} are similar to the proofs of Theorems \ref{thm:2.1} and \ref{thm:2.2} and are omitted.
\section{Acknowledgments}
The authors thank Mr.\ Scott MacDonald from the Mathematics Learning Center at UNLV for his comments and corrections on an earlier version of this manuscript and the proof reading. The authors thank the referee and editor for their careful reading and helpful suggestions.
\begin{thebibliography}{99}
\bibitem{Bal}
P. Bala, Linear divisibility sequences and Chebyshev polynomials, manuscript,
March 2014. Available at \url{https://oeis.org/A100047/a100047.pdf}.
\bibitem{BPP}
J.-P. B\'ezivin, A. Peth\"o, and A. J. van der Poorten, A full
characterization of divisibility sequences, {\it Amer. J. Math.} {\bf
112} (1990), 985--1001.
\bibitem{Bru}
R. A. Brualdi, {\it Introductory Combinatorics,} Fifth edition. Pearson Prentice Hall, 2010.
\bibitem{EPSW}
G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, {\it Recurrence Sequences}, AMS, 2003.
\bibitem{FHM}
R. Florez, R. Higuita, and A. Mukherjees, Characterization of the Fibonacci GCD property for generalized Fibonacci polynomials, \url{https://arxiv.org/abs/1701.06722}.
\bibitem{Hal}
M. Hall, Divisibility sequences of third order, {\it Am. J. Math.} {\bf 58} (1936), 577--584.
\bibitem{HS}
T. -X. He and P. J.-S. Shiue, On sequences of numbers and polynomials defined by linear recurrence relations of order $2$, {\it Int. J. Math. Math. Sci.} 2009, Art. ID 709386.
\bibitem{HPV}
P. Hilton, J. Pedersen, and L. Vrancken, On certain arithmetic properties of Fibonacci and Lucas numbers, {\it Fibonacci Quart.} {\bf 33} (1995), 211--217.
\bibitem{HB}
V. E. Hoggatt, Jr. and M. Bicknell-Johnson, Divisibility properties of polynomials in Pascal's triangle, {\it Fibonacci Quart.} {\bf 16} (1978), 501--513.
\bibitem{HBK}
V. E. Hoggatt Jr., M. Bicknell, and E. L. King, Fibonacci and Lucas triangles. {\it Fibonacci Quart.} {\bf 10} (1972), 555--560.
\bibitem{HL}
V. E. Hoggatt, Jr., and C. T. Long, Divisibility properties of generalized Fibonacci polynomials, {\it Fibonacci Quart.} {\bf 12} (1974), 113--122.
\bibitem{Hor}
A. F. Horadam, Basic properties of a certain generalized sequence of numbers, {\it Fibonacci Quart.} {\bf 3} (1965), 161--176.
\bibitem{IS}
P. Ingram and J. H. Silverman, Primitive divisors in elliptic
divisibility sequences, in D. Goldfeld, J. Jorgenson, P. Jones, D.
Ramakrishnan, K. A. Ribet, and J. Tate, eds., {\it Number Theory, Analysis,
and Geometry, In Memory of Serge Lang}, Springer, 2012, pp.~243--271.
\bibitem{Kos}
T. Koshy, {\it Fibonacci and Lucas Numbers with Applications}, Pure and Applied Mathematics, Wiley-Interscience, 2001.
\bibitem{LBF}
P. J. Larcombe, O. Bagdasar, and E. J. Fennessey, Horadam sequences: a
survey, {\it Bull. Inst. Combin. Appl.} {\bf 67} (2013), 49--72.
\bibitem{LT}
R. G. Larson and E. J. Taft, The algebraic structure of linearly recursive sequences under Hadamard product, {\it Israel J. Math.} {\bf 72} (1990), 118--132.
\bibitem{LMT}
R. Lidl, G. L. Mullen, and G. Turnwald, {\it Dickson Polynomials},
Pitman Monographs and Surveys in Pure and Applied Mathematics, Vol.~65.
Longman Scientific \& Technical and
John Wiley \& Sons, Inc., 1993.
\bibitem{Man}
T. Mansour, A formula for the generating functions of powers of
Horadam's sequence, {\it Australasian J. Combin.}, {\bf 30}
(2004), 207--212.
\bibitem{Mcd}
W. L. McDaniel, The G.C.D. in Lucas sequences and Lehmer number sequences, {\it Fibonacci Quart.} {\bf 29} (1991), 24--29.
\bibitem{MRW}
S. M\"uller, E. Roettger, and H. C. Williams, A cubic extension of the Lucas functions, {\it Ann. Sci. Math. Qu\'ebec}, {\bf 33} (2009), 185--224.
\bibitem{NZM}
I. Niven, H. S. Zuckerman, and H. L. Montgomery, {\it An Introduction to the Theory of Numbers}, Fifth Ed., John Wiley \& Sons, Inc., 1991.
\bibitem{Roe}
E. Roettger, {\it A Cubic Extension of the Lucas Functions}, Ph.D. thesis, University of Calgary, 2009.
\bibitem{Sch}
I. Schur, {\it Gesammelte Abhandlungen}, Band III.
Springer-Verlag, 1973.
\bibitem{TT}
B. Torrence and R. Torrence, Fibonacci, Lucas, and a game of chance, {\it Math. Mag.} {\bf 89} (2016), 342--351.
\bibitem{War}
M. Ward, A note on divisibility sequences, {\it Bull. Amer. Math. Soc.} {\bf 45} (1939), 334--336.
\bibitem{WP}
W. A. Webb and E. A. Parberry, Divisibility properties of Fibonacci polynomials, {\it Fibonacci Quart.} {\bf 7} (1969), 457--463.
\bibitem{WG}
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, {\it Int. J. Number Theory}, {\bf 7} (2011), 1255--1277.
\bibitem{WG15}
H. C. Williams and R. K. Guy, Odd and even linear divisibility
sequences of order 4, {\it Integers}, {\bf 15} (2015), Paper No.~A33.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39, Secondary 11B37, 05A15, 33C45.
\noindent \emph{Keywords: }
linear homogeneous recursive sequence, divisibility sequence, Fibonacci
sequence, Lucas sequence, Fibonacci polynomial.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A100047}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received March 25 2017;
revised versions received April 2 2017; August 26 2017; September 5 2017; September 7 2017.
Published in {\it Journal of Integer Sequences}, September 8 2017.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}