Parapermanents of Triangular Matrices and Some General Theorems on Number Sequences

Roman Zatorsky and Taras Goy Vasyl Stefanyk Precarpathian National University Department of Mathematics and Informatics Shevchenko str., 57 Ivano-Frankivsk Ukraine

                    romazatorsky@gmail.com
                      tarasgoy@yahoo.com

Abstract Applying the apparatus of triangular matrices, this paper determines general relations between the terms of the sequences generated by linear homogeneous recurrence equations. We single out, in particular, the class of normal linear recurrence equations, for which the corresponding number sequences have some interesting number-theoretic properties.

1 Introduction

At present, quite a few general theorems have been proved for linear recurrence relations. In fact, their content is similar to corresponding theorems from the theory of linear homogeneous and nonhomogeneous systems of equations with constant coefficients and the theory of homogenous and nonhomogeneous ordinary differential equations with constant coefficients. But so far there are no general methods of solution even for linear homogenous recurrence equations with variable coefficients.

Linear recurrence sequences with constant coefficients are efficiently used in different fields of mathematics (see, for example, [7, 25, 28, 30]). It is necessary, however, to find the exact roots of a corresponding characteristic equation, which can cause considerable difficulties.

The theoretical research tool for studying linear recurrent equations in this paper is parapermanents of triangular matrices [34, 35]. The paper aims at applying parapermanents of triangular matrices to solution of linear recurrence equations, determination of general relations between the terms of the sequences generated by these equations, and isolation of the class of normal linear recurrence equations, the number sequences of which have some general number-theoretic properties. The method makes it possible to investigate linear recurrence equations without solving corresponding characteristic equations. Here, the bijection is established between the number sequence defined by linear recurrence relation, its generating function and its n-th term given as a parapermanent of some n-th order triangular matrix.

2 Preliminaries and notations

A triangular table of numbers

A = (\begin{matrix}a_{11} \\ a_{21} & a_{22} \\ ⋯ & ⋯ & ... \\ a_{n1} & a_{n2} & ⋯ & a_{nn} \end{matrix})_{n}  (1)

is called a triangular matrix, and the number n is called its order [34, 35]. Note that a triangular matrix (1) is not a triangular matrix in the usual sense of this term as it is not a square matrix.

To every element a_{ij} of the triangular matrix (1), we correspond (i − j + 1) elements a_{ik}, k = j, j + 1, …, i, which are called derived elements, generated by element a_{ij}.

The product of all derived elements of the matrix (1) generated by element a_{ij} is denote by {a_{ij}} and called the factorial product of the element a_{ij}, i.e., {a_{ij}} = a_{ij} a_{i,j+1} ⋯ a_{ii}.

To each element a_{ij} of a matrix (1) we associate the triangular table of elements of matrix A that has a_{ij} in the bottom left corner. We call this table a corner of the matrix and denote it by R_{ij}(A). Corner R_{ij}(A) is a triangular matrix of order (i − j + 1), and it contains only elements a_{rs} of matrix (1) whose indices satisfy the inequalities j ⩽ s ⩽ r ⩽ i.

The parapermanent pper(A) of a triangular matrix (1) is the number

pper(A) = [\begin{matrix}a_{11} \\ a_{21} & a_{22} \\ ⋯ & ⋯ & ... \\ a_{n1} & a_{n2} & ⋯ & a_{nn} \end{matrix}]_{n} = ∑_{r=1}^{n} ∑_{p_{1}+···+p_{r}=n} a_{p_{1},1} ∏_{s=2}^{r}\{a_{p_{1}+···+p_{s}, p_{1}+···+p_{s−1}+1}\}, (2)

where p_{1}, p_{2}, …, p_{r} are positive integers, {a_{ij}} is the factorial product of the element a_{ij} of the matrix A. We shall also denote a parapermanent of the matrix (1) briefly by [a_{ij}]_{1≤j≤i≤n}.

The rectangular table T (i) of elements of the triangular matrix (1) is inscribed in matrix (1) if one of its vertex coincides with the element a_{n1}, and its opposite one coincides with the element a_{ii}, i = 1, 2, …, n. [37]

The parapermanent algebraic complement P_{ij} to the factorial product {a_{ij}} of the element a_{ij} of the matrix (1) is the number [34]

P_{ij} = pper(R_{j−1,1}) · pper(R_{n,i+1}),  (3)

where R_{j−1,1} and R_{n,i+1} are corners of the matrix (1), and pper(R_{01}) ≡ 1, pper(R_{n,n+1}) ≡ 1.

Theorem 1. [34] (Decomposition of a parapermanent by elements of an inscribed rectangular table). Let A be a triangular matrix (1), and T (i) be some inscribed rectangular table. Then

pper(A) = ∑_{s=1}^{i} ∑_{r=i}^{n} {a_{rs}} P_{rs},  (4)

where P_{rs} is a parapermanent algebraic complement to the factorial product of element a_{rs}, which belongs to T (i).

Corollary 2. For i = n we get decomposition of the parapermanent pper(A) by elements of the last row:

pper(A) = ∑_{s=1}^{n} {a_{ns}} · pper(R_{s−1,1}).  (5)

Lemma 3. [35] The system of equations

x_{i} = a_{ii}b_{1}x_{i−1} + a_{ii}a_{i,i−1}b_{2}x_{i−2} + ⋯ + a_{ii} ⋯ a_{i1}b_{i}, i = 1, 2, …, n,

has the solution x_{i} = [a_{sr} \frac{b_{s−r+1}}{b_{s−r}} ]_{1⩽r⩽s⩽i}, where b_{0} ≡ 1.

Lemma 4. [35] The system of equations

[(1 + δ_{sr}(x_{s} − 1))\frac{a_{s−r+1}}{a_{s−r}} ]_{1⩽r⩽s⩽i} = b_{i}, i = 1, 2, …, n,

where δ_{sr} is the Kronecker symbol, a_{0} = 1, has the solution

x_{i} = \frac{b_{i}}{a_{i}b_{0} + a_{i−1}b_{1} + a_{i−2}b_{2} + ⋯ + a_{1}b_{i−1}} (b_{0} ≡ 1).

3 Parapermanents and k-th order linear recurrence equa-

tions

Let us consider the linear recurrence equation of k-th order

u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2} + ⋯ + a_{k}u_{n−k},  (6)

with initial conditions

u_{0} = 1, u_{1} = b_{1}, u_{2} = b_{2}, …, u_{k−1} = b_{k−1}.  (7)

If it is difficult to solve a characteristic equation of the recurrence equation (6) then the following proposition can be useful, as it significantly complements Stanley’s theorem ([29, p. 202]): Theorem 5. [36]. For the sequence (u_{n})_{n≥0} the following three equations are equivalent:

(1) the linear recurrence equation (6) with initial conditions (7);

(2)

u_{n} = [ \begin{matrix}a_{1}c_{1} \\ \frac{a_{2}}{a_{1}} & a_{1}c_{2} \\ ⋯ & ⋯ & ... \\ \frac{a_{k−1}}{a_{k−2}} & \frac{a_{k−2}}{a_{k−3}} & ⋯ & a_{1}c_{k−1} \\ \frac{a_{k}}{a_{k−1}} & \frac{a_{k−1}}{a_{k−2}} & ⋯ & \frac{a_{2}}{a_{1}} & a_{1} \\ 0 & \frac{a_{k}}{a_{k−1}} & ⋯ & \frac{a_{3}}{a_{2}} & \frac{a_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ... \\ 0 & 0 & ⋯ & 0 & \frac{a_{k}}{a_{k−1}} & ⋯ & \frac{a_{2}}{a_{1}} & a_{1} \end{matrix} ]_{n}  (8)

with u_{0} = 1, a_{i} ≠ 0 for i = 1, 2, …, k − 1, where

c_{i} = \frac{b_{i}}{a_{i}b_{0} + a_{i−1}b_{1} + ⋯ + a_{1}b_{i−1}} , i = 1, 2, …, k − 1,  (9)

with b_{0} = 1; (3)

1 + ∑_{i=1}^{∞} u_{i}z^{i} = \frac{1 + b_{1} (1 − \frac{1}{c_{1}} ) z + b_{2} (1 − \frac{1}{c_{2}} ) z^{2} + ⋯ + b_{k−1} (1 − \frac{1}{c_{k−1}} ) z^{k−1}}{1 − a_{1}z − a_{2}z^{2} − ⋯ − a_{k}z^{k}} ,  (10)

where c_{i} ≠ 0 for i = 1, 2, …, k − 1.

The theorem is established in [36]; we just give the proof for convenience of the reader.

Proof. Equivalence of the recurrence equation (6), (7) and the equation (8) follows from the fact that numbers c_{1}, c_{2}, …, c_{k−1}, according to Lemma 4, are solutions of the system of equations

[(1 + δ_{sr}(c_{s} − 1))\frac{a_{s−r+1}}{a_{s−r}} ]_{1⩽r⩽s⩽i} = b_{i}, i = 1, 2, …, k − 1,

and the decomposition of the parapermanent in (8) for n ≥ k by elements of the last row (see Corollary 5).

Let us now prove the equivalence of the recurrence equation (6) with initial conditions (7) and the equation (10). To do this, we use the equality

(1 − ∑_{i=1}^{k} a_{i}x^{i}) (1 + ∑_{j=1}^{∞} u_{j}x^{j}) =

= 1 + (u_{1} − a_{1})x + (u_{2} − a_{1}u_{1} − a_{2})x^{2} + (u_{3} − a_{1}u_{2} − a_{2}u_{1} − a_{3})x^{3} + ⋯ ⋯ + (u_{k−1} − a_{1}u_{k−2} − a_{2}u_{k−3} − ⋯ − a_{k−2}u_{1} − a_{k−1})x^{k−1} +

+ ∑_{i=k}^{∞}(u_{i} − a_{1}u_{i−1} − a_{2}u_{i−2} − ⋯ − a_{k}u_{i−k}).

In the right hand of above equality, we shall replace u_{i} with b_{1}, b_{2}, …, b_{k−1}, and factor out b_{1} from the first parentheses, b_{2} from the second parentheses, and so on. If we denote

c_{1} = \frac{b_{1}}{a_{1}} , c_{2} = \frac{b_{2}}{a_{2} + a_{1}b_{1}} , c_{3} = \frac{b_{3}}{a_{3} + a_{2}b_{1} + a_{1}b_{2}} , …,

then

(1 − ∑_{i=1}^{k} a_{i}x^{i}) (1 + ∑_{j=1}^{∞} u_{j}x^{j})
= 1 + b_{1} (1 − \frac{1}{c_{1}} ) x + b_{2} (1 − \frac{1}{c_{2}} ) x^{2} + ⋯ + b_{k−1} (1 − \frac{1}{c_{k−1}} ) x^{k−1} +

+ ∑_{i=k}^{∞} (u_{i} − a_{1}u_{i−1} − a_{2}u_{i−2} − ⋯ − a_{k}u_{i−k}) .

Note that Theorem 5 is also true for the recurrence equations of the form (6) with variable coefficients.

The right hand of the equality (10) is called the generating function of the sequence (6).

Example 6. For the Tribonacci sequence u_{n} = u_{n−1} + u_{n−2} + u_{n−3}, u_{0} = u_{1} = u_{2} = 1 (\underline{A000213}) from (9) we shall find the numbers c_{1} = \frac{b_{1}}{a_{1}} = 1, c_{2} = \frac{b_{2}}{a_{2}+a_{1}b_{1}} = \frac{1}{2}, from (8) — the n-th term of the sequence written with help of the parapermanent of the triangular matrix

u_{n} = [\begin{matrix}1 \\ 1 & \frac{1}{2} \\ 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ ⋯ & ⋯ & ⋯ & ⋯ & ... \\ 0 & ⋯ & 0 & 1 & 1 & 1 \end{matrix}]_{n} ,  (11)

and from (10) — the generating function F (x) = \frac{1−x^{2}}{1−x−x^{2}−x^{3}} .

Let us consider the case when in (9) c_{1} = c_{2} = ⋯ = c_{k−1}. Then from (9) we get the system

b_{i} = a_{1}b_{i−1} + a_{2}b_{i−2} + ⋯ + a_{i−1}b_{1} + a_{i}, i = 1, 2, …, k − 1,

which, according to Lemma 3, has the solution

b_{i} = [ \begin{matrix}a_{1} \\ \frac{a_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ... \\ \frac{a_{i}}{a_{i−1}} & \frac{a_{i−1}}{a_{i−2}} & ⋯ & a_{1} \end{matrix} ]_{i} , i = 1, 2, …, k,  (12)

and the initial conditions (7) for the recurrence equation (6) becomes

u_{0} = 1, u_{i} = [ \begin{matrix}a_{1} \\ \frac{a_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ... \\ \frac{a_{i}}{a_{i−1}} & \frac{a_{i−1}}{a_{i−2}} & ⋯ & a_{1} \end{matrix} ]_{i} , i = 1, 2, …, k − 1.  (13)

The initial conditions (13) for the recurrence equation (6) are called normal initial conditions, and the sequence generated by normal initial conditions is called a normal sequence.

Corollary 7. For the sequence (u_{n})_{n≥0} the following three equations are equivalent:

(1) the linear recurrence equation (6) with the conditions (7), where numbers b_{i} are defined by (12);

(2)

u_{n} = [ \begin{matrix}a_{1} \\ \frac{a_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ... \\ \frac{a_{k}}{a_{k−1}} & \frac{a_{k−1}}{a_{k−2}} & ⋯ & a_{1} \\ 0 & \frac{a_{k}}{a_{k−1}} & ⋯ & \frac{a_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ & ... \\ 0 & … & 0 & \frac{a_{k}}{a_{k−1}} & … & \frac{a_{2}}{a_{1}} & a_{1} \end{matrix} ]_{n}  (14)

with u_{0} = 1, a_{i} ≠ 0 for i = 1, 2, …, k − 1;

(3)

1 + ∑_{i=1}^{∞} u_{i}x^{i} = \frac{1}{1 − a_{1}x − a_{2}x^{2} − ⋯ − a_{k}x^{k}} .  (15)

Proof. If the initial conditions of the recurrence equation (6) are normal, then it is obvious that all the numbers c_{1}, c_{2}, …, c_{n} in the Theorem 5 are equal to one. So, the normal initial conditions (13) together with the equation (8) for c_{i} = 1, i = 1, 2, …, k − 1, gives (14).

Example 8. For the Jacobsthal sequence (\underline{A001045}) u_{n} = u_{n−1} + 2u_{n−2}, u_{0} = u_{1} = 1, from (9) we shall find c_{1} = \frac{b_{1}}{a_{1}} = 1, from (14) — the recurrence equation

u_{n} = [\begin{matrix}1 \\ 2 & 1 \\ 0 & 2 & 1 \\ 0 & 0 & 2 & 1 \\ ⋯ & ⋯ & ⋯ & ⋯ & ... \\ 0 & ⋯ & 0 & 0 & 2 & 1 \end{matrix}]_{n} ,

and from (15) — the generating function F (x) = \frac{1}{1−x−2x^{2}} .

Example 9. For Narayana’s cows sequence (\underline{A000930}) u_{n} = u_{n−1} + u_{n−3}, u_{0} = u_{1} = u_{2} = 1, from (9) we shall find c_{1} = \frac{b_{1}}{a_{1}} = 1, c_{2} = \frac{b_{2}}{a_{2}+a_{1}b_{1}} = 1, and from (15) — the generating function F (x) = \frac{1}{1−x−x^{3}} .

Example 10. For Chebyshev polynomials of the second kind u_{n}(x) = 2xu_{n}(x) − u_{n−1}(x), u_{0}(x) = 1, u_{1}(x) = 2x, similarly to the preceding example, we shall find the number c_{1} = 1, the recurrence equation

u_{n}(x) = [\begin{matrix}2x \\ −\frac{1}{2x} & 2x \\ 0 & −\frac{1}{2x} & 2x \\ 0 & 0 & −\frac{1}{2x} & 2x \\ ⋯ & ⋯ & ⋯ & ⋯ & ... \\ 0 & ⋯ & 0 & 0 & −\frac{1}{2x} & 2x \end{matrix}]_{n} ,

and the generating function ∑_{i=0}^{∞} u_{i}(x)z^{i} = \frac{1}{1−2xz+z^{2}} .

The next theorem makes it possible to reestablish an appropriate recurrence equation with initial conditions by using a known generating function.

Theorem 11. Suppose we are given the generating function

f(z) = \frac{1 + d_{1}z + d_{2}z^{2} + ⋯ + d_{k−1}z^{k−1}}{1 − a_{1}z − a_{2}z^{2} − ⋯ − a_{k}z^{k}}  (16)

of the sequence (u_{n})_{n≥0}. Then the sequence (u_{n})_{n≥0} satisfies the recurrence equation (6) with initial conditions

u_{0} = 1, u_{i} = [ \begin{matrix}a_{1} + d_{1} \\ \frac{a_{2}+d_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ... \\ \frac{a_{i}+d_{i}}{a_{i−1}} & \frac{a_{i−1}}{a_{i−2}} & ⋯ & a_{1} \end{matrix} ]_{i} , i = 1, 2, …, k − 1,  (17)

with a_{0} ≠ 0 for i = 1, 2, …, k − 1.

Proof. The generating function of the sequence (u_{n})_{n≥0}, which satisfies the recurrence equation (6), follows from Theorem 5. According to Theorem 5, we also have the system b_{i} (1 − \frac{1}{c_{i}} ) = d_{i}, i = 1, 2, …, k − 1, which, after considering (9), we shall reduce to the system

b_{i} = a_{1}b_{i−1} + a_{2}b_{i−2} + ⋯ + a_{i−1}b_{1} + a_{i}b_{0} + d_{i}, i = 1, 2, …, k − 1,  (18)

with b_{0} = 1.

The proof of the theorem follows from the system (18) being decomposition of the right side of (17) by elements of the last row (see (5)).

4 Number-theoretic properties of sequences

Recurrences and sequences of numbers or polynomials generated by them arise in different fields of mathematics, and many problems in number theory and algebra come down to studying their properties [7, 25, 30]. But often, the properties of recurrence sequences are investigated regardless of the relevant equation, which complicates the process of studies.

Let us consider now general properties of sequences using linear recurrence equations generating them and the apparatus of triangular matrices.

Theorem 12. [35] Let the sequences (u_{n}^{∗})_{n≥1} and (u_{n})_{n≥1} satisfy the recurrence equations

u_{n}^{∗} = a_{1}u_{n−1}^{∗} + a_{2}u_{n−2}^{∗} + ⋯ + a_{k}u_{n−k}^{∗},
u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2} + ⋯ + a_{k}u_{n−k},

with general initial conditions u_{1}^{∗} = b_{1}, u_{2}^{∗} = b_{2}, …, u_{k}^{∗} = b_{k} and normal initial conditions

u_{1} = 1, u_{i} = [ \begin{matrix}a_{1} \\ \frac{a_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ... \\ \frac{a_{i−1}}{a_{i−2}} & \frac{a_{i−2}}{a_{i−3}} & ⋯ & a_{1} \end{matrix} ]_{i−1} , i = 2, 3, …, k,

respectively, with a_{i} ≠ 0 for i = 1, 2, …, k − 1. Then

u_{r+s}^{∗} = ∑_{i=1}^{k} a_{i} ∑_{j=r−i+1}^{r} u_{j}^{∗}u_{r+s−i−j+1},  (19)

where r + s > k.

Proof. From Corollary 7 it follows that the parapermanent (14) is the solution of equation (6) with initial conditions (7). Let us decompose the parapermanent (14) for n = r + s by elements of the inscribed rectangular table T (r). If b_{ij} is some element of the table T (r), then the first corner R_{j−1,1} of its parapermanent algebraic complement

P_{ij} = pper(R_{j−1,1}) · pper(R_{r+s−1,i+1}),

besides the coefficients of equation (6), will include the numbers c_{1}, c_{2}, …, c_{k}, which are defined by (9). That is why the parapermanent of the corner R_{j−1,1} is the j-th term of the sequence (u_{n}^{∗})_{n≥1}. In the second corner, all the numbers c_{i} = 1, and that is why its parapermanent is the (r + s − i)-th term of the sequence (u_{n})_{n≥1}. It is obvious that b_{ij} = 0, if k − 1 < i − j and b_{ij} = a_{i−j+1}, if 0 ≤ i − j ≤ k. If i − j = k − 1, then b_{ij} = a_{k}, i = j + k − 1, and the number j gets the value from r − k + 1 to r. Thus, all the summands from the decomposition of the parapermanent u_{r+s} by elements of the table T (r), which contain the

coefficients a_{k} of the equation (6), will be part of the sum a_{k} · ∑_{j=r−k+1}^{r} u_{j}^{∗}u_{r+s−j−k+1}.

If i − j = k − 2, then b_{ij} = a_{k−1}, i = j + k − 2, j = r − k + 2, …, r, and the similar sum

is a_{k−1} · ∑_{j=r−k+2}^{r} u_{j}^{∗}u_{r+s−j−k+2}. Continuing the process of calculating the sums like these, in

(k−1) steps we get the equality i = j, which means we shall come to the sum a_{1} ·∑_{j=r}^{r} u_{j}^{∗}u_{r+s−j}.

Thus, the index i of coefficients a_{i} will get the value from 1 to k, and the decomposition of the parapermanent u_{r+s}^{∗} by elements of the inscribed rectangular table T (r) will be (19).

Let us write the equality (19) for k = 1, k = 2, and k = 3 respectively:

u_{r+s}^{∗} = a_{1}u_{r}^{∗}u_{s},
u_{r+s}^{∗} = a_{1}u_{r}^{∗}u_{s} + a_{2}(u_{r−1}^{∗}u_{s} + u_{r}^{∗}u_{s−1}),
u_{r+s}^{∗} = a_{1}u_{r}^{∗}u_{s} + a_{2}(u_{r−1}^{∗}u_{s} + u_{r}^{∗}u_{s−1}) + a_{3}(u_{r−2}^{∗}u_{s} + u_{r−1}^{∗}u_{s−1} + u_{r}^{∗}u_{s−2}).  (20)

Replacing in (20) r with r + q, we get the equality

u_{r+q+s}^{∗} = u_{r+1}^{∗}u_{q+1}u_{s} + a_{2}u_{r}^{∗}u_{q}u_{s} + a_{2}u_{r+1}^{∗}u_{q}u_{s−1} + a_{2}^{2}u_{r}^{∗}u_{q−1}u_{s−1}.  (21)

Corollary 13. If the sequence (u_{n})_{n≥1} satisfies the recurrence equality (6) with normal initial conditions (13), then for its terms the following relations hold:

u_{r+s} = ∑_{i=1}^{k} a_{i} ∑_{j=r−i+1}^{r} u_{j}u_{r+s−i−j+1}.  (22)

The validity of Corollary 13 is immediate from Theorem 12. Let us write (22) for k = 1, k = 2, and k = 3 respectively:

u_{r+s} = a_{1}u_{r}u_{s},
u_{r+s} = a_{1}u_{r}u_{s} + a_{2}(u_{r−1}u_{s} + u_{r}u_{s−1}),
u_{r+s} = a_{1}u_{r}u_{s} + a_{2}(u_{r−1}u_{s} + u_{r}u_{s−1}) + a_{3}(u_{r−2}u_{s} + u_{r−1}u_{s−1} + u_{r}u_{s−2}).

The first ten terms of the normal number sequence, which are generated by linear secondorder recurrence equation

u_{n+2} = a_{1}u_{n+1} + a_{2}u_{n}, a_{1}, a_{2} ∈ ℤ\{0},  (23)

are as follows:

u_{1} = 1,
u_{2} = a_{1},
u_{3} = a_{1}^{2} + a_{2},
u_{4} = a_{1}^{3} + 2a_{1}a_{2},
u_{5} = a_{1}^{4} + 3a_{1}^{2}a_{2} + a_{2}^{2},
u_{6} = a_{1}^{5} + 4a_{1}^{3}a_{2} + 3a_{1}a_{2}^{2},
u_{7} = a_{1}^{6} + 5a_{1}^{4}a_{2} + 6a_{1}^{2}a_{2}^{2} + a_{2}^{3},
u_{8} = a_{1}^{7} + 6a_{1}^{5}a_{2} + 10a_{1}^{3}a_{2}^{2} + 4a_{1}a_{2}^{3},
u_{9} = a_{1}^{8} + 7a_{1}^{6}a_{2} + 15a_{1}^{4}a_{2}^{2} + 10a_{1}^{2}a_{2}^{3} + a_{2}^{4},
u_{10} = a_{1}^{9} + 8a_{1}^{7}a_{2} + 21a_{1}^{5}a_{2}^{2} + 20a_{1}^{3}a_{2}^{3} + 5a_{1}a_{2}^{4}.

For n ≥ 2 we get

u_{n} = [ \begin{matrix}a_{1} \\ \frac{a_{2}}{a_{1}} & a_{1} \\ 0 & \frac{a_{2}}{a_{1}} & a_{1} \\ 0 & 0 & \frac{a_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ⋯ & ⋯ & ... \\ 0 & ⋯ & 0 & 0 & \frac{a_{2}}{a_{1}} & a_{1} \end{matrix} ]_{n−1} = ∑_{k_{1}+2k_{2} = n−1} \frac{(k_{1} + k_{2})!}{k_{1}! k_{2}!}a_{1}^{k_{1}}a_{2}^{k_{2}}.

The first ten terms of the normal number sequence, which are generated by third order linear recurrence equation

u_{n+3} = a_{1}u_{n+2} + a_{2}u_{n+1} + a_{3}u_{n}, a_{1}, a_{2}, a_{3} ∈ ℤ\{0}, are as follows:

u_{1} = 1,
u_{2} = a_{1},
u_{3} = a_{1}^{2} + a_{2},
u_{4} = a_{1}^{3} + 2a_{1}a_{2} + a_{3},
u_{5} = a_{1}^{4} + 3a_{1}^{2}a_{2} + a_{2}^{2} + 2a_{1}a_{3},
u_{6} = a_{1}^{5} + 4a_{1}^{3}a_{2} + 3a_{1}a_{2}^{2} + 3a_{1}^{2}a_{3} + 2a_{2}a_{3},
u_{7} = a_{1}^{6} + 5a_{1}^{4}a_{2} + 6a_{1}^{2}a_{2}^{2} + 4a_{1}^{3}a_{3} + 6a_{1}a_{2}a_{3} + a_{2}^{3} + a_{3}^{2},
u_{8} = a_{1}^{7} + 6a_{1}^{5}a_{2} + 5a_{1}^{4}a_{3} + 10a_{1}^{3}a_{2}^{2} + 12a_{1}^{2}a_{2}a_{3} + 4a_{1}a_{2}^{3} + 3a_{1}a_{3}^{2} + 3a_{2}^{2}a_{3},
u_{9} = a_{1}^{8} + 7a_{1}^{6}a_{2} + 6a_{1}^{5}a_{3} + 15a_{1}^{4}a_{2}^{2} + 20a_{1}^{3}a_{2}a_{3} + 10a_{1}^{2}a_{2}^{3} + 6a_{1}^{2}a_{3}^{2} + 12a_{1}a_{2}^{2}a_{3} + a_{2}^{4} + 3a_{2}a_{3}^{2},

and for n ≥ 2 we get

u_{n} = [ \begin{matrix}a_{1} \\ \frac{a_{2}}{a_{1}} & a_{1} \\ \frac{a_{3}}{a_{2}} & \frac{a_{2}}{a_{1}} & a_{1} \\ 0 & \frac{a_{3}}{a_{2}} & \frac{a_{2}}{a_{1}} & a_{1} \\ ⋮ & ⋯ & ⋯ & ⋯ & ... \\ 0 & 0 & 0 & 0 & ⋯ & a_{1} \\ 0 & 0 & 0 & 0 & ⋯ & \frac{a_{2}}{a_{1}} & a_{1} \end{matrix} ]_{n−1} = ∑_{k_{1}+2k_{2}+3k_{3} = n−1} \frac{(k_{1} + k_{2} + k_{3})!}{k_{1}! k_{2}! k_{3}!}a_{1}^{k_{1}}a_{2}^{k_{2}}a_{3}^{k_{3}}.

Theorem 14. [35] Let the sequence (u_{n})_{n≥1} satisfy the second-order recurrence equation (23) with normal initial conditions u_{1} = 1, u_{2} = a_{1}. Then

(1) the following equalities hold:

u_{r+s} = u_{r+1}u_{s} + a_{2}u_{r}u_{s−1},  (24)
u_{sr} ≡ 0 (mod u_{r});  (25)

(2) if in the equation (23) the coefficients are relatively prime, then

gcd(u_{s}, u_{r}) = u_{gcd(s,r)}.  (26)

Proof. Let us first prove (24). To do this, we shall use the method of mathematical induction. We apply the Corollary 13 to the equation (23) with initial conditions u_{1} = 1, u_{2} = a_{1}. For k = 2 the equality (22) is

u_{r+s} = a_{2}u_{r−1}u_{s} + a_{1}u_{r}u_{s} + a_{2}u_{r}u_{s−1}.  (27)

From (27), considering (23), we get

u_{r+s} = u_{s}(a_{1}u_{r} + a_{2}u_{r−1}) + a_{2}u_{r}u_{s−1} = u_{r+1}u_{s} + a_{2}u_{r}u_{s−1}.

Let us prove (25). For s = r the equality (24) is

u_{2r} = u_{r}(u_{r+1} + a_{2}u_{r−1}),  (28)

that is (25) holds for s = 1 and s = 2. Let us assume (25) holds for s = 1, 2, …, m − 1, and prove its validity for s = m. As u_{mr} = u_{(m−1)r+r} = u_{(m−1)r+1}u_{r} + a_{2}u_{(m−1)r}u_{r−1}, and u_{(m−1)r} ≡ 0 (mod u_{r}), then u_{mr} = u_{(m−1)r+1}u_{r}, i.e., (25) holds for s = m.

In order to prove the equality (26), let us first prove that

gcd(u_{n}, u_{n+1}) = 1,  (29)
gcd(a_{2}, u_{n}) = 1.  (30)

For n = 1 the equality (29) is obvious. Let us assume that (29) holds for n = k and prove it for n = k+1. Let, conversely, gcd(u_{k+1}, u_{k+2}) = d > 1. Then from (23) for n = k it follows that either u_{k} ≡ 0 (mod d) or a_{2} ≡ 0 (mod d). In the first case, we come to a contradiction with the assumption that (29) holds for n = k, and in the second case from (23) for n = k it follows that a_{1} ≡ 0 (mod d), and this contradicts the fact that the coefficients of equation (23) are relatively prime. Thus, the equality (29) holds for an arbitrary n ∈ ℕ.

The validity of the equality (30) follows from the fact that assumption of the contrary proposition together with (23) for n = s − 1 leads to contradiction with (29).

Now let s < r. Then considering the equality (24), we have

gcd(u_{r}, u_{s}) = gcd(u_{r−s+s}, u_{r}) =
= gcd(u_{r−s+1}u_{s} + a_{2}u_{r−s}u_{s−1}, u_{s}) = gcd(a_{2}u_{r−s}u_{s−1}, u_{s}).

From (29), (30) it follows that gcd(a_{2}u_{s−1}, u_{s}) = 1. Therefore gcd(u_{r}, u_{s}) = gcd(u_{r−s}, u_{s}), and we get the equality (26).

Note that Theorem 14 also holds when the coefficients of linear recurrence equation (23) are functions of some variables.

Example 15. Let us consider the normal sequence of polynomials w_{n}(x) = \frac{x^{n}−1}{x−1}, which is generated by the recurrence equation w_{n+2}(x) = (x+1)w_{n+1}(x)−xw_{n}(x). Polynomials w_{n}(x) do not have real roots, and for prime values n > 3, they are connected with the problem of circle division into n equal parts. Gauss showed that the roots of polynomials w_{n}(x) are expressed as square radicals only when n is a Fermat prime, that is n = 2^{2^{k}} + 1 (\underline{A000215}). Only for these values of n, a circle can be divided into n equal parts with the help of a ruler and compass. According to Theorem 14, gcd(w_{n}(x), w_{m}(x)) = \frac{x^{gcd}(n,m)−1}{x−1}.

Corollary 16. If the sequence (u_{k})_{k≥1} satisfies the hypotheses of Theorem 14 and u_{k} ≠ 1, k ≥ 2, then the term u_{s} is a prime only when s is a prime.

The proof follows from (25).

Corollary 17. Let the sequence (u_{k})_{k≥1} satisfy the hypotheses of Theorem 14 and p is a prime. Then u_{p} has no common divisor with any of the preceding terms of sequence (u_{k})_{k≥1}.

The proof follows from (25).

Corollary 18. Let the sequence (u_{k})_{k≥1} satisfy the hypotheses of Theorem 14 and a_{2} = b^{2}, where b ∈ ℤ. Then each term u_{2m+1}, m > 1, can be written as the sum of squares of two nonnegative integers, namely

u_{2m+1} = u_{m+1}^{2} + (bu_{m})^{2}.

The validity of Corollary 18 follows from (24) for r = n and s = n + 1.

Example 19. The recurrence equation u_{n+2} = (k + 1)u_{n+1} − ku_{n} with normal initial conditions u_{1} = 1, u_{2} = k + 1, k ≥ 1, generates the number sequence (\frac{k^{n}−1}{k−1})_{n≥1}. The condition k ≥ 1 satisfies the condition u_{s} ≠ 1, s ≥ 2, of Corollary 16. According to Corollary 16 the number \frac{k^{n}−1}{k−1} is a prime, if n is a prime. For k = 2 we get a well known fact that Mersenne primes (\underline{A001348}) are among the numbers of the form 2^{p} − 1, where p is some prime. For k = 10 we get a famous proposition that repunits (primes which are written as \underbrace{11 ⋯ 1}_{n} in

the decimal system; see \underline{A002275}), are also sought for prime n.

As the recurrence equation u_{n+2} = u_{n+1} + u_{n} with normal initial conditions u_{1} = u_{2} = 1 generates the Fibonacci sequence, then Theorem 14 can be seen as generalization of some relations for Fibonacci numbers.

There are various generalizations of Fibonacci numbers. Some generalizations are connected with preservation of the recurrence relation F_{n+1} = F_{n} + F_{n−1} and replacement of initial conditions [13, 17, 33], others are based on a more general recurrence relation of the second order without changing the first two terms of the Fibonacci sequence [4, 5, 6, 10, 11, 26, 27, 32]. There are generalizations of the Fibonacci sequence when the recurrence relation has a more general form generalizing the initial conditions with that [1, 3, 9, 16, 14, 21, 22]. In particular, generalizations of the Fibonacci sequence for recurrence relations of higher orders were studied in [2, 8, 15, 19, 20, 30, 31].

Among the terms of number sequences, which satisfy one and the same recurrence equation but with different initial conditions, there are some interesting relations. Therefore studying the properties of the terms of one sequence, it is possible to draw some conclusions concerning the properties of the terms of another sequence.

As a consequence of Theorem 12 (when k = 2, r = 1, and s = n − 1), we have:

Theorem 20. If the sequences (u_{n})_{n≥1}, (u_{n}^{∗})_{n≥1} satisfy the linear second-order recurrence equation

u_{k+2} = a_{1}u_{k+1} + a_{2}u_{k}  (31)

with initial conditions

u_{1} = 1, u_{2} = a_{1}; u_{1}^{∗} = b_{1}, u_{2}^{∗} = b_{2},  (32)

respectively, then

u_{n}^{∗} = b_{2}u_{n−1} + a_{2}b_{1}u_{n−2}.  (33)

The next theorem singles out some classes of number sequences, whose odd-numbered terms can be written as the sum of several squares.

Theorem 21. [34] Let the sequences (u_{n})_{n≥1}, (u_{n}^{∗})_{n≥1} satisfy the linear second-order recurrence equation (31) with initial conditions

u_{1} = 1, u_{2} = a_{1}; u_{1}^{∗} = k, u_{2}^{∗} = a_{1}.  (34)

Then

(1) for n ≥ 3 the following relation holds:

u_{n}^{∗} = u_{n} + (k − 1)a_{2}u_{n−2};  (35)

(2) if

k = a_{2} = s^{2} + 1  (36)

and a_{1} > 0, then for n ≥ 3 the number u_{2n−1}^{∗} is the sum of three squares:

u_{2n−1}^{∗} = u_{n}^{2} + ((s^{2} + 1)u_{n−1})^{2} + ((s^{3} + s)u_{n−2})^{2};  (37)

(3) if

k = s^{2} + 1, a_{2} = b^{2},  (38)

then for n ≥ 2 the number u_{2n+1}^{∗} is the sum of four squares:

u_{2n+1}^{∗} = u_{n+1}^{2} + (bu_{n})^{2} + (sbu_{n})^{2} + (sb^{2}u_{n−1})^{2}.  (39)

Proof. The equality (35) follows from (33):

u_{n}^{∗} = b_{2}u_{n−1} + a_{2}b_{1}u_{n−2} = a_{1}u_{n−1} + a_{2}ku_{n−2} =
= a_{1}u_{n−1} + a_{2}u_{n−2} + a_{2}(k − 1)u_{n−2} = u_{n} + a_{2}(k − 1)u_{n−2}.

Let us prove (37). From (19) for k = 2 we have

u_{r+s}^{∗} = a_{1}u_{r}^{∗}u_{s} + a_{2}(u_{r−1}^{∗}u_{s} + u_{r}^{∗}u_{s−1}) = u_{r+1}^{∗}u_{s} + a_{2}u_{r}^{∗}u_{s−1}.

In the last equality we substitute r = n − 1 and s = n. Then, using (35), we obtain

u_{2n−1}^{∗} = (a_{1}u_{n−1}^{∗} + a_{2}u_{n−2}^{∗})u_{n} + a_{2}u_{n−1}^{∗}u_{n−1} = u_{n}^{∗}u_{n} + a_{2}u_{n−1}^{∗}u_{n−1} =
= (u_{n} + (k − 1)a_{2}u_{n−2})u_{n} + a_{2}(u_{n−1} + (k − 1)a_{2}u_{n−3})u_{n−1} =
= u_{n}^{2} + (k − 1)a_{2}u_{n−2}u_{n} + a_{2}u_{n−1}^{2} + (k − 1)a_{2}^{2}u_{n−3}u_{n−1} =
= u_{n}^{2} + (k − 1)a_{2}u_{n−2}(a_{1}u_{n−1} + a_{2}u_{n−2}) + a_{2}u_{n−1}^{2} + (k − 1)a_{2}^{2}u_{n−3}u_{n−1} =
= u_{n}^{2} + a_{2}u_{n−1}^{2} + (k − 1)a_{2}^{2}u_{n−2}^{2} + (k − 1)a_{2}u_{n−1}^{2} = u_{n}^{2} + ka_{2}u_{n−1}^{2} + (k − 1)a_{2}^{2}u_{n−2}^{2}.

Hence, using (36), we get (37).

To prove (39) we shall write (35) for n = 2m + 1:

u_{2m+1}^{∗} = u_{2m+1} + (k − 1)a_{2}u_{2m−1}.

Hence, using (24) for r = m and s = m + 1 and the condition (38), after simple transformations we obtain (39).

Example 22. If s = 0 we get k = a_{2} = 1 and the equality (37) is written as

u_{2n−1} = u_{n}^{2} + u_{n−1}^{2}.  (40)

Thus, all the terms of the normal number sequence with odd numbers, not less than 3, which are generated by the recurrence equation u_{n+2} = au_{n+1} + u_{n}, can be written as the sum of two squares, e.g.,

u_{3} = a^{2} + 1 = a^{2} + 1^{2},
u_{5} = a^{4} + 3a^{2} + 1 = (a^{2} + 1)^{2} + a^{2},
u_{7} = a^{6} + 5a^{4} + 6a^{2} + 1 = (a^{3} + 2a)^{2} + (a^{2} + 1)^{2},
u_{9} = a^{8} + 7a^{6} + 15a^{4} + 10a^{2} + 1 = (a^{4} + 3a^{2} + 1)^{2} + (a^{3} + 2a)^{2},
u_{11} = a^{10} + 9a^{8} + 28a^{6} + 35a^{4} + 15a^{2} + 1 = (a^{5} + 4a^{3} + 3a)^{2} + (a^{4} + 3a^{2} + 1)^{2}.

In general,

u_{2n−1} = ∑_{i=2}^{n+1} \binom{2n − i}{2(n − i + 1)}a^{2(n−i+1)} =

= ( ∑_{i=1}^{⌊ \frac{n+1}{2} ⌋} \binom{n − i}{n − 2i + 1}a^{n−2i+1})^{2} + (∑_{i=1}^{⌊ \frac{n}{2} ⌋} \binom{n − i − 1}{n − 2i}a^{n−2i})^{2} .

Note that for a = 1 the equality (40) is written as F_{2n−1} = F_{n}^{2} + F_{n−1}^{2}, where F_{n} are Fibonacci numbers, and

F_{n} = ∑_{i=1}^{⌊ \frac{n+1}{2} ⌋} \binom{n − i}{n − 2i + 1}.

Example 23. In item 2 of Theorem 21, let a_{1} = 4, s = 2. Then u_{1} = a_{2} = k = 5,

u_{n}^{∗} = \frac{3 · 5^{n−1} + 7 (−1)^{n−1}}{2} , u_{n} = \frac{5^{n} + (−1)^{n−1}}{6} ,

and the equality (37) becomes

\frac{3 · 5^{2n−2} + 7}{2} = (\frac{5^{n} + (−1)^{n−1}}{6} )^{2} + (\frac{5(5^{n−1} + (−1)^{n})}{6})^{2} + (\frac{5(5^{n} + (−1)^{n−1})}{3})^{2} .

For example, for n = 16 we have decomposition of the prime 396983861923217773441 into the sum of three different squares of positive integers, two of which are sequential:

396983861923217773441 = 25431315104^{2} + 25431315105^{2} + 10172526040^{2}.

Example 24. If in item 3 of Theorem 21 a_{1} = 3, a_{2} = 4, b = 2, s = 1, then

u_{n}^{∗} = 4^{n−1} + (−1)^{n−1}, u_{n} = \frac{4^{n} + (−1)^{n−1}}{5}

and the equality (39) becomes

2^{4m} + 1 = (\frac{4^{m+1} + (−1)^{m}}{5} )^{2} + (\frac{2^{2m+1} + 2(−1)^{m−1}}{5} )^{2} +

+ (\frac{2^{2m+1} + 2(−1)^{m−1}}{5} )^{2} + (\frac{2^{2m} + 4(−1)^{m}}{5} )^{2} .

For m = 2^{n−2} we obtain Fermat numbers F_{n} = 2^{4m} + 1 = 2^{2^{n}} + 1 (\underline{A000215}). The last equality can now be written as

2^{2^{n}} + 1 = (\frac{2^{2^{n−1}+2} + 1}{5})^{2} + (\frac{2^{2^{n−1}+1} − 2}{5})^{2} + (\frac{2^{2^{n−1}+1} − 2}{5})^{2} + (\frac{2^{2^{n−1}} + 4}{5})^{2} , (41)

where n ⩾ 3. For example,

F_{6} = 2^{64} + 1 = 3435973837^{2} + 1717986918^{2} + 1717986918^{2} + 858993460^{2}.

Using (41), with the help of simple transformations, Fermat numbers can be written (I. V. Fedak) as the sum of three squares:

F_{n} = 2^{2^{n}} + 1 = a_{n}^{2} + 1 = (\frac{2a_{n} − 2}{3})^{2} + (\frac{2a_{n} + 1}{3})^{2} + (\frac{a_{n} + 2}{3})^{2} .

For example, F_{6} = 2863311530^{2} + 2863311531^{2} + 1431655766^{2}.

5 Generalization of the Cassini formula

Over 300 years have passed since the discovery of the Cassini formula for Fibonacci numbers

F_{n−1}F_{n+1} − F_{n}^{2} = (−1)^{n}.

During this time, many studies have appeared presenting new similar formulae for other number sequences, which have become classical. But the methods proposed in the preceding sections make it possible to unify researches in this direction. It turns out that normal number sequences mostly have the same properties as Fibonacci numbers. It can be illustrated with the results of Theorem 14, Corollary 17, etc. In this section we shall prove some general theorems, which generalize the Cassini identity.

Consider normal number sequences of the second order

u_{0} = 0, u_{1} = 1, u_{n+2} = a_{1}u_{n−1} + a_{2}u_{n}.  (42)

For these sequences, the following equality holds [34]:

u_{r+s} = u_{r+1}u_{s} + a_{2}u_{r}u_{s−1},  (43)

where r ≥ 1, s ≥ 2. Let in (43) r = n, s = n − 1. Then

u_{2n−1} = u_{n+1}u_{n−1} + a_{2}u_{n}u_{n−2}.

For r = n − 1, s = n from (43) we have

u_{2n−1} = u_{n}^{2} + a_{2}u_{n−1}^{2}.

By subtracting two last equalities, we obtain the relation

u_{n+1}u_{n−1} − u_{n}^{2} = −a_{2}(u_{n}u_{n−2} − u_{n−1}^{2}).

Thus, we get the sequence of equalities

(−a_{2})^{0}(u_{n+1}u_{n−1} − u_{n}^{2}) = (−a_{2})^{1}(u_{n}u_{n−2} − u_{n−1}^{2}),
(−a_{2})^{1}(u_{n+1}u_{n−1} − u_{n}^{2}) = (−a_{2})^{2}(u_{n}u_{n−2} − u_{n−1}^{2}),
⋮
(−a_{2})^{n−3}(u_{4}u_{2} − u_{3}^{2}) = (−a_{2})^{n−2}(u_{3}u_{1} − u_{2}^{2}),

by adding which, we get the generalized Cassini formula

u_{n+1}u_{n−1} − u_{n}^{2} = (−1)^{n}a_{2}^{n−1}.

In the equality (43), let r = n − 1, s = n − 3. Then

u_{2n−4} = u_{n}u_{n−3} + a_{2}u_{n−1}u_{n−4}.

If r = n − 2, s = n − 2, then from above equality we get

u_{2n−4} = u_{n−1}u_{n−2} + a_{2}u_{n−2}u_{n−3}.

By subtracting two last equalities, we obtain

u_{n}u_{n−3} − u_{n−1}u_{n−2} = −a_{2}(u_{n−1}u_{n−4} − u_{n−2}u_{n−3}).

Thus, we get the equalities

(−a_{2})^{0}(u_{n}u_{n−3} − u_{n−1}u_{n−2}) = (−a_{2})^{1}(u_{n−1}u_{n−4} − u_{n−2}u_{n−3}),
(−a_{2})^{1}(u_{n−1}u_{n−4} − u_{n−2}u_{n−3}) = (−a_{2})^{2}(u_{n−2}u_{n−5} − u_{n−3}u_{n−4}),
⋮
(−a_{2})^{n−5}(u_{5}u_{2} − u_{4}u_{3}) = (−a_{2})^{n−4}(u_{4}u_{1} − u_{3}u_{2}).

Hence, by adding all these equalities, we finally get the equality

u_{n}u_{n−3} − u_{n−1}u_{n−2} = (−1)^{n}a_{1}a_{2}^{n−3}.

In this way, we prove the following proposition.

Theorem 25. For normal number sequences of the second order (42) the following equalities are true:

u_{n+1}u_{n−1} − u_{n}^{2} = (−1)^{n}a_{2}^{n−1},  (44)
u_{n}u_{n−3} − u_{n−1}u_{n−2} = (−1)^{n}a_{1}a_{2}^{n−3}.  (45)

For the sequences (u_{n})_{n≥1}, (u_{n}^{∗})_{n≥1}, which are generated by the second-order recurrence relation with initial conditions u_{1} = 1, u_{2} = a_{1} u_{1}^{∗} = b_{1}, u_{2}^{∗} = b_{2} respectively, the following equality is true

u_{n}^{∗} = b_{2}u_{n−1} + a_{2}b_{1}u_{n−2}.  (46)

Let us apply (46) to determine the Cassini formula for the sequence (u_{n}^{∗})_{n≥1}:

u_{n+1}^{∗}u_{n−1}^{∗} − (u_{n}^{∗})^{2} =
= (b_{2}u_{n} + a_{2}b_{1}u_{n−1})(b_{2}u_{n−2} + a_{2}b_{1}u_{n−3}) − (b_{2}u_{n−1} + a_{2}b_{1}u_{n−2})^{2} =
= b_{2}^{2}(u_{n}u_{n−2} − u_{n−1}^{2}) + a_{2}^{2}b_{1}^{2}(u_{n−1}u_{n−3} − u_{n−2}^{2}) + a_{2}b_{2}b_{1}(u_{n}u_{n−3} − u_{n−1}u_{n−2}).

Using (44), (45), we shall substitute relevant values instead of parentheses in the last equalities

u_{n+1}^{∗}u_{n−1}^{∗} − (u_{n}^{∗})^{2} = (−1)^{n−1}b_{2}^{2}a_{2}^{n−2} + (−1)^{n}a_{2}^{2}b_{1}^{2}a_{2}^{n−3} + (−1)^{n}a_{2}b_{1}b_{2}a_{1}a_{2}^{n−3} =
= (−1)^{n−1}a_{2}^{n−2}(b_{2}^{2} − a_{2}b_{1}^{2} − a_{1}b_{1}b_{2}).

Theorem 26. For normal number sequences

u_{1} = 1, u_{2} = a_{1}, u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2}  (47)

the following equalities hold:

u_{n}u_{n−k} − u_{n−1}u_{n−(k−1)} = (−1)^{n+k(mod 2)−1}a_{2}^{n−k}u_{k−1},  (48)

where k ≥ 2, n ≥ k + 1.

Proof. We shall prove the theorem by induction for k. For k = 2 the proposition of the theorem is true based on the equality (44). Assume that the proposition of the theorem is true for n = k and we shall prove that the proposition of the theorem is also true for n = k + 1. We get

u_{n}u_{n−(k+1)} − u_{n−1}u_{n−k} = (a_{1}u_{n−1} + a_{2}u_{n−2})u_{n−(k+1)} − (a_{1}u_{n−2} + a_{2}u_{n−3})u_{n−k} =
= a_{1} (u_{n−1}u_{(n−1)−k} − u_{n−2}u_{(n−1)−(k−1)}) + a_{2} (u_{n−2}u_{(n−2)−(k−1)} − u_{n−3}u_{(n−2)−(k−2)}) =
= a_{1}(−1)^{(n−1)+(k mod 2)−1}a_{2}^{(n−1)−k}u_{k−1} + a_{2}(−1)^{(n−2)+(k−1)(mod 2)−1}a_{2}^{(n−2)−(k−1)}u_{k−2} =
= (−1)^{n+(k mod 2)}a_{2}^{n−(k+1)}(a_{1}u_{k−1} + a_{2}u_{k−2}) = (−1)^{n+(k mod 2)}a_{2}^{n−(k+1)}u_{k}.

Theorem 27. The terms of the normal number sequence (47) satisfy the relation

u_{n}u_{n−k} − u_{n−s}u_{n−(k−s)} = (−1)^{n+(k mod 2)−1}a_{2}^{n−k}u_{s}u_{k−s}.  (49)

Proof. We shall prove by induction for s. For s = 1 (49) is written as the equality (48) from Theorem 26. We shall denote U(n, k, s) = u_{n}u_{n−k} − u_{n−s}u_{n−(k−s)}. Then

U(n, k, s + 1) = u_{n}u_{n−k} − u_{n−(s+1)}u_{n−(k−(s+1))} =
= (a_{1}u_{n−1} + a_{2}u_{n−2}) u_{n−k} − u_{n−(s+1)} (a_{1}u_{(n−1)−((k−1)−s)} + a_{2}u_{(n−2)−((k−1)−s)}) =
= a_{1}U(n − 1, k − 1, s) + a_{2}U(n − 2, k − 2, s − 1) =
= (−1)^{(n−1)+((k−1) mod 2)−1}a_{1}a_{2}^{(n−1)−(k−1)}u_{s}u_{(k−1)−s} +
+(−1)^{(n−2)+((k−2) mod 2)−1}a_{2}a_{2}^{(n−2)−(k−2)}u_{s−1}u_{(k−2)−(s−1)} =
= (−1)^{n+(k mod 2)−1}a_{2}^{n−k}u_{k−(s+1)}(a_{1}u_{s} + a_{2}u_{s−1}) = (−1)^{n+(k mod 2)−1}a_{2}^{n−k}u_{s+1}u_{k−(s+1)}.

Theorem 28. For the sequences (u_{n})_{n≥1} and (u_{n}^{∗})_{n≥1}, which satisfy the linear recurrence equation (31) with initial conditions u_{1} = a_{1}, u_{2} = a_{2} and u_{1}^{∗} = b_{1}, u_{2}^{∗} = b_{2} respectively, the following identity is true:

u_{n}^{∗}u_{n−k}^{∗} − u_{n−s}^{∗}u_{n−(k−s)}^{∗} = (−1)^{n+(k mod 2)}a_{2}^{n−k−1} (b_{2}^{2} − a_{2}b_{1}^{2} − a_{1}b_{1}b_{2}) u_{s}u_{k−s}.

Proof. To prove this we shall use the identity (33):

u_{n}^{∗}u_{n−k}^{∗} − u_{n−s}^{∗}u_{n−(k−s)}^{∗} = (b_{2}u_{n−1} + a_{2}b_{1}u_{n−2})(b_{2}u_{n−k−1} + a_{2}b_{1}u_{n−k−2}) −
−(b_{2}u_{n−s−1} + a_{2}b_{1}u_{n−s−2}) (b_{2}u_{n−(k−s)−1} + a_{2}b_{1}u_{n−(k−s)−2}) =
= b_{2}^{2}U(n − 1, k, s) + a_{2}^{2}b_{1}^{2}U(n − 2, k, s) +
+ a_{2}b_{2}b_{1}U(n − 1, k + 1, s) + a_{2}b_{2}b_{1}U(n − 2, k − 1, s) =
= (−1)^{n−1+(kbmod2)−1}b_{2}^{2}a_{2}^{n−1−k}u_{s}u_{k−s} + (−1)^{n−2+(k mod 2)−1}a_{2}^{2}b_{1}^{2}a_{2}^{n−2−k}u_{s}u_{k−s} +
+(−1)^{n−1+((k+1) mod 2)−1}a_{2}b_{2}b_{1}a_{2}^{(n−1)−(k+1)}u_{s}u_{(k+1)−s} +
+(−1)^{(n−2)+((k−1) mod 2)−1}a_{2}b_{2}b_{1}a_{2}^{(n−2)−(k−1)}u_{s}u_{(k−1)−s} =
= (−1)^{n+(k mod 2)}a_{2}^{n−k−2}u_{s} (a_{2}b_{2}^{2}u_{k−s} − a_{2}^{2}b_{1}^{2}u_{k−s} − a_{2}b_{1}b_{2}u_{k−s+1} + a_{2}^{2}b_{1}b_{2}u_{k−s−1}) =
= (−1)^{n+(k mod 2)}a_{2}^{n−k−1} (b_{2}^{2} − a_{2}b_{1}^{2} − a_{1}b_{1}b_{2}) u_{s}u_{k−s}.

6 Acknowledgments

The authors would like to thank the anonymous referee for valuable comments and suggestions that improved the original version of the article.

References

[1] K. T. Atanassov, On a generalization of the Fibonacci sequence in the case of three sequences, Fibonacci Quart. 27 (1989), 7–10.

[2] H. Belbachir and F. Bencherif, Linear recurrent sequences and powers of a square matrix, Integers 6 (2006), #A12.

[3] G. Bilgici, New generalizations of Fibonacci and Lucas sequences, Appl. Math. Sci. 8 (2014), 1429–1437.

[4] C. Bolat and H. Köse, On the properties of k-Fibonacci numbers, Int. J. Contemp. Math. Sci. 22 (2010), 1097–1105.

[5] P. Catarino, On some identities for k-Fibonacci sequence, Int. J. Contemp. Math. Sci. 9 (2014), 37–42.

[6] G. Cerda, Matrix methods in Horadam sequences, Bol. Mat. 19 (2012), 97–106.

[7] P. Cull, M. Flahive, and R. Robson, Difference Equations: From Rabbits to Chaos, Springer, 2005.

[8] G. Dresden and Zhaohui Du, A simplified Binet formula for k-generalized Fibonacci numbers, J. Integer Sequences 17 (2014), Article 14.4.7.

[9] A. Dujella, Generalized Fibonacci numbers and the problem of Diophantus, Fibonacci Quart. 34 (1996), 164–175.

[10] M. Edson, S. Lewis, and O. Yayenie, The k-periodic Fibonacci sequences and extended Binet’s formula, Integers 11 (2011), #A32.

[11] S. Falcón and A. Plaza, On the Fibonacci k-numbers, Chaos Solutions Fractals 32 (2007), 1615–1624.

[12] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. A Foundation for Computer Science, Addison-Wesley, 1994.

[13] A. F. Horadam, A generalized Fibonacci sequence, Amer. Math. Monthly 68 (1961), 455–459.

[14] A. F. Horadam and A. G. Shannon, Generalization of identities of Catalan and others, Port. Math. 44 (1987), 137–148.

[15] F. T. Howard and C. Cooper, Some identities for r-Fibonacci numbers, Fibonacci Quart. 49 (2011), 231–243.

[16] N. Irmak and M. Apl, Some indentities for generalized Fibonacci and Lucas sequences, Hacet. J. Math. Stat. 42 (2013), 331–338.

[17] S. T. Klein, Combinatorial representation of generalized Fibonacci numbers, Fibonacci Quart. 29 (1991), 124–131.

[18] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley, 2001.

[19] K. Kuhapatanakul and L. Sukruan, The generalized Tribonacci numbers with negative subscripts, Integers 14 (2014), #A32.

[20] C. Levesque, On m-th order linear recurrences, Fibonacci Quart. 23 (1985), 290–293.

[21] R. S. Melham, A Fibonacci identity in the spirit of Simson and Gelin-Cesaro, Fibonacci Quart. 41 (2003), 142–143.

[22] N. Y. Özgür, On the sequences related to Fibonacci and Lucas numbers, J. Korean Math. Soc. 42 (2005), 135–151.

[23] S. P. Pethe and C. N. Phadte, A generalization of the Fibonacci sequence, in G. E. Bergum, A. N. Philippou, and A. F. Horadam, eds., Applications of Fibonacci Numbers, Vol. 5, Kluwer Academic Publishers, 1993, pp. 465–472.

[24] S. Rabinowitz, Algorithmic manipulation of second order linear recurrences, Fibonacci Quart. 37 (1999), 162–177.

[25] K. H. Rosen, Discrete Mathematics and its Applications, McGraw-Hill, 2011.

[26] M. Sahin, The Gelin-Cesaro identity in some conditional sequences, Hacet. J. Math. Stat. 40 (2011), 855–861.

[27] G. Sbultari, Generalized Fibonacci sequence and linear congruences, Fibonacci Quart. 40 (2002), 446–452.

[28] R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013.

[29] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997.

[30] R. B. Taher and M. Rachidi, Linear recurrence relations in the algebra of matrices and applications, Linear Algebra Appl. 330 (2001), 15–24.

[31] D. Tasci and M. C. Firengiz, Incomplete Fibonacci and Lucas p-numbers, Math. Comput. Modelling 52 (2010), 1763–1770.

[32] O. Yayenie, A note on generalized Fibonacci sequences, Appl. Math. Comput. 217 (2011), 5603–5611.

[33] J. E. Walton and A. F. Horadam, Some further identities for the generalized Fibonacci sequences {H_{n}}, Fibonacci Quart. 12 (1974), 272–280.

[34] R. A. Zatorsky, Theory of paradeterminants and its applications, Algebra Discrete Math. 1 (2007), 109–138.

[35] R. A. Zatorsky, Calculus of Triangular Matrices, Simyk, 2010.

[36] R. A. Zatorsky and I. Ì. Lytvynenko, Applications of parapermanents of linear recurrent sequences, Research Bulletin of NTUU “KPI” 5 (2008), 122–128.

[37] R. A. Zatorsky, Paradeterminants and parapermanents of triangular matrices, Reports of the National Academy of Sciences of Ukraine 8 (2002), 21–25.

2010 Mathematics Subject Classification: Primary 15A15; Secondary 11B37, 11B39. Keywords: triangular matrix, parapermanent, recurrence equation, generating function.

(Concerned with sequences \underline{A000045}, \underline{A000213}, \underline{A000215}, \underline{A000930}, \underline{A001045}, \underline{A001348}, and \underline{A002275}.)

Received February 23 2015; revised version received December 20 2015. Published in Journal of Integer Sequences, January 10 2016.

Return to Journal of Integer Sequences home page.