%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-25/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{thrm}{Theorem}
\newtheorem{corl}{Corollary}
\newtheorem*{lmma}{Lemma}
\newtheorem*{rmrk}{Remark}

\title{Squares of Second-Order Linear Recurrence Sequences}
\author{
Tom C. Brown\footnote{Department of Mathematics and Statistics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6, Canada. \texttt{tbrown@sfu.ca}} and
Peter Jau-shyong Shiue\footnote{Department of Mathematical Sciences, University of Nevada, Las Vegas, NV, USA 89154-4020. \texttt{shiue@nevada.edu}}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and P.J.-S. {Shiue}, \emph{Squares of second-order sequences}, Fib. Quart. \textbf{33}
  (1995), 352--356.}\bigskip\end{center}

\begin{abstract}We discuss integer sequences $\{T_n\}$ such that $\{T_n\}$ satisfies
a second-order homogeneous linear recurrence relation with constant integer
coefficients, and $\{T_n^2\}$ satisfies a second-order linear recurrence
relation with constant integer coefficients. We also prove some related results.
\end{abstract}

\section{Introduction \label{s1}}

Let us call a sequence $\{T_n\}$ an ``$m$th-order sequence'' if $\{T_n\}_{n\geq0}$
satisfies an $m$th order linear recurrence relation with constant integer coefficients.
It is well known \cite{poorten1973,selmer1966} that if $\{T_n\}_{n\geq0}$ is a
second-order sequence then the sequence of squares $\{T_n^2\}_{n\geq0}$ is a
third-order sequence. (It is also easy to show this directly.) It would be of
interest to be able to describe all second-order sequences $\{T_n\}_{n\geq0}$ such
that $\{T_n^2\}_{n\geq0}$ is a \emph{second}-order sequence.

In this note we do this for certain \emph{homogeneous} sequences $\{T_n\}_{n\geq0}$.
That is, we assume that $\{T_n\}_{n\geq0}$ satisfies a recurrence of the form $T_0
= a$, $T_1 = b$, $T_{n+1}=cT_n-dT_{n-1}$, $n\geq1$, where $a$, $b$, $c\neq0$, $d\neq0$
are integers, $ab\neq0$, and $x^2 - cx + d= 0$ has distinct roots. It then turns out
that $\{T_n^2\}_{n\geq0}$ satisfies a second-order linear recurrence (which we
describe in Theorem \ref{t6}) if and only if $d = 1$.

As an illustration of this, consider the sequence $1,2,7,26,97,362,\ldots$, which
satisfies the second-order recurrence $B_0=1$, $B_1=2$, $B_{n+1}=4B_n-B_{n-1}$,
$n\geq1$. The sequence of squares $1^2,2^2,7^2,26^2,97^2,362^2,\ldots$ satisfies
the second-order recurrence $S_0=1$, $S_1=4$, $S_{n+1}=14S_n-S_{n-1}-6$, $n\geq1$.

We also consider second-order sequences $\{T_n\}_{n\geq0}$ such that a slight
perturbation of the sequence of squares $\{T_n^2\}_{n\geq0}$ is a second-order
sequence. For example, the sequence $1,1,3,7,17,41,99,\ldots$ satisfies the
second-order recurrence $B_0=B_1=1$, $B_{n+1}=2B_n+B_{n-1}$, $n\geq1$, and the
``perturbed'' sequence of squares $1^2$, $1^2+1$, $3^2$, $7^2+1$, $17^2$, $41^2
+1$, $99^2$, \ldots, satisfies the second-order recurrence $S_0=1$, $S_1=2$,
$S_{n+1}=6S_n-S_{n-1}-2$, $n\geq1$.

We begin with some special cases using elementary techniques. Then, in the last
section, we handle the general case using an old result of E. S. Selmer
\cite{selmer1966}, which states that if $T_{n+1}=AT_n+BT_{n-1}$, $n\geq1$, and
$x^2 - Ax - B = (x-\alpha)(x-\beta)$, $\alpha\neq\beta$, then $T_{n+1}^2 =
CT_n^2+DT_{n-1}^2 + ET_{n-2}^2$, $n\geq2$, where $x^2 - Cx^2 - Dx - E = (x-\alpha^2)
(x-\beta^2)(x-\alpha\beta)$.

\section{Some special cases\label{s2}}

We begin with some special cases, for which we will use the following Lemma.

\begin{lmma} Let $p\geq4$ be any integer, let $\delta=\sqrt{\frac{p}4}+\sqrt{\frac{p}4-1}$,
and let $S_n = \left(\delta^n + \frac1{\delta^n}\right)^2$, $n\geq0$. Then these numbers
$S_n$ satisfy the following identities.
\begin{enumerate}
\item[(a)] For all $0\leq m\leq n$,
\[ (S_n-2)(S_m-2) = S_{n+m}+S_{n-m}-4. \]
(In particular, $(S_n-2)^2 = S_{2n}$, so $S_{2n}$ is always a perfect square.)

\item[(b)] For all $0\leq m \leq n$, $m\equiv n\Mod2$,
\[ S_nS_m = (S_{(n+m)/2} + S_{(n-m)/2} - 4)^2. \]
(In particular, $S_{n+k}S_{n-k} = (S_n+S_k-4)^2$ and $pS_{2n+1}=S_1S_{2n+1} = (S_n+S_{n+1}
- 4)^2$, so that $S_{2n+1}$ is always a perfect square provided $p$ is a perfect square.)

\item[(c)] For all $0\leq m\leq n$, $m\equiv n\Mod2$,
\[ (S_n - 4)(S_m-4) = S_{(n+m)/2} + S_{(n-m)/2})^2. \]
(In particular, $(p-4)(S_{2n+2}-4) = (S_1-4)(S_{2n+1}-4)=(S_{n+1}-S_n)^2$, so that
$S_{2n+1}-4$ is always a perfect square provided $p-4$ is a perfect square.)

\item[(d)] $S_{n+1} = (p-2)S_n - S_{n-1} - 2(p-4)$, $n\geq1$.
\end{enumerate}\end{lmma}
\begin{proof} We prove part (d) in detail. The proofs of parts (a), (b), and
(c) are very similar, and are omitted.

Note that $\frac1\delta = \sqrt{\frac{p}4} - \sqrt{\frac{p}4-1}$, so that
$\left(\delta+\frac1\delta\right)^2=p$. Then
\begin{align*}
pS_{n+1}
&= \left(\delta+\frac1\delta\right)^2S_{n+1}
= \left[\left(\delta+\frac1\delta\right)\left(\delta^{n+1}+\frac1{\delta^{n+1}}\right)\right]^2 \\
&= \left[\left(\delta^{n+2}+\frac1{\delta^{n+2}}\right) + \left(\delta^n+\frac1{\delta^n}\right)\right]^2
= S_{n+2} + S_n + 2\left[\delta^{2n+2} + \frac1{\delta^{2n+2}} + \delta^2 + \frac1{\delta^2}\right] \\
&= S_{n+2} + S_n + 2\left[\left(\delta^{n+1}+\frac1{\delta^{n+1}}\right)^2 - 2 + \left(\delta+\frac1\delta\right)^2 - 2\right]
= S_{n+2} + S_n + 2S_{n+1} + 2(p-4),
\end{align*}
that is, $S_{n+2} = (p-2)S_{n+1} - S_n - 2(p-4)$, $n\geq0$.
\end{proof}

\section{Second order sequences $\{T_n\}_{n\geq0}$ whose squares $\{T_n^2\}_{n\geq0}$ are also second order sequences. Special Cases.}

\begin{thrm}\label{t1} Let $d\geq3$ be an integer. Define the sequence $\{B_n\}_{n\geq0}$
by $B_0=2$, $B_1=d$, $B_{n+2}=dB_{n+1}-B_n$, $n\geq0$. Then the sequence of squares
$\{B_n^2\}_{n\geq0}$ satisfies the second-order recurrence $B_{n+2}^2 = (d^2-2)B_{n+1}^2
- B_n^2 - 2(d^2-4)$, $n\geq0$.\end{thrm}
\begin{proof} Solving the recurrence $B_0=2$, $B_1=d$, $B_{n+2}=dB_{n+1}-B_n$, $n\geq0$
in the usual way gives $B_n = \delta^n + \frac1{\delta^n}$, $n\geq0$, where $\delta =
\sqrt{\frac{d^2}4}+\sqrt{\frac{d^2}4-1}$, $\frac1\delta=\sqrt{\frac{d^2}4}-\sqrt{\frac{d^2}4
-1}$. Let us now simplify the notation by setting $S_n=B_n^2$, $n\geq0$. Then $S_n=
\left(\delta+\frac1\delta\right)^2$, $n\geq0$, and by part (d) of the Lemma (with
$p=d^2$), $S_{n+2}=(d^2-2)S_{n+1}-S_n-2(d^2-4)$, $n\geq0$.\end{proof}

\section{Perturbed sequences\label{s4}}

Here we give a second-order sequence whose squares, when slightly perturbed, form a
second-order sequence.

\begin{thrm}\label{t2} Let $d\geq1$ be an integer. Define the sequence $\{C_n\}_{n\geq0}$
by $C_0=2$, $C_1=d$, $C_{n+2}=dC_{n+1}+C_n$, $n\geq0$. Let $S_{2n}=C_{2n}^2$, $S_{2n+1}
=C_{2n+1}^2+4$, $n\geq0$. Then $S_{n+2}=(d^2+2)S_{n+1}-S_n-2d^2$, $n\geq0$.\end{thrm}
\begin{proof} Solving the recurrence $C_0=2$, $C_1=d$, $C_{n+1}=dC_{n+1}+C_n$, $n\geq0$
in the usual way gives $C_n = \delta^n + \left(\frac{-1}{\delta}\right)^n$, where
$\delta=\sqrt{\frac{d^2}4+1}+\sqrt{\frac{d^2}4}$, $\frac1\delta=\sqrt{\frac{d^2}4+1}-
\sqrt{\frac{d^2}4}$. Then $S_{2n} = C_{2n}^2= \left(\delta^{2n}+\frac1{\delta^{2n}}\right)^2$,
$S_{2n+1} = C_{2n+1}^2 + 4 = \left(\delta^{2n+1}+\frac1{\delta^{2n+1}}\right)^2$, $n\geq0$.

Since $\left(\delta+\frac1{\delta}\right)^2 = d^2+4$, we obtain $(d^2+4)S_{n+1} =
\left[\left(\delta+\frac1{\delta}\right)\left(\delta^{n+1}+\frac1{\delta^{n+1}}\right)\right]^2$,
and the calculations used in the proof of part (d) of the Lemma now give $S_{n+2}=(d^2+2)S_{n+1}
-S_n-2d^2$, $n\geq0$.\end{proof}

\begin{corl}\label{c1} Let $S_{2n}= L_{2n}^2$, $S_{2n+1} = L_{2n+1}^2+4$, $n\geq0$,
where $\{L_n\}$ is the Lucas sequence. Then $S_{n+2} = 3S_{n+1} - S_n - 2$, $n\geq0$.
\end{corl}\begin{proof} This is the case $d = 1$ of Theorem \ref{t2}.\end{proof}

\begin{corl}\label{c2} Let $T_{2n} = F_{2n}^2+\frac45$, $T_{2n+1} = F_{2n+1}^2$,
$n\geq0$, where $\{F_n\}$ is the Fibonacci sequence. Then $T_{n+2}=3T_{n+1}-T_n-2$,
$n\geq0$.\end{corl}\begin{proof} This follows from Corollary \ref{c1} and the
identity \cite[pp. 56]{hoggatt1980} $5F_n^2=L_n^2-4(-1)^n$.\end{proof}

\section{Additional special cases\label{s5}}

If we now write $\delta=\sqrt{s}-\sqrt{s-1}$, $S_n=\frac14\left(\delta^{n}+\frac1{\delta^{n}}\right)^2$,
$n\geq0$, we obtain, just as in the Lemma, $S_0=1$, $S_1=s$, $S_{n+2}=4(s-2)S_{n+1}
- S_n-2(s-1)$, $n\geq0$.

The following two results can now be proved in essentially the same way as
Theorems \ref{t1} and \ref{t2}.

\begin{thrm}\label{t3} Let $d\geq2$ be an integer. Define the sequence $\{B_n\}_{n\geq0}$
by $B_0=1$, $B_1=d$, $B_{n+2}=2dB_{n+1}-B_n$, $n\geq0$. Then the sequence of
squares $\{B_n^2\}_{n\geq0}$ satisfies the second-order recurrence
\[ B_{n+2}^2 = (4d^2-2)B_{n+1}-B_n - 2d^2, ~~ n\geq0.\]\end{thrm}

\begin{thrm}\label{t4} Let $d\geq1$ be an integer. Define the sequence $\{C_n\}_{n\geq0}$
by $C_0=1$, $C_1=d$, $C_{n+2}=2dC_{n+1}+C_n$, $n\geq0$. Let $S_{2n} = C_{2n}^2$,
$S_{2n+1} = C_{2n+1}^2$, $n\geq0$. Then $S_{n+2} = (4d^2+2)S_{n+1} - S_n - 2d^2$,
$n\geq0$.\end{thrm}

\section{The more general homogeneous case\label{s6}}

\begin{thrm}\label{t5} Let $a,b,c\neq0$, $d\neq0$ be integers, with $ab\neq0$ and $c^2\neq4d$.
Let $B_0=a$, $B_1=b$, $B_{n+1}=cB_n-dB_{n-1}$, $n\geq1$. Then $B_{n+1}^2=(c^2-2d)
B_n^2 - d^2B_{n-1}^2 + 2(b^2-a^2d-abc)d^n$, $n\geq1$.\end{thrm}
\begin{proof} Let $\alpha,\beta$ be the roots of $x^2 -cx + d = 0$. Then
$\alpha,\beta = \frac12(c\pm\sqrt{c^2-4d})$, $\alpha\neq\pm\beta$, $\alpha^2,
\beta^2 = \frac12(c^2-2d\pm c\sqrt{c^2-4d})$, $\alpha\beta = d$. Also $\alpha^2
\neq \beta^2\neq d$, since $c\neq0$, $d\neq0$, $c^2\neq4d$.

According to the result of Selmer stated in the Introduction, there are constants
$A$, $B$, $C$ such that $B_n^2 = A\alpha^{2n} + B\beta^{2n} + Cd^n$, $n\geq0$.

Solving the system
\[\begin{array}{rcl}
a^2 &= B_0^2 &= A + B + C \\
b^2 &= B_1^2 &= A\alpha^2 + B\beta^2 + Cd \\
(bc-ad)^2 &= B_2^2 &= A\alpha^4 + B\beta^4 + Cd^2
\end{array}\]
for $C$ gives $C = \frac{2(b^2 + a^2d- abc)}{4d - c^2}$.

Using $(c^2-2d)\alpha^{2n} - d^2\alpha^{2n-2} = \alpha^{2n+2}$ and $(c^2-2d)
\beta^{2n}-d^2\beta^{2n-2} = \beta^{2n+2}$ gives $(c^2-2d)B_n^2 - d^2B_{n-1}^2
+ed^n = A\alpha^{2n+2} + B\beta^{2n+2} + C[(c^2-2d)d^n - d^{n+1}] + ed^n$.
Now choosing $e$ so that $C[(c^2-2d)d^n - d^{n+1}] + ed^n = Cd^{n+1}$ (namely
$e = C(4d - c^2) = 2(b^2 + a^2d - abc)$), finally gives $(c^2-2d)B_n^2 -
d^2B_{n-1}^2 + ed^n = A\alpha^{2n+2} + B\beta^{2n+2} + Cd^{n+1} = B_{n+1}^2$,
which completes the proof.\end{proof}

\begin{rmrk} The result of Theorem \ref{t5} appears in \cite{wilf1992}.
\end{rmrk}

Applying Theorem \ref{t5} to the question raised in the Introduction, we immediately
get the following result.

\begin{thrm}\label{t6} Let $a,b,c\neq0$, $d\neq0$ be integers, with $ab\neq0$
and $c^2\neq4d$. Let $B_0=a$, $B_1=b$, $B_{n+1}=cB_n-dB_{n-1}$, $n\geq1$.
Then the sequence of squares $\{B_n^2\}_{n\geq0}$ satisfies a second-order
linear recurrence (with constant coefficients) if and only if $d=1$, in
which case $B_{n+1}^2 = (c^2-2)B_n^2 - B_{n-1}^2 + 2(b^2 + a^2 - abc)$,
$n\geq1$.\end{thrm}

Our final result is the general version of Theorem \ref{t2}, in which we
consider a perturbation of the sequence of squares.

\begin{thrm}\label{t7} Let $a,b,c\neq0$, $d\neq0$ be integers, with $ab\neq0$
and $c^2\neq4d$, such that $e = \frac{4(a^2 + abc - b^2)}{c^2 + 4}$ is an
integer. Define the sequence $\{B_n\}_{n\geq0}$ by $B_0=a$, $B_1=b$,
$B_{n+1}=cB_n + B_{n-1}$, $n\geq1$. Let $S_{2n} = B_{2n}^2$, $S_{2n+1}=
B_{2n+1}^2 + e$, $n\geq0$. Then $\{S_n\}_{n\geq0}$ satisfies the second-order
recurrence $S_{n+1} = (c^2+2)S_n - S_{n-1} + 2e + 2(b^2 - a^2 - abc)$, $n\geq1$.
\end{thrm}
\begin{proof} This is a direct application of Theorem \ref{t5} with $d=-1$,
according to which $B_{n+1}^2 = (c^2 + 2)B_n^2 - B_{n-1}^2 + 2(b^2-a-abc)
(-1)^n$.\end{proof}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}

