Permanental Representations of Negatively Subscripted Generalized Order-k Fibonacci Numbers

Hacène Belbachir

USTHB Faculty of Mathematics RECITS Laboratory

P. O. Box 32 El Alia, 16111, Algiers

Algeria

hbelbachir@usthb.dz

Ihab-Eddine Djellas

USTHB Faculty of Mathematics RECITS Laboratory

P. O. Box 32 El Alia, 16111, Algiers

Algeria

Centre de Recherche sur l’Information Scientifique et Technique–CERIST

Algiers, Algeria

 idjellas@usthb.dz

Fariza Krim Oran 1 University Faculty of Sciences GEAN Laboratory P. O. Box 1524

El Menaouer, 31000, Oran

Algeria USTHB Faculty of Mathematics RECITS Laboratory

P. O. Box 32 El Alia, 16111, Algiers

Algeria

   fkrim@usthb.dz

Abstract We introduce an extension to the negative indices of a family of generalized Fibonacci sequences of order-k, and for which we establish recurrence relations. We also give permanental representations of negatively subscripted generalized Fibonacci and Lucas sequences via Hessenberg matrices.

1 Introduction

A family of k sequences of the generalized order-k Fibonacci numbers was defined and studied by Er [3], for n > 0 and 1 ≤ i ≤ k, as follows:

g_{n}^{(i)} = c_{1}g_{n−1}^{(i)} + c_{2}g_{n−2}^{(i)} + ⋯ + c_{k}g_{n−k}^{(i)},  (1)

where c_{1}, c_{2}, …, c_{k} are real constant coefficients, with c_{k} ≠ 0, and for 1 − k ≤ n ≤ 0,

g_{n}^{(i)} = \begin{cases}1, & for i = 1 − n; \\ 0, & otherwise. \end{cases}

Several sequences were derived from (1). Lee and Lee [6] studied the sequence obtained from (1) by setting (c_{1}, c_{2}, …, c_{k}) = (1, 1, …, 1) and i = 1, which is called in the present paper order-k Fibonacci sequence (g̃_{n}^{(k)})_{n}. Also, Lee [8] studied order-k Lucas sequence denoted (l_{n}^{(k)})_{n}, for k ≥ 2. The sequence (l_{n}^{(k)})_{n} is obtained from (1) by setting (c_{1}, c_{2}, …, c_{k}) = (1, 1, …, 1) with initial conditions l_{0}^{(k)} = 2, l_{j}^{(k)} = 2^{j−1}, for j = 1, …, k − 1, and l_{k}^{(k)} = 2^{k−1} + 1.

In the present paper, we consider the family of shifted generalized order-k Fibonacci sequences defined as (1), but with initial conditions, for 0 ≤ n ≤ k − 1,

g_{n}^{(i)} = \begin{cases}1, & for i = k − n; \\ 0, & otherwise. \end{cases}

The permanent of a square matrix A = (a_{ij})_{n×n} is defined as follows:

per A = ∑_{σ∈𝔖_{n}} ∏_{i=1}^{n} a_{iσ(i)},

where the summation runs over all permutations σ of the symmetric group 𝔖_{n} of order n.

Next, we present the definition of matrix contraction; see for instance [2]. Let A = (a_{ij}) be an m × n real matrix with row vectors α_{1}, α_{2}, …, α_{m}. We say that A is contractible on column (resp., row) k if column (resp., row) k contains exactly two nonzero entries. If A is contractible on column k with a_{ik} ≠ 0 ≠ a_{jk} and i ≠ j, then the (m − 1) × (n − 1) matrix A_{ij}^{(k)}, obtained from A by replacing row i by a_{jk}α_{i} + a_{ik}α_{j} and deleting row j and column k, is called the contraction of A on column k relative to rows i and j.

Brualdi and Gibson [2] gave the following lemma.

Lemma 1. Let A be a nonnegative integral matrix of order n > 1, and let B be a contraction of A. Then

per A = per B.

Permanental representations of recurrent sequences have been investigated by several authors. Yilmaz and Bozkurt [11] gave permanental representations of sums of Fibonacci and Lucas numbers via Hessenberg matrices. Lee et al. [7] obtained g_{n+k−1}^{(k)} as the permanent of an n × n upper triangular (0, 1)-matrix; that is a matrix whose all entries are either 0 or 1. Lee [8] constructed a (0, 1)-matrix of order n and established that the permanent of that matrix is the (n − 1)^{th} term l_{n−1}^{(k)} of the order-k Lucas sequence.

The aim of this work is to propose an extension to negative indices of the family of generalized order-k Fibonacci sequences (g_{n}^{(i)})_{n}, 1 ≤ i ≤ k. For instance, extensions to negative indices of order-k Fibonacci, order-k Lucas, order-k Pell, and order-k Jacobsthal are also given. As application, we provide some permanental representations.

The present paper is organized as follows: In Section 2, we give an extension of order-k Fibonacci, order-k Lucas, and the family of generalized order-k Fibonacci sequences (g_{n}^{(i)})_{n}, 1 ≤ i ≤ k, to negatively subscripted indices. We also provide recurrence formulas for the n^{th} term of these negatively subscripted sequences. In Section 3, we present negatively subscripted generalized order-k Fibonacci numbers as the permanent of special Hessenberg matrix. In Section 4, we give more permanental representations of negatively subscripted order-k Fibonacci and order-k Lucas sequences. We conclude by Section 5, where we provide proofs of the results presented in Sections 3 and 4.

2 Extension to negative indices

Extension to negative indices of classical Fibonacci sequence (F_{n})_{n} with initial conditions F_{0} = 0, F_{1} = 1 is given for n ≥ 1, by

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

The extension to negative indices of classical Lucas sequence (L_{n})_{n} with initial conditions L_{0} = 2, L_{1} = 1 is given for n ≥ 1, by

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

Firstly, we propose an extension of order-k Fibonacci sequence (g̃_{n}^{(k)})_{n} to negatively subscripted indices, for n ≥ 1, as follows:

g̃_{−n}^{(k)} = −g̃_{−n+1}^{(k)} − g̃_{−n+2}^{(k)} − ⋯ − g̃_{−n+k−1}^{(k)} + g̃_{−n+k}^{(k)}.  (4)

For example, for k = 2, (g̃_{n}^{(2)})_{n∈ℤ} is the classical Fibonacci sequence.

For k = 3, (g̃_{n}^{(3)})_{n∈ℤ} is the Tribonacci sequence

…, −8, 4, 1, −3, 2, 0, −1, 1, 0, 0, 1, 1, 2, 4, 7, 13, …

For k = 4, (g̃_{n}^{(4)})_{n∈ℤ} is the Quadrabonacci sequence

…, 0, 1, −3, 2, 0, 0, −1, 1, 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, …

An extension of order-k Lucas sequence (l_{n}^{(k)})_{n} to negatively subscripted indices, for n ≥ 1, is given by

l_{−n}^{(k)} = −l_{−n+1}^{(k)} − l_{−n+2}^{(k)} − ⋯ − l_{−n+k−1}^{(k)} + l_{−n+k}^{(k)}.  (5)

For example, for k = 2, (l_{n}^{(2)})_{n∈ℤ} is the Lucas sequence.

For k = 3, (l_{n}^{(3)})_{n∈ℤ} is the Tribonacci-Lucas sequence

…, 6, −11, 6, 1, −4, 3, 0, −1, 2, 1, 2, 5, 8, 15, 28, 51, …

For k = 4, (l_{n}^{(4)})_{n∈ℤ} is the Quadrabonacci-Lucas sequence

…, −11, 6, 0, 1, −4, 3, 0, 0, −1, 2, 1, 2, 4, 9, 16, 31, 60, …

Secondly, we establish the extension of the family of generalized order-k Fibonacci sequences, (g_{n}^{(i)})_{n}, 1 ≤ i ≤ k, to negatively subscripted indices, in the following way:

g_{−n}^{(i)} = −\frac{c_{k−1}}{c_{k}} g_{−n+1}^{(i)} − \frac{c_{k−2}}{c_{k}} g_{−n+2}^{(i)} − ⋯ − \frac{c_{1}}{c_{k}} g_{−n+k−1}^{(i)} + \frac{1}{c_{k}} g_{−n+k}^{(i)}.  (6)

where, c_{j} ∈ ℝ for 1 ≤ j ≤ k and c_{k} ≠ 0. And g_{−n}^{(i)} is said to be the n^{th} negatively subscripted generalized order-k Fibonacci number of the sequence number i of the family.

For instance, we give the extension to negative indices of classical order-k sequences. We start by a family of order-k Fibonacci sequences defined for 1 ≤ i ≤ k and n ≥ k as follows:

f_{n}^{(i)} = f_{n−1}^{(i)} + f_{n−2}^{(i)} + ⋯ + f_{n−k}^{(i)},

with initial conditions; for 0 ≤ n ≤ k − 1,

f_{n}^{(i)} = \begin{cases}1, & for i = k − n; \\ 0, & otherwise. \end{cases}

For n ≥ 1, we give the extension of the family of order-k Fibonacci sequences to negative indices as follows:

f_{−n}^{(i)} = −f_{−n+1}^{(i)} − f_{−n+2}^{(i)} − ⋯ − f_{−n+k−1}^{(i)} + f_{−n+k}^{(i)}.  (7)

The following table gives the first terms of negatively subscripted order-k Fibonacci sequences for n ≥ 1,

k = 2  k = 3  k = 4
i = 1 1, −1, 2, −3, 5, −8, 13, −21, 34, −55 …  1, −1, 0, 2, −3, 1, 4, −8, 5, 7 …  1, −1, 0, 0, 2, −3, 1, 0, 4, −8 …
i = 2 −1, 2, −3, 5, −8, 13, −21, 34, −55, 89 … −1, 2, −1, −2, 5, −4, −3, 12, −13, −2 … −1, 2, −1, 0, −2, 5, −4, 1, −4, 12 …
i = 3 −1, 0, 2, −3, 1, 4, −8, 5, 7, −20 … −1, 0, 2, −1, −2, 1, 4, −4, −3, 4 …
i = 4  −1, 0, 0, 2, −3, 1, 0, 4, −8, 5 …

Table 1: First terms of negatively subscripted order-k Fibonacci sequences

Remark 2. For k = 2, (f_{−n}^{(1)})_{n} is the extension to negative indices of classical Fibonacci numbers.

Kiliç and Taşci [5] studied a family of k sequences of order-k Pell numbers defined for n > 0 and 1 ≤ i ≤ k, as follows:

P_{n}^{(i)} = 2P_{n−1}^{(i)} + P_{n−2}^{(i)} + ⋯ + P_{n−k}^{(i)}.  (8)

with initial conditions; for 1 − k ≤ n ≤ 0,

P_{n}^{(i)} = \begin{cases}1, & for n = 1 − i; \\ 0, & otherwise. \end{cases}

Next, we consider k sequences of shifted order-k Pell numbers (8) for n ≥ k and 1 ≤ i ≤ k, with initial conditions, for 0 ≤ n ≤ k − 1,

P_{n}^{(i)} = \begin{cases}1, & for i = k − n; \\ 0, & otherwise. \end{cases}

Then for n ≥ 1, we give extension of these sequences (8) to negative indices as follows:

P_{−n}^{(i)} = −P_{−n+1}^{(i)} − ⋯ − P_{−n+k−2}^{(i)} − 2P_{−n+k−1}^{(i)} + P_{−n+k}^{(i)}.  (9)

The next table gives the first terms of negatively subscripted order-k Pell sequences for n ≥ 1,

k = 2  k = 3  k = 4
i = 1 1, −2, 5, −12, 29, −70, 169, −408 … 1, −1, −1, 4, −3, −6, 16, −7, −31, 61 … 1, −1, 0, −1, 4, −4, 2, −7, 17, −18 …
i = 2 −2, 5, −12, 29, −70, 169, −408, 985 … −2, 3, 1, −9, 10, 9, −38, 30, 55, −153 … −2, 3, −1, 2, −9, 12, −8, 16, −41, 53 …
i = 3  −2, 3, −3, 1, 4, −12, 21, −26, 19, 9 … −1, −1, 3, 0, −2, −5, 10, −1, −1, −23 …
i = 4  −1, 0, −1, 4, −4, 2, −7, 17, −18, 17 …

Table 2: First terms of negatively subscripted order-k Pell sequences

Remark 3. Some of the sequences in Table 2 are known in OEIS [9], as for example, \underline{A215936}, \underline{A276229}, and \underline{A078021}.

In 2009, Yilmaz and Bozkurt [10] studied a family of k sequences of order-k Jacobsthal numbers defined for n > 0 and 1 ≤ i ≤ k, as follows:

J_{n}^{(i)} = J_{n−1}^{(i)} + 2J_{n−2}^{(i)} + ⋯ + J_{n−k}^{(i)},  (10)

with initial conditions for 1 − k ≤ n ≤ 0,

J_{n}^{(i)} = \begin{cases}1, & for n = 1 − i; \\ 0, & otherwise. \end{cases}

As before, we consider k sequences of shifted order-k Jacobsthal numbers (10) for n ≥ k and 1 ≤ i ≤ k, with initial conditions for 0 ≤ n ≤ k − 1,

J_{n}^{(i)} = \begin{cases}1, & for i = k − n; \\ 0, & otherwise. \end{cases}

Then, for n ≥ 1, we give the extension of these sequences (10) to negative indices as follows:

J_{−n}^{(i)} = −\frac{1}{2}J_{−n+1}^{(i)} + \frac{1}{2}J_{−n+2}^{(i)}, for k = 2, 1 ≤ i ≤ 2,  (11)
J_{−n}^{(i)} = −J_{−n+1}^{(i)} − ⋯ − J_{−n+k−3}^{(i)} − 2J_{−n+k−2}^{(i)} − J_{−n+k−1}^{(i)} + J_{−n+k}^{(i)}. for k ≥ 3  (12)

The next table gives the first terms of negatively subscripted order-k Jacobsthal sequences for n ≥ 1,

k = 2  k = 3  k = 4
i = 1 \frac{1}{2}, −\frac{1}{4}, \frac{3}{8}, −\frac{5}{16}, \frac{11}{32}, −\frac{21}{64}, \frac{43}{128}, −\frac{85}{256} … 1, −2, 3, −3, 1, 4, −12, 21, −26, 19 … 1, −1, −1, 2, 2, −6, −1, 13, −3 …
i = 2 −\frac{1}{2}, \frac{3}{4}, −\frac{5}{8}, \frac{11}{16}, −\frac{21}{32}, \frac{43}{64}, −\frac{85}{128}, \frac{171}{256} … −1, 3, −5, 6, −4, −3, 16, −33, 47 … −1, 2, 0, −3, 0, 8, −5, −14, 16, 25 …
i = 3  −2, 3, −3, 1, 4, −12, 21, −26, 19, 9 … −2, 1, 4, −4, −7, 12, 10, −31, −8 …
i = 4  −1, −1, 2, 2, −6, −1, 13, −3, −28 …

Table 3: First terms of negatively subscripted order-k Jacobsthal sequences

Remark 4. The sequences of k = 3 are known in the OEIS as \underline{A077990}, \underline{-A078064}, and \underline{A077990} respectively.

We now give some results on the n^{th} negatively subscripted generalized order-k Fibonacci number g_{−n}^{(i)} using matrix methods.

Theorem 5. For n ≥ 0 and 2 ≤ i ≤ k, we have

g_{−n−1}^{(i)} = −\frac{c_{i−1}}{c_{k}} g_{−n}^{(k)} + g_{−n}^{(i−1)},  (13)

and for i = 1,

g_{−n−1}^{(1)} = \frac{1}{c_{k}} g_{−n}^{(k)}.  (14)

Proof. For the proof, we use the matrix approach. The matrix approach was used, for example, by Kalman [4] and Er [3] to study generalized Fibonacci numbers. Let

A := (\begin{matrix}−\frac{c_{k−1}}{c_{k}} & −\frac{c_{k−2}}{c_{k}} & −\frac{c_{k−3}}{c_{k}} & ⋯ & −\frac{c_{1}}{c_{k}} & \frac{1}{c_{k}} \\ 1 & 0 & 0 & ⋯ & 0 & 0 \\ 0 & 1 & 0 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 1 & 0 \end{matrix} ) .

We have the following n order-k recurrence relations

( g_{−n−1}^{(i)} ; g_{−n}^{(i)} ; ⋮ ; g_{−n+k−2}^{(i)}) = A ( g_{−n}^{(i)} ; g_{−n+1}^{(i)} ; ⋮ ; g_{−n+k−1}^{(i)}) .  (15)

In order to deal with k sequences of negatively subscripted generalized order-k Fibonacci sequences at the same time, we construct a k × k square matrix G_{−n} as follows:

G_{−n} = (\begin{matrix}g_{−n}^{(k)} & g_{−n}^{(k−1)} & g_{−n}^{(k−2)} & ⋯ & g_{−n}^{(1)} \\ g_{−n+1}^{(k)} & g_{−n+1}^{(k−1)} & g_{−n+1}^{(k−2)} & ⋯ & g_{−n+1}^{(1)} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ g_{−n+k−1}^{(k)} & g_{−n+k−1}^{(k−1)} & g_{−n+k−1}^{(k−2)} & ⋯ & g_{−n}^{(1)} \end{matrix}) .

It is clear that, A = G_{−1}.

Next, (15) becomes

G_{−n−1} = AG_{−n}.

By induction, it is also clear that

G_{−n−1} = A^{n}A = G_{−n}A.

Finally, we have

G_{−n−1} = AG_{−n} = G_{−n}A.  (16)

Thus, Equations (13) and (14) are deduced from (16).

From Theorem 5, we get the following results:

Corollary 6. Let f_{−n}^{(i)} be the n^{th} negatively subscripted order-k Fibonacci number of the sequence number i. Then

f_{−n−1}^{(1)} = f_{−n}^{(k)};
f_{−n−1}^{(i)} = −f_{−n}^{(k)} + f_{−n}^{(i−1)}; 2 ≤ i ≤ k.

Corollary 7. Let P_{−n}^{(i)} be the n^{th} negatively subscripted order-k Pell number of the sequence number i. Then

P_{−n−1}^{(1)} = P_{−n}^{(k)};
P_{−n−1}^{(2)} = −2P_{−n}^{(k)} + P_{−n}^{(1)};
P_{−n−1}^{(i)} = −P_{−n}^{(k)} + P_{−n}^{(i−1)}; 3 ≤ i ≤ k.

Corollary 8. Let J_{−n}^{(i)} be the n^{th} negatively subscripted generalized order-k Jacobsthal number of the sequence number i. Then for k ≥ 3,

J_{−n−1}^{(1)} = J_{−n}^{(k)};
J_{−n−1}^{(2)} = −J_{−n}^{(k)} + J_{−n}^{(1)};
J_{−n−1}^{(3)} = −2J_{−n}^{(k)} + J_{−n}^{(2)};
J_{−n−1}^{(i)} = −J_{−n}^{(k)} + J_{−n}^{(i−1)}; 4 ≤ i ≤ k.

We conclude this section by defining a generalized order-k Fibonacci sequence (V_{n})_{n} with arbitrary initial conditions and we give the extension of the sequence (V_{n})_{n} to negative indices. Then we give the n^{th} negatively subscripted number V_{−n} as the sum of k terms of negatively subscripted generalized order-k Fibonacci numbers defined in (6).

For n ≥ k, let V_{n} be as follows:

V_{n} = c_{1}V_{n−1} + c_{2}V_{n−2} + ⋯ + c_{k}V_{n−k},

with integer initial conditions V_{0}, V_{1}, …, V_{k−1}, where c_{1}, c_{2}, …, c_{k} ∈ ℝ.

Belbachir and Bencherif [1] gave the explicit formula of the n^{th} term of the sequence (V_{n})_{n}.

Then for n ≥ 1, the value V_{−n} is as follows:

V_{−n} = −\frac{c_{k−1}}{c_{k}} V_{−n+1} − \frac{c_{k−2}}{c_{k}} V_{−n+2} − ⋯ − \frac{c_{1}}{c_{k}} V_{−n+k−1} + \frac{1}{c_{k}} V_{−n+k}.  (17)

Note that for (V_{0}, …, V_{k−i−1}, V_{k−i}, V_{k−i+1}, …, V_{k−1}) = (0, …, 0, 1, 0, …, 0), 1 ≤ i ≤ k, we have V_{n} = g_{n}^{(i)}.

The n^{th} term V_{−n} is given by

Theorem 9. For n ≥ 1,

V_{−n} = ∑_{i=0}^{k−1} a_{i}g_{−n}^{(k−i)},  (18)

where g_{−n}^{(j)} is the n^{th} negatively subscripted generalized order-k Fibonacci number of the sequence number i (6).

Proof. By induction on n.

For n = 1, V_{−1} = −\frac{c_{k−1}}{c_{k}} V_{0} − ⋯ − \frac{c_{1}}{c_{k}} V_{k−2} + \frac{1}{c_{k}} V_{k−1} = −\frac{c_{k−1}}{c_{k}} a_{0} − ⋯ − \frac{c_{1}}{c_{k}} a_{k−2} + \frac{1}{c_{k}} a_{k−1} = ∑_{i=0}^{k−1} a_{i}g_{−1}^{(k−i)}.

Now suppose that (18) is true for 2 ≤ j ≤ n and we prove the formula for n + 1:

V_{−n−1} = −\frac{c_{k−1}}{c_{k}} V_{−n} − \frac{c_{k−2}}{c_{k}} V_{−n+1} − ⋯ − \frac{c_{1}}{c_{k}} V_{−n+k−2} + \frac{1}{c_{k}} V_{−n+k−1}.

and

V_{−n−1} = −\frac{c_{k−1}}{c_{k}} ∑_{i=0}^{k−1} a_{i}g_{−n}^{(k−i)} − \frac{c_{k−2}}{c_{k}} ∑_{i=0}^{k−1} a_{i}g_{−n+1}^{(k−i)} − ⋯ − \frac{c_{1}}{c_{k}} ∑_{i=0}^{k−1} a_{i}g_{−n+k−2}^{(k−i)} + \frac{1}{c_{k}} ∑_{i=0}^{k−1} a_{i}g_{−n+k−1}^{(k−i)}

= a_{0} (−\frac{c_{k−1}}{c_{k}} g_{−n}^{(k)} − \frac{c_{k−2}}{c_{k}} g_{−n+1}^{(k)} − ⋯ − \frac{c_{1}}{c_{k}} g_{−n+k−2}^{(k)} + \frac{1}{c_{k}} g_{−n+k−1}^{(k)})

+ a_{1} (−\frac{c_{k−1}}{c_{k}} g_{−n}^{(k−1)} − \frac{c_{k−2}}{c_{k}} g_{−n+1}^{(k−1)} − ⋯ − \frac{c_{1}}{c_{k−1}} g_{−n+k−2}^{(k−1)} + \frac{1}{c_{k−1}} g_{−n+k−1}^{(k−1)})

+ ⋯ +

+ a_{k−1} (−\frac{c_{k−1}}{c_{k}} g_{−n}^{(1)} − \frac{c_{k−2}}{c_{k}} g_{−n+1}^{(1)} − ⋯ − \frac{c_{1}}{c_{k}} g_{−n+k−2}^{(1)} + \frac{1}{c_{k}} g_{−n+k−1}^{(1)})

= a_{0}g_{−n−1}^{(k)} + a_{1}g_{−n−1}^{(k−1)} + ⋯ + a_{k−1}g_{−n−1}^{(1)}

= ∑_{i=0}^{k−1} a_{i}g_{−n−1}^{(k−i)}.

Thus (18) is true for all n ≥ 1.

3 Representation of negatively subscripted generalized order-k Fibonacci numbers

In this section, we give a representation of the family of negatively subscripted generalized order-k Fibonacci numbers (6) using the permanent of Hessenberg matrices.

We introduce the n × n matrix W_{n} = (w_{st}) with w_{1t} = 0, for 1 ≤ t ≤ n and for all 1 < i ≤ n,

w_{st} = \begin{cases}1, & if s = t + 1; \\ −\frac{c_{k−(t−s)−1}}{c_{k}} , & if 0 ≤ t − s ≤ k − 2; \\ \frac{1}{c_{k}} , & if s = t − k + 1; \\ 0, & elsewhere. \end{cases}

And we construct, for n ≥ 1, the n × n matrix A_{n}^{i}, for 1 ≤ i ≤ k, as follows:

A_{n}^{i} = W_{n} + ∑_{t=1}^{n} (\frac{δ_{i,k}^{t}(k)}{c_{k}} − ∑_{j=1}^{k−1} δ_{i,j}^{t}(k)\frac{c_{k−j}}{c_{k}} ) E_{1t}

with δ_{a,b}^{c}(d) defined for 1 ≤ a, b, c ≤ d as

δ_{a,b}^{c}(d) = \begin{cases}1, & if a + b = c + d; \\ 0, & otherwise. \end{cases}  (19)

And E_{st} denotes the n × n matrix with 1 in position (s, t) and 0 elsewhere.

Then A_{n}^{i} is as follows:

A_{n}^{i} = (\begin{matrix}A_{1} & A_{2} & A_{3} & ⋯ & A_{k} & 0 & 0 & ⋯ & 0 \\ 1 & −\frac{c_{k−1}}{c_{k}} & −\frac{c_{k−2}}{c_{k}} & ⋯ & −\frac{c_{1}}{c_{k}} & \frac{1}{c_{k}} & 0 & ⋯ & 0 \\ 0 & 1 & −\frac{c_{k−1}}{c_{k}} & ⋯ & −\frac{c_{2}}{c_{k}} & −\frac{c_{1}}{c_{k}} & \frac{1}{c_{k}} & ... & ⋮ \\ & & & & & & & ... & 0 \\ ⋮ & & & & & & & ... & \frac{1}{c_{k}} \\ & & & & & & & ... & −\frac{c_{1}}{c_{k}} \\ & & & & & & & ... & ⋮ \\ 0 & ⋯ & & & & ⋯ & 0 & 1 & −\frac{c_{k−1}}{c_{k}} \end{matrix} ) ,  (20)

where A_{t} = \frac{δ_{i,k}^{t}(k)}{c_{k}} − ∑_{j=1}^{k−1} δ_{i,j}^{t}(k)\frac{c_{k−j}}{c_{k}}, for 1 ≤ t ≤ k.

We now give the representation of negatively subscripted generalized order-k Fibonacci numbers.

Theorem 10. For n ≥ 1, let A_{n}^{i} be as in (20) and g_{−n}^{(i)} be the n^{th} negatively subscripted generalized order-k Fibonacci number of the sequence number i, then

per A_{n}^{i} = g_{−n}^{(i)}.  (21)

For instance, we give the following representations of k sequences of negatively subscripted order-k Fibonacci, order-k Pell, and order-k Jacobsthal numbers.

Let F_{n}^{i} be the n × n matrix defined, for 1 ≤ i ≤ k, as follows:

F_{n}^{i} = (\begin{matrix}δ_{i,k}^{1}(k) − ∑_{j=1}^{k−1} δ_{i,j}^{1}(k) & δ_{i,k}^{2}(k) − ∑_{j=1}^{k−1} δ_{i,j}^{2}(k) & δ_{i,k}^{3}(k) − ∑_{j=1}^{k−1} δ_{i,j}^{3}(k) & ⋯ & δ_{i,k}^{k} − ∑_{j=1}^{k−1} δ_{i,j}^{k}(k) & 0 & 0 & ⋯ & 0 \\ 1 & −1 & −1 & ⋯ & −1 & 1 & 0 & ⋯ & 0 \\ 0 & 1 & −1 & ⋯ & −1 & −1 & 1 & ... & ⋮ \\ & & & & & & & ... & 0 \\ ⋮ & & & & & & & ... & 1 \\ & & & & & & & ... & −1 \\ & & & & & & & ... & ⋮ \\ 0 & ⋯ & & & & ⋯ & 0 & 1 & −1 \end{matrix}) . (22)

where δ_{i,k}^{t}(k) and δ_{i,j}^{t}(k) is defined as in (19) for all 1 ≤ t ≤ k and 1 ≤ j ≤ k − 1.

Corollary 11. For n ≥ 1, let F_{n}^{i} be as in (22) and f_{−n}^{(i)} be the n^{th} negatively subscripted order-k Fibonacci number of the sequence number i, then

per F_{n}^{i} = f_{−n}^{(i)}.  (23)

Let P_{n}^{i} be the n × n matrix defined for 1 ≤ i ≤ k in the following way:

P_{n}^{i} = (\begin{matrix}S_{1} & S_{2} & ⋯ & S_{k−1} & S_{k} & 0 & 0 & ⋯ & 0 \\ 1 & −1 & ⋯ & −1 & −2 & 1 & 0 & ⋯ & 0 \\ 0 & 1 & −1 & ⋯ & −1 & −2 & 1 & ... & ⋮ \\ & & & & & & & ... & 0 \\ ⋮ & & & & & & & ... & 1 \\ & & & & & & & ... & −2 \\ & & & & & & & ... & ⋮ \\ 0 & ⋯ & & & & ⋯ & 0 & 1 & −1 \end{matrix}) ,  (24)

where S_{t} = δ_{i,k}^{t} − 2δ_{i,k−1}^{t} − ∑_{j=1}^{k−2} δ_{i,j}^{t} for 1 ≤ t ≤ k and δ_{i,j}^{t}(k) is defined as in (19).

Corollary 12. For n ≥ 1, let P_{n}^{i} be as in (24) and P_{−n}^{(i)} be the n^{th} negatively subscripted order-k Pell number of the sequence number i, then

per P_{n}^{i} = P_{−n}^{(i)}.  (25)

Let J_{n}^{i} be the n × n matrix defined for 1 ≤ i ≤ k and k ≥ 3 as follows:

J_{n}^{i} = (\begin{matrix}T_{1} & T_{2} & T_{3} & ⋯ & T_{k−2} & T_{k−1} & T_{k} & 0 & 0 & ⋯ & 0 \\ 1 & −1 & −1 & ⋯ & −1 & −2 & −1 & 1 & 0 & ⋯ & 0 \\ 0 & 1 & −1 & ⋯ & −1 & −1 & −2 & −1 & 1 & ... & ⋮ \\ & & & & & & & & & ... & 0 \\ ⋮ & & & & & & & & & ... & 1 \\ & & & & & & & & & ... & −1 \\ & & & & & & & & & ... & −2 \\ & & & & & & & & & ... & −1 \\ & & & & & & & & & ... & ⋮ \\ 0 & ⋯ & & & & & & ⋯ & 0 & 1 & −1 \end{matrix}) ,  (26)

where T_{t} = δ_{i,k}^{t} − 2δ_{i,k−2}^{t} − δ_{i,k−1}^{t} − ∑_{j=1}^{k−3} δ_{i,j}^{t} for 1 ≤ t ≤ k and δ_{i,j}^{t}(k) is defined as in (19).

Corollary 13. For n ≥ 1, let J_{n}^{i} be as in (26) and J_{−n}^{(i)} be the n^{th} negatively subscripted order-k Jacobsthal number of the sequence number i, then

per J_{n}^{i} = J_{−n}^{(i)}.  (27)

4 More permanental representations of negatively subscripted order-k Fibonacci and order-k Lucas numbers

In this section, we give numerous types of matrices whose permanent are negatively subscripted order-k Fibonacci and order-k Lucas terms.

We first establish two kinds of permanental representations of the negatively subscripted order-k Fibonacci sequence (g̃_{−n})_{n}. We introduce an n × n (0, 1, −1)-matrix B_{(n,k)} defined by

b_{ij} = \begin{cases}1, & for j − i = −1 or k − 1; \\ −1, & for 0 ≤ j − i ≤ k − 2; \\ 0, & elsewhere. \end{cases}  (⋆)

And we construct for n > k, the n × n (0, 1, −1)-matrices F_{(n,k)} and F̃_{(n,k)} as follows:

F_{(n,k)} = B_{(n,k)} + 2E_{11} + k−1 ; ∑_{j=2}E_{1j} − E_{1k},

F̃_{(n,k)} = B_{(n,k)} + 2 ∑_{j=1}^{k−1} E_{1j},

where E_{ij} denotes the n×n matrix with 1 in position (i, j) and 0 elsewhere. F_{(n,k)} and F̃_{(n,k)} correspond to

F_{(n,k)} = (\begin{matrix}1 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 0 \\ 1 & −1 & ⋯ & −1 & 1 & 0 & ⋯ & 0 \\ & ... & ... & & ... & ... & ... & ⋮ \\ & & & & & & ... & 0 \\ & & & & & & ... & 1 \\ & & & & & & & −1 \\ ⋮ & & & & & ... & ... & ⋮ \\ 0 & & & & & & 1 & −1 \end{matrix})

and

F̃_{(n,k)} = (\begin{matrix}1 & 1 & ⋯ & 1 & 0 & 0 & ⋯ & 0 \\ 1 & −1 & ⋯ & −1 & 1 & 0 & ⋯ & 0 \\ & ... & ... & & ... & ... & ... & ⋮ \\ & & & & & & ... & 0 \\ & & & & & & ... & 1 \\ & & & & & & & −1 \\ ⋮ & & & & & ... & ... & ⋮ \\ 0 & & & & & & 1 & −1 \end{matrix}) .

Then we give the two permanental representations of the negatively subscripted order-k Fibonacci sequence.

Theorem 14. For n > k, we have

per F_{(n,k)} = g̃_{−n}^{(k)}  (28)

and

per F̃_{(n,k)} = g̃_{−n+k}^{(k)}.  (29)

Next, using the same approach given in Theorem 14, see next section, we give a representation of l_{−n+1}^{(k)}.

We use the n × n square matrix B_{(n,k)} = (b_{ij}) given by (⋆), and we construct for n > k, the n × n matrix A_{(n,k)} as follows:

A_{(n,k)} = B_{(n,k)} + 2E_{11} + k−1 ; ∑_{j=2}E_{1j} − E_{1k} + E_{1,k+1},

where E_{ij} is the n × n matrix with 1 in position (i, j) and 0 elsewhere.

The matrix A_{(n,k)} corresponds to

A_{(n,k)} = (\begin{matrix}1 & 0 & ⋯ & 0 & 0 & 1 & 0 & ⋯ & 0 \\ 1 & −1 & ⋯ & −1 & −1 & 1 & 0 & ... & ⋮ \\ & ... & ... & & ... & −1 & & & 0 \\ & & & ... & & ... & ... & ... & ⋮ \\ & & & & & & & & 1 \\ & & & & & & & & −1 \\ & & & & & & & ... & ⋮ \\ & & & & & & ... & ... & ⋮ \\ 0 & & ⋯ & & & 0 & & 1 & −1 \end{matrix}) .

Theorem 15. For n > k, we have

per A_{(n,k)} = l_{−n+1}^{(k)}.

Proof. The proof is the same as Theorem 14, see next section.

Finally, let B_{n} be an n × n matrix defined by

B_{n} = T_{n} + 2(E_{11} + E_{22} + E_{33} − E_{43}) + E_{13} − E_{23} + E_{24} − E_{34},

where T_{n} is the n × n (0, 1, −1)-matrix such that t_{ii} = −1, t_{ij} = 1 if and only if |j − i| = 1.

The matrix B_{n} corresponds to

B_{n} = (\begin{matrix}1 & 1 & 1 & 0 & 0 & ⋯ & & 0 \\ 1 & 1 & 0 & 1 & 0 & & & ⋮ \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & −1 & −1 & 1 & 0 \\ 0 & 0 & 0 & 1 & −1 & 1 & ... & ⋮ \\ ⋮ & & & & ... & ... & ... & 0 \\ & & & & ... & ... & ... & 1 \\ 0 & ⋯ & & & & 0 & 1 & −1 \end{matrix}) .

Then we obtain the following result. Theorem 16. For n ≥ 4, we have

per B_{n} = l_{−n+1}^{(2)}.

5 Proofs

We start this section by giving the proof of Theorem 10, Proof. We have

\frac{δ_{i,k}^{1}}{c_{k}} − ∑_{t=1}^{k−1} δ_{i,t}^{1} \frac{c_{k−t}}{c_{k}} = \begin{cases}\frac{1}{c_{k}} , & for i = 1; \\ −\frac{c_{i−1}}{c_{k}} , & for 2 ≤ i ≤ k. \end{cases}

On the other hand by Theorem 5, we have

g_{−1}^{(i)} = \begin{cases}\frac{1}{c_{k}} , & for i = 1; \\ −\frac{c_{i−1}}{c_{k}} , & for 2 ≤ i ≤ k. \end{cases}

Thus,

\frac{δ_{i,k}^{1}}{c_{k}} − ∑_{t=1}^{k−1} δ_{i,t}^{1} \frac{c_{k−t}}{c_{k}} = g_{−1}^{(i)}.

Next for 2 ≤ j ≤ k−1, by the definition of shifted generalized order-k Fibonacci sequences (1), we have

\frac{δ_{i,k}^{j}}{c_{k}} − ∑_{t=1}^{k−1} δ_{i,t}^{j} \frac{c_{k−t}}{c_{k}} = \begin{cases}0, & for 1 ≤ i ≤ j − 1; \\ \frac{1}{c_{k}} g_{k−j}^{(i)}, & for i = j; \\ −\frac{c_{i−1}}{c_{k}} g_{k−i}^{(i)}, & for j + 1 ≤ i ≤ k. \end{cases}

Then \frac{δ_{i,k}^{j}}{c_{k}} − ∑_{t=1}^{k−1} δ_{i,t}^{j} \frac{c_{k−t}}{c_{k}} can be written as

\frac{δ_{i,k}^{j}}{c_{k}} − ∑_{t=1}^{k−1} δ_{i,t}^{j} \frac{c_{k−t}}{c_{k}} = \frac{1}{c_{k}} g_{k−j}^{(i)} − ∑_{t=j}^{k−1} \frac{c_{k−t}}{c_{k}} g_{t−j}^{(i)}.

Finally,

\frac{δ_{i,k}^{k}}{c_{k}} − ∑_{t=1}^{k−1} δ_{i,t}^{k} \frac{c_{k−t}}{c_{k}} = \begin{cases}\frac{1}{c_{k}} g_{0}^{(k)}, & for i = k; \\ 0, & otherwise. \end{cases}

Then for 1 ≤ i ≤ k, we have

\frac{δ_{i,k}^{k}}{c_{k}} − ∑_{t=1}^{k−1} δ_{i,t}^{k} \frac{c_{k−t}}{c_{k}} = \frac{1}{c_{k}} g_{0}^{(i)}.

Hence, the matrix A_{n}^{i} can be written as follows:

A_{n}^{i} = (\begin{matrix}g_{−1}^{(i)} & \frac{1}{c_{k}} g_{k−2}^{(i)} − ∑_{t=2}^{k−1} \frac{c_{k−t}}{c_{k}} g_{t−2}^{(i)} & \frac{1}{c_{k}} g_{k−3}^{(i)} − ∑_{t=3}^{k−1} \frac{c_{k−t}}{c_{k}} g_{t−3}^{(i)} & ⋯ & \frac{1}{c_{k}} g_{0}^{(i)} & 0 & 0 & ⋯ & 0 \\ 1 & −\frac{c_{k−1}}{c_{k}} & −\frac{c_{k−2}}{c_{k}} & ⋯ & −\frac{c_{1}}{c_{k}} & \frac{1}{c_{k}} & 0 & ⋯ & 0 \\ 0 & 1 & −\frac{c_{k−1}}{c_{k}} & ⋯ & −\frac{c_{2}}{c_{k}} & −\frac{c_{1}}{c_{k}} & \frac{1}{c_{k}} & ... & ⋮ \\ & & & & & & & ... & 0 \\ ⋮ & & & & & & & ... & \frac{1}{c_{k}} \\ & & & & & & & ... & −\frac{c_{1}}{c_{k}} \\ & & & & & & & ... & ⋮ \\ 0 & ⋯ & & & & ⋯ & 0 & 1 & −\frac{c_{k−1}}{c_{k}} \end{matrix} ) .

By Lemma 1, the matrix A_{n}^{i} is contractible on column 1 relative to rows 1 and 2. Let (A_{n}^{i})^{1} be the (n−1)×(n−1) contraction matrix, then we have per A_{n}^{i} = per(A_{n}^{i})^{1} and (A_{n}^{i})^{1} is as follows:

(A_{n}^{i})^{1} = (\begin{matrix}g_{−2}^{(i)} & \frac{1}{c_{k}} g_{k−3}^{(i)} − ∑_{t=2}^{k−1} \frac{c_{k−t}}{c_{k}} g_{t−3}^{(i)} & \frac{1}{c_{k}} g_{k−4}^{(i)} − ∑_{t=3}^{k−1} \frac{c_{k−t}}{c_{k}} g_{t−4}^{(i)} & ⋯ & \frac{1}{c_{k}} g_{−1}^{(i)} & 0 & 0 & ⋯ & 0 \\ 1 & −\frac{c_{k−1}}{c_{k}} & −\frac{c_{k−2}}{c_{k}} & ⋯ & −\frac{c_{1}}{c_{k}} & \frac{1}{c_{k}} & 0 & ⋯ & 0 \\ 0 & 1 & −\frac{c_{k−1}}{c_{k}} & ⋯ & −\frac{c_{2}}{c_{k}} & −\frac{c_{1}}{c_{k}} & \frac{1}{c_{k}} & ... & ⋮ \\ & & & & & & & ... & 0 \\ ⋮ & & & & & & & ... & \frac{1}{c_{k}} \\ & & & & & & & ... & −\frac{c_{1}}{c_{k}} \\ & & & & & & & ... & ⋮ \\ 0 & ⋯ & & & & ⋯ & 0 & 1 & −\frac{c_{k−1}}{c_{k}} \end{matrix} ) .

Furthermore, the matrix (A_{n}^{i})^{1} is also contractible on column 1 relative to rows 1 and 2. Continuing the same contraction process we get by Lemma 1,

per A_{n}^{i} = per(A_{n}^{i})^{p}

with (A_{n}^{i})^{p} defined for p ≤ n − k by

(A_{n}^{i})^{p} = (\begin{matrix}g_{−p−1}^{(i)} & \frac{1}{c_{k}} g_{−p+k−2}^{(i)} − ∑_{t=2}^{k−1} \frac{c_{k−t}}{c_{k}} g_{−p+t−2}^{(i)} & ⋯ & \frac{1}{c_{k}} g_{−p+1}^{(i)} − \frac{c_{1}}{c_{k}} g_{−p}^{(i)} & \frac{1}{c_{k}} g_{−p}^{(i)} & 0 & 0 & ⋯ & 0 \\ 1 & −\frac{c_{k−1}}{c_{k}} & ⋯ & −\frac{c_{2}}{c_{k}} & −\frac{c_{1}}{c_{k}} & \frac{1}{c_{k}} & 0 & ⋯ & 0 \\ 0 & 1 & ⋯ & −\frac{c_{3}}{c_{k}} & −\frac{c_{2}}{c_{k}} & −\frac{c_{1}}{c_{k}} & \frac{1}{c_{k}} & ... & ⋮ \\ & & & & & & & ... & 0 \\ ⋮ & & & & & & & ... & \frac{1}{c_{k}} \\ & & & & & & & ... & −\frac{c_{1}}{c_{k}} \\ & & & & & & & ... & ⋮ \\ 0 & ⋯ & & & ⋯ & 0 & 0 & 1 & −\frac{c_{k−1}}{c_{k}} \end{matrix} ) .

And for p ≥ n − k + 1, (A_{n}^{i})^{p} is defined as follows:

(A_{n}^{i})^{p} = (\begin{matrix}g_{−p−1}^{(i)} & \frac{1}{c_{k}} g_{−p+k−2}^{(i)} − ∑_{t=2}^{k−1} \frac{c_{k−t}}{c_{k}} g_{−p+t−2}^{(i)} & ⋯ & \frac{1}{c_{k}} g_{−n+k+1}^{(i)} − ∑_{t=n−p+1}^{k−1} \frac{c_{k−t}}{c_{k}} g_{−n+t+1}^{(i)} & \frac{1}{c_{k}} g_{−n+k}^{(i)} − ∑_{t=n−p}^{k−1} \frac{c_{k−t}}{c_{k}} g_{−n+t}^{(i)} \\ 1 & −\frac{c_{k−1}}{c_{k}} & ⋯ & −\frac{c_{k−n+p+2}}{c_{k}} & −\frac{c_{k−n+p+1}}{c_{k}} \\ 0 & 1 & ⋯ & −\frac{c_{k−n+p+3}}{c_{k}} & −\frac{c_{k−n+p+2}}{c_{k}} \\ ⋮ & & & & ⋮ \\ 0 & ⋯ & 0 & 1 & −\frac{c_{k−1}}{c_{k}} \end{matrix}) .

Then

(A_{n}^{i})^{n−2} = (\begin{matrix}g_{−n+1}^{(i)} & \frac{1}{c_{k}} g_{−n+k}^{(i)} − ∑_{t=2}^{k−1} \frac{c_{k−t}}{c_{k}} g_{−n+t}^{(i)} \\ 1 & −\frac{c_{k−1}}{c_{k}} \end{matrix}) .

By Lemma 1, we have

per A_{n}^{i} = per(A_{n}^{i})^{n−2} = −\frac{c_{k−1}}{c_{k}} g_{−n+1}^{(i)} + \frac{1}{c_{k}} g_{−n+k}^{(i)} − ∑_{t=2}^{k−1} \frac{c_{k−t}}{c_{k}} g_{−n+t}^{(i)}

= \frac{1}{c_{k}} g_{−n+k}^{(i)} − ∑_{t=1}^{k−1} \frac{c_{k−t}}{c_{k}} g_{−n+t}^{(i)}

= g_{−n}^{(i)}.

So per A_{n}^{i} = g_{−n}^{(i)} and the proof is complete.

Secondly, we provide the proof of Theorem 14, Proof. Let F_{(n,k)}^{p} = (f_{ij}^{p}) be the p^{th} contraction of F_{(n,k)}, 1 ≤ p ≤ n − 2.

The matrix F_{(n,k)} = (f_{ij}), can be contracted on column 1 relative to rows 1 and 2.

We can easily verify that if p = 1,

f_{11}^{1} = f_{12}^{1} = ⋯ = f_{1k−1}^{1} = −1, f_{1k}^{1} = 1 and f_{1q}^{1} = 0, for q ≥ k + 1; and for all i = 2, …, n − 1,

\begin{cases}f_{i,i−1} = 1, \\ f_{ij} = −1, & for 0 ≤ j − i ≤ k − 2; \\ f_{ij} = 1 & for j − i = k − 1. \end{cases}

Hence

F_{(n,k)}^{1} = (\begin{matrix}−1 & ⋯ & −1 & 1 & 0 & ⋯ & 0 \\ 1 & −1 & ⋯ & −1 & 1 & ... & ⋮ \\ & & & & ... & ... & 0 \\ & & & & & ... & 1 \\ ⋮ & & & & & & −1 \\ & & & & ... & ... & ⋮ \\ 0 & & ⋯ & & & 1 & −1 \end{matrix})

and

F_{(n,k)}^{1} = (\begin{matrix}g̃_{−2}^{(k)} & g̃_{k−3}^{(k)} − ∑_{j=−1}^{k−4} g̃_{j}^{(k)} & g̃_{k−4}^{(k)} − ∑_{j=−1}^{k−5} g̃_{j}^{(k)} & ⋯ & −g̃_{−1}^{(k)} + g̃_{0}^{(k)} & g̃_{−1}^{(k)} & 0 & ⋯ & 0 \\ 1 & −1 & −1 & ⋯ & & −1 & 1 & ... & ⋮ \\ 0 & 1 & −1 & ⋯ & & & −1 & ... & 0 \\ & & & & & & & ... & 1 \\ & & & & & & & & −1 \\ & & & & & & ... & ... & ⋮ \\ 0 & & & ⋯ & & & 0 & 1 & −1 \end{matrix}) .

Furthermore, the matrix F_{(n,k)}^{1} can be contracted. From Lemma 1 we obtain

per F_{(n,k)} = per F_{(n,k)}^{p}

with F_{(n,k)}^{p} defined for p ≤ n − k by

F_{(n,k)}^{p} = (\begin{matrix}g̃_{−p−1}^{(k)} & g̃_{−p+k−2}^{(k)} − ∑_{j=0}^{k−3} g̃_{−p+j}^{(k)} & ⋯ & −g̃_{−p}^{(k)} + g̃_{−p+1}^{(k)} & g̃_{−p}^{(k)} & 0 & ⋯ & 0 \\ 1 & −1 & ⋯ & ⋯ & −1 & 1 & ... & ⋮ \\ & & & & & ... & ... & 0 \\ & & & & & & ... & 1 \\ & & & & & & & −1 \\ & & & & & ... & ... & ⋮ \\ 0 & & ⋯ & & & 0 & 1 & −1 \end{matrix}) .

And for p ≥ n − k + 1, F_{(n,k)}^{p} is defined as

F_{(n,k)}^{p} = (\begin{matrix}g̃_{−p−1}^{(k)} & g̃_{−p+k−2}^{(k)} − ∑_{j=0}^{k−3} g̃_{−p+j}^{(k)} & ⋯ & g̃_{k−n+1}^{(k)} − ∑_{j=0}^{k−(n−p)} g̃_{−p+j}^{(k)} & g̃_{k−n}^{(k)} − ∑_{j=0}^{k−(n−p+1)} g̃_{−p+j}^{(k)} \\ 1 & −1 & ⋯ & ⋯ & −1 \\ 0 & 1 & ⋯ & & −1 \\ .. & & & & ⋮ \\ 0 & & ⋯ & 1 & −1 \end{matrix}) .

So we have

F_{(n,k)}^{n−2} = (\begin{matrix}g̃_{−n+1}^{(k)} & g̃_{−n+k}^{(k)} − ∑_{j=0}^{k−3} g̃_{−n+2+j}^{(k)} \\ 1 & −1 \end{matrix}) .

Lemma 1 gives

per F_{(n,k)} = per (\begin{matrix}g̃_{−n+1}^{(k)} & g̃_{−n+k}^{(k)} − ∑_{j=0}^{k−3} g̃_{−n+2+j}^{(k)} \\ 1 & −1 \end{matrix})
= −g̃_{−n+1}^{(k)} + g̃_{−n+k}^{(k)} − ∑_{j=0}^{k−3} g̃_{−n+2+j}^{(k)}
= g̃_{−n+k}^{(k)} − (g̃_{−n+1}^{(k)} + g̃_{−n+2}^{(k)} + ⋯ + g̃_{−n+k−1}^{(k)}) .

So per F_{(n,k)} = g̃_{−n}^{(k)} and the proof of Identity (28) is complete.

By Lemma 1, we can write

per F̃_{(n,k)} = per F̃_{(n,k)}^{1},  (30)

where F̃_{(n,k)}^{1} is the first contraction of F̃_{(n,k)}.

Then f̃_{11}^{1} = f̃_{12}^{1} = ⋯ = f̃_{1k−1}^{1} = 0, f̃_{1k}^{1} = 1 and f̃_{1q}^{1} = 0 (q ≥ k+1); and for i = 2, …, n−1, f̃_{i,i−1}^{1} = 1, f̃_{ij}^{1} = −1 for (0 ≤ j − i ≤ k − 2) and f̃_{ij}^{1} = 1 for (j − i = k − 1).

That is,

per F̃_{(n,k)}^{1} = per (0 0 ⋯ 1 0 ⋯ 0 ; 1 −1 ⋯ −1 1 ... ⋮ ; 0 1  ... ... 0 ; ... 1 ; −1 ; ⋮ ; 0  ⋯  0 1 −1)_{n−1} .

Computing per F̃_{(n,k)}^{1} by the Laplace expansion with respect to the first column, we obtain

per F̃_{(n,k)}^{1} = per (\begin{matrix}1 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 1 & −1 & ⋯ & −1 & 1 & ... & ⋮ \\ & & & & ... & ... & 0 \\ & & & & & ... & 1 \\ & & & & & & −1 \\ & & & & ... & ... & ⋮ \\ & & ⋯ & & & 1 & −1 \end{matrix})_{n−k} .

From identity (28), per F̃_{(n,k)}^{1} = per F_{(n−k,k)} = g̃_{−(n−k)}^{(k)}, and from (30), we have, per F̃_{(n,k)} = g̃_{−n+k}^{(k)}. The proof is complete. We conclude this section with the proof of Theorem 16.

Proof. If n = 4,

per B_{4} = per (\begin{matrix}1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & −1 & −1 \end{matrix}) = −4 = l_{−3}^{(2)}.

By induction on n, we assume that per B_{n} = l_{−n+1}^{(2)} and we establish that per B_{n+1} = l_{−n}^{(2)}. Let

F = (0 ⋮ 0 1) .

Then

B_{n+1} = (\begin{matrix}B_{n} & F \\ F^{t} & −1 \end{matrix}) .

Let B_{n}^{(p)} be the p^{th} contraction of B_{n}. Since

B_{n}^{(n−2)} = (\begin{matrix}l_{−n+2}^{(2)} & l_{−n+3}^{(2)} \\ 1 & −1 \end{matrix}) ,

we get

per B_{n+1} = per B_{n+1}^{(n−2)} = per (\begin{matrix}l_{−n+2}^{(2)} & l_{−n+3}^{(2)} & 0 \\ 1 & −1 & 1 \\ 0 & 1 & −1 \end{matrix}) = l_{−n+2}^{(2)}−l_{−n+3}^{(2)}+l_{−n+2}^{(2)} = l_{−n+2}^{(2)}−l_{−n+1}^{(2)} = l_{−n}^{(2)}.

The proof is completed.

6 Acknowledgments

The authors express their gratitude to the reviewer and the editor for the helpful remarks and recommendations which improved the quality of the paper. This work is supported partially by DGRSDT Grant number C0656701.

References

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

[2] R. A. Brualdi and P. M. Gibson, Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function, J. Combin. Theory Ser. A 22 (1977), 194–230.

[3] M. C. Er, Sums of Fibonacci numbers by matrix methods, Fibonacci Quart. 22 (1984), 204–207.

[4] D. Kalman, Generalized Fibonacci numbers by matrix methods, Fibonacci Quart. 20 (1982), 73–76.

[5] E. Kiliç and D. Taşci, The generalized Binet formula, representation and sums of the generalized order-k Pell numbers, Taiwanese J. Math. 10 (2006), 1661–1670.

[6] G. Y. Lee and S. G. Lee, A note on generalized Fibonacci numbers, Fibonacci Quart. 33 (1995), 273–278.

[7] G. Y. Lee, S. G. Lee, and H. G. Shin, On the k-generalized Fibonacci matrix {Q}_{k}, Linear Algebra Appl. 251 (1997), 73–88.

[8] G. Y. Lee, k-Lucas numbers and associated bipartite graphs, Linear Algebra Appl. 320 (2000), 51–61.

[9] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, https://oeis. org, 2022.

[10] F. Yilmaz and D. Bozkurt, The generalized order-k Jacobsthal numbers, Int. J. Contemp. Math. Sci. 4 (2009), 1685–1694.

[11] F. Yilmaz and D. Bozkurt, On the Fibonacci and Lucas numbers, their sums and permanents of one type of Hessenberg matrices, Hacet. J. Math. Stat. 43 (2014), 1001– 1007.

2020 Mathematics Subject Classification: Primary 15A15; Secondary 11B39, 11B37, 05A05. Keywords: permanent, Fibonacci number, Lucas number, Pell number, Jacobsthal number, order-k Fibonacci number, negatively subscripted Fibonacci number, Hessenberg matrix.

(Concerned with sequences \underline{A077990}, \underline{A078021}, \underline{A078064}, \underline{A215936}, and \underline{A276229}.)

Received December 20 2021; revised versions received December 22 2021; June 16 2022; June 19 2022. Published in Journal of Integer Sequences, June 22 2022.

Return to Journal of Integer Sequences home page.