<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf On the Shifted Product of Binary  \\
\vskip .1in
Recurrences
}
\vskip 1cm
\large
Omar Khadir \\
Department of Mathematics\\
University of Hassan II \\
Mohammedia, Morocco \\
\href{mailto:khadir@hotmail.com}{\tt  khadir@hotmail.com} \\ 

\bigskip

K\'alm\'an Liptai \\
Institute of Mathematics and Informatics\\
Eszterh\'azy K\'aroly College \\
Eger, Hungary \\
\href{mailto:liptaik@gemini.ektf.hu}{\tt liptaik@gemini.ektf.hu} \\ 

\bigskip

L\'aszl\'o~Szalay\footnote{Research supported
by the J\'anos Bolyai Scholarship of HAS, by the Hungarian
National Foundation for Scientific Research Grant No.\ T 61800 FT, and by the Mexican-Hungarian bilateral TeT.} \\
Institute of Mathematics and Statistics\\
University of West Hungary \\
Sopron, Hungary \\
\href{mailto:laszalay@ktk.nyme.hu}{\tt laszalay@ktk.nyme.hu} \\
\end{center}

\vskip .2 in

\begin{abstract} 
The present paper studies the diophantine equation
$G_nH_n+c=x_{2n}$ and related questions, where the integer binary
recurrence sequences $\{G\}$, $\{H\}$ and $\{x\}$ satisfy the same
recurrence relation, and $c$ is a given integer. We prove necessary and
sufficient conditions for the solubility of $G_nH_n+c=x_{2n}$. Finally,
a few relevant examples are provided.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}


%\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,latexsym,amsopn,amstext,amsxtra,euscript,amscd}


%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}{Lemma}
\newtheorem{claim}[theorem]{Claim}
%\newtheorem{cor}[theorem]{Corollary}
%\newtheorem{prop}[theorem]{Proposition}
%\newtheorem{definition}{Definition}
\newtheorem{question}{Question}
%\newtheorem{rem}[theorem]{Remark}
%\newtheorem{conj}{Conjecture}
%\newtheorem{example}[theorem]{Example}

\def\halmos{\rule{6pt}{6pt}}

\newcommand {\N}{{\mathbb N}}
\newcommand {\Z}{{\mathbb Z}}
\newcommand {\Q}{{\mathbb Q}}
\newcommand {\R}{{\mathbb R}}



\vskip 1cm

%--------------------------------------------------------

\section{Introduction}

Let the binary recurrences $\{a\}_{n=0}^\infty$, $\{b\}_{n=0}^\infty$, $\{c\}_{n=0}^\infty$ and $\{d\}_{n=0}^\infty$
satisfy the recurrence relation
\begin{equation}\label{br}
X_{n+2}=6X_{n+1}-X_n,\qquad n\in\mathbb{N},
\end{equation}
with the initial values
$$
a_0=-1,~a_1=1;\quad b_0=1,~b_1=5;\quad c_0=0,~c_1=2;\quad d_0=3,~d_1=17;
$$
respectively (Sloane: $\{c\}$ is \seqnum{A001542}, $\{d\}$ is \seqnum{A001541}). Here, and in the sequel, $\mathbb{N}$ denotes the set of non-negative integers. By the recurrences above, we can define a fifth sequence $\{x\}_{n=0}^\infty$  via
\begin{equation} \label{eloall}
x_{2n}=a_nb_n+1\quad,\quad x_{2n+1}=c_nd_n+1,\qquad n\in\mathbb{N}.
\end{equation}
The sequence $\{x\}$ (the first few terms are: $0,~1,~6,~35,~204,~1189,~\dots$, Sloane: \seqnum{A001109}) also satisfies (\ref{br}), in spite of the unusual method of its composition, 
which we discovered while studying the terms of  $\{x\}$, called balancing numbers. A positive integer $x\ge2$ is called a {\it balancing number\/} for the integer $y$ if 
\begin{equation} \label{gbal1} 
1+\cdots +(x-1)=(x+1)+\cdots +(y-1) 
\end{equation} 
holds. This definition was introduced by Finkelstein \cite{F} (he called balancing numbers {\it numerical centers}) when he solved a puzzle from the book \cite{A}. For other properties of balancing numbers see, for example \cite{BP}. Clearly, (\ref{gbal1}) leads to the Pell equation $(2y-1)^2-2(2x)^2=1$, and the possible values of $x$ can be described by a suitable recurrence relation of type (\ref{br}). It is known that all real binary recurrences satisfying (\ref{br}) form a vector space  of dimension 2 over $\R$. Definition (\ref{eloall}) (and later (\ref{egyes})) does not fit the vector space structure. The question arises which other integer binary recurrences can possess the interesting property described by (\ref{eloall}) or its generalization. 

The phenomena appearing in (\ref{eloall}) is a specific case of a more general property. Let $t\in\N^+$ and put $\alpha=t+\sqrt{t^2+1}$, $\beta=t-\sqrt{t^2+1}$. Define the sequences $\{T\}_{n=0}^\infty$ and $\{U\}_{n=0}^\infty$ by
$\alpha^n=T_n+U_n\sqrt{t^2+1}$. It is easy to see that the sequences $\{T\}$ and $\{U\}$ both satisfy the recurrence relation $X_n=2t X_{n-1}+X_{n-2}$ with the initial values $T_0=1$, $T_1=t$ and $U_0=0$, $U_1=1$, respectively. The corresponding explicit formulae 
$$
T_n=\frac{\alpha^n+\beta^n}{2}\quad{\rm and}\quad U_n=\frac{\alpha^n-\beta^n}{2\sqrt{t^2+1}}
$$
show that
$$
U_{n\mp(-1)^n}T_{n\pm(-1)^n}\mp t=\frac{1}{2}\,U_{2n}
$$
holds. Subsequently, the choice $a_n=T_{2n-1}$, $b_n=U_{2n+1}$, $c_n=T_{2n+2}$, $d_n=U_{2n}$ implies $a_nb_n+t=U_{4n}/2\in\N$ and $c_nd_n+t=U_{4n+2}/2\in\N$. That is, the example given at the start of the introduction is a particular case of this construction with $t=1$. 
Observe, that $X_n=(4t^2+2)X_{n-1}-X_{n-2}$ holds for all the sequences $\{a\}$, $\{b\}$, $\{c\}$ and $\{d\}$, and also for $\{x_n\}=\{U_{2n}/2\}$. Thus, we can provide infinitely many, but not all examples similar to (\ref{eloall}) (see in Section 4) since the coefficients $A=4t^2+2$ and $B=-1$ do not represent the most general case.


Now consider a slightly different property having a
similar flavor.  Assume that $A&gt;0$ and $B\ne0$ are integers with non-vanishing $D=A^2+4B$, further let  $\cal B$ denote 
the set of all integer binary recurrences $\{X\}_{n=0}^\infty$ satisfying the recurrence relation
\begin{equation}\label{brAB}
X_{n+2}=AX_{n+1}+BX_n,\qquad n\in\mathbb{N}.
\end{equation}
If $\{u\}_{n=0}^\infty$ and $\{v\}_{n=0}^\infty$ are elements of $\cal B$ with the initial values $u_0=0$, $u_1=1$ and $v_0=2$, $v_1=A$, respectively, then the equality
\begin{equation} \label{mult} 
u_nv_n=u_{2n}
\end{equation}
holds for any non-negative integer $n$. Identity (\ref{mult}) is well-known, and all books or papers dealing, for instance, with the Fibonacci sequence mention the formula $F_nL_n=F_{2n}$, where $F_n$ and $L_n$ are the $n$th term of the Fibonacci (Sloane: \seqnum{A000045}) and Lucas sequences (Sloane: \seqnum{A000032}), respectively. Note, that the sequences $\{F\}$ and $\{L\}$ both satisfy (\ref{brAB}) with $A=B=1$.
\medskip

In this paper, we examine how we can construct a binary recurrence $\{x\}$ as a shifted product of two binary recurrences satisfying the same recurrence relation. More precisely, given the integers $c$ and $l$, we consider the equation 
\begin{equation}\label{egyes}
G_nH_n+c=x_{2n+l},
\end{equation} 
where $\{G\}_{n=0}^\infty$, $\{H\}_{n=0}^\infty$ and $\{x\}_{n=0}^\infty$ belong to the class of binary recurrences given by (\ref{brAB}). There is no restriction in assuming that $l=0$, since $l$ causes only a translation in the subscript. 

Moreover, suppose that $c$ is a fixed integer, and the binary recursive sequences $\{G\}$ and $\{J\}_{n=0}^\infty$ also belong to ${\cal B}$.
Analogously to (\ref{eloall}), we investigate and determine the binary recurrences $\{H\}$ and $\{K\}_{n=0}^\infty$ of $\cal B$, which generate a sequence $\{x\}\in{\cal B}$ satisfying
$$
x_{2n}=G_n H_n+c\quad,\quad x_{2n+1}=J_n K_n+c,\qquad n\in\mathbb{N}.
$$

It is worth noting that if one forgets about the integrality conditions, then obviously $c$ can be considered to be either $0$ or $1$. Indeed, if $c\ne0$, then we can replace $\{x_n\}$ by $\{x_n/c\}$, further $\{G_n\}$, $\{H_n\}$, $\{J_n\}$ and $\{K_n\}$
by $\{G_n/\sqrt{c}\}$, $\{H_n/\sqrt{c}\}$, $\{J_n/\sqrt{c}\}$ and $\{K_n/\sqrt{c}\}$, respectively, which results in assuming that $c=1$.

%-------------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------------


\section{Preliminaries}

For any complex numbers $\alpha,~\beta,~\dots$ and for any sequence $\{X\}_{n=0}^\infty\in{\cal B}$ put $\alpha_X=X_1-\alpha X_0$, $\beta_X=X_1-\beta X_0$, etc.
Recall, that $A&gt;0$ and $B\ne0$ are integers and $D=A^2+4B\ne0$.
 
\begin{lemma} \label{alap}
Assume that $\{G\}\in{\cal B}$. Then the zeros $\alpha=(A+\sqrt{D})/2$ and $\beta=(A-\sqrt{D})/2$ of the companion polynomial $p(x)=x^2-Ax-B$ of $\{G\}$ are distinct and nonzero. Further
\begin{itemize}
	\item $\alpha\beta=-B,\quad \alpha+\beta=A,\quad\alpha-\beta=\sqrt{D},$
	%\item $ A\alpha+B=\alpha^2,\quad A\beta+B=\beta^2,\quad A\alpha^2+2B\alpha=\sqrt{D}\alpha^2,\quad A\beta^2+2B\beta =-\sqrt{D}\beta^2.$
	\item $D&gt;0$ implies \ $\beta&lt;\alpha$ and \ $1&lt;\alpha$.
\end{itemize}
Moreover,
\begin{equation}\label{expl}
G_n=\frac{\beta_G\alpha^n-\alpha_G\beta^n}{\sqrt{D}}.
\end{equation}
\end{lemma}

\begin{proof}
All formulae and statements of Lemma \ref{alap} are known. Nevertheless, the first two conditions are immediate from the determination of $\alpha$ and $\beta$, while (\ref{expl}) can be derived from the basic theorem concerning the linear recurrences (see, for instance, \cite{ST}). Note that $\alpha$ and $\beta$ are conjugate zeros of $p(x)$ if they are not integers.
\end{proof}

\begin{remark}
%The companion polynomial $p(x)$, in fact, belongs to the whole class ${\cal B}$, not only to $\{G\}$ itself. 
Later we will use the results of Lemma \ref{alap} without any comment. 
\end{remark}

In the present and next sections we assume that $c\in\mathbb{Z}$, $l=0$. Further  $\{G\}\in{\cal B}$, $\{H\}\in{\cal B}$ and $\{x\}\in{\cal B}$ satisfy (\ref{egyes}). 

\begin{lemma} \label{x1}
$$
x_1=\frac{G_1H_1-BG_0H_0+c(1-B)}{A}.
$$
\end{lemma}

\begin{proof}
Combining $x_0=G_0H_0+c$, $x_2=G_1H_1+c$ and $x_2=Ax_1+Bx_0$, we immediately get the desired statement.
\end{proof}

Now we define some important constants which will be useful in studying our problems. Put
\begin{equation}\label{Eabab}
E_\alpha=\frac{\beta_G\beta_H}{D}-\frac{\beta_x}{\sqrt{D}},\quad\quad
E_\beta=\frac{\alpha_G\alpha_H}{D}+\frac{\alpha_x}{\sqrt{D}},\quad\quad
E_{\alpha\beta}=\frac{\beta_G\alpha_H+\alpha_G\beta_H}{D}.
\end{equation}
Further, let
\begin{equation}\label{Delt}
\Delta=(2G_1-AG_0)H_1-(2BG_0+AG_1)H_0\in\mathbb{Z}.
\end{equation}

\begin{remark}\label{r2}
We call $\{\widetilde{G}\}_{n=0}^\infty$ the companion sequence of $\{G\}\in{\cal B}$ if $\{\widetilde{G}\}$ is also in $\cal B$ and $\widetilde{G}_0=2G_1-AG_0$, $\widetilde{G}_1=2BG_0+AG_1$. Thus, $\Delta$ can be simplified as $\widetilde{G}_0H_1-\widetilde{G}_1H_0$.

Sometimes it is more convenient to write (\ref{Delt}) in the form $\Delta=2G_1H_1-2BG_0H_0-A(G_1H_0+G_0H_1)$.
%What is more, $\Delta=\alpha_G\beta_H+\alpha_H\beta_G$ also holds.
\end{remark}

\begin{lemma} \label{kifejt}
The quantities from (\ref{Eabab}) can also be given in the forms
\begin{equation}\label{fair}
E_\alpha=\frac{\beta}{AD}\left(\Delta-\frac{1-\beta^2}{\beta}\sqrt{D}c\right),\quad\quad
E_\beta=\frac{\alpha}{AD}\left(\Delta+\frac{1-\alpha^2}{\alpha}\sqrt{D}c\right),\quad\quad
E_{\alpha\beta}=\frac{\Delta}{D}.
\end{equation}
\end{lemma}

\begin{proof}
Recall the definition of $E_\alpha$ and $\beta_G=G_1-\beta G_0$, $\beta_H=H_1-\beta H_0$, $\beta_x=x_1-\beta x_0$, $x_0=G_0H_0+c$. These formulae, together with Lemma \ref{x1}, yield
$$
E_\alpha=\frac{\beta}{AD}\left(2G_1H_1-2BG_0H_0-A(G_1H_0+G_0H_1)-\frac{1-\beta^2}{\beta}\sqrt{D}c\right).
$$
In order to complete the proof on $E_\alpha$, observe that the first three terms in the paranthesis above make up $\Delta$ (see Remark \ref{r2}). 

If $\alpha\not\in\mathbb{Z}$, then $E_\beta$ is a conjugate of $E_\alpha$; hence, the second part of the lemma is obvious.
Otherwise, we can use the same procedure we applied to $E_\alpha$.

Finally, one can easily get $E_{\alpha\beta}=\Delta/D$ from the parts of definition (\ref{Eabab}) concerned with $E_{\alpha\beta}$. 
\end{proof}



%-------------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------------


\section{The equation $G_nH_n+c=x_{2n}$}

Now we proceed to the solution of the first problem. The following result provides necessary conditions for the solubility of equation (\ref{egyes}).

\begin{theorem}\label{t:nec1}
Let $c\in\mathbb{Z}$. If there exist sequences $\{G\}\in{\cal B}$, $\{H\}\in{\cal B}$ and $\{x\}\in{\cal B}$ such that $G_nH_n+c=x_{2n}$ then one of the following cases holds.
\begin{itemize}
	\item If $c=0$ then $\Delta=0$;
	\item if $c\ne0$ then either $B=-1$, $\Delta=Dc$;  or $\beta=\pm1$, $\Delta=0$.  
\end{itemize}
\end{theorem}

\begin{remark}
The assertion $B=-1$, together with $\beta\in\mathbb{R}$ implies $0&lt;\beta&lt;1$. Then the two instances in the second part of Theorem \ref{t:nec1} are not-overlapping. 
\end{remark}


\begin{proof}
$G_nH_n+c=x_{2n}$ is equivalent to 
\begin{equation}\label{main}
E_\alpha\alpha^{2n}+E_\beta\beta^{2n}-E_{\alpha\beta}(\alpha\beta)^n+c=0,\qquad n\in\mathbb{N}.
\end{equation}

Since (\ref{main}) is true for all $n$, therefore it is true for $n=0,~1,~2,~3$. Consequently, (\ref{main}) at $n=0,~1,~2,~3$ is a homogeneous linear system of four equations in the unknowns $E_{\alpha},~E_{\beta},~E_{\alpha\beta}$ and $c$. The determinant
$$
{\cal{D}}=\left|
\begin{array} {cccc} 
1 &amp; 1 &amp; -1 &amp; 1 \\
\alpha^2 &amp; \beta^2 &amp; -\alpha\beta &amp; 1 \\
\alpha^4 &amp; \beta^4 &amp; -(\alpha\beta)^2 &amp; 1 \\
\alpha^6 &amp; \beta^6 &amp; -(\alpha\beta)^3 &amp; 1 \\
\end{array}
\right|
$$
of the coefficient matrix is the negative of the Vandermonde of $\alpha^2,~\beta^2,~\alpha\beta$ and $1$. Hence,
\begin{equation}\label{vanderm}
{\cal{D}}=-V(\alpha^2,\beta^2,\alpha\beta, 1)=\alpha\beta(\alpha-\beta)^3(\alpha+\beta)(1-\alpha^2)(1-\beta^2)(1-\alpha\beta).
\end{equation}

If the homogeneous system has only the trivial solution $c=0$ and $E_\alpha=E_\beta=E_{\alpha\beta}=0$, then, by Lemma \ref{kifejt}, we obtain 
$$
E_\alpha=\frac{\beta}{AD}\Delta=0,\quad\quad E_\beta=\frac{\alpha}{AD}\Delta=0,\quad\quad E_{\alpha\beta}=\frac{1}{D}\Delta=0.
$$
The coefficient of $\Delta$ is nonzero in any of the three equalities. Subsequently, $\Delta=0$ follows. 

If the system has infinitely many solutions, then ${\cal{D}}=0$. Recalling (\ref{vanderm}) and the conditions $\alpha\beta\ne0$, $\alpha\ne\beta$ (see Lemma \ref{alap}), we distinguish four cases.
\begin{description}
	\item[1. $\alpha+\beta=0$.] We deduce a degenerate recursion characterized by $\alpha/\beta=-1$. Thus $A=0$, and we have arrived at a contradiction.
	\item[2. $1-\alpha^2=0$.]  Now $\alpha=\pm1\in\mathbb{R}$. This is impossible since $\alpha&gt;1$ holds.
	\item[3. $1-\beta^2=0$.] Both cases $\beta=\pm1$ lead to the solutions $E_\alpha=E_{\alpha\beta}=0$ and $E_\beta=-c$, where $c$ is a free variable. Clearly, by (\ref{fair}), $E_{\alpha\beta}$ implies $\Delta=0$.
	\item[4. $1-\alpha\beta=0$.] Obviously, $B=-1$. Moreover $D=A^2-4\ne0$ yields $A\ne2$. The infinitely many solutions of the system can be described by $E_\alpha=E_\beta=0$ and
	\begin{equation}\label{c4}
	 c=-\frac{\alpha\beta(\alpha-\beta)^2}{(\alpha^2-1)(\beta^2-1)}E_{\alpha\beta}.
	\end{equation}
	Since $\alpha\beta=B$ and $(\alpha-\beta)^2=A^2-4$, relation (\ref{c4}) together with 
	$(\alpha^2-1)(\beta^2-1)=(A\alpha-2)(A\beta-2)=-A^2+4$ gives $E_{\alpha\beta}=c$, where $c$ is a free variable. Then, again by (\ref{fair}), $\Delta=Dc$.
\end{description}

\end{proof}

Theorem \ref{t:nec1} provides necessary conditions for the sequences $\{G\}$, $\{H\}$ and $\{x\}$ satisfying $G_nH_n+c=x_{2n}$. Now we show that the conditions are, essentially, sufficient as well. More precisely, we prove the following theorem.

\begin{theorem}\label{t:suff1}
Suppose that the integers $c$, $G_0$, $G_1$, $H_0$ and $H_1$ are fixed. Put $x_0=G_0H_0+c$. If 
\begin{eqnarray*}
&amp; &amp; c=0,\; \Delta=0;\; \text{or} \\
&amp; &amp; c\ne0,\; B=-1,\; \Delta=Dc;\; \text{or} \\
&amp; &amp;c\ne0,\; \beta=\pm1, \; \Delta=0, 
\end{eqnarray*}
hold, as well as 
\begin{eqnarray*}
x_1&amp;=&amp;\frac{G_1H_1-BG_0H_0}{A}\in\mathbb{Z}, \quad\text{or} \\
x_1&amp;=&amp;\frac{G_1H_1+G_0H_0+2c}{A}\in\mathbb{Z}, \quad\text{or} \\
x_1&amp;=&amp;\frac{G_1H_1-BG_0H_0+(1-B)c}{A}\in\mathbb{Z},
\end{eqnarray*}
respectively, then the terms of the sequences $\{G\}\in{\cal B}$, $\{H\}\in{\cal B}$ and $\{x\}\in{\cal B}$ satisfy
$$G_nH_n+c=x_{2n}, \qquad n\in\mathbb{N}.$$
\end{theorem}

\begin{remark}
Theorem \ref{t:suff1} asserts necessarily that $x_1$ is an integer, otherwise $\{x\}$ would not be an integer sequence although it satisfies $G_nH_n+c=x_{2n}$. For example, let
$c=0$, $A=14$, $B=-5$, $G_0=2$, $G_1=3$, $H_0=-1$, $H_1=1$. Then $\Delta=0$, $x_1=-1/2$, and 
\begin{eqnarray*}
\{G\}&amp;:&amp;\quad 2,~3,~32,~433,~\dots\;; \\
\{H\}&amp;:&amp;\quad -1,~1,~19,~261,~\dots\;; \\
\{x\}&amp;:&amp;\quad-2=G_0H_0,\;\;-\frac{1}{2},\;\;3=G_1H_1,\;\;\frac{89}{2},\;\;608=G_2H_2,\;\;\frac{16579}{2},\;\;113013=G_3H_3,\;\;\dots \;.
\end{eqnarray*}
\end{remark}

\begin{proof}
We will use the notation of the previous sections. By (\ref{Delt}), it is easy to verify that 
$G_1H_0+G_0H_1=(2G_1H_1-2BG_0H_0-\Delta)/A$. Combining it with 
$$
\beta_G\beta_H=G_1H_1+\beta^2G_0H_0-\beta(G_1H_0+G_0H_1)\quad\text{and}\quad
\alpha_G\alpha_H=G_1H_1+\alpha^2G_0H_0-\alpha(G_1H_0+G_0H_1),
$$
respectively, we obtain
\begin{equation}\label{kife1}
\beta_G\beta_H=\frac{\sqrt{D}(G_1H_1-\beta^2G_0H_0)+\beta\Delta}{A}\quad\text{and}\quad
\alpha_G\alpha_H=\frac{\sqrt{D}(-G_1H_1+\alpha^2G_0H_0)+\alpha\Delta}{A}.
\end{equation}
By $x_0=G_0H_0+c$ and Lemma \ref{x1}, we also have
\begin{equation}\label{kife2}
\beta_x=x_1-\beta x_0=\frac{G_1H_1-\beta^2G_0H_0+(1-\beta^2)c}{A}\quad\text{and}\quad\alpha_x=x_1-\alpha x_0=\frac{G_1H_1-\alpha^2G_0H_0+(1-\alpha^2)c}{A}.
\end{equation}
Thus, by (\ref{kife1}) and (\ref{kife2}),
$$
G_nH_n+c=\frac{\beta_G\alpha^n-\alpha_G\beta^n}{\sqrt{D}}\,\frac{\beta_H\alpha^n-\alpha_H\beta^n}{\sqrt{D}}+c=
\frac{\beta_G\beta_H\alpha^{2n}+\alpha_G\alpha_H\beta^{2n}-\Delta(\alpha\beta)^n+cD}{D},
$$
which is equivalent to
\begin{equation}\label{kife}
\frac{\beta_x\alpha^{2n}-\alpha_x\beta^{2n}}{\sqrt{D}}+\underbrace{
\frac{1}{A}\left(\frac{\beta\Delta}{D}-\frac{1-\beta^2}{\sqrt{D}}c\right)\alpha^{2n}+
\frac{1}{A}\left(\frac{\alpha\Delta}{D}+\frac{1-\alpha^2}{\sqrt{D}}c\right)\beta^{2n}-
\left(\frac{\Delta}{D}(\alpha\beta)^n-c\right)}_{W}.
\end{equation}
Here, the first summand is just $x_{2n}$. Now we show that the remaining part of (\ref{kife}), denoted by $W$, vanishes under certain conditions. First, suppose that $c=0$ and $\Delta=0$. Then, obviously $W=0$. 

Assume now $c\ne0$, and consider the case $B=-1$ (i.e.,~$\alpha\beta=1$) with $\Delta=cD$. It follows that
$$
W=\frac{c}{A}\left(\beta-\frac{1-\beta^2}{\sqrt{D}}\right)\alpha^{2n}+\frac{c}{A}\left(\alpha+\frac{1-\alpha^2}{\sqrt{D}}\right)\beta^{2n}=
\frac{c}{A\sqrt{D}}\left(\alpha^{2n}-\beta^{2n}\right)(\alpha\beta-1).
$$
But the last factor vanishes since $\alpha\beta=1$. Consequently, $W$ is zero again.

In the third case, we have $\beta=\pm1$ and $\Delta=0$. Thus,
$$
W=\frac{c}{A}\left(-\frac{1-\beta^2}{\sqrt{D}}\right)\alpha^{2n}+\frac{c}{A}\left(\frac{1-\alpha^2}{\sqrt{D}}\right)\beta^{2n}+c=
\frac{c}{A}\left(\frac{1-\alpha^2}{\sqrt{D}}\right)+c=\frac{c}{A\sqrt{D}}(1-\beta^2)=0.
$$
The proof is therefore complete.
\end{proof}


%-------------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------------


\section{The system $x_{2n}=G_nH_n+c$, $x_{2n+1}=J_nK_n+c$}

The investigation here is based on the results of the previous sections. We have to handle only two more problems, namely the question of the translation by 1 in the subscript, and the question of putting two subsequences of $\{x\}$ together.

According to the definition of $\Delta$, we introduce the notation
$\Delta_2=(2J_1-AJ_0)K_1-(2BJ_0+AJ_1)K_0\in\mathbb{Z}$.
The next statement is an immediate consequence of Theorem \ref{t:nec1}.

\begin{theorem}\label{t5}
Suppose that $c\in\mathbb{Z}$ and the sequences $\{G\}$, $\{H\}$, $\{J\}$, $\{K\}$ and $\{x\}$, all are in $\cal B$, satisfy $x_{2n}=G_nH_n+c$ and $x_{2n+1}=J_nK_n+c$. Suppose furthermore that the following two conditions
\begin{itemize}
	\item If $c=0$ then $\Delta=\Delta_2=0$, 
	\item if $c\ne0$ then either $B=-1$, $\Delta=\Delta_2=Dc$ or $\beta=\pm1$, $\Delta=\Delta_2=0$
\end{itemize}
hold.
\end{theorem}


Recall, that $A&gt;0,~B\ne0$ with $D\ne0$. Now we are going to formulate the reciprocal of Theorem \ref{t5}. 

\begin{theorem}
Let $c\in\mathbb{Z}$ be given. Suppose that $\{G_n\}$, $\{H_n\}$, $\{J_n\}$, $\{K_n\}$ all are elements of the set ${\cal B}$, and the integers $G_i,~H_i,~J_i,~K_i$ ($i=0,~1$) fulfill one of the following conditions
\begin{itemize}
	\item $\Delta=\Delta_2=0$ if $c=0$;
	\item $B=-1$ and $\Delta=\Delta_2=Dc$ if $c\ne0$;
	\item $\beta=\pm1$ and $\Delta=\Delta_2=0$ if $c\ne0$.
\end{itemize}
If
$x_0=G_0H_0+c$, $x_1=J_0K_0+c$, $x_2=G_1H_1+c$ and $x_3=J_1K_1+c$ satisfy $x_2=Ax_1+Bx_0$ and $x_3=Ax_2+Bx_1$,  then the sequence $\{x_n\}$ given by
$$
x_{2n}=G_n H_n+c\quad,\quad x_{2n+1}=J_n K_n+c,\qquad n\in\mathbb{N}
$$
belongs to ${\cal B}$.
\end{theorem}


\begin{proof}
First we prove that, under the given conditions, the relation $x_{2n+2}=Ax_{2n+1}+Bx_{2n}$ holds, i.e.,
$$
G_{n+1}H_{n+1}+c=A(J_{n}K_{n}+c)+B(G_{n}H_{n}+c).
$$
By (\ref{expl}), it is equivalent to
\begin{eqnarray*}
&amp; &amp;\frac{\beta_G\alpha^{n+1}-\alpha_G\beta^{n+1}}{\sqrt{D}} \frac{\beta_H\alpha^{n+1}-\alpha_H\beta^{n+1}}{\sqrt{D}}+c= \\
&amp; &amp;=A\left(\frac{\beta_J\alpha^{n}-\alpha_J\beta^{n}}{\sqrt{D}} \frac{\beta_K\alpha^{n}-\alpha_K\beta^{n}}{\sqrt{D}}+c\right)+B
\left(\frac{\beta_G\alpha^{n}-\alpha_G\beta^{n}}{\sqrt{D}} \frac{\beta_H\alpha^{n}-\alpha_H\beta^{n}}{\sqrt{D}}+c\right),
\end{eqnarray*}
which in turn is equivalent to
\begin{multline}\label{marci1}
\alpha^{2n}
\underbrace{\left((\alpha^2-B)\beta_G
\beta_H-A\beta_J\beta_K\right)}_{W_1}
+\beta^{2n}\underbrace{\left((\beta^2-B)\alpha_G
\alpha_H-A\alpha_J\alpha_K\right)}_{W_2}+  \\
\underbrace{(-B)\left(2B\Delta+A\Delta_2\right)+(1-A-B)Dc}_{W_3}=0.
\end{multline}
%where the left hand side of (\ref{marci1}) is splitted up three terms with coefficients $W_1$, $W_2$ and $W_3$.

The value of $W_3$ seems to be the simplest to determine. Obviously, $\Delta=\Delta_2=0$, and $c=0$ provide immediately $W_3=0$. If $c\ne0$ and $\Delta=\Delta_2=Dc$, $B=-1$, then again $W_3=0$.
Otherwise, when $c\ne0$ and $\Delta=\Delta_2=0$, $\beta=\pm1$, we must distinguish two cases. When $\beta=1$, we obtain $W_3=0$, while $\beta=-1$ we get $W_3=2(1-\alpha)Dc$. 

We next compute $W_1$. Here condition $\alpha^2-B=A\alpha$, together with the definition of $\beta_G,~\beta_H,~\beta_J$ and $\beta_K$, provides 
\begin{equation}\label{pentek}
W_1=A\left(\alpha G_1H_1-\beta BG_0H_0+B(G_1H_0+G_0H_1)\right)- \\
\frac{A}{\alpha}\left(\alpha J_1K_1-\beta BJ_0K_0+B(J_1K_0+J_0K_1)\right).
\end{equation}
We can replace the terms $G_1H_0+G_0H_1$ and $J_1K_0+J_0K_1$ in (\ref{pentek}) by
$$
\frac{2G_1H_1-2BG_0H_0-\Delta}{A}\quad\text{and}\quad \frac{2J_1K_1-2BJ_0K_0-\Delta_2}{A},
$$
respectively. Thus,
\begin{eqnarray*}
W_1&amp;=&amp;(A\alpha+2B)G_1H_1-B(\beta A+2B)G_0H_0-B\Delta- \\
&amp;&amp; \frac{1}{\alpha}\left(
(A\alpha+2B)J_1K_1-B(\beta A+2B)J_0K_0-B\Delta_2\right)\\
&amp;=&amp; \left(\alpha\sqrt{D}G_1H_1+\beta B\sqrt{D}G_0H_0-B\Delta\right)- \\
&amp;&amp;
\frac{1}{\alpha}\left(\alpha\sqrt{D}J_1K_1+\beta B\sqrt{D}J_0K_0-B\Delta_2\right),
\end{eqnarray*}
since $\alpha A+2B=\alpha\sqrt{D}$ and $B(\beta A+2B)=-\beta B\sqrt{D}$.
Using $G_0H_0=x_0-c$, etc., it follows that
$$
W_1=\sqrt{D}\left(
(\alpha x_2-x_3)+\frac{\beta B}{\alpha}(\alpha x_0-x_1)+\left(1-\alpha-\beta B+\frac{\beta B}{\alpha}\right)c\right)+\left(\frac{\Delta_2}{\alpha}-\Delta\right)B.
$$
We use $x_3=Ax_2+Bx_1$ and $x_2=Ax_1+Bx_0$ to get $\alpha x_2-x_3=\beta^2(\alpha x_0-x_1)$. Consequently,
we get $(\alpha x_2-x_3)+\frac{\beta B}{\alpha}(\alpha x_0-x_1)=0$. Since $1-\alpha-\beta B+\beta B/\alpha=(\alpha-1)(\beta^2-1)$, we conclude that
\begin{equation}\label{conj1}
W_1=\sqrt{D}(\alpha-1)(\beta^2-1)c+B\left(\frac{\Delta_2}{\alpha}-\Delta\right).
\end{equation}
Similar arguments applied to $W_2$ give
\begin{equation}\label{conj2}
W_2=-\sqrt{D}(\beta-1)(\alpha^2-1)c+B\left(\frac{\Delta_2}{\beta}-\Delta\right).
\end{equation}
Note that if $\alpha\not\in\mathbb{Z}$ then $W_1$ and $W_2$ are conjugates, therefore (\ref{conj2}) comes directly from (\ref{conj1}).
 
Clearly, $W_1=W_2=0$ if $c=0$ and $\Delta=\Delta_2=0$ hold. Now consider the second possibility, when $c\ne0$, $\Delta=\Delta_2=Dc$ and $B=-1$. The last condition shows that $\beta$ is the reciprocal of $\alpha$. Thus, the coefficients $(\alpha-1)(\beta^2-1)$ and $(\beta-1)(\alpha^2-1)$ in (\ref{conj1}) and (\ref{conj2}), respectively, coincide $(\beta-1)\sqrt{D}$ and $-(\alpha-1)\sqrt{D}$, respectively. Hence, $W_1=W_2=0$ holds again.
Finally,  $c\ne0$ and $\Delta=\Delta_2=0$ yield $W_1=\sqrt{D}c(1-\alpha)(1-\beta^2)$ and $W_2=-\sqrt{D}c(1-\beta)(1-\alpha^2)$. This leads to $\beta=\pm1$. Subsequently, $W_1=0$, while
$W_2=0$, or $W_2=-2\sqrt{D}(1-\alpha^2)$ depending on the sign of $\beta$. 
 
%Turn now to the computation of $W_2$. Unless $\beta=\pm1$, the coefficient $W_2$ in (\ref{marci1}) is a conjugate of %$W_1$, therefore $W_2=0$. In the third case, using the method employed to $W_1$, we get %$W_2=-\sqrt{D}c(1-\beta)(1-\alpha^2)$. Note, that this is zero only if $\beta=1$, meanwhile  %$W_2=-2\sqrt{D}c(1-\alpha^2)$ when $\beta=-1$.

Consider now $W_1$, $W_2$ and $W_3$ again. Ignoring the trivial cases, it is sufficient to look at only the case $\beta=-1$. Now $W_1=0$, $W_2=-2\sqrt{D}c(1-\alpha^2)$ and $W_3=2(1-\alpha)Dc$. Therefore,
$$
x_{2n+2}-Ax_{2n+1}-Bx_{2n}=0\cdot\alpha^{2n}-2\sqrt{D}c(1-\alpha^2)(-1)^{2n}+2(1-\alpha)Dc=-2\sqrt{D}c(1-\alpha)(1+\beta)=0.
$$

So, we have showed that $x_{2n+2}=Ax_{2n+1}+Bx_{2n}$. 
The argument for $x_{2n+3}=Ax_{2n+2}+Bx_{2n}$ is entirely similar to the procedure we have just applied.
\end{proof}


%-------------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------------


\section{Examples}

\begin{example}{\rm
This example indicates some difficulties arising if $c\in\mathbb{Z}$, the sequence $\{G\}\in{\cal B}$ is fixed, and one intends to determine a sequence $\{H\}\in{\cal B}$ (and $\{x\}\in{\cal B}$) such that $G_nH_n+c=x_{2n}$.

Let $A=3$, $B=-1$ and $c=7$, $G_0=1$, $G_1=2$ (Sloane: \seqnum{A001519}). Thus, $D=5$, $\Delta=Dc=35$. To find $\{H\}$, it is necessary to solve the linear diophantine equation 
$$
H_1-4H_0=35
$$ 
(see Remark \ref{r2}). Clearly, it is solvable. For example, put $H_0=t\in\mathbb{Z}$ and $H_1=4t+35$. Now, by Theorem \ref{t:suff1}, we must verify that $x_1$ is an integer. Here, $x_1=3t+28$. The sequences are given by
\begin{eqnarray*}
\{G\}&amp;:&amp;\quad 1,~2,~5,~13,~\dots\;; \\
\{H\}&amp;:&amp;\quad t,~4t+35,~11t+105,~29t+280,~\dots\;; \\
\{x\}&amp;:&amp;\quad t+7,\;\;3t+28,\;\;8t+77,\;\;21t+203,\;\;55t+532,\;\;144t+1393,\;\;377t+3467,\;\;\dots\;. 
\end{eqnarray*}

It is easy to see that for any $G_1\in\mathbb{Z}$ there exist suitable sequences $\{H\}$. Indeed, for an arbitrary $G_1$ we obtain the diophantine equation  
\begin{equation}\label{dio}
(2G_1-3)H_1+(2-3G_1)H_0=35.
\end{equation}
But (\ref{dio}) is solvable in $H_1$ and $H_0$ since $\gcd(2G_1-3,2-3G_1)$ divides 5. 
}
\end{example}

Note, that there are fewer problems in the other two cases of Theorem \ref{t:suff1}, since, instead of $Dc$, the right hand side of the corresponding linear diophantine equations is zero. Therefore, we only have to guarantee $x_1\in\mathbb{Z}$. 

\begin{example} {\rm
We give a class of recurrences $\{G\}$ having no pair $\{H\}$ with the desired property. Suppose that $B=-1$, $c=1$, and to facilitate the calculations, let $G_1=G_0$.

Thus $\gcd(2G_1-AG_0,-2G_0+AG_1)=G_0\gcd(2-A,-2+A)=G_0(A-2)$. But $D=A^2-4\ne0$ excludes $A=2$, therefore
$$
G_0(A-2)\not\;\mid (A^2-4)\quad\Longleftrightarrow\quad G_0\not\;\mid (A+2). 
$$
Hence, if we choose an integer $G_0$ which does not divide $A+2$, then the linear diophantine equation 
$$G_0(2-A)H_1+G_0(A-2)H_0=A^2-4$$ is not solvable in integers $H_1$ and $H_0$.
}
\end{example}

\begin{example} {\rm
Consider now the first example in the Introduction, where the composition of four sequences was defined. Let $A=6$, $B=-1$ and $c=1$. Let also $G_0=-1$, $G_1=1$, $J_0=0$, and $J_1=2$. We have $D=32$, $\Delta=32$.
Both of the diophantine equations
\begin{eqnarray*}
8H_1-8H_0 &amp; = &amp; 32\\
4K_1-12K_0 &amp; = &amp; 32
\end{eqnarray*}
are solvable. Take the parametrizations $H_0=t\in\mathbb{Z}$, $H_1=t+4$ and  $K_0=s\in\mathbb{Z}$, $K_1=3s+8$. To join the subsequences with even and odd subscripts, we must check the recurrence relation $x_{n+2}=6x_{n+1}-x_n$. Since the four sequences 
\begin{eqnarray*}
\{G\}&amp;:&amp;\quad -1,~1,~7,~41,~\dots\;; \\
\{H\}&amp;:&amp;\quad t,~t+4,~5t+24,~29t+140,~\dots\;; \\
\{J\}&amp;:&amp;\quad 0,~2,~12,~70,~\dots\;; \\
\{K\}&amp;:&amp;\quad s,~3s+8,~17s+48,~99s+280,~\dots \\
\text{generate}\qquad\qquad\qquad\qquad\qquad &amp; &amp;  \\
\{x\}&amp;:&amp;\quad -t+1,\;\;1,\;\;t+5,\;\;6s+17,\;\;35t+169,\;\;204s+577,\;\;\dots\;, 
\end{eqnarray*}
therefore, by the given recurrence rule, $6(t+5)-1=6s+17$, or equivalently $s=t+2$ must hold. 
So we obtain
\begin{eqnarray*}
\qquad\qquad\qquad\{x\}&amp;:&amp;\quad -t+1,\;\;1,\;\;t+5,\;\;6t+29,\;\;35t+169,\;\;204t+985,\;\;\dots\; 
\end{eqnarray*}
where the particular case $t=1$ gives the sequence 
\begin{eqnarray*}
\{x\}&amp;:&amp;\quad 0,\;\;1,\;\;6,\;\;35,\;\;204,\;\;1189,\;\;\dots\;\qquad\qquad\;\; .
\end{eqnarray*}
of balancing numbers.}
\end{example}
\medskip

\section{Acknowledgements}

The authors thank the anonymous referee for valuable remarks, especially for the idea to shorten the proof of Theorem~\ref{t:nec1}.

\begin{thebibliography}{29}

\bibitem{A} J.~P.~Adams, {\it Puzzles for Everybody}, Avon Publications, 1955.

\bibitem{BP} A.~Behera and G.~Panda, On the square roots of triangular numbers, {\it Fibonacci Quart.},
{\bf 37} (1999), 98--105.

\bibitem{F} R.~P.~Finkelstein, The house problem, {\it American Math. Monthly}, {\bf 72} (1965), 1082--1088.
  
\bibitem{ST} T.~N.~Shorey and R.~Tijdeman, {\it Exponential Diophantine Equations}, Cambridge University Press, 1986.  

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 11D61.

\noindent \emph{Keywords: }  binary recurrence.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000032},
\seqnum{A000045},
\seqnum{A001109},
\seqnum{A001519},
\seqnum{A001541}, and
\seqnum{A001542}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 29 2009;
revised version received April 29 2010; May 29 2010.  
Published in {\it Journal of Integer Sequences}, June 1 2010.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

</pre></body></html>