Decomposable Forms Generated by Linear Recurrences

Kálmán Győry Institute of Mathematics University of Debrecen

Egyetem tér 1 Debrecen H4032

Hungary

gyory@science.unideb.hu

Attila Pethő Institute of Computer Sciences

University of Debrecen

Kassai út 26 Debrecen H4028

Hungary

petho.attila@unideb.hu

László Szalay Department of Mathematics

J. Selye University

Hradná 21 Komárno 945 01

Slovakia

and

Institute of Informatics and Mathematics University of Sopron Bajcsy Zs. utca 4 Sopron H9400

Hungary

szalay.laszlo@uni-sopron.hu

Abstract

Consider k ≥ 2 distinct, linearly independent, homogeneous linear recurrences of order k satisfying the same recurrence relation. We prove that the recurrences are related to a decomposable form of degree k, and there is a general identity with a suitable exponential expression depending on the recurrences. This identity is a common and very broad generalization of several known identities. Further, if the recurrences are integer sequences, then the diophantine equation associated with the decomposable form and the exponential term has infinitely many integer solutions generated by the terms of the recurrences. We describe a method for the complete factorization of the decomposable form. Both the form and its decomposition are explicitly given if k = 2, and we present a typical example for k = 3. The basic tool we use is the matrix method.

1 Introduction

Let k be an integer with k ≥ 2. A sequence (G_{n}) of complex numbers is called a linear recurrence of order k if there exist γ_{0}, …, γ_{k−1} ∈ ℂ such that

G_{n+k} = γ_{k−1}G_{n+k−1} + ⋯ + γ_{0}G_{n}  (1)

holds for all n ≥ 0, where k is the smallest integer with this property. The polynomial

P (X) = X^{k} − γ_{k−1}X^{k−1} − ⋯ − γ_{0}  (2)

is the characteristic polynomial of (G_{n}). Note that the definition of the order implies that γ_{0} ≠ 0.

Dividing (1) by γ_{0} ≠ 0 and rearranging the equality, we obtain

G_{n} = −\frac{γ_{1}}{γ_{0}} G_{n+1} − ⋯ − \frac{γ_{k−1}}{γ_{0}} G_{n+k−1} + \frac{1}{γ_{0}} G_{n+k}.

Now applying the substitution n → −n − k we find

G_{−(n+k)} = −\frac{γ_{1}}{γ_{0}} G_{−(n+k−1)} − ⋯ − \frac{γ_{k−1}}{γ_{0}} G_{−(n+1)} + \frac{1}{γ_{0}} G_{−n},

which is a linear recursion for the negative branch of (G_{n}). The results of the present paper hold for this two-sided infinite sequence, which we can also consider as a number-theoretic function G_{n} : ℤ ↦ ℂ.

There exist a huge number of relations involving linear recurrences in the corresponding literature, in particular for k = 2. Identities with Fibonacci numbers (F_{n}) (see The On-Line Encyclopedia of Integer Sequences [10], sequence \underline{A000045}), or Lucas numbers (L_{n}) (\underline{A000032}) numbers play a distinguished role among them. The Fibonacci Quarterly is devoted mainly to such work. The sequences (F_{n}), (L_{n}) have the initial terms F_{0} = 0, L_{0} = 2, F_{1} = L_{1} = 1, and both satisfy the recursion

x_{n} = Ax_{n−1} + Bx_{n−2}  (3)

with A = B = 1. From this rich variety of identities we quote three, namely

L_{n}^{2} − 5F_{n}^{2} = (L_{n} − \sqrt{5}F_{n})(L_{n} + \sqrt{5}F_{n}) = 4(−1)^{n},  (4)
F_{n+1}^{2} − F_{n}F_{n+1} − F_{n}^{2} = (F_{n+1} − \frac{1 + \sqrt{5}}{2}F_{n}) (F_{n+1} − \frac{1 − \sqrt{5}}{2}F_{n}) = (−1)^{n}, (5)
F_{n−1}F_{n+1} − F_{n}^{2} = (−1)^{n}.  (6)

All three belong to the folklore and can be easily generalized to all second-order recurrences. Indeed, assume that (G_{n}), and (Ĝ_{n}) satisfy recursion (3). If their initial terms are G_{0}, G_{1}, Ĝ_{0} = 2G_{1} − AG_{0}, Ĝ_{1} = AG_{1} + 2BG_{0}, then we say that (Ĝ_{n}) is associated with (G_{n}). Here A, B, G_{0}, G_{1} denote complex numbers with the conditions B ≠ 0 and |G_{0}| + |G_{1}| ≠ 0. Assume that α and β are the (not necessarily different) zeros of the characteristic polynomial P (X) = X^{2} − AX − B. Put D = A^{2} + 4B, which is the discriminant of P, and introduce the notation C_{G} = G_{1}^{2} − AG_{0}G_{1} − BG_{0}^{2}. Then the identities

Ĝ_{n}^{2} − DG_{n}^{2} = (Ĝ_{n} − \sqrt{D}G_{n})(Ĝ_{n} + \sqrt{D}G_{n}) = 4C_{G}(−B)^{n},  (7)
G_{n+1}^{2} − AG_{n}G_{n+1} − BG_{n}^{2} = (G_{n+1} − αG_{n}) (G_{n+1} − βG_{n}) = C_{G}(−B)^{n},  (8)
G_{n−1}G_{n+1} − G_{n}^{2} = −C_{G}(−B)^{n−1}  (9)

hold, and it is a simple exercise to see that they are direct generalizations of (4)–(6) respectively. Note that the second one is equivalent to the third one by (G_{n+1}−AG_{n})G_{n+1}−BG_{n}^{2} = BG_{n−1}G_{n+1} − BG_{n}^{2}, and this phenomenon is obviously true for (5) and (6) too.

Assuming |B| = 1 and using (7), Pethő [11] characterized the polynomials whose values appear infinitely many times in (G_{n}). One can reverse identity (5) such that the only positive integer solutions to the equation

x^{2} − xy − y^{2} = ±1

are (F_{n}, F_{n+1}). Jones [5] gave a good overview of this equation and its relation to the solution of Hilbert’s tenth problem.

For recurrences of higher order there are only a few and complicated identities available. In particular, we do not know any generalizations of (7). Recently, Craveiro et al. [2] explored a nice generalization of the so-called Cassini identity (6) for recurrences of arbitrary order k. They investigated also analytical and combinatorial properties of their result. Corollary 3 of Theorem 1 of this paper provides a new contribution to this question. In fact, we consider the problem with arbitrary set of initial values apart from singular cases. Corollary 3 via Theorem 1 makes it possible to determine a Cassini-like identity if the basic recurrence of order k is given. However such an identity is expected to be rather compound.

The main result of this article is a common and wide extension of (7), (8), and other identities to k ≥ 2 for linear recurrences of order k satisfying the same recursive rule, including their connection with decomposable forms and diophantine equations.

2 New results

We shall prove some general results. Note that the basic field we work in is the set ℂ of complex numbers, but the machinery works even for arbitrary fields.

Theorem 1. Let (G_{n}^{(j)}), j = 1, …, k be linear recursive sequences of complex numbers of order k with the same characteristic polynomial (2) having constant term −γ_{0} ≠ 0. If the sequences are ℂ-linearly independent, then there exists a homogeneous polynomial F ∈ ℂ[X_{1}, X_{2}, …, X_{k}] of degree k such that

F (G_{n}^{(1)}, G_{n}^{(2)}, …, G_{n}^{(k)}) = ((−1)^{k+1}γ_{0})^{n}

holds for all n ∈ ℤ.

A homogeneous polynomial Q ∈ ℂ[X_{1}, X_{2}, …, X_{k}] is called decomposable if it splits completely into linear factors. Hence a decomposable form is necessarily homogeneous, but for k ≥ 3 the converse is not true in general. The next theorem is a remarkable completion of Theorem 1.

Theorem 2. Under the assumptions of Theorem 1 the homogeneous polynomial F is decomposable.

Clearly, Theorem 2 is a continuation of Theorem 1, and we could have presented them together. However their proofs differ significantly, which explains their separation.

We emphasize that the proofs are constructive, and following their arguments one can compute the polynomial F and its decomposition into linear factors. Unfortunately, F has no nice general form if k ≥ 3, so we will omit its explicit constitution. On the other hand, F is given precisely when k = 2 (see Theorem 9 and the description after). Furthermore, we will show some representative examples in Section 6.

A simple consequence of the main theorems is the following generalization of (8).

Corollary 3. Let (G_{n}) be a linear recursive sequence of complex numbers of order k satisfying (1). If the vectors ḡ_{j} = (G_{j}, G_{j+1}, …, G_{j+k−1}), j = 0, …, k − 1 are ℂ-linearly independent, then there exists a decomposable form F ∈ ℂ[X_{1}, X_{2}, …, X_{k}] of degree k such that

F (G_{n}, G_{n+1}, …, G_{n+k−1}) = ((−1)^{k+1}γ_{0})^{n}

holds for all n ∈ ℤ.

The linear recursive sequences with initial values G_{0} = ⋯ = G_{k−2} = 0, G_{k−1} = 1 satisfy always the assumption of this corollary, hence the statement too. The k-generalized Fibonacci sequences (F_{n}^{(k)}) (or, in other words, k-step Fibonacci numbers), which are defined by the initial values F_{0}^{(k)} = ⋯ = F_{k−2}^{(k)} = 0, F_{k−1}^{(k)} = 1 and by the recursion F_{n+k}^{(k)} = F_{n+k−1}^{(k)} + ⋯ + F_{n}^{(k)} are important examples. Here the upper index (k) in F_{n}^{(k)} means traditionally the parameter k, while in Theorem 1 the upper index (j) denotes the jth from the k given sequences. Clearly, the case k = 2 is the Fibonacci sequence.

In fact, the sequence (G_{n}) is a complex-valued number-theoretic function. Another direct consequence of Theorem 1 is as follows. The conditions of Theorem 1 are valid here, too.

Corollary 4. Let (G_{n}^{(j)}), j = 1, …, k be linear recursive sequences of complex numbers of order k with the same characteristic polynomial (2). Then these sequences and the sequence (γ_{0}^{n}) are algebraically dependent.

It is possible to extend (G_{n}) to a complex function G(z) such that G_{n} = G(n) for all n ∈ ℤ. Indeed, assume that P (X) in (2) has the factorization

P (X) = (X − α_{1})^{m_{1}}(X − α_{2})^{m_{2}} ⋯ (X − α_{h})^{m_{h}},

where α_{1}, …, α_{h} denote pairwise distinct complex numbers and m_{j}, j = 1, …, h are positive integers. Then, see e.g., [13], there exist polynomials g_{j} ∈ ℂ[X] of degree at most m_{j} − 1 such that

G_{n} = g_{1}(n)α_{1}^{n} + g_{2}(n)α_{2}^{n} + ⋯ + g_{h}(n)α_{h}^{n}

holds for all n ∈ ℤ. Hence G(z) = g_{1}(z)α_{1}^{z} + g_{2}(z)α_{2}^{z} + ⋯ + g_{h}(z)α_{h}^{z} is a complex function with G(n) = G_{n} for all n ∈ ℤ. For example, the extensions of the Fibonacci and the Lucas sequences are the complex functions

F (z) = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{z} − (\frac{1 − \sqrt{5}}{2})^{z}) , L(z) = (\frac{1 + \sqrt{5}}{2})^{z} + (\frac{1 − \sqrt{5}}{2})^{z} ,

respectively. One can easily verify that identities (4)–(6) remain true if we replace n, F_{n}, L_{n}, (−1)^{n} by z, F (z), L(z), (−1)^{z}, respectively. An interpretation of the generalized identities is the fact that the corresponding complex functions are algebraically dependent.

It is well known, see e.g., [7, Chapter 10.2], that a function f(z) satisfies the linear differential equation with characteristic polynomial P (X) if and only if it is identical with one of the above defined G(z). Our next theorem is a generalization of Corollary 4.

Theorem 5. Let P (X) ∈ ℂ[X] be a polynomial of degree k with simple zeros, and assume P (0) ≠ 0. Let k_{0} ≥ k and denote by G_{j}(z), 1 ≤ j ≤ k_{0} pairwise different solutions of a homogeneous linear differential equation with characteristic polynomial P (X). Then G_{j}(z), 1 ≤ j ≤ k_{0} and the function ((−1)^{k}P (0))^{z} are algebraically dependent.

As we noted, Theorem 2 and its constructive proof have a remarkable consequence in the theory of diophantine equations. This is presented as Theorem 6 in Section 3, where it is more suitable to formulate the precise statement. Indeed, if the (G_{n}^{(j)})’s are integer sequences, then it is possible to have infinitely many integer solutions to the polynomial-exponential diophantine equation

F̃(x_{1}, x_{2}, …, x_{k}) = pq^{n}  (10)

in integers x_{1}, x_{2}, …, x_{k} and n ≥ 0, where F̃ is a decomposable form of degree k depending on the parameters of the sequences, and p, q are suitable integers (see (24) below). If F̃ is irreducible over ℚ[X_{1}, …, X_{k}], then we may assume that F̃ is, up to a constant factor, a full norm form. It follows from a result of Borevich and Safarevich [1] that if the splitting field of F̃ differs from ℚ and from the imaginary quadratic number fields, then (10) has infinitely many solutions for q = 1 and for some integer p. More generally, by a celebrated theorem of Schmidt [12] on norm form equations, the set of solutions is a union of a finite set and finitely many families of solutions. For a further generalization for arbitrary decomposable form equations see Győry [4]. The families mentioned are sums of products of powers of appropriate algebraic numbers. Fixing all but one exponent and letting the remaining exponents run through non-negative integers we see that each family includes linear recursive sequences.

Our result shows that (10) may have infinitely many solutions in the case when F̃ is reducible over ℚ[X_{1}, …, X_{k}], too.

In our paper, we apply a linear algebraic approach. We were also motivated to contribute to the development of the so-called matrix method often used in the theory of linear recurrences. At the early 80’s Gould [3] presented a survey on the Q-matrices, and he refers to Simson who first gave the formula (6). This identity, together with its generalization (9) is an easy consequence of our Theorem 9 in Section 6 with the notation H_{n} = G_{n+1} (for H_{n} again see Theorem 9). Theorem 9 is a common extension of identities (7)–(9), and provides the background for the case of k ≥ 2 linear recurrences of order k in general appearing in Theorem 1.

We mention that recently Craviero et al. [2] have given a generalization of Cassini identity for the k-generalized Fibonacci numbers with specific initial vector set. The basic approach of [2] coincides with the idea of Lemma 2.1 of [9], and we exploit the advantages of this argument in the present paper.

The paper is organized as follows. In Section 3, we give two proofs for Theorem 1. In the next section, we prove Theorem 2, while Section 5 is devoted to the proof of corollaries 3 and 4 and of Theorem 5. Section 6 specializes the results of Theorem 1 and 2 to the cases k = 2 and k = 3. In Subsection 6.1, we present explicit formula in full generality if k = 2, while in Subsection 6.2, we compute the appropriate formula only for three given third order recursive sequence. Other examples for larger k values might be easily presented by following the method of the proofs.

3 The homogeneous polynomials

Before starting the first proof of Theorem 1, we introduce some notation and summarize well known facts.

Recall that k ≥ 2 is an integer, and γ_{0}, γ_{1}, …, γ_{k−1} denote arbitrary complex numbers. Consider the set of recurrent sequences

Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})} = {(x_{n})_{n∈ℤ} ∈ ℂ^{∞} | x_{n} = γ_{k−1}x_{n−1} + γ_{k−2}x_{n−2} + ⋯ + γ_{0}x_{n−k}} .  (11)

Clearly, sequences (11) satisfy a common recurrence rule, but they differ in their initial values. They constitute a ℂ-vector space with respect to coordinate-wise addition and multiplication by scalar. The dimension of the vector space is k if and only if γ_{0} ≠ 0. To be able to apply linear algebraic tools we assume γ_{0} ≠ 0 in the sequel. Throughout this paper we deal with vector spaces over the field of complex numbers ℂ, therefore we do not always mention the ground field.

3.1 First proof of Theorem 1

Proof. Assume that the recurrences

(G_{n}^{(1)}), (G_{n}^{(2)}), …, (G_{n}^{(k)}) ∈ Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})}  (12)

are ℂ-linearly independent. Then, equivalently, the vectors

ḡ_{0} = [ G_{0}^{(1)} ; ⋮ ; G_{0}^{(k)} ] , ḡ_{1} = [ G_{1}^{(1)} ; ⋮ ; G_{1}^{(k)} ] , …, ḡ_{k−1} = [ G_{k−1}^{(1)} ; ⋮ ; G_{k−1}^{(k)} ]  (13)

are also linearly independent. Define the matrices G, G^{⋆} ∈ ℂ^{k×k} as follows. The column vectors of G are ḡ_{0}, ḡ_{1}, …, ḡ_{k−1}, respectively, while ḡ_{1}, ḡ_{2}, …, ḡ_{k} admit the column vectors of G^{⋆} in this order. The k recurrences in (12), together with their initial values build up the vector recurrence

ḡ_{n} = γ_{k−1}ḡ_{n−1} + γ_{k−2}ḡ_{n−2} + ⋯ + γ_{0}ḡ_{n−k}, n ≥ k  (14)

with initial vectors (13). In particular, (14) provides the last column vector ḡ_{k} of G^{⋆}. The linear independence of the column vectors of G guarantees that

Δ = det(G) ≠ 0.  (15)

Let r̄_{i} denote the ith column vector of the transposition G^{⊤} of G for each i = 1, 2, …, k. That is r̄_{i} = [G_{0}^{(i)}, G_{1}^{(i)}, …, G_{k−1}^{(i)}]^{⊤}, the entries are exactly the initial values of the ith sequence we fixed in (12). Clearly, the vectors

r̄_{1}, r̄_{2} …, r̄_{k}  (16)

form a basis of the vector space ℂ^{k}.

Put

M = G^{⋆}G^{−1} = \frac{1}{Δ} · G^{⋆} · adj(G).

The extension of Lemma 2.1 of [9] from ℝ to ℂ shows that the vector sequence (ḡ_{n}) generated by the initial vectors (13) and by the vector recurrence (14) satisfies

ḡ_{n+1} = Mḡ_{n},  n ≥ 0.  (17)

The proof of this lemma even shows that the characteristic polynomial of matrix M is

k_{M}(x) = det(xI − M) = x^{k} − γ_{k−1}x^{k−1} − ⋯ − γ_{1}x − γ_{0},  (18)

which is also the characteristic polynomial of each recurrence of Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})} (I denotes the k × k unit matrix). Thus k_{M}(0) = det(−M) = −γ_{0}, and then det(M) = (−1)^{k}(−γ_{0}), which is denoted in the sequel by δ. Hence

det(M^{n}) = (det(M))^{n} = δ^{n}.  (19)

This observation gives later the right-hand side of the principal identity of this article (with a suitable homogeneous polynomial of degree k on the left-hand side).

Now we turn our attention to the matrices

M^{n} = [m_{i,j}^{(n)}]_{i,j=1,2,...,k} , n ∈ ℕ.

Since M^{n} = γ_{k−1}M^{n−1} + γ_{k−2}M^{n−2} + ⋯ + γ_{0}M^{n−k} holds for n ≥ k, the same recurrence rule is valid for each element-wise sequence (m_{i,j}^{(n)}) of the matrix sequence (M^{n}). That is,

m_{i,j}^{(n)} = γ_{k−1}m_{i,j}^{(n−1)} + γ_{k−2}m_{i,j}^{(n−2)} + ⋯ + γ_{0}m_{i,j}^{(n−k)}.

Such a sequence is determined by the initial values m_{i,j}^{(0)}, m_{i,j}^{(1)}, …, m_{i,j}^{(k−1)}. Collect them into the initial column vector \overline{m}_{i,j} ∈ ℂ^{k} (see (20)), which can be given as a linear combination of the basis vectors (16). More precisely, there exist uniquely determined coordinates c_{i,j}^{(u)} ∈ ℂ, u = 1, 2, …, k, such that

\overline{m}_{i,j} = [ m_{i,j}^{(0)} ; m_{i,j}^{(1)} ; ⋮ ; m_{i,j}^{(k−1)} ] = ∑_{u=1}^{k} c_{i,j}^{(u)}r̄_{u}.  (20)

This is a system of k linear equations in the k unknowns c_{i,j}^{(1)}, c_{i,j}^{(2)}, …, c_{i,j}^{(k)} (if i, j are fixed), and the system can be solved, for instance, by Cramer’s rule. Assume that G_{u} is the matrix derived by replacing the uth column vector of G^{⊤} by the vector \overline{m}_{i,j}. Then, using det(M^{⊤}) = det(M) = Δ, clearly

c_{i,j}^{(u)} = \frac{det(G_{u})}{Δ}.  (21)

Since the initial values determine a complete sequence of Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})}, the coefficients (21) appearing in (20) descend for the whole sequence (m_{i,j}^{(n)}). Thus the main consequence of the previous arguments is the equality

m_{i,j}^{(n)} = ∑_{u=1}^{k} c_{i,j}^{(u)}G_{n}^{(u)}.

In this manner, we are able to represent any entry of the matrix M^{n} as a linear combination of the nth terms of the linear recurrences (G_{n}^{(1)}), (G_{n}^{(2)}), …, (G_{n}^{(k)}) ∈ Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})}. Subsequently, the determinant of M^{n} is a homogeneous polynomial of degree k in G_{n}^{(1)}, G_{n}^{(2)}, …, G_{n}^{(k)}. We let F denote this form. Combining it with (19) we obtain

F (G_{n}^{(1)}, G_{n}^{(2)}, …, G_{n}^{(k)}) = δ^{n},  (22)

and the proof is complete.

Now assume that the coefficients γ_{i}, and the initial terms of the sequences G_{n}^{(j)} are integers. Then (G_{n}^{(j)}) is a sequence of integers (j is fixed). Multiply both sides of (22) by Δ^{k}, because (21) is now a rational number with denominator dividing Δ. Then F̃ = Δ^{k}F has integer coefficients. Consequently, the polynomial-exponential diophantine equation

F̃(x_{1}, x_{2}, …, x_{k}) = Δ^{k}δ^{n}  (23)

possesses infinitely many integer solutions in integers x_{1}, x_{2}, …, x_{k} and n. Now we record the results in

Theorem 6. Let (12) be recursive sequences of integers with initial values (13) such that (15) holds. Then for n ≥ 0

(x_{1}, x_{2}, …, x_{k}) = (G_{n}^{(1)}, G_{n}^{(2)}, …, G_{n}^{(k)})

is the solution to the diophantine equation

F̃(x_{1}, x_{2}, …, x_{k}) = Δ^{k}δ^{n},  (24)

where the coefficients of the homogeneous form F̃ depend on the parameters of the sequences.

Proof. The proof is given before the enunciation of the theorem.

Note that the proof is constructive, in the sense that following the method we can compute F̃, Δ, and δ if the initial values and the recurrence rule is fixed. This will be illustrated later, in Section 6 for binary recurrences in general, and for a triple of ternary recurrences.

3.2 Alternative proof of Theorem 1

Proof. Here we provide an alternative proof for the existence of the form F on the left-hand side of (22). The notation is taken from the preceding parts of Section 3. Observe first that

G^{∗} = GT

with the matrix

T = [ \begin{matrix}0 & 0 & ⋯ & 0 & γ_{0} \\ 1 & 0 & ⋯ & 0 & γ_{1} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 0 & γ_{k−2} \\ 0 & 0 & ⋯ & 1 & γ_{k−1} \end{matrix} ] .

Thus we have

M = G^{∗}G^{−1} = GTG^{−1}.

This matrix equality immediately implies

• det(M) = det(T) = (−1)^{k−1}γ_{0}, and

• M^{n} = GT^{n}G^{−1} for n ≥ 0.

Here GT^{n} is a matrix with the column vectors ḡ_{n}, ḡ_{n+1}, …, ḡ_{n+k−1}. On the other hand, from (17) we know ḡ_{n+j} = M^{j}ḡ_{n}. Hence all entries of GT^{n} are linear combinations of the terms G_{n}^{(1)}, G_{n}^{(2)}, …, G_{n}^{(k)}, where the coefficients are the elements of M^{j}, j = 0, …, k − 1, and they are independent from n. Subsequently, the determinant of GT^{n} is a signed sum of the products of k linear forms in G_{n}^{(1)}, G_{n}^{(2)}, …, G_{n}^{(k)} i.e., a homogeneous form of degree k. Multiplying this by det(G^{−1}), which is the determinant of a constant matrix, we obtain that det(M^{n}) is also a homogeneous form of degree k.

4 Decomposability of F

This section is devoted to the study and proof of the decomposability of the homogeneous polynomial F provided in Section 3. Recall that F (x_{1}, x_{2}, …, x_{k}) = F̃(x_{1}, x_{2}, …, x_{k})/Δ^{k} (see (22) and (23)).

Proof of Theorem 2. The proof consists of two main parts. In the first part, we show that a specific homogeneous polynomial, say F_{S}, is decomposable if the initial k sequences from Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})} are chosen advantageously. Then, in the second part, we find a connection between these favorable sequences and arbitrary packages of k sequences.

Part 1. Recall that the characteristic polynomial k_{M}(x) of the family Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})} of homogeneous linear recurrences (11) we investigate is (18). Assume that it has the decomposition

k_{M}(x) = (x − α_{1})^{m_{1}}(x − α_{2})^{m_{2}} ⋯ (x − α_{h})^{m_{h}}  (25)

into linear factors, where α_{i} ∈ ℂ (i = 1, 2, …, h) are distinct, and m_{1} + m_{2} + ⋯ + m_{h} = k. For each pair (i, j), where i ∈ {1, 2, …, h} and j ∈ {0, 1, …, m_{i} − 1}, consider the sequences

S_{n}^{(i,j)} = n^{j}α_{i}^{n}, (n ≥ 0).  (26)

Note that the range for j depends on the value of i, but we do not indicate this fact in the notation.

The sequences (26) belong to Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})}; this fact is based on the following two observations, or simply we may refer to the theory of difference equations, see e.g., the classical book of Milne-Thomson [8, Chapter XIII]. Firstly, if the multiplicity of an α_{i} is m_{i}, then α_{i} is also a zero of the derivatives k_{M}^{(j)}(x) for j = 0, 1, …, m_{i} − 1. Secondly, from the theory of Stirling number of second kind we know that n^{j} = ∑_{v=0}^{j} \left\{{j \atop v}\right\}(n)_{v}, where \left\{{j \atop v}\right\} denotes a Stirling numbers of second kind, and (n)_{v} = n(n − 1) ⋯ (n − v + 1) is a falling factorial.

Another important argument is that the sequences in (26) are ℂ-linearly independent, consequently they form a basis of Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})}. This follows again from [8, Chapter XIII]. (A similar result is given in [6].)

Analogously to G, we define the matrix G_{S} by the initial values of the sequences S_{n}^{(i,j)} such that the first row contains the initial values of S_{n}^{(1,0)}, etc. The matrix G_{S} can be split into horizontal stripes such that stripe i ∈ {1, 2, …, h} contains m_{i} rows. The enumeration of stripes begins at the top of the matrix, and the entries of stripe i are given as follows:

G_{S} = [ ⋮ ; ⋮ ; 1 α_{i}  α_{i}^{2}  α_{i}^{3}  …  …  α_{i}^{k−1} ; 0 α_{i} 2α_{i}^{2}  3α_{i}^{3} …  … (k − 1)α_{i}^{k−1} ; 0 α_{i} 2^{2}α_{i}^{2}  3^{2}α_{i}^{3} …  … (k − 1)^{2}α_{i}^{k−1} ; ⋮ ⋮  ⋮  ⋮  ...  ⋮ ; 0 α_{i} 2^{m_{i}−1}α_{i}^{2} 3^{m_{i}−1}α_{i}^{3} …  … (k − 1)^{m_{i}−1}α_{i}^{k−1} ; ⋮ ; ⋮ ] .

Let M_{i} = m_{1} + m_{2} + ⋯ + m_{i−1}. The numbering of rows of stripe i are M_{i} + (j + 1), where j = 0, …, m_{i} − 1. The matrix G_{S}^{⋆} is analogous to G^{⋆} too. We define the block diagonal matrix

B = [ \begin{matrix}B_{1} & O & ⋯ & O \\ O & B_{2} & ⋯ & O \\ ⋮ & ⋮ & ... & ⋮ \\ O & O & ⋯ & B_{h} \end{matrix} ] ∈ ℂ^{k×k} with B_{i} = [ \begin{matrix}α_{i} & 0 & ⋯ & 0 & ⋯ & 0 \\ α_{i} & α_{i} & ⋯ & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ \\ α_{i} & ⋯ & ⋯ & α_{i} & ⋯ & 0 \\ ⋮ & ⋮ & b_{u,v}^{(i)} & ⋮ & ... & ⋮ \\ α_{i} & ⋯ & ⋯ & ⋯ & ⋯ & α_{i} \end{matrix} ] ∈ ℂ^{m_{i}×m_{i}}

for i = 1, 2, …, h such that the general term b_{u,v}^{(i)} = \binom{u}{v}α_{i} is the entry of the (u + 1)th row and (v + 1)th column of B_{i}, with the conditions 0 ≤ v ≤ u ≤ m_{i} − 1. Here the minors O are suitable zero matrices. Since B_{i} is a lower diagonal matrix then B is so.

Using the notation above we will show that

G_{S}^{∗} = BG_{S}.

Note that block B_{i} has influence only on stripe i of G_{S} when carrying out the matrix multiplication BG_{S}. In stripe i we have exactly the rows M_{i}+1+u, where u = 0, 1, …, m_{i}−1. Our method is to calculate the dot product^{1} of row M_{i} + 1 + u from B and column ℓ from G_{S}, where ℓ = 1, 2, …, k. This is given in detail by

[ 0 ⋯ 0 \binom{u}{0}α_{i} \binom{u}{1}α_{i} ⋯ \binom{u}{u}α_{i} 0 ⋯ 0 ] · [ ⋮ ; α_{i}^{ℓ−1} ; (ℓ − 1)α_{i}^{ℓ−1} ; ⋮ ; (ℓ − 1)^{u}α_{i}^{ℓ−1} ; ⋮ ; (ℓ − 1)^{m_{i}−1}α_{i}^{ℓ−1} ; ⋮ ] .

Hence the dot product equals

\binom{u}{0}α_{i}^{ℓ} + \binom{u}{1}(ℓ − 1)α_{i}^{ℓ} + ⋯ + \binom{u}{u}(ℓ − 1)^{u}α_{i}^{ℓ} = ((l − 1) + 1)^{u} α_{i}^{ℓ} = ℓ^{u}α_{i}^{ℓ} = S_{ℓ}^{(i,u)}.

Recall that S_{ℓ}^{(i,u)} is the general term of the matrix G_{S}^{∗} such that it is the element of the (u + 1)th row of stripe i in the column ℓ (ℓ = 1, 2, …, k).

Subsequently, we have

M_{S} = G_{S}^{∗}G_{S}^{−1} = (BG_{S}) G_{S}^{−1} = B,

and then M_{S}^{n} = B^{n} follows. We know that B is a lower diagonal matrix. Thus det(B) is the product of the elements lying in the main diagonal, i.e.,

det(B) = α_{1}^{m_{1}}α_{2}^{m_{2}} ⋯ α_{h}^{m_{h}}.

Finally,

det (M_{S}^{n}) = (det(B))^{n} = α_{1}^{m_{1}n}α_{2}^{m_{2}n} ⋯ α_{h}^{m_{h}n} = (S_{n}^{(1,0)})^{m_{1}} (S_{n}^{(2,0)})^{m_{2}} ⋯ (S_{n}^{(h,0)})^{m_{h}} .

1The dot product of the vectors μ̄ = [μ_{1}, …, μ_{k}] and ν̄^{⊤} = [ν_{1}, …, ν_{k}]^{⊤} is the complex number ∑_{j=1}^{k} μ_{j}ν_{j}.

So we have found that det (M_{S}^{n}) is a corresponding value of the decomposable form

F_{S}(y_{1}, y_{2}, …, y_{h}) = y_{1}^{m_{1}}y_{2}^{m_{2}} ⋯ y_{h}^{m_{h}}

at the point ((S_{n}^{(1,0)}), (S_{n}^{(2,0)}), ⋯, (S_{n}^{(h,0)})). Thus the assertion of the theorem holds for this particular choice of the recurrences.

Part 2. Recall that sequences (12) form a basis in Γ_{k}^{(γ_{0},γ_{1},...,γ_{k−1})} because Δ ≠ 0. Hence there exists a unique matrix A = [a_{i,j}] ∈ ℂ^{h×k} such that

[ S_{n}^{(1,0)} S_{n}^{(2,0)} ⋯ S_{n}^{(h,0)} ]^{⊤} = A [ G_{n}^{(1)} G_{n}^{(2)} ⋯ G_{n}^{(k)} ]^{⊤} .  (27)

Now consider the substitution ȳ = [y_{1}, y_{2}, …, y_{h}]^{⊤} = A[x_{1}, x_{2}, …, x_{k}]^{T} = Ax̄. Denoting by ā_{i} the ith row vector of A we compute the dot product

y_{i} = ā_{i}[x_{1}, x_{2}, …, x_{k}]^{⊤}

for every i = 1, 2, …, h. Now we can define F (x_{1}, …, x_{k}) = F (x̄) as follows:

F_{S}(ȳ) = y_{1}^{m_{1}}y_{2}^{m_{2}} ⋯ y_{h}^{m_{h}} = ∏_{i=1}^{h} (ā_{i}[x_{1}, x_{2} …, x_{k}]^{⊤})^{m_{i}} = F (x̄).

With the result from Part 1 we know that F is a decomposable form of degree k with the property

F (G_{n}^{(1)}, …, G_{n}^{(k)}) = ((−1)^{k}k_{M}(0))^{n} = δ^{n}, (n = 0, 1, …).

Thus the proof is complete.

Remark 7. If every zero of the characteristic polynomial k_{M}(x) is simple (i.e., h = k), then the matrix G_{S} simplifies to

G_{S} = [ \begin{matrix}1 & α_{1} & ⋯ & α_{1}^{k−1} \\ 1 & α_{2} & ⋯ & α_{2}^{k−1} \\ ⋮ & ⋮ & ... & ⋮ \\ 1 & α_{k} & ⋯ & α_{k}^{k−1} \end{matrix} ] = AG

(the second equality is implied by (27)). Consequently, A = G_{S}G^{−1}, and then

ȳ = G_{S}G^{−1}x̄.

Finally, we obtain F_{S}(ȳ) = F_{S}(G_{S}G^{−1}x̄) = F (x̄).

We conclude this section by giving a general example to demonstrate the power of our results.

Example 8. Consider the sequences of (12) such that the characteristic polynomial has factorization (25). Assume that we have the specific initial vectors

ḡ_{0} = [ 1 0 ⋮ 0 ] , ḡ_{1} = [ 0 1 ⋮ 0 ] , …, ḡ_{k−1} = [ 0 0 ⋮ 1 ] .  (28)

Using the advantageous properties of this orthonormal basis, we can easily show that

S_{n}^{(j,0)} = 1 · G_{n}^{(1)} + α_{j} · G_{n}^{(2)} + ⋯ + α_{j}^{k−1} · G_{n}^{(k)}, (j = 1, 2, …, h).

Consequently,

y_{j} = x_{1} + α_{j}x_{2} + ⋯ + α_{j}^{k−1}x_{k}, (j = 1, 2, …, h),

and then

F (x_{1}, x_{2}, …, x_{k}) = ∏_{i=1}^{h}(x_{1} + α_{j}x_{2} + ⋯ + α_{j}^{k−1}x_{k})^{m_{j}}

follows. Hence the complete factorization of the form F is determined. Note that the simplicity depends on the features of the orthonormal basis (28).

5 Proof of the corollaries and Theorem 5

Proof of Corollary 3. The entries of the vectors ḡ_{j}, j = 0, …, k − 1 are the initial values of the sequences (G_{n+j}), j = 0, …, k − 1. At the beginning of the proof of Theorem 1 we pointed out that the linear independence of the vectors ḡ_{j} and the linear independence of the sequences (G_{n+j}) is equivalent. Thus the sequences (G_{n+j}), j = 0, …, k − 1 are linearly independent and Theorem 1 implies the existence of a homogeneous form F, while Theorem 2 justifies the decomposability of F.

Proof of Corollary 4. If the sequences (G_{n}^{(j)}), j = 1, …, k are linearly dependent, then upon enlarging this set with the sequence (γ_{0}^{n}), the linear dependent property remains true, and this is a very special algebraic dependence. Otherwise, if (G_{n}^{(j)}), j = 1, …, k are linearly independent, then Theorem 1 (more precisely equation (22)) verifies the algebraic dependence.

Proof of Theorem 5. Assume that P (X) = z_{k}X^{k} + z_{k−1}X^{k−1} + ⋯ + z_{0}, where z_{0} ≠ 0. The differential equation with characteristic polynomial P (X) has the form

z_{k}f(z)^{(k)} + z_{k−1}f(z)^{(k−1)} + ⋯ + z_{0} = 0.  (29)

Here f^{(ℓ)} denotes the ℓth derivative of f. The pair-wisely distinct zeros of P (X) are denoted by α_{1}, α_{2}, …, α_{k}. The function f(z) is a solution of (29) if and only if it has the form

f(z) = f_{1}α_{1}^{z} + f_{2}α_{2}^{z} + ⋯ + f_{k}α_{k}^{z},

with complex numbers f_{1}, f_{2}, …, f_{k}.

The set of solutions of (29) form a ℂ-vector space with respect to the addition of functions and multiplication with complex numbers. We let S(P) denote this set. The functions α_{1}^{z}, α_{2}^{z}, …, α_{k}^{z} are linearly independent, thus the dimension of S(P) is k.

Assume that G_{j}(z), j ≤ k_{0} are pairwise different solutions of (29). If they are ℂ-linearly dependent, which always holds when k_{0} > k, then the same is true if we enlarge their set with the function ((−1)^{k}P (0))^{z}. It remains to examine the case when k_{0} = k and the functions G_{j}(z), j ≤ k_{0} are linearly independent. Then they form a basis of S(P). The functions α_{1}^{z}, α_{2}^{z}, …, α_{k}^{z} belong to S(P), thus there exist complex numbers a_{ij}, 1 ≤ i, j ≤ k such that

α_{i}^{z} = ∑_{j=1}^{k} a_{ij}G_{j}(z).  (30)

On the other hand, we have

α_{1}^{z}α_{2}^{z} ⋯ α_{k}^{z} = (α_{1}α_{2} ⋯ α_{k})^{z} = ((−1)^{k}P (0))^{z}.

Inserting the linear relations of Eq. (30) here we obtain the statement.

6 Binary and ternary recurrences

6.1 Binary recurrences, a general identity

In this subsection, we present the general identity (33) below with two binary recurrences satisfying the same recurrence relation. This is a special case of (22). On the other hand it provides a common generalization of (7)–(9). At the end of this subsection a few examples will illustrate (33). In the computations, we will follow the arguments of the previous sections.

Assume k = 2. For simplicity suppose that the two recurrent sequences are (G_{n}) and (H_{n}), their initial values are G_{0}, G_{1} and H_{0}, H_{1} respectively. Furthermore set γ_{1} = A and γ_{0} = B. Then the two sequences above belong to

Γ_{2}^{(B,A)} = {(x_{n})_{n∈ℤ} ∈ ℂ^{∞} | x_{n} = Ax_{n−1} + Bx_{n−2}, n ≥ 2} .

Now

G = [ \begin{matrix}G_{0} & G_{1} \\ H_{0} & H_{1} \end{matrix} ] , G^{⋆} = [ \begin{matrix}G_{1} & AG_{1} + BG_{0} \\ H_{1} & AH_{1} + BH_{0} \end{matrix} ] ,

and assume that Δ = det(G) = G_{0}H_{1} − G_{1}H_{0} ≠ 0. Then

G^{−1} = \frac{1}{Δ} [ \begin{matrix}H_{1} & −G_{1} \\ −H_{0} & G_{0} \end{matrix} ] .

We introduce the notation C_{G} = G_{1}^{2} − AG_{0}G_{1} − BG_{0}^{2} (also see before the equations (7)–(9)), and analogously C_{H} = H_{1}^{2} − AH_{0}H_{1} − BH_{0}^{2}. We further define E_{10} = G_{1}H_{1} − AG_{1}H_{0} − BG_{0}H_{0}, and E_{01} = G_{1}H_{1} − AG_{0}H_{1} − BG_{0}H_{0}. One can easily see that

M = G^{⋆}G^{−1} = \frac{1}{Δ} [ \begin{matrix}E_{10} & −C_{G} \\ C_{H} & −E_{01} \end{matrix} ] .  (31)

Clearly, k_{M}(x) = x^{2} − Ax − B = (x − α)(x − β) and det(M) = −B. Obviously, det(M^{n}) = (−B)^{n}, A = α + β and B = −αβ. (Note that α and β are not necessarily distinct.)

The element sequences of the powers of matrix M satisfy

m_{i,j}^{(n)} = Am_{i,j}^{(n−1)} + Bm_{i,j}^{(n−2)}, (n ≥ 2; 1 ≤ i, j ≤ 2).

The initial values are clear from M^{0} = I and from M (here I is the 2 × 2 unit matrix). Now

[ \begin{matrix}m_{i,j}^{(0)} \\ m_{i,j}^{(1)} \end{matrix} ] = c_{i,j}^{(1)} [ \begin{matrix}G_{0} \\ G_{1} \end{matrix} ] + c_{i,j}^{(2)} [ \begin{matrix}H_{0} \\ H_{1} \end{matrix} ] ,  (1 ≤ i, j ≤ 2).  (32)

Once we have the solutions to (32) in c_{i,j}^{(1)} and c_{i,j}^{(2)}, then m_{i,j}^{(n)} = c_{i,j}^{(1)}G_{n} + c_{i,j}^{(2)}H_{n} holds. A straightforward calculation shows that

M^{n} = \frac{1}{Δ} [ \begin{matrix}(−H_{0}m_{1,1}^{(1)} + H_{1})G_{n} + (G_{0}m_{1,1}^{(1)} − G_{1})H_{n} & −H_{0}m_{1,2}^{(1)}G_{n} + G_{0}m_{1,2}^{(1)}H_{n} \\ −H_{0}m_{2,1}^{(1)}G_{n} + G_{0}m_{2,1}^{(1)}H_{n} & (−H_{0}m_{2,2}^{(1)} + H_{1})G_{n} + (G_{0}m_{2,2}^{(1)} − G_{1})H_{n} \end{matrix} ] ,

where we used the values m_{1,1}^{(0)} = m_{2,2}^{(0)} = 1, m_{1,2}^{(0)} = m_{2,1}^{(0)} = 0. In fact, to determine det(M^{n}) we do not need the exact values m_{i,j}^{(1)} given in (31), only the identities

m_{1,1}^{(1)}m_{2,2}^{(1)} − m_{1,2}^{(1)}m_{2,1}^{(1)} = det(M) = −B

and

m_{1,1}^{(1)} + m_{2,2}^{(1)} = tr(M) = A.

Indeed, if we figure out simply the determinant of the matrix M^{n}, and collect the coefficient of the terms G_{n}^{2}, G_{n}H_{n}, and H_{n}^{2} respectively, then the key moment of the simplification is the application of these identities. Finally, the computations lead to

(−B)^{n} = det (M^{n}) = \frac{C_{H}}{Δ^{2}} G_{n}^{2} + \frac{C_{GH}}{Δ^{2}} G_{n}H_{n} + \frac{C_{G}}{Δ^{2}} H_{n}^{2},

where C_{GH} = −(E_{10} + E_{01}). Moreover, one can show that C_{GH} can be given by using the corresponding associated sequences as follows: C_{GH} = G_{0}Ĥ_{1} − G_{1}Ĥ_{0} = H_{0}Ĝ_{1} − H_{1}Ĝ_{0}. Then we have the desired equality given in

Theorem 9. The terms of the recurrences above satisfy

C_{H}G_{n}^{2} + C_{GH}G_{n}H_{n} + C_{G}H_{n}^{2} = (−B)^{n}Δ^{2}.  (33)

This is a nice common generalization of (7)–(9). Indeed, observe that Theorem 9 leads to (7) whenever (H) is the associated sequence of (G). Really, it is easy to show that CĜ = −DC_{G}, C_{GĜ} = 0 (i.e., C_{GH} vanishes if (H) = (Ĝ)), and in this particular case Δ = −2C_{G} holds. Insert these values into (33) to immediately obtain (7). For (9), let H_{n} = G_{n+1}; the details here are omitted.

The binary quadratic form on the left-hand side of (33) is trivially decomposable. The decomposition is formulated by

((H_{1} − αH_{0})G_{n} − (G_{1} − αG_{0})H_{n})) · ((H_{1} − βH_{0})G_{n} − (G_{1} − βG_{0})H_{n}) = (−B)^{n}Δ^{2}.

Now we illustrate Theorem 9 by five examples given in Table 1. One or two coefficients from

\begin{matrix}(A, B) & G & M & (−B)^{n}Δ^{2} = C_{H}G_{n}^{2} + C_{GH}G_{n}H_{n} + C_{G}H_{n}^{2} \\ (0, 4) & [ \begin{matrix}1 & 2 \\ 2 & 3 \end{matrix} ] & [ \begin{matrix}2 & 0 \\ 7 & −2 \end{matrix} ] & (−4)^{n}(−1)^{2} = −7G_{n}^{2} + 4G_{n}H_{n} = G_{n}(4H_{n} − 7G_{n}) \\ (2, −1) & [ \begin{matrix}2 & 3 \\ 4 & 5 \end{matrix} ] & [ \begin{matrix}1/2 & 1/2 \\ −1/2 & 3/2 \end{matrix} ] & 1^{n}(−2)^{2} = G_{n}^{2} − 2G_{n}H_{n} + H_{n}^{2} = (G_{n} − H_{n})^{2} \\ (7, −10) & [ \begin{matrix}0 & 1 \\ 2 & 7 \end{matrix} ] & [ \begin{matrix}7/2 & 1/2 \\ 9/2 & 7/2 \end{matrix} ] & 10^{n}(−2)^{2} = −9G_{n}^{2} + H_{n}^{2} \\ (7, −10) & [ \begin{matrix}1 & 2 \\ 1 & 5 \end{matrix} ] & [ \begin{matrix}2 & 0 \\ 0 & 5 \end{matrix} ] & 10^{n}3^{2} = 9G_{n}H_{n} \\ (4, −1) & [ \begin{matrix}1 & 2 \\ 3 & 4 \end{matrix} ] & [ \begin{matrix}13/2 & −3/2 \\ 23/2 & −5/2 \end{matrix} ] & 1^{n}(−2)^{2} = −23G_{n}^{2} + 18G_{n}H_{n} − 3H_{n}^{2} \end{matrix}

Table 1: Binary recurrence examples.

{C_{G}, C_{H}, C_{GH}} may vanish in (33), which provides a large variety of identities.

6.2 Ternary recurrences

Instead of pointing out the complicated general formula it is better to present an example which is typical of the ternary forms we are studying. Examples for higher-order linear recurrences can be produced analogously.

There are only a few papers in the literature which work with three different ternary recurrences satisfying the same recurrence rule. An example is [14], which studies the Narayana sequence (A_{n}) (\underline{A000930}), Narayana-Lucas sequence (B_{n}), (\underline{A001609}), and Narayana-Perrin sequence (C_{n}). These recurrences satisfy

x_{n} = x_{n−1} + x_{n−3}

with initial values given by

A_{0} = 0, A_{1} = 1, A_{2} = 1; B_{0} = 3, B_{1} = 1, B_{2} = 1; C_{0} = 3, C_{1} = 0, C_{2} = 2,

respectively. Let α_{i} (i = 1, 2, 3) denote the simple zeros of the characteristic polynomial k(x) = x^{3} − x^{2} − 1 such that α_{1} ∈ ℝ and α_{3} is the complex conjugate of α_{2}. Following the the method we described in detail leads to the diophantine equation

−187x^{3}+159x^{2}y−45x^{2}z−189xy^{2}+306xyz−117xz^{2}+y^{3}−45y^{2}z+63yz^{2}−27z^{3} = −216, (34)

which possesses infinitely many integer solutions x = A_{n}, y = B_{n}, z = C_{n}. In this case, Δ = −6, and the base of the exponential term is 1. Note that all the 10 coefficients in the corresponding F̃ are non-zero. The ternary form of (34) can be decomposed in the algebraic number field ℚ[α_{1}, α_{2}] as

− ∏_{i=1}^{3} ((3α_{i}^{2} + 3α_{i} − 2)x + (−3α_{i}^{2} + 3α_{i} + 2)y + (3α_{i}^{2} − 3α_{i})z) .

7 Acknowledgments

We thank Robert Tichy for his help in the formulation of Theorem 5, and Andrew Scoones for his comments. K. Győry and L. Szalay were supported by the Hungarian National Foundation for Scientific Research Grant No. 128088, and No. 130909. For L. Szalay, this research was supported by the Slovak Scientific Grant Agency VEGA 1/0776/21.

References

[1] Z. I. Borevic̆ and I. R. S̆afarevic̆, Number Theory (Russian), Izdat. Nauka, Moscow, 1964. English translation in A. I. Borevich and I. R. Shafarevich, Number Theory, Pure and Applied Mathematics, Vol. 20, Academic Press, 1966.

[2] I. M. Craveiro, E. V. Pereira Spreafico, and M. Rachidi, Generalized Cassini identities via the generalized Fibonacci fundamental system. Applications, Indian J. Pure Appl. Math. (2023).

[3] H. W. Gould, A history of the Fibonacci Q-matrix and a higher-dimensional problem, Fibonacci Quart. 19 (1981), 250–257.

[4] K. Győry, On the numbers of families os solutions of systems of decomposable form equations, Publ. Math. Debrecen 42 (1993), 65–101.

[5] J. P. Jones, Diophantine representation of the Fibonacci numbers, Fibonacci Quart. 13 (1975), 84–88.

[6] D. Kalman, The generalized Vandermonde matrix, Math. Mag. 57 (1984), 15–21.

[7] K. Königsberger, Analysis 1, 6th edition, Springer, 2003.

[8] L. M. Milne-Thomson, The Calculus of Finite Differences, Macmillan, 1933.

[9] L. Németh and L. Szalay, Power sums in hyperbolic Pascal triangles, An. Ştiinţ. Univ. “Ovidius” Constanţa Ser. Mat. 26 (2018), 189–203.

[10] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org, 2023.

[11] A. Pethő, On the solution of the equation G_{n} = P (x), in Fibonacci Numbers and Their Applications, D. Reidel Publ. Comp., 1986, pp. 193–201.

[12] W. M. Schmidt, Norm form equations, Ann. Math. 96 (1972), 526–551.

[13] T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations, Vol. 87, Cambridge Tracts in Mathematics, Cambridge Univ. Press, 1986.

[14] Y. Soykan, On generalized Narayana numbers, Int. J. Adv. Appl. Math. Mech. 7 (2020), 43–56.

2020 Mathematics Subject Classification: Primary 11B37; Secondary 11D61, 11D72. Keywords: linear recurrence, decomposable form, general identity, diophantine equation, matrix method.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000930}, and \underline{A001609}.)

Received November 10 2023; revised versions received February 14 2024; February 22 2024. Published in Journal of Integer Sequences, March 1 2024.

Return to Journal of Integer Sequences home page.