On the Shifted Product of Binary Recurrences

Omar Khadir Department of Mathematics

University of Hassan II Mohammedia, Morocco

khadir@hotmail.com

Kálmán Liptai

Institute of Mathematics and Informatics

Eszterházy Károly College

Eger, Hungary

liptaik@gemini.ektf.hu

László Szalay^{1}

Institute of Mathematics and Statistics

University of West Hungary

Sopron, Hungary

laszalay@ktk.nyme.hu

Abstract

The present paper studies the diophantine equation G_{n}H_{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_{n}H_{n} + c = x_{2n}. Finally, a few relevant examples are provided.

1Research supported by the János Bolyai Scholarship of HAS, by the Hungarian National Foundation for Scientific Research Grant No. T 61800 FT, and by the Mexican-Hungarian bilateral TeT.

1 Introduction

Let the binary recurrences {a}_{n=0}^{∞}, {b}_{n=0}^{∞}, {c}_{n=0}^{∞} and {d}_{n=0}^{∞} satisfy the recurrence relation

X_{n+2} = 6X_{n+1} − X_{n},  n ∈ ℕ,  (1)

with the initial values

a_{0} = −1, a_{1} = 1; b_{0} = 1, b_{1} = 5; c_{0} = 0, c_{1} = 2; d_{0} = 3, d_{1} = 17;

respectively (Sloane: \{c\} is \underline{A001542}, \{d\} is \underline{A001541}). Here, and in the sequel, ℕ denotes the set of non-negative integers. By the recurrences above, we can define a fifth sequence {x}_{n=0}^{∞} via

x_{2n} = a_{n}b_{n} + 1 , x_{2n+1} = c_{n}d_{n} + 1,  n ∈ ℕ.  (2)

The sequence \{x\} (the first few terms are: 0, 1, 6, 35, 204, 1189, …, Sloane: \underline{A001109}) also satisfies (1), 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 ≥ 2 is called a balancing number for the integer y if

1 + ⋯ + (x − 1) = (x + 1) + ⋯ + (y − 1)  (3)

holds. This definition was introduced by Finkelstein [3] (he called balancing numbers numerical centers) when he solved a puzzle from the book [1]. For other properties of balancing numbers see, for example [2]. Clearly, (3) 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 (1). It is known that all real binary recurrences satisfying (1) form a vector space of dimension 2 over ℝ. Definition (2) (and later (6)) does not fit the vector space structure. The question arises which other integer binary recurrences can possess the interesting property described by (2) or its generalization.

The phenomena appearing in (2) is a specific case of a more general property. Let t ∈ ℕ^{+} and put α = t + \sqrt{t^{2} + 1}, β = t − \sqrt{t^{2} + 1}. Define the sequences \{T \}_{n=0}^{∞} and \{U\}_{n=0}^{∞} by α^{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} = 2tX_{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{α^{n} + β^{n}}{2} and U_{n} = \frac{α^{n} − β^{n}}{2\sqrt{t^{2} + 1}}

show that

U_{n∓(−1)^{n}}T_{n±(−1)^{n}} ∓ 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_{n}b_{n} + t = U_{4n}/2 ∈ ℕ and c_{n}d_{n} + t = U_{4n+2}/2 ∈ ℕ. 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 (2)

(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 ≠ 0 are integers with non-vanishing D = A^{2} + 4B, further let B denote the set of all integer binary recurrences {X}_{n=0}^{∞} satisfying the recurrence relation

X_{n+2} = AX_{n+1} + BX_{n},  n ∈ ℕ.  (4)

If {u}_{n=0}^{∞} and {v}_{n=0}^{∞} are elements of B with the initial values u_{0} = 0, u_{1} = 1 and v_{0} = 2, v_{1} = A, respectively, then the equality

u_{n}v_{n} = u_{2n}  (5)

holds for any non-negative integer n. Identity (5) is well-known, and all books or papers dealing, for instance, with the Fibonacci sequence mention the formula F_{n}L_{n} = F_{2n}, where F_{n} and L_{n} are the nth term of the Fibonacci (Sloane: \underline{A000045}) and Lucas sequences (Sloane: \underline{A000032}), respectively. Note, that the sequences \{F \} and \{L\} both satisfy (4) with A = B = 1.

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

G_{n}H_{n} + c = x_{2n+l},  (6)

where {G}_{n=0}^{∞}, {H}_{n=0}^{∞} and {x}_{n=0}^{∞} belong to the class of binary recurrences given by (4). 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}^{∞} also belong to B. Analogously to (2), we investigate and determine the binary recurrences {H} and {K}_{n=0}^{∞} of B, which generate a sequence {x} ∈ B satisfying

x_{2n} = G_{n}H_{n} + c , x_{2n+1} = J_{n}K_{n} + c, 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 ≠ 0, 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.

2 Preliminaries

For any complex numbers α, β, … and for any sequence {X}_{n=0}^{∞} ∈ B put α_{X} = X_{1} − αX_{0}, β_{X} = X_{1} − βX_{0}, etc. Recall, that A > 0 and B ≠ 0 are integers and D = A^{2} + 4B ≠ 0.

Lemma 1. Assume that \{G\} ∈ B. Then the zeros α = (A + \sqrt{D})/2 and β = (A − \sqrt{D})/2 of the companion polynomial p(x) = x^{2} − Ax − B of {G} are distinct and nonzero. Further • αβ = −B, α + β = A, α − β = \sqrt{D},

• D > 0 implies β < α and 1 < α.

Moreover,

G_{n} = \frac{β_{G}α^{n} − α_{G}β^{n}}{\sqrt{D}} .  (7)

Proof. All formulae and statements of Lemma 1 are known. Nevertheless, the first two conditions are immediate from the determination of α and β, while (7) can be derived from the basic theorem concerning the linear recurrences (see, for instance, [4]). Note that α and β are conjugate zeros of p(x) if they are not integers.

Remark 2. Later we will use the results of Lemma 1 without any comment.

In the present and next sections we assume that c ∈ ℤ, l = 0. Further {G} ∈ B, {H} ∈ B and {x} ∈ B satisfy (6).

Lemma 3.

x_{1} = \frac{G_{1}H_{1} − BG_{0}H_{0} + c(1 − B)}{A}.

Proof. Combining x_{0} = G_{0}H_{0} + c, x_{2} = G_{1}H_{1} + c and x_{2} = Ax_{1} + Bx_{0}, we immediately get the desired statement.

Now we define some important constants which will be useful in studying our problems. Put

E_{α} = \frac{β_{G}β_{H}}{D} − \frac{β_{x}}{\sqrt{D}},  E_{β} = \frac{α_{G}α_{H}}{D} + \frac{α_{x}}{\sqrt{D}},  E_{αβ} = \frac{β_{G}α_{H} + α_{G}β_{H}}{D} .  (8)

Further, let

Δ = (2G_{1} − AG_{0})H_{1} − (2BG_{0} + AG_{1})H_{0} ∈ ℤ.  (9)

Remark 4. We call {G̃}_{n=0}^{∞} the companion sequence of {G} ∈ B if {G̃} is also in B and G̃_{0} = 2G_{1} − AG_{0}, G̃_{1} = 2BG_{0} + AG_{1}. Thus, Δ can be simplified as G̃_{0}H_{1} − G̃_{1}H_{0}.

Sometimes it is more convenient to write (9) in the form Δ = 2G_{1}H_{1} − 2BG_{0}H_{0} − A(G_{1}H_{0} + G_{0}H_{1}).

Lemma 5. The quantities from (8) can also be given in the forms

E_{α} = \frac{β}{AD} (Δ − \frac{1 − β^{2}}{β} \sqrt{D}c) ,  E_{β} = \frac{α}{AD} (Δ + \frac{1 − α^{2}}{α} \sqrt{D}c) ,  E_{αβ} = \frac{Δ}{D}. (10)

Proof. Recall the definition of E_{α} and β_{G} = G_{1} − βG_{0}, β_{H} = H_{1} − βH_{0}, β_{x} = x_{1} − βx_{0}, x_{0} = G_{0}H_{0} + c. These formulae, together with Lemma 3, yield

E_{α} = \frac{β}{AD} (2G_{1}H_{1} − 2BG_{0}H_{0} − A(G_{1}H_{0} + G_{0}H_{1}) − \frac{1 − β^{2}}{β} \sqrt{D}c) .

In order to complete the proof on E_{α}, observe that the first three terms in the paranthesis above make up Δ (see Remark 4).

If α ∉ ℤ, then E_{β} is a conjugate of E_{α}; hence, the second part of the lemma is obvious. Otherwise, we can use the same procedure we applied to E_{α}.

Finally, one can easily get E_{αβ} = Δ/D from the parts of definition (8) concerned with E_{αβ}.

3 The equation G_{n}H_{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 (6).

Theorem 6. Let c ∈ ℤ. If there exist sequences {G} ∈ B, {H} ∈ B and {x} ∈ B such that G_{n}H_{n} + c = x_{2n} then one of the following cases holds.

• If c = 0 then Δ = 0;

• if c ≠ 0 then either B = −1, Δ = Dc; or β = ±1, Δ = 0.

Remark 7. The assertion B = −1, together with β ∈ ℝ implies 0 < β < 1. Then the two instances in the second part of Theorem 6 are not-overlapping.

Proof. G_{n}H_{n} + c = x_{2n} is equivalent to

E_{α}α^{2n} + E_{β}β^{2n} − E_{αβ}(αβ)^{n} + c = 0,  n ∈ ℕ.  (11)

Since (11) is true for all n, therefore it is true for n = 0, 1, 2, 3. Consequently, (11) at n = 0, 1, 2, 3 is a homogeneous linear system of four equations in the unknowns E_{α}, E_{β}, E_{αβ} and c. The determinant

D = | \begin{matrix}1 & 1 & −1 & 1 \\ α^{2} & β^{2} & −αβ & 1 \\ α^{4} & β^{4} & −(αβ)^{2} & 1 \\ α^{6} & β^{6} & −(αβ)^{3} & 1 \end{matrix} |

of the coefficient matrix is the negative of the Vandermonde of α^{2}, β^{2}, αβ and 1. Hence,

D = −V (α^{2}, β^{2}, αβ, 1) = αβ(α − β)^{3}(α + β)(1 − α^{2})(1 − β^{2})(1 − αβ).  (12)

If the homogeneous system has only the trivial solution c = 0 and E_{α} = E_{β} = E_{αβ} = 0, then, by Lemma 5, we obtain

E_{α} = \frac{β}{AD}Δ = 0,  E_{β} = \frac{α}{AD}Δ = 0,  E_{αβ} = \frac{1}{D}Δ = 0.

The coefficient of Δ is nonzero in any of the three equalities. Subsequently, Δ = 0 follows.

If the system has infinitely many solutions, then D = 0. Recalling (12) and the conditions αβ ≠ 0, α ≠ β (see Lemma 1), we distinguish four cases.

1. α + β = 0. We deduce a degenerate recursion characterized by α/β = −1. Thus A = 0, and we have arrived at a contradiction.

2. 1 − α^{2} = 0. Now α = ±1 ∈ ℝ. This is impossible since α > 1 holds.

3. 1 − β^{2} = 0. Both cases β = ±1 lead to the solutions E_{α} = E_{αβ} = 0 and E_{β} = −c, where c is a free variable. Clearly, by (10), E_{αβ} implies Δ = 0.

4. 1 − αβ = 0. Obviously, B = −1. Moreover D = A^{2} − 4 ≠ 0 yields A ≠ 2. The infinitely many solutions of the system can be described by E_{α} = E_{β} = 0 and

c = −\frac{αβ(α − β)^{2}}{(α^{2} − 1)(β^{2} − 1)}E_{αβ}.  (13)

Since αβ = B and (α − β)^{2} = A^{2} − 4, relation (13) together with (α^{2} − 1)(β^{2} − 1) = (Aα − 2)(Aβ − 2) = −A^{2} + 4 gives E_{αβ} = c, where c is a free variable. Then, again by (10), Δ = Dc.

Theorem 6 provides necessary conditions for the sequences {G}, {H} and {x} satisfying G_{n}H_{n} + c = x_{2n}. Now we show that the conditions are, essentially, sufficient as well. More precisely, we prove the following theorem.

Theorem 8. Suppose that the integers c, G_{0}, G_{1}, H_{0} and H_{1} are fixed. Put x_{0} = G_{0}H_{0} + c. If

c = 0, Δ = 0; or
c ≠ 0, B = −1, Δ = Dc; or
c ≠ 0, β = ±1, Δ = 0,

hold, as well as

x_{1} = \frac{G_{1}H_{1} − BG_{0}H_{0}}{A} ∈ ℤ, or
x_{1} = \frac{G_{1}H_{1} + G_{0}H_{0} + 2c}{A} ∈ ℤ, or
x_{1} = \frac{G_{1}H_{1} − BG_{0}H_{0} + (1 − B)c}{A} ∈ ℤ,

respectively, then the terms of the sequences {G} ∈ B, {H} ∈ B and {x} ∈ B satisfy

G_{n}H_{n} + c = x_{2n}, n ∈ ℕ.

Remark 9. Theorem 8 asserts necessarily that x_{1} is an integer, otherwise {x} would not be an integer sequence although it satisfies G_{n}H_{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 Δ = 0, x_{1} = −1/2, and

{G} : 2, 3, 32, 433, …;
{H} : −1, 1, 19, 261, …;
\{x\} : −2 = G_{0}H_{0}, −\frac{1}{2}, 3 = G_{1}H_{1}, \frac{89}{2}, 608 = G_{2}H_{2}, \frac{16579}{2}, 113013 = G_{3}H_{3}, ….

Proof. We will use the notation of the previous sections. By (9), it is easy to verify that G_{1}H_{0} + G_{0}H_{1} = (2G_{1}H_{1} − 2BG_{0}H_{0} − Δ)/A. Combining it with

β_{G}β_{H} = G_{1}H_{1}+β^{2}G_{0}H_{0}−β(G_{1}H_{0}+G_{0}H_{1}) and α_{G}α_{H} = G_{1}H_{1}+α^{2}G_{0}H_{0}−α(G_{1}H_{0}+G_{0}H_{1}), respectively, we obtain

β_{G}β_{H} = \frac{\sqrt{D}(G_{1}H_{1} − β^{2}G_{0}H_{0}) + βΔ}{A} and α_{G}α_{H} = \frac{\sqrt{D}(−G_{1}H_{1} + α^{2}G_{0}H_{0}) + αΔ}{A}.

(14)

By x_{0} = G_{0}H_{0} + c and Lemma 3, we also have

β_{x} = x_{1}−βx_{0} = \frac{G_{1}H_{1} − β^{2}G_{0}H_{0} + (1 − β^{2})c}{A} and α_{x} = x_{1}−αx_{0} = \frac{G_{1}H_{1} − α^{2}G_{0}H_{0} + (1 − α^{2})c}{A}.

(15)

Thus, by (14) and (15),

G_{n}H_{n} + c = \frac{β_{G}α^{n} − α_{G}β^{n}}{\sqrt{D}} \frac{β_{H}α^{n} − α_{H}β^{n}}{\sqrt{D}} + c = \frac{β_{G}β_{H}α^{2n} + α_{G}α_{H}β^{2n} − Δ(αβ)^{n} + cD}{D},

which is equivalent to

\frac{β_{x}α^{2n} − α_{x}β^{2n}}{\sqrt{D}} + \underbrace{\frac{1}{A} (\frac{βΔ}{D} − \frac{1 − β^{2}}{\sqrt{D}} c) α^{2n} + \frac{1}{A} (\frac{αΔ}{D} + \frac{1 − α^{2}}{\sqrt{D}} c) β^{2n} − (\frac{Δ}{D}(αβ)^{n} − c)}_{W} .

(16)

Here, the first summand is just x_{2n}. Now we show that the remaining part of (16), denoted by W, vanishes under certain conditions. First, suppose that c = 0 and Δ = 0. Then, obviously W = 0.

Assume now c ≠ 0, and consider the case B = −1 (i.e., αβ = 1) with Δ = cD. It follows that

W = \frac{c}{A} (β − \frac{1 − β^{2}}{\sqrt{D}} ) α^{2n} + \frac{c}{A} (α + \frac{1 − α^{2}}{\sqrt{D}} ) β^{2n} = \frac{c}{A\sqrt{D}} (α^{2n} − β^{2n}) (αβ − 1).

But the last factor vanishes since αβ = 1. Consequently, W is zero again.

In the third case, we have β = ±1 and Δ = 0. Thus,

W = \frac{c}{A} (−\frac{1 − β^{2}}{\sqrt{D}} ) α^{2n} + \frac{c}{A} (\frac{1 − α^{2}}{\sqrt{D}} ) β^{2n} + c = \frac{c}{A} (\frac{1 − α^{2}}{\sqrt{D}} ) + c = \frac{c}{A\sqrt{D}}(1 − β^{2}) = 0.

The proof is therefore complete.

4 The system x_{2n} = G_{n}H_{n} + c, x_{2n+1} = J_{n}K_{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 Δ, we introduce the notation Δ_{2} = (2J_{1} − AJ_{0})K_{1} − (2BJ_{0} + AJ_{1})K_{0} ∈ ℤ. The next statement is an immediate consequence of Theorem 6.

Theorem 10. Suppose that c ∈ ℤ and the sequences {G}, {H}, {J}, {K} and {x}, all are in B, satisfy x_{2n} = G_{n}H_{n} + c and x_{2n+1} = J_{n}K_{n} + c. Suppose furthermore that the following two conditions • If c = 0 then Δ = Δ_{2} = 0,

• if c ≠ 0 then either B = −1, Δ = Δ_{2} = Dc or β = ±1, Δ = Δ_{2} = 0 hold.

Recall, that A > 0, B ≠ 0 with D ≠ 0. Now we are going to formulate the reciprocal of Theorem 10. Theorem 11. Let c ∈ ℤ be given. Suppose that {G_{n}}, {H_{n}}, {J_{n}}, {K_{n}} all are elements of the set B, and the integers G_{i}, H_{i}, J_{i}, K_{i} (i = 0, 1) fulfill one of the following conditions

• Δ = Δ_{2} = 0 if c = 0;

• B = −1 and Δ = Δ_{2} = Dc if c ≠ 0;

• β = ±1 and Δ = Δ_{2} = 0 if c ≠ 0. If x_{0} = G_{0}H_{0} + c, x_{1} = J_{0}K_{0} + c, x_{2} = G_{1}H_{1} + c and x_{3} = J_{1}K_{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 , x_{2n+1} = J_{n}K_{n} + c, n ∈ ℕ

belongs to B. 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 (7), it is equivalent to

\frac{β_{G}α^{n+1} − α_{G}β^{n+1}}{\sqrt{D}} \frac{β_{H}α^{n+1} − α_{H}β^{n+1}}{\sqrt{D}} + c =

= A (\frac{β_{J}α^{n} − α_{J}β^{n}}{\sqrt{D}} \frac{β_{K}α^{n} − α_{K}β^{n}}{\sqrt{D}} + c) + B (\frac{β_{G}α^{n} − α_{G}β^{n}}{\sqrt{D}} \frac{β_{H}α^{n} − α_{H}β^{n}}{\sqrt{D}} + c) ,

which in turn is equivalent to

α^{2n} \underbrace{((α^{2} − B)β_{G}β_{H} − Aβ_{J}β_{K})}_{W_{1}} +β^{2n} \underbrace{((β^{2} − B)α_{G}α_{H} − Aα_{J}α_{K})}_{W_{2}} +

\underbrace{(−B) (2BΔ + AΔ_{2}) + (1 − A − B)Dc}_{W_{3}} = 0. (17)

The value of W_{3} seems to be the simplest to determine. Obviously, Δ = Δ_{2} = 0, and c = 0 provide immediately W_{3} = 0. If c ≠ 0 and Δ = Δ_{2} = Dc, B = −1, then again W_{3} = 0. Otherwise, when c ≠ 0 and Δ = Δ_{2} = 0, β = ±1, we must distinguish two cases. When β = 1, we obtain W_{3} = 0, while β = −1 we get W_{3} = 2(1 − α)Dc.

We next compute W_{1}. Here condition α^{2} − B = Aα, together with the definition of β_{G}, β_{H}, β_{J} and β_{K}, provides

W_{1} = A (αG_{1}H_{1} − βBG_{0}H_{0} + B(G_{1}H_{0} + G_{0}H_{1}))−\frac{A}{α} (αJ_{1}K_{1} − βBJ_{0}K_{0} + B(J_{1}K_{0} + J_{0}K_{1})) .

(18)

We can replace the terms G_{1}H_{0} + G_{0}H_{1} and J_{1}K_{0} + J_{0}K_{1} in (18) by

\frac{2G_{1}H_{1} − 2BG_{0}H_{0} − Δ}{A} and \frac{2J_{1}K_{1} − 2BJ_{0}K_{0} − Δ_{2}}{A} ,

respectively. Thus,

W_{1} = (Aα + 2B)G_{1}H_{1} − B(βA + 2B)G_{0}H_{0} − BΔ −
\frac{1}{α} ((Aα + 2B)J_{1}K_{1} − B(βA + 2B)J_{0}K_{0} − BΔ_{2})
= (α\sqrt{D}G_{1}H_{1} + βB\sqrt{D}G_{0}H_{0} − BΔ) −

\frac{1}{α} (α\sqrt{D}J_{1}K_{1} + βB\sqrt{D}J_{0}K_{0} − BΔ_{2}) ,

since αA + 2B = α\sqrt{D} and B(βA + 2B) = −βB\sqrt{D}. Using G_{0}H_{0} = x_{0} − c, etc., it follows that

W_{1} = \sqrt{D} ((αx_{2} − x_{3}) + \frac{βB}{α} (αx_{0} − x_{1}) + (1 − α − βB + \frac{βB}{α} ) c) + (\frac{Δ_{2}}{α} − Δ) B.

We use x_{3} = Ax_{2} + Bx_{1} and x_{2} = Ax_{1} + Bx_{0} to get αx_{2} − x_{3} = β^{2}(αx_{0} − x_{1}). Consequently, we get (αx_{2} − x_{3}) + \frac{βB}{α} (αx_{0} − x_{1}) = 0. Since 1 − α − βB + βB/α = (α − 1)(β^{2} − 1), we conclude that

W_{1} = \sqrt{D}(α − 1)(β^{2} − 1)c + B (\frac{Δ_{2}}{α} − Δ) .  (19)

Similar arguments applied to W_{2} give

W_{2} = −\sqrt{D}(β − 1)(α^{2} − 1)c + B (\frac{Δ_{2}}{β} − Δ) .  (20)

Note that if α ∉ ℤ then W_{1} and W_{2} are conjugates, therefore (20) comes directly from (19).

Clearly, W_{1} = W_{2} = 0 if c = 0 and Δ = Δ_{2} = 0 hold. Now consider the second possibility, when c ≠ 0, Δ = Δ_{2} = Dc and B = −1. The last condition shows that β is the reciprocal of α. Thus, the coefficients (α − 1)(β^{2} − 1) and (β − 1)(α^{2} − 1) in (19) and (20), respectively, coincide (β−1)\sqrt{D} and −(α−1)\sqrt{D}, respectively. Hence, W_{1} = W_{2} = 0 holds again. Finally, c ≠ 0 and Δ = Δ_{2} = 0 yield W_{1} = \sqrt{D}c(1−α)(1−β^{2}) and W_{2} = −\sqrt{D}c(1−β)(1−α^{2}). This leads to β = ±1. Subsequently, W_{1} = 0, while W_{2} = 0, or W_{2} = −2\sqrt{D}(1 − α^{2}) depending on the sign of β.

Consider now W_{1}, W_{2} and W_{3} again. Ignoring the trivial cases, it is sufficient to look at only the case β = −1. Now W_{1} = 0, W_{2} = −2\sqrt{D}c(1−α^{2}) and W_{3} = 2(1−α)Dc. Therefore,

x_{2n+2}−Ax_{2n+1}−Bx_{2n} = 0·α^{2n}−2\sqrt{D}c(1−α^{2})(−1)^{2n}+2(1−α)Dc = −2\sqrt{D}c(1−α)(1+β) = 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.

5 Examples

Example 12. This example indicates some difficulties arising if c ∈ ℤ, the sequence {G} ∈ B is fixed, and one intends to determine a sequence {H} ∈ B (and {x} ∈ B) such that G_{n}H_{n} + c = x_{2n}.

Let A = 3, B = −1 and c = 7, G_{0} = 1, G_{1} = 2 (Sloane: \underline{A001519}). Thus, D = 5, Δ = Dc = 35. To find {H}, it is necessary to solve the linear diophantine equation

H_{1} − 4H_{0} = 35

(see Remark 4). Clearly, it is solvable. For example, put H_{0} = t ∈ ℤ and H_{1} = 4t + 35. Now, by Theorem 8, we must verify that x_{1} is an integer. Here, x_{1} = 3t + 28. The sequences are given by

{G} : 1, 2, 5, 13, …;
{H} : t, 4t + 35, 11t + 105, 29t + 280, …;
{x} : t + 7, 3t + 28, 8t + 77, 21t + 203, 55t + 532, 144t + 1393, 377t + 3467, ….

It is easy to see that for any G_{1} ∈ ℤ there exist suitable sequences {H}. Indeed, for an arbitrary G_{1} we obtain the diophantine equation

(2G_{1} − 3)H_{1} + (2 − 3G_{1})H_{0} = 35.  (21)

But (21) is solvable in H_{1} and H_{0} since gcd(2G_{1} − 3, 2 − 3G_{1}) divides 5.

Note, that there are fewer problems in the other two cases of Theorem 8, since, instead of Dc, the right hand side of the corresponding linear diophantine equations is zero. Therefore, we only have to guarantee x_{1} ∈ ℤ.

Example 13. 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 ≠ 0 excludes A = 2, therefore

G_{0}(A − 2) |̸ (A^{2} − 4) ⟺ G_{0} |̸ (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}.

Example 14. 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, Δ = 32. Both of the diophantine equations

8H_{1} − 8H_{0} = 32
4K_{1} − 12K_{0} = 32

are solvable. Take the parametrizations H_{0} = t ∈ ℤ, H_{1} = t+4 and K_{0} = s ∈ ℤ, 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

{G} : −1, 1, 7, 41, …;
{H} : t, t + 4, 5t + 24, 29t + 140, …;
{J} : 0, 2, 12, 70, …;
{K} : s, 3s + 8, 17s + 48, 99s + 280, …

generate

{x} : −t + 1, 1, t + 5, 6s + 17, 35t + 169, 204s + 577, …,

therefore, by the given recurrence rule, 6(t + 5) − 1 = 6s + 17, or equivalently s = t + 2 must hold. So we obtain

{x} : −t + 1, 1, t + 5, 6t + 29, 35t + 169, 204t + 985, …

where the particular case t = 1 gives the sequence

{x} : 0, 1, 6, 35, 204, 1189, …  .

of balancing numbers.

6 Acknowledgements

The authors thank the anonymous referee for valuable remarks, especially for the idea to shorten the proof of Theorem 6.

References

[1] J. P. Adams, Puzzles for Everybody, Avon Publications, 1955.

[2] A. Behera and G. Panda, On the square roots of triangular numbers, Fibonacci Quart., 37 (1999), 98–105.

[3] R. P. Finkelstein, The house problem, American Math. Monthly, 72 (1965), 1082–1088.

[4] T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations, Cambridge University Press, 1986.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11D61. Keywords: binary recurrence.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A001109}, \underline{A001519}, \underline{A001541}, and \underline{A001542}.) Received August 29 2009; revised version received April 29 2010; May 29 2010. Published in Journal of Integer Sequences, June 1 2010. Return to Journal of Integer Sequences home page.