Determinants and Recurrence Sequences

Milan Janjić Department of Mathematics and Informatics University of Banja Luka Republic of Srpska Bosnia and Herzegovina

                        agnus@blic.net

Abstract

We examine relationships between two minors of order n of some matrices of n rows and n + r columns. This is done through a class of determinants, here called n-determinants, the investigation of which is our objective.

As a consequence of our main result we obtain a generalization of theorem of the product of two determinants.

We show the upper Hessenberg determinants, with −1 on the subdiagonal, belong to our class. Using such determinants allow us to represent terms of various recurrence sequences in the form of determinants. We illustrate this with several examples. In particular, we state a few determinants, each of which equals a Fibonacci number.

Also, several relationships among terms of sequences defined by the same recurrence equation are derived.

1 Introduction

In the second section of this paper we define n-determinants and derive a relationship between n-determinants and recurrence sequences. We apply the result on a particular kind of ndeterminants to obtain an extension of the theorem of the product of two determinants.

In Section 3 we consider 1-determinants, which appear to be the upper Hessenberg determinants. Some important mathematical objects may be represented as 1-determinants. This is found to be the case for the Catalan numbers, the Bell numbers, the Fibonacci numbers, the Fibonacci polynomials, the generalized Fibonacci numbers, the Tchebychev polynomials of both kinds, the continuants, the derangements, the factorials and the terms of any homogenous linear recurrence equation. We also find several 1-determinants, each of which equals a Fibonacci number.

The case n = 2 is examined in Section 4. We show that, in a particular case, 2determinants produce relationships between two sequences given by the same recurrence equation, with possibly different initial conditions. In this sense, we prove a formula for the Fibonacci polynomials from which several well-known formulas follow. For example, this is the case with the Ocagne’s formula and the index reduction formula. Analogous formulas for the Tchebychev polynomials are then stated. Also, we derive a result for the continuants, generalizing the fundamental theorem of convergents. Another result generalizes the standard recurrence equation for the derangements.

In Section 5, we consider 3-determinants which connect terms of three sequences given by the same recurrence equation.

The obtained results are concerned with several sequences from [5].

2 n-determinants

In this section we define n-determinants and give its relationships with recurrence sequences. We also consider a particular class of n-determinants which leads to a generalization of the theorem of the product of determinants. Note that entries of the considered matrices may belong to arbitrary commutative ring.

Let n and r be positive integers. We consider the following n + r − 1 by r matrix

P = (\begin{matrix}p_{1,1} & p_{1,2} & ⋯ & p_{1,r−1} & p_{1,r} \\ p_{2,1} & p_{2,2} & ⋯ & p_{2,r−1} & p_{2,r} \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ \\ p_{n,1} & p_{n,2} & ⋯ & p_{n,r−1} & p_{n,r} \\ −1 & p_{n+1,2} & ⋯ & p_{n+1,r−1} & p_{n+1,r} \\ 0 & −1 & ⋯ & p_{n+2,r−1} & p_{n+2,r} \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ \\ 0 & 0 & ⋯ & p_{n+r−2,r−1} & p_{n+r−2,r} \\ 0 & 0 & ⋯ & −1 & p_{n+r−1,r} \end{matrix}) .  (1)

Note that entries (n + i, i), (i = 1, …, r − 1) in P equal −1.

Definition 1. If Q is a submatrix of order r of P, we say that det Q is an n-determinant.

We connect matrix (1) with a recursively given sequence of vector-columns in the following way: Let A be a square matrix of order n. We define a block matrix A_{r} = [A|A_{n+1}| ⋯ |A_{n+r}] of n rows and n + r columns (where A_{n+j}, (j = 1, 2, …, r) are vector -columns) as follows:

A_{n+j} = ∑_{i=1}^{n+j−1} p_{i,j}A_{i}, (j = 1, 2, …, r).  (2)

We shall establish a relationship of n-determinants and minors of order n of A_{r}.

For a sequence 1 ≤ j_{1} < j_{2} < ⋯ < j_{r} < n + r of positive integers, we let M = M(ĵ_{1}, ĵ_{2}, …, ĵ_{r}) denote the minor of A_{r} of order n, obtained by deleting columns j_{1}, j_{2}, …, j_{r} of A_{r}. We shall also write M(ĵ_{1}, …, ĵ_{r}, A_{i_{1}}, A_{i_{2}}, …, A_{i_{k}}) if we want to stress that M contains i_{1}, i_{2}, …, i_{k} columns of A_{r}.

Note that the last column of A_{r} cannot be deleted.

The sign σ(M) of M is defined as

σ(M) = (−1)^{nr+j_{1}+j_{2}+···+j_{r}+ \frac{(r−1)r}{2}} .

We let Q = Q(j_{1}, …, j_{r}) denote the submatrix of order r, laying in j_{1}, j_{2}, …, j_{r} rows of P. Hence, det Q is an n-determinant.

We now prove the following result.

Theorem 2. Let 1 ≤ j_{1} < ⋯ < j_{r} < r + n be a sequence of positive integers. Then,

M(ĵ_{1}, …, ĵ_{r}) = σ(M) · det Q · det A.  (3)

Proof. The proof is by induction on r. For r = 1, we have 1 ≤ j_{1} ≤ n, since the case j_{1} > r makes no sense. It follows that M = M(ĵ_{1}). Taking i = 1 in (2), we obtain

A_{n+1} = ∑_{m=1}^{n} p_{m,1}A_{m}.

Hence, we obtain M(ĵ_{1}) as a sum of n terms. It is clear that this sum reduces to a single term, in which m = j_{1}. We conclude that

M(ĵ_{1}) = p_{j_{1},1}M(ĵ_{1}, A_{j_{1}}),

where M(ĵ_{1}, A_{j_{1}}) denotes the minor of order n of A_{r}, in which the j_{1}th column is shifted at the nth place. In M(ĵ_{1}, A_{j_{1}}), we interchange the last column with the preceding one and repeat this until the j_{1}th column takes the j_{1}th place. For this, we need n − j_{1} interchanges. It follows that

M(ĵ_{1}) = (−1)^{n+j_{1}}p_{j_{1},1} · det A.

On the other hand, we obviously have det Q = p_{j_{1},1}, and σ(M) = (−1)^{n+j_{1}}, which proves the theorem, for r = 1.

Assume that the theorem is true for 1 ≤ k < r. The last column of the minor M(ĵ_{1}, …, ĵ_{r}) is column n + r of A_{r}. The condition (2) implies

M(ĵ_{1}, …, ĵ_{r}) = ∑_{m=1}^{n+r−1} p_{m,r}M(ĵ_{1}, …, ĵ_{r}, A_{m}).

Note that the column A_{m} is the last column in each minor on the right-hand side of the preceding equation. Hence, in the sum on the right-hand side only terms obtained for j_{m} ∈ {j_{1}, …, j_{r}} remain. They are of the form:

S(t) = p_{j_{t},r}M(ĵ_{1}, …, ĵ_{t}, … ĵ_{r}, A_{j_{t}}), (t = 1, 2, …, r),

that is,

S(t) = (−1)^{n+r−1−j_{t}}p_{j_{t},r}M(ĵ_{1}, …, A_{j_{t}}, … ĵ_{r}).

Applying the induction hypothesis yields

S(t) = (−1)^{n+t−1−j_{t}}σ(M(ĵ_{1}, …, A_{j_{t}}, … ĵ_{r}))p_{j_{t},r}Q(j_{1}, …, ĵ_{t}, …, j_{r}) · det A.

By a simple calculation, we obtain

(−1)^{n+t−1−j_{t}}σ(M(ĵ_{1}, …, A_{j_{t}}, … ĵ_{r})) = (−1)^{r+t}σ(M),

hence,

S(t) = σ(M)(−1)^{r+t}Q(j_{1}, …, ĵ_{t}, …, j_{r}) · det A.

Summing over all t gives

∑_{t=1}^{r} S(t) = σ(M)[ ∑_{t=1}^{r}(−1)^{r+t}p_{j_{t},r}Q(j_{1}, …, ĵ_{t}, …, j_{r})] · det A.

The expression in the square brackets is the expansion of det Q by elements of the last column, and the theorem is proved.

We now investigate a particular class of n-determinants, arising from an n + r − 1 by r block-matrix P of the form

P = [\frac{S}{T} ] ,  (4)

where

S = (\begin{matrix}p_{1,1} & p_{1,2} & ⋯ & p_{1,r−1} & p_{1,r} \\ p_{2,1} & p_{2,2} & ⋯ & p_{2,r−1} & p_{2,r} \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ \\ p_{n,1} & p_{n,2} & ⋯ & p_{n,r−1} & p_{n,r} \end{matrix}) , T = (\begin{matrix}−1 & 0 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ \\ 0 & 0 & ⋯ & −1 & 0 \end{matrix}) .

Proposition 3. Each n-determinant of the matrix (4) equals, up to the sign, a minor of S.

Proof. We obtain an n-determinant by deleting n − 1 rows of P. It follows that each ndeterminant must contain at least one row of S. Let 1 ≤ j_{1} < j_{2} < ⋯ < j_{k} ≤ n < j_{k+1} < ⋯ < j_{r} < n + r, (k ≥ 1) be arbitrary, and consider the submatrix Q laying in j_{1}, j_{2}, …, j_{r} rows of P. It has the following form

Q = (\frac{Q_{1}}{Q_{2}} ) ,

where Q_{1} lies in rows j_{1}, j_{2}, …, j_{k} of S, and Q_{2} lies in rows j_{k+1} − n, …, j_{r} − n of T. If k = r, then Q = Q_{1}, therefore det Q is a minor of S.

Thus, we may assume that k < r. We calculate det Q by expansion across the rows of Q_{2}. The matrix Q_{2} has a unique nonzero minor D of order r − k, which lies in k + 1, …, r rows of Q. Its value obviously equals (−1)^{r−k}. The sum of the indices of rows of Q, in which D lies, is

(k + 1) + (k + 2) + ⋯ + r = \frac{(r − k)(r + k + 1)}{2}.

The sum of indices of columns in which D lies equals

(j_{k+1} − n) + ⋯ + (j_{r} − n) = j_{k+1} + ⋯ + j_{r} − (r − k)n.

We thus obtain that

det Q = (−1)^{τ} det Q_{4},

where τ = \frac{(r−k)(k+r+3−2n)}{2} + j_{k+1} + ⋯ + j_{r}, and det Q_{4} is the complement minor of D, laying in columns different from j_{k+1}, …, j_{r}. Clearly, det Q_{4} is a minor of S, and the proposition is true.

As a consequence of Theorem (3) we obtain

Proposition 4. Let A be arbitrary matrix of order n, let B be arbitrary n by r matrix. Consider the block matrix A_{r} = [A|AB]. Let 1 ≤ j_{1} < j_{2} < ⋯ < j_{k} ≤ n < j_{k+1} < ⋯ < j_{r} < n + r, (k ≥ 1) be arbitrary. If M(ĵ_{1}, …, ĵ_{r}) has the same meaning as before, then

(−1)^{σ}M = det A · det Q_{4},  (5)

where σ = \frac{k^{2}−2kn+k}{2} + j_{1} + j_{2} + ⋯ + j_{k}, and the submatrix Q_{4} lies in j_{1}, j_{2}, …, j_{k} rows, and in columns different from j_{k+1}, j_{k+2}, …, j_{r} of B.

Proof. It is easy to see that the matrix A_{r}, corresponding to the matrix (4), has the form

A_{r} = [A|AB].

After a simple calculation we obtain σ = \frac{k^{2}−2kn+k}{2} + j_{1} + j_{2} + ⋯ + j_{k}, and the assertion follows from the preceding proposition.

Remark 5. Note that equation (5) is a generalization of the theorem of the product of two determinants.

Namely, in the case r = n = k, and j_{i} = i, (i = 1, 2, …, n), we have det Q = det B, M = det AB, and σ(M) = 1, so that equation (5) becomes

det(AB) = det A · det B.

3 1-determinants

In this case, A is a matrix of order 1, that is, a single element. We also have j_{1} = 1, j_{2} = 2, …, j_{r} = r, hence, the minor M(ĵ_{1}, ĵ_{2}, …, ĵ_{r}) must be of the form: M(ˆ1, ˆ2, …, r̂). We easily obtain that σ(M) = 1. The matrix P is as follows:

P = (\begin{matrix}p_{1,1} & p_{1,2} & p_{1,3} & ⋯ & p_{1,r−1} & p_{1,r} \\ −1 & p_{2,2} & p_{2,3} & ⋯ & p_{2,r−1} & p_{2,r} \\ 0 & −1 & p_{3,3} & ⋯ & p_{3,r−1} & p_{3,r} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & p_{r−1,r−1} & p_{r−1,r} \\ 0 & 0 & 0 & ⋯ & −1 & p_{r,r} \end{matrix}) .  (6)

We see that Q = P. Therefore, each 1-determinant is an upper Hessenberg determinant. Applying Theorem 2, we obtain the following result.

Proposition 6. Let a_{1}, a_{2}, … be a sequence such that

a_{1+r} = ∑_{i=1}^{r} p_{i,r}a_{i}.  (7)

Then,

a_{r+1} = a_{1} det P.

This result is known. For instance, it follows from Theorem 4.20,[1].

Remark 7. In the paper [3], we found a combinatorial interpretation for the coefficients of the characteristic polynomials of some 1-determinants.

We give a number of examples for sequences given by the formula (7). Some of them are well-known. In all examples, we take a_{1} = 1.

1^{∘} Catalan numbers (\underline{A000108}). We let C_{n} denote the nth Catalan number. If we take p_{i,j} = C_{j−i}, then equation (7) becomes

a_{1+r} = ∑_{i=1}^{r} C_{r−i}a_{i}.

The Segner’s recurrence formula for Catalan numbers implies that a_{r+1} = C_{r}. Hence, a way to write the Segner’s formula in terms of determinants is

C_{r} = |\begin{matrix}C_{0} & C_{1} & C_{2} & ⋯ & C_{r−2} & C_{r−1} \\ −1 & C_{0} & C_{1} & ⋯ & C_{r−3} & C_{r−1} \\ 0 & −1 & C_{0} & ⋯ & C_{r−4} & C_{r−3} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & C_{0} & C_{1} \\ 0 & 0 & 0 & ⋯ & −1 & C_{0} \end{matrix}| .

2^{∘} Bell numbers (\underline{A000110}). If one takes p_{i,j} = \binom{j−1}{i−1} in (6), then (7) becomes the recursion for the Bell numbers. Thus, a determinantal expression for the Bell number B_{r} is

B_{r} = |\begin{matrix}\binom{0}{0} & \binom{1}{0} & \binom{2}{0} & ⋯ & \binom{r−2}{0} & \binom{r−1}{0} \\ −1 & \binom{1}{1} & \binom{2}{1} & ⋯ & \binom{r−2}{1} & \binom{r−1}{1} \\ 0 & −1 & \binom{2}{2} & ⋯ & \binom{r−2}{2} & \binom{r−1}{2} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & \binom{r−2}{r−2} & \binom{r−1}{r−2} \\ 0 & 0 & 0 & ⋯ & −1 & \binom{r−1}{r−1} \end{matrix}| .

The order of the determinant equals r.

3^{∘} Eigensequences for Stirling numbers (\underline{A003659}). If \left\{{n \atop k}\right\} is the Stirling number of the second kind, and p_{i,j} = \left\{{j−1 \atop i−1}\right\} in (6), then (7) becomes the recursion for the socalled eigensequence (E_{1}, E_{2}, …) of the Stirling number of the second kind. Therefore,

E_{r} = |\begin{matrix}\left\{{0 \atop 0}\right\} & \left\{{1 \atop 0}\right\} & \left\{{2 \atop 0}\right\} & ⋯ & \left\{{r−2 \atop 0}\right\} & \left\{{r−1 \atop 0}\right\} \\ −1 & \left\{{1 \atop 1}\right\} & \left\{{2 \atop 1}\right\} & ⋯ & \left\{{r−2 \atop 1}\right\} & \left\{{r−1 \atop 1}\right\} \\ 0 & −1 & \left\{{2 \atop 2}\right\} & ⋯ & \left\{{r−2 \atop 2}\right\} & \left\{{r−1 \atop 2}\right\} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & \left\{{r−2 \atop r−2}\right\} & \left\{{r−1 \atop r−2}\right\} \\ 0 & 0 & 0 & ⋯ & −1 & \left\{{r−1 \atop r−1}\right\} \end{matrix}| .

Note that analogous identity holds for the unsigned Stirling numbers of the first kind (\underline{A143805}).

4^{∘} Factorials (\underline{A000142}). Let k be a positive integer. Consider the following 1-determi-nant D of order r > 1:

D = |\begin{matrix}1 & 1 & 1 & 1 & ⋯ & 1 & 1 \\ −1 & k & k & k & ⋯ & k & k \\ 0 & −1 & k + 1 & k + 1 & ⋯ & k + 1 & k + 1 \\ 0 & 0 & −1 & k + 2 & ⋯ & k + 2 & k + 2 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & −1 & k + r − 3 & k + r − 3 \\ 0 & 0 & 0 & ⋯ & 0 & −1 & k + r − 2 \end{matrix}| .

In this case, the formula (7) becomes

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

Subtracting the equation

a_{r+2} = 1 + ∑_{i=2}^{r+1}(k + i − 2)a_{i}

from the preceding easily yields

a_{r+2} = (k + r)a_{r+1},

which is the recursion for the falling factorials. Hence,

D = \frac{(k + r − 1)!}{k!}.

5^{∘} Derangements (\underline{A000166}). We let D_{r} denote the number of derangements of r. The recurrence equation for the derangements is

D_{2} = 1, D_{3} = 2, D_{r} = (r − 1)(D_{r−2} + D_{r−1}), (r ≥ 4).

Hence,

D_{r+1} = |\begin{matrix}1 & 1 & 0 & 0 & ⋯ & 0 & 0 \\ −1 & 1 & 2 & 0 & ⋯ & 0 & 0 \\ 0 & −1 & 2 & 3 & ⋯ & 0 & 0 \\ 0 & 0 & −1 & 3 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & r − 1 & r \\ 0 & 0 & 0 & ⋯ & 0 & −1 & r \end{matrix}| .

6^{∘} Fibonacci polynomials. In this case, we consider the recurrence equation

a_{1} = 1, a_{2} = x, a_{k+1} = a_{k−1} + xa_{k}, (k ≥ 2)

for Fibonacci polynomials. Hence, for Fibonacci polynomial F_{r+1}(x) we have

F_{r+1}(x) = |\begin{matrix}x & 1 & 0 & ⋯ & 0 & 0 \\ −1 & x & 1 & ⋯ & 0 & 0 \\ 0 & −1 & x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & x & 1 \\ 0 & 0 & 0 & ⋯ & −1 & x \end{matrix}| .

The order of the determinant equals r. Taking x = 1,, in particular, we obtain the well-known determinantal expression for Fibonacci numbers.

7^{∘} Tchebychev polynomials of the first kind. The recurrence relation for the Tchebychev polynomials of the first kind is

T_{0}(x) = 1, T_{1}(x) = x, T_{k}(x) = −T_{k−2}(x) + 2xT_{k−1}(x), (k > 2).

Theorem 6 now implies the following equation:

T_{r}(x) = |\begin{matrix}x & −1 & 0 & ⋯ & 0 & 0 \\ −1 & 2x & −1 & ⋯ & 0 & 0 \\ 0 & −1 & 2x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 2x & −1 \\ 0 & 0 & 0 & ⋯ & −1 & 2x \end{matrix}| .

The order of the determinant is r. A similar formula holds for Tchebychev polynomials U_{r}(x) of the second kind.

8^{∘} Hermite polynomials. For the Hermite polynomials H_{r}(x), we have the following recurrence equation:

H_{0}(x) = 1, H_{1}(x) = 2x, H_{r+1}(x) = −2rH_{r−1}(x) + 2xH_{r}(x), (r ≥ 2).

Applying Theorem 6, we obtain the following expression:

H_{r}(x) = |\begin{matrix}2x & −2 & 0 & ⋯ & 0 & 0 \\ −1 & 2x & −4 & ⋯ & 0 & 0 \\ 0 & −1 & 2x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 2x & −2(r − 1) \\ 0 & 0 & 0 & ⋯ & −1 & 2x \end{matrix}| .

9^{∘} Continuants. Take in (7) p_{k,k} = p_{k}, p_{k−1,k} = 1, and p_{i,j} = 0 otherwise. We obtain

the recursion:

a_{1} = 1, p_{1}, a_{1+k} = a_{k−1} + p_{k}a_{k}, (k = 2, …).

The terms of this sequence are the continuants, and are denoted by (p_{1}, p_{2}, …, p_{r}). We thus obtain the following well-known formula:

(p_{1}, p_{2}, …, p_{r}) = |\begin{matrix}p_{1} & 1 & 0 & ⋯ & 0 & 0 \\ −1 & p_{2} & 1 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & p_{r−1} & 1 \\ 0 & 0 & 0 & ⋯ & −1 & p_{r} \end{matrix}| .  (8)

10^{∘} Linear homogenous recurrence equation. Let b_{1}, b_{2}, …, b_{k} be given elements. Consider the sequence 1, a_{2}, a_{3}, … defined as follows:

a_{2} = b_{1}, …, a_{k+1} = b_{k}, a_{r+1} = ∑_{i=r−k+1}^{r} p_{i,r}a_{i}, (r > k).

We thus have a linear homogenous recurrence equation of order k. From Theorem 2 follows

a_{r+1} = |\begin{matrix}b_{1} & b_{2} & ⋯ & b_{k} & 0 & 0 & ⋯ & ⋯ & 0 \\ −1 & 0 & ⋯ & 0 & p_{k+1,1} & 0 & ⋯ & ⋯ & 0 \\ 0 & −1 & ⋯ & 0 & p_{k+1,2} & p_{k+2,2} & ⋯ & ⋯ & 0 \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋮ & ⋯ & ⋯ & ⋮ \\ 0 & 0 & ⋯ & 0 & p_{k+1,k−1} & p_{k+2,k−1} & ⋯ & ⋯ & 0 \\ 0 & 0 & ⋯ & −1 & p_{k+1,k} & p_{k+2,k} & ⋯ & ⋯ & 0 \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋮ & ⋯ & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 & ⋮ & ⋮ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & ⋯ & 0 & ⋮ & ⋮ & ⋯ & −1 & p_{k,r} \end{matrix}| .

11^{∘} Generalized Fibonacci numbers. Taking in the preceding formula that each p_{i,j} equals 1, we obtain k-step Fibonacci numbers dependent on the initial conditions. The standard k-step Fibonacci numbers F_{n+k}^{(k)} are obtained for b_{1} = b_{2} = ⋯ = b_{k−1} = 0, b_{k} = 1. We thus have

F_{r+k}^{(k)} = |\begin{matrix}1 & 1 & ⋯ & 1 & 0 & ⋯ & 0 & 0 & 0 \\ −1 & 1 & ⋯ & 1 & 1 & ⋯ & 0 & 0 & 0 \\ 0 & −1 & ⋯ & 1 & 1 & ⋯ & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & ⋯ & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & ⋯ & −1 & 1 \end{matrix}| ,

where the size of the determinant is r + k.

12^{∘} Fibonacci numbers (\underline{A000045}) Consider the sequence given by

a_{1} = 1, a_{2} = 1, a_{r} = ∑_{i=1}^{r−2} a_{i}, (r > 2).

This, in fact, is a recursion for the Fibonacci numbers. To show this, we first replace r by r + 1 to obtain

a_{r+1} = ∑_{i=1}^{r−1} a_{i}.

Subtracting two last equations yields

a_{r+1} = a_{r} + a_{r−1},

which is the standard recursion for the Fibonacci numbers.

Proposition 6 implies

F_{r−1} = |\begin{matrix}1 & 1 & ⋯ & 1 & ⋯ & 1 & 1 \\ −1 & 0 & ⋯ & 1 & ⋯ & 1 & 1 \\ 0 & −1 & ⋯ & 1 & ⋯ & 1 & 1 \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋯ & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 0 & ⋯ & 0 & 1 \\ 0 & 0 & ⋯ & 0 & ⋯ & −1 & 0 \end{matrix}| .

The order of the determinant equals r.

13^{∘} Fibonacci numbers. We define a matrix Q_{r} = (q_{ij}) of order r as follows:

q_{ij} = \begin{cases}−1, & if i = j + 1; \\ i + j + 1 mod 2, & if i ≤ j; \\ 0, & otherwise. \end{cases}

We find the recursion which, as in Proposition 6, produces this matrix. Obviously, a_{1} = 1, a_{2} = 1, a_{3} = 1, a_{4} = 2, and

a_{2r} = a_{1} + ⋯ + a_{2r−1}.

Also,

a_{2r+2} = a_{1} + ⋯ + a_{2r−1} + a_{2r+1}.

Subtracting two last equation yields a_{2r+2} = a_{2r+1} + a_{2r}. Similarly, a_{2r+1} = a_{2r} + a_{2r−1}. The recursion for the Fibonacci numbers is thus obtained. It follows that F_{r−1} = det Q_{r}, (r > 1).

14^{∘} Fibonacci numbers with odd indices (\underline{A001519}). Define a matrix Q_{r} = (q_{ij}) of order r as follows:

q_{ij} = \begin{cases}−1, & if i = j + 1, \\ 2, & if i = j, \\ 1, & if i < j, \\ 0, & otherwise. \end{cases} .

In this case, we have the recursion a_{1} = 1, a_{2} = 2, a_{3} = 5, a_{r+1} = ∑_{i=1}^{r−1} +2a_{r}, (r ≥ 2). From this, we easily obtain the recursion

a_{r+2} = 3a_{r+1} − a_{r}.

The identity 7, proved in [2], shows that we have a recursion for the Fibonacci numbers with odd indices. It follows that F_{2r+1} = det Q_{r}.

Note that we described in [3] a connection of this determinant with a particular kind of composition of natural numbers.

15^{∘} Fibonacci numbers with even indices (\underline{A001906} ). For the matrix

Q_{r} = |\begin{matrix}1 & 2 & 3 & ⋯ & r − 1 & r \\ −1 & 1 & 2 & ⋯ & r − 2 & r − 1 \\ 0 & −1 & 1 & ⋯ & r − 3 & r − 2 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 1 & 2 \\ 0 & 0 & 0 & ⋯ & −1 & 1 \end{matrix}| ,

the corresponding recursion has the form:

a_{1} = 1, a_{2} = 3, a_{1+r} = ∑_{i=1}^{r}(r − i + 1)a_{i}, (r ≥ 2).

Also,

a_{2+r} = ∑_{i=1}^{r+1}(r − i + 1)a_{i} + ∑_{i=1}^{r+1} a_{i}.

Subtracting this equation from the preceding one, we obtain

a_{2+r} − a_{1+r} = ∑_{i=1}^{r+1} a_{i}.

In the same, way we obtain

a_{3+r} − a_{2+r} = ∑_{i=1}^{r+2} a_{i}.

Again, we subtract this equation from the preceding one to obtain

a_{3+r} = 3a_{2+r} − a_{1+r}.

This is a recursion for Fibonacci numbers, by Identity 7 in [2]. Taking into count the initial conditions, we have det Q_{r} = F_{2r}.

4 2-determinants

In this section we consider the case n = 2. We first investigate the case that p_{i,j} = 0, (j > i). Then, P has at most three nonzero diagonals, and may be written in the form:

P = |\begin{matrix}b_{1} & 0 & 0 & ⋯ & 0 & 0 \\ c_{2} & b_{2} & 0 & ⋯ & 0 & 0 \\ −1 & c_{3} & b_{3} & ⋯ & 0 & 0 \\ 0 & −1 & c_{4} & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋯ & ⋮ & ⋮ \\ 0 & 0 & ⋮ & ⋯ & c_{r} & b_{r} \\ 0 & 0 & ⋮ & ⋯ & −1 & c_{r+1} \end{matrix}| .  (9)

The corresponding 2-determinant det Q is a lower triangular block determinant of the form:

| \begin{matrix}Q_{11} & 0 \\ Q_{12} & Q_{22} \end{matrix} | .  (10)

Here, Q_{11} is a lower triangular determinant lying in the first k rows and the first k columns of Q. It follows that Q_{11} = b_{1} ⋯ b_{k}. The order of Q_{22} is r − k and it is of the same form as the determinant of the matrix P in (6).

As a consequence of Theorem 2, we obtain

Proposition 8. Let (b_{1}, b_{2}, …), (c_{2}, c_{3}, …) be any two sequences. Let

(a_{1}^{(i)}, a_{2}^{(i)}, …) (i = 1, 2)

be two sequences defined by the same recurrence equation of the second order:

a_{r}^{(i)} = b_{r−2}a_{r−2}^{(i)} + c_{r−1}a_{r−1}^{(i)}, (r > 2), (i = 1, 2)..

Then,

|\begin{matrix}a_{k+1}^{(1)} & a_{r+2}^{(1)} \\ a_{k+1}^{(2)} & a_{r+2}^{(2)} \end{matrix}| = (−1)^{k}b_{1} ⋯ b_{k} · d_{r−k+1} · |\begin{matrix}a_{1}^{(1)} & a_{2}^{(1)} \\ a_{1}^{(2)} & a_{2}^{(2)} \end{matrix}| ,

where

d_{1} = 1, d_{2} = c_{k+2}, d_{i} = b_{k+i−1}d_{i−2} + c_{k+i}d_{i−1}, (i > 2)..

We illustrate the preceding proposition with some examples.

1^{∘} Fibonacci polynomials. Take x_{1}^{(1)} = F_{u}(x), x_{2}^{(1)} = F_{u+1}(x), x_{1}^{(2)} = F_{v}(x), x_{2}^{(2)} = F_{v+1}(x), b_{i} = 1, c_{i+1} = x, (i = 1, 2, …).

Note that, in this case, the 2-determinant equals the Fibonacci polynomial F_{r−k}(x). From Proposition 8, we obtain the following identity:

|\begin{matrix}F_{u+k}(x) & F_{u+r}(x) \\ F_{v+k}(x) & F_{v+r}(x) \end{matrix}| = (−1)^{k}F_{r−k}(x) · |\begin{matrix}F_{u}(x) & F_{u+1}(x) \\ F_{v}(x) & F_{v+1}(x) \end{matrix}| .  (11)

Several well-known formulas may be obtained from this.

Taking u = 1, v = 0 yields

F_{k+1}(x)F_{r}(x) − F_{k}(x)F_{r+1}(x) = (−1)^{k}F_{r−k}(x),

which is the Ocagne’s identity for the Fibonacci polynomials. Applying this identity on the right-hand side of (11), we obtain

|\begin{matrix}F_{u+m}(x) & F_{u+r}(x) \\ F_{v+m} & F_{v+r}(x) \end{matrix}| = (−1)^{m+u+1}F_{r−m}(x)F_{v−u}(x).

We now may easily derive the index-reduction formula for the Fibonacci polynomials. Namely, replacing m by m − t and r by r − t, we get

|\begin{matrix}F_{u+k−t}(x) & F_{u+r−t}(x) \\ F_{v+k−t}(x) & F_{v+r−t}(x) \end{matrix}| = (−1)^{k−t+u+1}F_{r−k}(x)F_{v−u}(x).

Comparing the last two equations produces

|\begin{matrix}F_{u+k−t}(x) & F_{u+r−t}(x) \\ F_{v+k−t}(x) & F_{v+r−t}(x) \end{matrix}| = (−1)^{t} |\begin{matrix}F_{u+k}(x) & F_{u+r}(x) \\ F_{v+k}(x) & F_{v+r}(x) \end{matrix}| ,

which is the index reduction formula.

Note that such a formula for the Fibonacci numbers is proved in [4].

2^{∘} Fibonacci and Lucas polynomials. The Lucas polynomials L_{r}(x) satisfy the same recurrence relation as do the Fibonacci polynomials with different initial conditions. In this case, also, the 1-determinant equals a Fibonacci polynomial. We state two equations, one for mixed Lucas and Fibonacci polynomials, another for Lucas polynomials:

|\begin{matrix}F_{u+k}(x) & F_{u+r}(x) \\ L_{v+k}(x) & L_{v+r}(x) \end{matrix}| = (−1)^{k}F_{r−k}(x) · |\begin{matrix}F_{u}(x) & F_{u+1}(x) \\ L_{v}(x) & L_{v+1}(x) \end{matrix}| ,

and

|\begin{matrix}L_{u+k}(x) & L_{u+r}(x) \\ L_{v+k}(x) & L_{v+r}(x) \end{matrix}| = (−1)^{k}F_{r−k}(x) · |\begin{matrix}L_{u}(x) & L_{u+1}(x) \\ L_{v}(x) & L_{v+1}(x) \end{matrix}| .

3^{∘} Tchebychev polynomials. Tchebychev polynomials of the first and second kind also satisfy the same recursion with different initial conditions. Here, the 1-determinant equals a Tchebychev polynomial of the second kind. We state the following three identities, which are a consequence of Proposition 8.

|\begin{matrix}U_{u+k}(x) & U_{u+r}(x) \\ U_{v+k}(x) & U_{v+r}(x) \end{matrix}| = U_{r−k−1}(x) |\begin{matrix}U_{u}(x) & U_{u+1}(x) \\ U_{v}(x) & U_{v+1}(x) \end{matrix}| ,

|\begin{matrix}T_{u+k}(x) & T_{u+r}(x) \\ T_{v+k}(x) & T_{v+r}(x) \end{matrix}| = U_{r−k−1}(x) |\begin{matrix}T_{u}(x) & T_{u+1}(x) \\ T_{v}(x) & T_{v+1}(x) \end{matrix}| ,

|\begin{matrix}U_{u+k}(x) & U_{u+r}(x) \\ T_{v+k}(x) & T_{v+r}(x) \end{matrix}| = U_{r−k−1}(x) |\begin{matrix}U_{u}(x) & U_{u+1}(x) \\ T_{v}(x) & T_{v+1}(x) \end{matrix}| .

4^{∘} Continued fractions. Up until now, the division was not used. We might therefore assume that the elements of the concerned sequences belong to any commutative ring with 1. In this part, we suppose that they are positive real numbers. Let A_{2} be the identity matrix of order 2, and let (c_{1}, c_{2}, …) be an arbitrary sequence of positive real numbers. Form the matrix A_{r} by the following rule:

A_{2+k} = A_{k} + c_{k}A_{k+1}, (k = 1, 2, …, r).

It is easy to see that A_{r} has the form:

A_{r} = (\begin{matrix}1 & 0 & 1 & c_{2} & … & (c_{2}, c_{3}, …, c_{r}) \\ 0 & 1 & c_{1} & (c_{1}, c_{2}) & … & (c_{1}, c_{2}, c_{3}, …, c_{r}) \end{matrix}) ,

where (c_{m}, c_{m+1}, …, c_{p}) are the continuants. The 1-determinant equals the continuant (c_{k+2}, c_{k+3}, …, c_{r}).

The fundamental recurrence relation for the continued fractions gives an expression for the difference between two consecutive convergents. Equation 8 allows us to derive a formula for the difference between two arbitrary convergents. The following formula holds:

|\begin{matrix}(c_{2}, c_{3}, …, c_{k}) & (c_{2}, c_{3}, …, c_{r}) \\ (c_{1}, c_{2}, c_{3}, …, c_{k}) & (c_{1}, c_{2}, c_{3}, …, c_{r}) \end{matrix}| = (−1)^{k+1}(c_{k+2}, c_{k+3}, …, c_{r}),

or, equivalently,

\frac{(c_{1}, c_{2}, c_{3}, …, c_{r})}{(c_{2}, c_{3}, …, c_{r})} − \frac{(c_{1}, c_{2}, c_{3}, …, c_{k})}{(c_{2}, c_{3}, …, c_{k})} = (−1)^{k+1} \frac{(c_{k+2}, c_{k+3}, …, c_{r})}{(c_{2}, c_{3}, …, c_{k}) · (c_{2}, c_{3}, …, c_{r})},

with the convention that for r = k + 1 the expression (c_{k+2}, c_{k+3}, …, c_{r}) equals 1.

If r < k + 1, then the proof follows from Proposition 8. If r = k + 1, then we take (c_{k+2}, c_{k+3}, …, c_{m}) = 1, as then there is no matrix Q_{22}. Hence, our formula becomes the continued fraction fundamental recurrence relation.

5^{∘} Derangements. Take A = (\begin{matrix}1 & 0 \\ 1 & 1 \end{matrix}) . Let the matrix A_{r} be formed by the recursion

A_{2+r} = r(A_{1+r} + A_{r}), (r ≥ 1).

It is obvious that the rth element of the first row of A_{r} equals D_{r−1}. Also, the rth term of the second row of A_{r} equals (r − 1)!. It follows that

M(k + 1, r + 1) = |\begin{matrix}D_{k} & D_{r} \\ k! & r! \end{matrix}| .

We thus obtain the following identity:

|\begin{matrix}D_{k} & D_{r} \\ k! & r! \end{matrix}| = (−1)^{k}k! |\begin{matrix}k + 1 & k + 2 & 0 & ⋯ & 0 & 0 \\ −1 & k + 2 & k + 3 & ⋯ & 0 & 0 \\ 0 & −1 & k + 3 & ⋯ & 0 & 0 \\ 0 & 0 & −1 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & r − 1 & r \\ 0 & 0 & 0 & ⋯ & −1 & r \end{matrix}| .

In particular, for r = k + 1, we have the standard recursion D_{k+1} = kD_{k} + (−1)^{k} for the derangements.

The preceding identities are derived from homogenous recurrence equations of order two. We shall now consider the case of a recurrence equation of order three.

Theorem 9. Let r be a positive integer, and let (a_{i}), (b_{i+1}), (c_{i+2}), (i = 1, 2, …) be arbitrary sequences. Let A be a matrix of order 2, and let the matrix A_{r} be defined as follows:

A_{3} = b_{1}A_{1} + c_{2}A_{2}, A_{3+j} = a_{j}A_{j} + b_{j+1}A_{j+1} + c_{j+2}A_{j+2}, (1 < j < r − 2).

Then, the corresponding 2-determinant Q is determined by two homogenous recurrence equations of order 3.

Proof. In this case the matrix P has the following form:

P = (\begin{matrix}b_{1} & a_{1} & 0 & ⋯ & 0 & 0 & 0 \\ c_{2} & b_{2} & a_{2} & ⋯ & 0 & 0 & 0 \\ −1 & c_{3} & b_{3} & … & 0 & 0 & 0 \\ 0 & −1 & c_{4} & … & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & c_{r−1} & b_{r−1} & a_{r−1} \\ 0 & 0 & 0 & ⋯ & −1 & c_{r} & b_{r} \\ 0 & 0 & 0 & ⋯ & 0 & −1 & c_{r+1} \end{matrix}) .

The 2-determinant det Q is obtained from P by deleting the (k + 1)th row of P, where (0 ≤ k < r). We let D(i_{1}, …, i_{t}) denote the minor of P, the main diagonal of which is (i_{1}, i_{2}, …, i_{t}). Hence,

det Q = D(b_{1}, …, b_{k}, c_{k+2}, …, c_{r+1}).

In the expansion of det Q across the first k rows all terms are zero, except eventually two. Hence,

det Q = D(b_{1}, …, b_{k})D(c_{k+2}, …, c_{r+1}) + a_{k}D(b_{1}, …, b_{k−1})D(c_{k+3}, …, c_{r+1}).

Furthermore, we have

D(b_{1}) = b_{1}, D(b_{1}, b_{2}) = |\begin{matrix}b_{1} & a_{1} \\ c_{2} & b_{2} \end{matrix}| , D(b_{1}, b_{2}, b_{3}) = |\begin{matrix}b_{1} & a_{1} & 0 \\ c_{2} & b_{2} & a_{2} \\ −1 & c_{3} & b_{3} \end{matrix}| .

Assume k > 3. Expanding D(b_{1}, …, b_{k}) by the elements of the last column, we obtain

D(b_{1}, …, b_{k}) = b_{k}D(b_{1}, …, b_{k−1}) − a_{k−1}c_{k}D(b_{1}, …, b_{k−2}) − a_{k−1}a_{k−2}D(b_{1}, …, b_{k−3}). (12)

Also,

D(c_{k+2}) = c_{k+2}, D(c_{k+2}, c_{k+3}) = |\begin{matrix}c_{k+2} & b_{k+2} \\ −1 & c_{k+3} \end{matrix}| ,

and

D(c_{k+2}, c_{k+3}, c_{k+4}) = |\begin{matrix}c_{k+2} & b_{k+2} & a_{k+2} \\ −1 & c_{k+3} & b_{k+3} \\ 0 & −1 & c_{k+4} \end{matrix}| .

If k > 3, then by expanding D(c_{k+2}, …, c_{r+1}) along the first column, we obtain

\begin{aligned}D(c_{k+2}, …, c_{r+1}) \\ & = c_{k+3}D(c_{k+3}, …, c_{r+1}) + b_{k+2}D(c_{k+4}, …, c_{r+1}) \\ & + a_{k+2}D(c_{k+5}, …, c_{r+1}). \end{aligned}  (13)

It follows that the 2-determinant det Q is uniquely determined by the recurrence equations (12) and (13).

We illustrate the preceding considerations with two particular cases. We first assume that all a’s, b’s, and c’s equal 1. Then,

D(b_{1}) = 1, D(b_{1}, b_{2}) = 0, D(b_{1}, b_{2}, b_{3}) = −2,

and, for s > 3,

D(b_{1}, b_{2}, …, b_{s}) = D(b_{1}, …, b_{s−1}) − D(b_{1}, …, b_{s−2}) − D(b_{1}, …, b_{s−3}).

This recursion designates the so-called reflected Tribonacci numbers (\underline{A057597}). We denote these numbers by RT_{i} (i = 1, 2, …). Also,

D(c_{1}) = 1, D(c_{1}, c_{2}) = 2, D(c_{1}, c_{2}, c_{3}) = 4,

and, for s > 3,

D(c_{1}, c_{2}, …, c_{s}) = D(c_{1}, …, c_{s−1}) + D(c_{1}, …, c_{s−2}) + D(c_{1}, …, c_{s−3}).

Hence, if we denote by T_{i}, i = 0, 1, 2, … the Tribonacci numbers (\underline{A000073}) we have

D(c_{1}, c_{2}, …, c_{s}) = T_{s+2}, (s = 1, 2, …).

Hence, our 2-determinant Q consists of Tribonacci and reflected Tribonacci numbers. On the other hand, if A is the identity matrix of order 2, then the first row of A_{r} consists of the above Tribonacci numbers. The second rows consists of Tribonacci numbers T̃_{i}, (i = 0, 1, …) with the initial conditions given by T̃(0) = 1, T̃(1) = 0, T̃(2) = 1, (\underline{A001590}). As a consequence of Theorem 2, we have

Corollary 10. Let k < r be nonnegative integers. The following identity holds

|\begin{matrix}T̃_{k+1} & T̃_{r+2} \\ T_{k+1} & T_{r+2} \end{matrix}| = (−1)^{k} |\begin{matrix}RT_{k−1} & −RT_{k} \\ T_{r−k} & T_{r−k−1} \end{matrix}| .

Assume now that the b’s are all equal zero and the a’s and the c’s are all equal 1. Then the recursion (12) gives the sequence x_{1}, x_{2}, …, such that x_{n} = \underline{A077962}(n). Also, the recursion (13) produces the sequence y_{1}, y_{2}, …, such that y_{n} = \underline{A000930}(n).

Next, the rows of A_{r} form sequences a_{1}^{(i)}, a_{2}^{(i)}, … (i = 1, 2) such that, for n ≥ 4 we have a_{n}^{(1)} = \underline{A000930}(n − 4), a_{n}^{(2)} = \underline{A000930}(n − 2). We thus obtain

Corollary 11. For integers 3 ≤ k < r we have

|\begin{matrix}y_{k−3} & y_{r−2} \\ y_{k−1} & y_{r} \end{matrix}| = (−1)^{k} |\begin{matrix}x_{k−1} & −x_{k} \\ y_{r−k} & y_{r−k−1} \end{matrix}| .

5 3-determinants

In this section, the order of the matrix A is 3. We investigate in detail the particular case when p_{i,j} = 0, (j > i). Then, the matrix P is of order (r + 2) × r, may have at most four nonzero diagonals, and has the form:

P = (\begin{matrix}a_{1} & 0 & 0 & ⋯ & 0 & 0 & 0 \\ b_{2} & a_{2} & 0 & ⋯ & 0 & 0 & 0 \\ c_{3} & b_{3} & a_{3} & … & 0 & 0 & 0 \\ −1 & c_{4} & b_{4} & … & 0 & 0 & 0 \\ 0 & −1 & c_{5} & ⋯ & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & c_{r} & b_{r} & a_{r} \\ 0 & 0 & 0 & ⋯ & −1 & c_{r+1} & b_{r+1} \\ 0 & 0 & 0 & ⋯ & 0 & −1 & c_{r+2} \end{matrix}) .

The corresponding 3-determinant det Q is obtained by deleting rows k + 1 and m + 1 of P, where (0 ≤ k < m ≤ r + 1). The matrix Q is a lower triangular block matrix of the form (10), with det Q_{11} = a_{1} · a_{2} ⋯ a_{k}. The order of the matrix Q_{22} is r − k.

We denote det Q_{22} = D_{k}(s, r), where s = m − k. Note that s ≥ 1. For the columns of A_{r} we have the following recursion:

A_{3+i} = a_{i}A_{i} + b_{i+1}A_{1+i} + c_{i+2}A_{i+2}, (i ≥ 1).  (14)

It follows that the sequences in the rows of A_{r} satisfy recurrence equations of order 3, with the initial conditions given by the rows of A. The set {j_{1}, …, j_{r}} equals {1, 2, …, k, k + 2, …, m, m + 2, …, r + 2}. A simple calculation shows that σ(M) = (−1)^{m+k+1}. As a consequence of Theorem 2, we have

Proposition 12. Let A be any matrix of order 3, let (a_{i}), (b_{i+1}), (c_{i+2}), (i = 1, 2, …) be any sequences. Then,

M(k + 1, m + 1, r + 2) = (−1)^{m+k+1}a_{1} ⋯ a_{k} det Q · det A.

We next prove the following Proposition 12.

Proposition 13. The determinant det Q_{22} is determined with three recurrence relations.

Proof. The matrix Q_{22} has at most five nonzero diagonals. Assume that s ≥ 3. 1) The main diagonal of Q_{22} is

b_{k+2}, …, b_{k+s}, { \atop k + s + 1}, c_{k+s+2}, …, c_{r+2},

where there are s − 1 of b’s and r + 1 − k − s of a’s

2) The first superdiagonal is

a_{k+2}, …, a_{k+s}, { \atop k + s + 1}, b_{k+s+2} …, b_{r+1},

where there are s − 1 of a’s and r − k − s of b’s.

3) The first subdiagonal is

c_{k+3}, …, c_{k+s}, { \atop k + s + 1}, −1, …, −1,

where there are s − 2 of c’s and r + 1 − k − s of −1’s.

4) The second superdiagonal is

0, …, 0, { \atop k + s + 1}, a_{k+s+2}, …, a_{r},

where there are s − 1 of 0’s and r − k − s − 1 of a’s.

5) The second subdiagonal is

−1, …, −1, { \atop k + s + 1}, 0, …, 0,

where there are s − 3 of −1’s and r + 1 − k − s of 0’s.

Case s = 1. We begin with

D_{k}(1, k) = 1, D_{k}(1, k + 1) = c_{k+3}, D_{k}(1, k + 2) = |\begin{matrix}c_{k+3} & b_{k+3} \\ −1 & c_{k+4} \end{matrix}| .

For t > 2, expanding D_{k}(1, k+t) by elements from the last row yields the following recursion:

\begin{aligned}D_{k}(1, k + t) \\ & = c_{k+t+2}D_{k}(1, k + t − 1) + b_{k+t+1}D_{k}(1, k + t − 2) \\ & + a_{k+t}D_{k}(1, k + t − 3). \end{aligned}  (15)

Case s = 2. We have

D_{k}(2, k + 1) = b_{k+2}, D_{k}(2, k + 2) = |\begin{matrix}b_{k+2} & a_{k+2} \\ −1 & c_{k+4} \end{matrix}| ,

D_{k}(2, k + 3) = |\begin{matrix}b_{k+2} & a_{k+2} & 0 \\ −1 & c_{k+4} & b_{k+4} \\ 0 & −1 & c_{k+5} \end{matrix}| .

For t ≥ 4, we calculate D_{k}(2, k + t) by the recursion (15).

Case s = 3. We now have D_{k}(3, k + 2) = b_{k+2},

D_{k}(3, k + 3) = |\begin{matrix}b_{k+2} & a_{k+2} \\ c_{k+3} & b_{k+3} \end{matrix}| , D_{k}(3, k + 4) = |\begin{matrix}b_{k+2} & a_{k+2} & 0 \\ c_{k+3} & b_{k+3} & a_{k+3} \\ 0 & −1 & c_{k+5} \end{matrix}| ,

D_{k}(3, k + 5) = |\begin{matrix}b_{k+2} & a_{k+2} & 0 & 0 \\ c_{k+3} & b_{k+3} & a_{k+3} & 0 \\ 0 & −1 & c_{k+5} & b_{k+5} \\ 0 & 0 & −1 & c_{k+6} \end{matrix}| .

For t > 5, we calculate D_{k}(3, k + t) again by the recursion (15).

Case s ≥ 4. The minors D_{k}(s, k+s−1), …, D_{k}(s, k+2s−1) may be obtained as follows:

D_{k}(s, k + s − 1) = b_{k+2}, D_{k}(s, k + s) = |\begin{matrix}b_{k+2} & a_{k+2} \\ c_{k+3} & b_{k+3} \end{matrix}| ,

D_{k}(s, k + s + 1) = |\begin{matrix}b_{k+2} & a_{k+2} & 0 \\ c_{k+3} & b_{k+3} & a_{k+3} \\ −1 & c_{k+4} & b_{k+4} \end{matrix}| .

When 1 < t ≤ s − 1, we have the following recursion:

\begin{aligned}D_{k}(s, k + s + t) \\ & = b_{t+k+2}D_{k}(s, k + s + t − 1) − a_{t+k+1}c_{t+k+2}D_{k}(s, k + s + t − 2) \\ & − a_{t+k+1}a_{t+k}D_{k}(s, k + s + t − 3). \end{aligned}  (16)

Next, we have

D_{k}(s, k + 2s) = c_{s+k+2}D_{k}(s, k + 2s − 1) + a_{s+k}D_{k}(s, k + 2s − 2).

If s < r − k, then

D_{k}(s, k + 2s + 1) = c_{s+k+3}D_{k}(s, k + 2s) + b_{s+k+2}D_{k}(s, k + 2s − 1).

If s + 1 < r − k, then for t, where s + 1 < t ≤ r − k, we have the recursion (15).

The recursion with respect to k is backward. The minimal value that r can take is r = k. Then,

D_{k}(1, k) = 1, D_{k}(2, k + 1) = D_{k}(3, k + 2) = b_{k+2}.

Assume that s > 3. Expanding D_{k}(s, r) by elements of the first row, we obtain the following recursion:

\begin{aligned}D_{k}(s, r) = b_{k+2}D_{k+1}(s − 1, r − 1) \\ & − a_{k+2}c_{k+3}D_{k+2}(s − 2, r − 2) \\ & − a_{k+2}a_{k+3}D_{k+3}(s − 3, r − 3) \end{aligned} .  (17)

We have thus proved that det Q is uniquely determined by the formulas (15), (16), and (17).

We state some particular cases.

1^{∘} All a’s equal 0. It follows from (12) that all minors M(k + 1, m + 1, r + 3) are zeros, except the case k = 0, when we have the same situation as in the preceding section.

2^{∘} All b’s equal 0, and all a’s and c’s equal 1. The formula (14) has the form:

A_{3+i} = A_{i} + A_{i+2}, (i ≥ 1).

If A is the identity matrix, then the rows of A_{r} make the so-called middle sequence (\underline{A000930}). For a fixed k the first three rows of the array det Q_{22} are obtained by the recursion (15), hence they are also formed from the numbers of the middle sequence. If s > 3, then the first s − 1 elements in row s are obtained by the recursion (16). The remaining terms are again obtained from (15). Therefore, Proposition (12) gives an identity for the numbers of the middle sequence.

3^{∘} All c’s equal 0, and all a’s and b’s equal 1. In this case, we have

A_{3+i} = A_{i} + A_{i+1}, (i ≥ 1),

which is the recursion for the Padovan sequence (\underline{A000931}). From Proposition 12, we obtain an assertion for the Padovan numbers.

4^{∘} All a’s, b’s and c’s equal 1. The rows of A_{r} are made of Tribonacci numbers, with the initial conditions given by the rows of A. Proposition 12 produces an identity for Tribonacci numbers.

Assume that A is the identity matrix of order 3. Let T_{t_{1},t_{2},t_{3}}(n), (n = 1, 2, …) denote Tribonacci numbers with initial conditions T_{t_{1},t_{2},t_{3}}(1) = t_{1}, T_{t_{1},t_{2},t_{3}}(2) = t_{2}, T_{t_{1},t_{2},t_{3}}(3) = t_{3}.

We then have

Proposition 14. Let 0 ≤ k < m < r + 2 be integers. Then,

|\begin{matrix}T_{1,0,0}(k) & T_{1,0,0}(m) & T_{1,0,0}(r + 2) \\ T_{0,1,0}(k) & T_{0,1,0}(m) & T_{0,1,0}(r + 2) \\ T_{0,0,1}(k) & T_{0,0,1}(m) & T_{0,0,1}(r + 2) \end{matrix}| = (−1)^{m+k+1}D_{k}(m − k, r).

Note that the nature of numbers D_{k}(m − k, r) depends on values of k, m − k and r.

References

[1] R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer-Verlag, 1999.

[2] A. T. Benjamin and J. J. Quinn, Proofs that Really Count, Mathematical Association of America, 2003.

[3] M, Janjić, Hessenberg matrices and integer sequences, J. Integer Sequences, 10 (2010), Article 10.7.8.

[4] R. C. Johnson, Fibonacci numbers and matrices, manuscript available at

    http://www.dur.ac.uk/bob.johnson/fibonacci/, 2008.

[5] N. J. A. Sloane, Online Encyclopedia of Integer Sequences, http://oeis.org.

[6] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

2000 Mathematics Subject Classification: Primary 11P99; Secondary 11B39. Keywords: determinant, recurrence equation, Fibonacci number, convergent, derangements.

(Concerned with sequence \underline{A000045}, \underline{A000073}, \underline{A000108}, \underline{A000110}, \underline{A000142}, \underline{A000166}, \underline{A000930}, \underline{A000931}, \underline{A001519}, \underline{A001590}, \underline{A001906}, \underline{A003659}, \underline{A057597}, \underline{A077962}, and \underline{A143805}.)

Received December 20 2011; revised version received March 13 2012. Published in Journal of Integer Sequences, March 13 2012.

Return to Journal of Integer Sequences home page.