%%%% 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, ÓÈÎïÊÓƵ, 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}