\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>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>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>0$ implies \ $\beta<\alpha$ and \ $1<\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<\beta<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 & 1 & -1 & 1 \\ \alpha^2 & \beta^2 & -\alpha\beta & 1 \\ \alpha^4 & \beta^4 & -(\alpha\beta)^2 & 1 \\ \alpha^6 & \beta^6 & -(\alpha\beta)^3 & 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>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*} & & c=0,\; \Delta=0;\; \text{or} \\ & & c\ne0,\; B=-1,\; \Delta=Dc;\; \text{or} \\ & &c\ne0,\; \beta=\pm1, \; \Delta=0, \end{eqnarray*} hold, as well as \begin{eqnarray*} x_1&=&\frac{G_1H_1-BG_0H_0}{A}\in\mathbb{Z}, \quad\text{or} \\ x_1&=&\frac{G_1H_1+G_0H_0+2c}{A}\in\mathbb{Z}, \quad\text{or} \\ x_1&=&\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\}&:&\quad 2,~3,~32,~433,~\dots\;; \\ \{H\}&:&\quad -1,~1,~19,~261,~\dots\;; \\ \{x\}&:&\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>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*} & &\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= \\ & &=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&=&(A\alpha+2B)G_1H_1-B(\beta A+2B)G_0H_0-B\Delta- \\ && \frac{1}{\alpha}\left( (A\alpha+2B)J_1K_1-B(\beta A+2B)J_0K_0-B\Delta_2\right)\\ &=& \left(\alpha\sqrt{D}G_1H_1+\beta B\sqrt{D}G_0H_0-B\Delta\right)- \\ && \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\}&:&\quad 1,~2,~5,~13,~\dots\;; \\ \{H\}&:&\quad t,~4t+35,~11t+105,~29t+280,~\dots\;; \\ \{x\}&:&\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 & = & 32\\ 4K_1-12K_0 & = & 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\}&:&\quad -1,~1,~7,~41,~\dots\;; \\ \{H\}&:&\quad t,~t+4,~5t+24,~29t+140,~\dots\;; \\ \{J\}&:&\quad 0,~2,~12,~70,~\dots\;; \\ \{K\}&:&\quad s,~3s+8,~17s+48,~99s+280,~\dots \\ \text{generate}\qquad\qquad\qquad\qquad\qquad & & \\ \{x\}&:&\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\}&:&\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\}&:&\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}