More Determinant Representations for Sequences

Alireza Moghaddamfar and Hadiseh Tajbakhsh Department of Mathematics K. N. Toosi University of Technology P. O. Box 16315-1618 Tehran, Iran and Research Institute for Fundamental Sciences (RIFS) Tabriz, Iran

                      moghadam@kntu.ac.ir
                        moghadam@ipm.ir

Abstract In this paper, we will find some new families of infinite (integer) matrices whose entries satisfy a non-homogeneous recurrence relation and such that the sequence of their leading principal minors is a subsequence of the Fibonacci, Lucas, Jacobsthal, or Pell sequences.

1 Introduction

Throughout this paper, unless noted otherwise, we will use the following notation. Let α = (α_{i})_{i⩾0} and β = (β_{i})_{i⩾0} be two arbitrary sequences starting with a common first term α_{0} = β_{0}. We denote by P_{α,β}(n) the generalized Pascal triangle associated with the sequences α and β, which is introduced as follows. Actually, P_{α,β}(n) = [P_{i,j}]_{0⩽i,j⩽n} is a square matrix of order n + 1 whose (i, j)-entry P_{i,j} obeys the following rules:

P_{i,0} = α_{i}, P_{0,j} = β_{j} for i, j = 0, 1, 2, …, n, and P_{i,j} = P_{i,j−1} + P_{i−1,j} for 1 ⩽ i, j ⩽ n.

We also denote by T_{α,β}(n) = [T_{i,j}]_{0⩽i,j⩽n} the Toeplitz matrix of order n + 1 whose (i, j)-entry T_{i,j} obeys the following rules:

T_{i,0} = α_{i}, T_{0,j} = β_{j} for i, j = 0, 1, 2, …, n, and T_{i,j} = T_{k,l} if i − j = k − l.

The unipotent lower triangular matrix L(n) = [L_{i,j}]_{0⩽i,j⩽n} is again a square matrix of order n + 1 with entries:

L_{i,j} = \{ \begin{matrix}0, & if 0 ⩽ i < j ⩽ n; \\ \binom{i}{j}, & if 0 ⩽ j ⩽ i ⩽ n. \end{matrix}

We put U(n) = L(n)^{t}, where A^{t} signifies the transpose of matrix A. Moreover, a lower Hessenberg matrix H(n) = [H_{i,j}]_{0⩽i,j⩽n} is a square matrix of order n + 1, where H_{i,j} = 0 whenever j > i + 1 and H_{i,i+1} ≠ 0 for some i, 0 ⩽ i ⩽ n − 1.

Given a matrix A, we denote by R_{i}(A) (resp., C_{j}(A)) the row i (resp., the column j) of A. We also denote by A^{[1]} the submatrix obtained from A by deleting the first column of A.

Given a sequence φ = (φ_{i})_{i≥0}, define the binomial transform of φ to be the sequence φ̂ = (φ̂_{i})_{i⩾0} with

φ̂_{i} = ∑_{k=0}^{i}(−1)^{i+k}\binom{i}{k}φ_{k}.

The Fibonacci sequence (\underline{A000045} in [3]) is defined by the recurrence relation:

F_{0} = 0, F_{1} = 1, F_{n} = F_{n−1} + F_{n−2} for n ⩾ 2.

The Lucas sequence (\underline{A000032} in [3]) is defined by the recurrence relation:

L_{0} = 2, L_{1} = 1, L_{n} = L_{n−1} + L_{n−2} for n ⩾ 2.

The Jacobsthal sequence (\underline{A001045} in [3]) is defined by the recurrence relation:

J_{0} = 0, J_{1} = 1, J_{n} = J_{n−1} + 2J_{n−2} for n ⩾ 2.

The Pell sequence (\underline{A000129} in [3]) is defined by the recurrence relation:

P_{0} = 0, P_{1} = 1, P_{n} = 2P_{n−1} + P_{n−2} for n ⩾ 2.

Let A = [A_{i,j}]_{i,j⩾0} be an arbitrary infinite matrix. We denote the elementary row operation of type three by O_{r,s}(λ), where r ≠ s and λ a scalar, that is

R_{k}(O_{r,s}(λ)A) = \{ \begin{matrix}R_{r}(A) + λR_{s}(A), & if k = r; \\ R_{k}(A), & if k ≠ r. \end{matrix}

The nth leading principal minor of A, denoted by d_{n}(A), is defined as follows:

d_{n}(A) = det[A_{i,j}]_{0⩽i,j⩽n}, (n = 0, 1, 2, 3, …).

We put D(A) = (d_{n}(A))_{n⩾0}. Two infinite matrices A and B are said to be equimodular if D(A) = D(B). Given a sequence ω = (ω_{n})_{n⩾0}, a family {A_{t}| t ∈ I} of equimodular matrices are said to be ω-equimodular if D(A_{t}) = ω for all t ∈ I. We will denote the family of ω-equimodular matrices by A_{ω}. The infinite matrices in A_{ω} are said to be determinant representations of ω. Note that for any sequence ω = (ω_{n})_{n⩾0}, there is a determinant representation of ω, in other words A_{ω} ≠ ∅. Indeed, expanding along the last rows, it is easy to see that

( \begin{matrix}ω_{0} & 1 & ∗ & ∗ & ∗ & ⋯ \\ −ω_{1} & 0 & 1 & ∗ & ∗ & ⋯ \\ ω_{2} & 0 & 0 & 1 & ∗ & ⋯ \\ −ω_{3} & 0 & 0 & 0 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ∈ A_{ω},

(see also Theorem 3.2 and the Remark after this theorem in [4]). Especially, there are many different determinant representations of ω, when ω is a (sub-)sequence of Fibonacci, Lucas, Jacobsthal and Pell sequences. Some examples of such matrices can be found in [1, 2].

In this paper, we are going to find some determinant representations of the sequences:

F = (F_{n+1})_{n⩾0}, L = (L_{n+1})_{n⩾0}, J = (J_{n+1})_{n⩾0} and P = (P_{n+1})_{n⩾0}.

It is worthwhile to point out that we will use non-homogeneous recurrence relations to construct these determinant representations.

In the sequel, we introduce a new family of (infinite) matrices A(∞) = [A_{i,j}]_{i,j⩾0}, whose entries obey a non-homogeneous recurrence relation. Actually, for two constants u and v, and arbitrary sequences λ = (λ_{i})_{i⩾0} and μ = (μ_{i})_{i⩾0} with μ_{0} = 0, the first column and row of matrix A(∞) are the sequences

(A_{i,0})_{i⩾0} = (λ_{0}, λ_{1}, λ_{2}, …, A_{i,0} = λ_{i}, …),

and

(A_{0,j})_{j⩾0} = (λ_{0}, λ_{0} + u, λ_{0} + 2u, …, A_{0,j} = λ_{0} + ju, …),

respectively, while the remaining entries A_{i,j} (i, j ⩾ 1) are obtained from the following nonhomogeneous recurrence relation:

A_{i,j} = A_{i,j−1} + A_{i−1,j} − λ_{i−1} + μ_{i} − μ_{i−1} + (j − 1)(v − u), i, j ⩾ 1.

We denote by A(n) the submatrix of A(∞) consisting of the entries in its first n + 1 rows and columns. The matrix A(3), for example, is then given by

A(3) = ( \begin{matrix}λ_{0} & λ_{0} + u & λ_{0} + 2u & λ_{0} + 3u \\ λ_{1} & λ_{1} + μ_{1} + u & λ_{1} + 2μ_{1} + 2u + v & λ_{1} + 3μ_{1} + 3u + 3v \\ λ_{2} & λ_{2} + μ_{2} + u & λ_{2} + 2μ_{2} + μ_{1} + 2u + 2v & λ_{2} + 3μ_{2} + 3μ_{1} + 3u + 7v \\ λ_{3} & λ_{3} + μ_{3} + u & λ_{3} + 2μ_{3} + μ_{2} + μ_{1} + 2u + 3v & λ_{3} + 3μ_{3} + 3μ_{2} + 4μ_{1} + 3u + 12v \end{matrix} ) .

Finally, the main result of this paper can be stated as follows:

Main Theorem. The matrix A(n), n ⩾ 0, defined as above, satisfies the following statements:

(a) A(n) = L(n) · H(n) · U(n), where

H(n) = ( λ̂_{0} u 0  ⋯  0 ; λ̂_{1} ; λ̂_{2} ; ⋮  T_{(μ̂_{1},μ̂_{2},μ̂_{3},...),(μ̂_{1},v,0,0,...)}(n − 1) ; λ̂_{n} ) .

In particular, we have det(A(n)) = det(H(n)).

(b) In the case when u = v = 1 and λ_{i} = (2^{i} − 1)c + 1, we have the following statements:

(b. 1) if μ_{i} = (2^{i} + \frac{(i−2)(i+1)}{2}) c − \frac{i(i−3)}{2}, then det(A(n)) = F_{n+1}.

(b. 2) if μ_{i} = (\frac{5·3^{i}}{4} − 2^{i} − \frac{2i+1}{4}) c + \frac{5(3^{i}−1)}{4} + \frac{i}{2}, then det(A(n)) = L_{n+1}.

(b. 3) if μ_{i} = i^{2}c − i^{2} + 2i, then det(A(n)) = J_{n+1}.

(b. 4) if μ_{i} = (2^{i+1} + \frac{(i+1)(i−4)}{2}) c + \frac{(5−i)i}{2}, then det(A(n)) = P_{n+1}.

As mentioned previously, we have obtained some determinant representations of the sequences:

F = (F_{n+1})_{n⩾0}, L = (L_{n+1})_{n⩾0}, J = (J_{n+1})_{n⩾0} and P = (P_{n+1})_{n⩾0},

which are presented in the following:

\begin{matrix}( \begin{matrix}1 & 2 & 3 & ⋯ \\ c + 1 & 2c + 3 & 3c + 6 & ⋯ \\ 3c + 1 & 7c + 3 & 12c + 8 & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ∈ A_{F}, & ( \begin{matrix}1 & 2 & 3 & ⋯ \\ c + 1 & 2c + 5 & 3c + 10 & ⋯ \\ 3c + 1 & 9c + 13 & 16c + 30 & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ∈ A_{L}, \\ ( \begin{matrix}1 & 2 & 3 & ⋯ \\ c + 1 & 2c + 3 & 3c + 6 & ⋯ \\ 3c + 1 & 7c + 2 & 12c + 6 & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ∈ A_{J} and & ( \begin{matrix}1 & 2 & 3 & ⋯ \\ c + 1 & 2c + 4 & 3c + 8 & ⋯ \\ 3c + 1 & 8c + 5 & 14c + 13 & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ∈ A_{P}. \end{matrix}

2 Main results

As the first result of this paper, we consider the following theorem.

Theorem 1. For two arbitrary sequences (λ_{i})_{i⩾0} and (μ_{i})_{i⩾0}, with μ_{0} = 0, and some integers u and v, let A(∞) = [A_{i,j}]_{i,j⩾0} be an infinite dimensional matrix whose entries are given by

A_{i,j} = A_{i,j−1} + A_{i−1,j} − λ_{i−1} + μ_{i} − μ_{i−1} + (j − 1)(v − u), i, j ⩾ 1  (1)

and the initial conditions A_{i,0} = λ_{i} and A_{0,i} = λ_{0} + iu, i ⩾ 0. If A(n) = [A_{i,j}]_{0⩽i,j⩽n}, then we have

A(n) = L(n) · H(n) · U(n),  (2)

where

H(n) = ( λ̂_{0} u 0  ⋯  0 ; λ̂_{1} ; λ̂_{2} ; ⋮  T_{(μ̂_{1},μ̂_{2},μ̂_{3},...),(μ̂_{1},v,0,0,...)}(n − 1) ; λ̂_{n} ) .

Proof. First of all, we recall that the entries of L(n) = [L_{i,j}]_{0⩽i,j⩽n} satisfy the following recurrence

L_{i,j} = L_{i−1,j−1} + L_{i−1,j}, 1 ⩽ i, j ⩽ n.  (3)

Similarly, for the entries of U(n) = [U_{i,j}]_{0⩽i,j⩽n} we have

U_{i,j} = U_{i−1,j−1} + U_{i,j−1}, 1 ⩽ i, j ⩽ n.  (4)

In what follows, for convenience, we will let A = A(n), L = L(n), H = H(n) and U = U(n). Now, for the proof of the desired factorization we compute the (i, j)-entry of L · H · U, that is

(L · H · U)_{i,j} = ∑_{r=0}^{n} ∑_{s=0}^{n} L_{i,r}H_{r,s}U_{s,j}.  (5)

In fact, we should establish

\begin{aligned}R_{0}(L · H · U) & = R_{0}(A) = & (λ_{0}, λ_{0} + u, …, λ_{0} + nu), \\ C_{0}(L · H · U) & = C_{0}(A) = & (λ_{0}, λ_{1}, …, λ_{n}), \end{aligned}

and finally, show that

(L · H · U)_{i,j} = (L · H · U)_{i−1,j−1} + (L · H · U)_{i−1,j} − λ_{i−1} + μ_{i} − μ_{i−1} + (j − 1)(v − u), (6)

for 1 ⩽ i, j ⩽ n.

Let us do the required calculations. Assume first that i = 0. Then, we have

(L · H · U)_{0,j} = ∑_{r=0}^{n} ∑_{s=0}^{n} L_{0,r}H_{r,s}U_{s,j} = ∑_{s=0}^{n} H_{0,s}U_{s,j} = H_{0,0}U_{0,j} + H_{0,1}U_{1,j} = λ_{0} + ju,

and so R_{0}(L · H · U) = R_{0}(A) = (λ_{0}, λ_{0} + u, …, λ_{0} + nu). Assume next that j = 0. In this case, we obtain

(L · H · U)_{i,0} = ∑_{r=0}^{n} ∑_{s=0}^{n} L_{i,r}H_{r,s}U_{s,0} = ∑_{r=0}^{n} L_{i,r}H_{r,0} = ∑_{r=0}^{n} \binom{i}{r}λ̂_{r} = λ_{i},

and hence we have C_{0}(L · H · U) = C_{0}(A) = (λ_{0}, λ_{1}, …, λ_{n}).

Finally, we must establish (6). Let us for the moment assume that 1 ⩽ i, j ⩽ n. In this case, we have

(L · H · U)_{i,j} = ∑_{r=0}^{n} ∑_{s=0}^{n} L_{i,r}H_{r,s}U_{s,j} = ∑_{r=0}^{n} L_{i,r}H_{r,0}U_{0,j} + ∑_{r=0}^{n} ∑_{s=1}^{n} L_{i,r}H_{r,s}U_{s,j}.  (7)

Let Ω(i, j) = ∑_{r=0}^{n} ∑_{s=1}^{n} L_{i,r}H_{r,s}U_{s,j}. Then, using (4), we obtain

\begin{aligned}Ω(i, j) & = & ∑_{r=0}^{n} ∑_{s=1}^{n} L_{i,r}H_{r,s}(U_{s−1,j−1} + U_{s,j−1}) \\ & = & ∑_{r=0}^{n} ∑_{s=1}^{n} L_{i,r}H_{r,s}U_{s−1,j−1} + ∑_{r=0}^{n} ∑_{s=1}^{n} L_{i,r}H_{r,s}U_{s,j−1} \\ & = & ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i,r}H_{r,s}U_{s−1,j−1} + (L · H · U)_{i,j−1} \\ & & + ∑_{s=1}^{n} L_{i,0}H_{0,s}U_{s−1,j−1} − ∑_{r=0}^{n} L_{i,r}H_{r,0}U_{0,j−1} \end{aligned}  (8)

For convenience, we write Θ(i, j) = ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i,r}H_{r,s}U_{s−1,j−1}. Now, we apply (3), to get

Θ(i, j) = ∑_{r=1}^{n} ∑_{s=1}^{n} (L_{i−1,r−1} + L_{i−1,r})H_{r,s}U_{s−1,j−1}
= ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i−1,r−1}H_{r,s}U_{s−1,j−1} + ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i−1,r}H_{r,s}U_{s−1,j−1}
= ∑_{r=2}^{n} ∑_{s=2}^{n} L_{i−1,r−1}H_{r,s}U_{s−1,j−1} + ∑_{r=1}^{n} L_{i−1,r−1}H_{r,1}U_{0,j−1}

+ ∑_{s=2}^{n} L_{i−1,0}H_{1,s}U_{s−1,j−1} + ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i−1,r}H_{r,s}U_{s−1,j−1}

= ∑_{r=2}^{n} ∑_{s=2}^{n} L_{i−1,r−1}H_{r,s}U_{s−1,j−1} + ∑_{r=1}^{n} L_{i−1,r−1}H_{r,1}U_{0,j−1}

+ ∑_{s=2}^{n} L_{i−1,0}H_{1,s}U_{s−1,j−1} + ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i−1,r}H_{r,s}(U_{s,j} − U_{s,j−1}) (by (4))

= ∑_{r=2}^{n} ∑_{s=2}^{n} L_{i−1,r−1}H_{r−1,s−1}U_{s−1,j−1} + ∑_{r=1}^{n} L_{i−1,r−1}H_{r,1}U_{0,j−1}

+ ∑_{s=2}^{n} L_{i−1,0}H_{1,s}U_{s−1,j−1} + ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i−1,r}H_{r,s}U_{s,j}

− ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i−1,r}H_{r,s}U_{s,j−1} (by the structure of H)

= ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i−1,r}H_{r,s}U_{s,j−1} + ∑_{r=1}^{n} L_{i−1,r−1}H_{r,1}U_{0,j−1} + ∑_{s=2}^{n} L_{i−1,0}H_{1,s}U_{s−1,j−1}

+ ∑_{r=1}^{n} ∑_{s=0}^{n} L_{i−1,r}H_{r,s}U_{s,j} − ∑_{r=1}^{n} L_{i−1,r}H_{r,0}U_{0,j} − ∑_{r=1}^{n} ∑_{s=1}^{n} L_{i−1,r}H_{r,s}U_{s,j−1}

(note that L_{i−1,n−1} = U_{n−1,j−1} = 0)

= ∑_{r=1}^{n} L_{i−1,r−1}H_{r,1}U_{0,j−1} + ∑_{s=2}^{n} L_{i−1,0}H_{1,s}U_{s−1,j−1} + ∑_{r=0}^{n} ∑_{s=0}^{n} L_{i−1,r}H_{r,s}U_{s,j}

− ∑_{s=0}^{n} L_{i−1,0}H_{0,s}U_{s,j} − ∑_{r=1}^{n} L_{i−1,r}H_{r,0}U_{0,j}

= ∑_{r=1}^{n} L_{i−1,r−1}H_{r,1}U_{0,j−1} + ∑_{s=2}^{n} L_{i−1,0}H_{1,s}U_{s−1,j−1} + (L · H · U)_{i−1,j}

− ∑_{s=0}^{n} L_{i−1,0}H_{0,s}U_{s,j} − ∑_{r=1}^{n} L_{i−1,r}H_{r,0}U_{0,j} (by (5)).

By substituting this in (8), we obtain

Ω(i, j) = (L · H · U)_{i,j−1} + (L · H · U)_{i−1,j}

+ ∑_{r=1}^{n} L_{i−1,r−1}H_{r,1}U_{0,j−1} + ∑_{s=2}^{n} L_{i−1,0}H_{1,s}U_{s−1,j−1}

− ∑_{s=0}^{n} L_{i−1,0}H_{0,s}U_{s,j} − ∑_{r=1}^{n} L_{i−1,r}H_{r,0}U_{0,j}

+ ∑_{s=1}^{n} L_{i,0}H_{0,s}U_{s−1,j−1} − ∑_{r=0}^{n} L_{i,r}H_{r,0}U_{0,j−1}.

Finally, if the above expression is substituted in (7) and the sums are put together, then we obtain

(L · H · U)_{i,j} = (L · H · U)_{i−1,j} + (L · H · U)_{i,j−1} + Ψ(i, j),

where

Ψ(i, j) := ∑_{r=0}^{n} L_{i,r}H_{r,0}U_{0,j} + ∑_{r=1}^{n} L_{i−1,r−1}H_{r,1}U_{0,j−1} + ∑_{s=2}^{n} L_{i−1,0}H_{1,s}U_{s−1,j−1}

− ∑_{s=0}^{n} L_{i−1,0}H_{0,s}U_{s,j} − ∑_{r=1}^{n} L_{i−1,r}H_{r,0}U_{0,j} + ∑_{s=1}^{n} L_{i,0}H_{0,s}U_{s−1,j−1}

− ∑_{r=0}^{n} L_{i,r}H_{r,0}U_{0,j−1}.

However, by easy calculations one can show that

∑_{r=0}^{n} L_{i,r}H_{r,0}U_{0,j} − ∑_{r=0}^{n} L_{i,r}H_{r,0}U_{0,j−1} = 0,

∑_{r=1}^{n} L_{i−1,r−1}H_{r,1}U_{0,j−1} = ∑_{r=1}^{n} \binom{i−1}{r−1}μ̂_{r} = ∑_{r=1}^{n} (\binom{i}{r} − \binom{i−1}{r}) μ̂_{r} = μ_{i} − μ_{i−1},

∑_{r=1}^{n} L_{i−1,r}H_{r,0}U_{0,j} = ∑_{r=0}^{n} λ̂_{r} − λ_{0} = λ_{i−1} − λ_{0},

∑_{s=2}^{n} L_{i−1,0}H_{1,s}U_{s−1,j−1} = (j − 1)v,

∑_{s=0}^{n} L_{i−1,0}H_{0,s}U_{s,j} = λ_{0} + ju,

∑_{s=1}^{n} L_{i,0}H_{0,s}U_{s−1,j−1} = u,

and so

Ψ(i, j) = μ_{i} − μ_{i−1} − λ_{i−1} + (j − 1)(v − u).

This completes the proof.

Before stating the next result, we need to introduce some additional definitions. Let λ = (λ_{i})_{i⩾0} and μ = (μ_{i})_{i⩾0} be two arbitrary sequences. The convolution of λ and μ is the sequence ν = (ν_{i})_{i⩾0}, where

ν_{i} = ∑_{k=0}^{i} λ_{k}μ_{i−k}.

The convolution matrix associated with sequences λ and μ is the infinite matrix A(∞) whose first column C_{0}(A(∞)) is λ and whose jth column (j = 1, 2, …) is the convolution of sequences C_{j−1}(A(∞)) and μ. We say that the convolution matrix of the sequences λ and λ is the convolution matrix of the sequence λ. There are many well-known integer matrices which can be written as convolution matrices of some sequences. For instance, U(∞) is the convolution matrix of the sequences (1, 0, 0, …) and (1, 1, 0, 0, …) and P_{(1,1,...),(1,1,...)}(∞) is the convolution matrix of the sequence (1, 1, …).

We will need the following technical result [4, Theorem 3.1].

Proposition 2. Let

A(x) = ∑_{n=1}^{∞} a_{n}x^{n−1}, B(x) = ∑_{n=0}^{∞} b_{n}x^{n}, V (x) = ∑_{n=0}^{∞} v_{n}x^{n} and W (x) = ∑_{n=0}^{∞} w_{n}x^{n}

be the generating functions for the sequences (a_{n})_{n⩾1}, (b_{n})_{n⩾0}, (v_{n})_{n⩾0}, and (w_{n})_{n⩾0}, respectively. Consider an infinite dimensional matrix of the following form:

M(∞) = ( \begin{matrix}b_{0} & v_{0} & v_{0}w_{0} & ⋯ \\ b_{1} & v_{1} & v_{0}w_{1} + v_{1}w_{0} & ⋯ \\ b_{2} & v_{2} & v_{0}w_{2} + v_{1}w_{1} + v_{2}w_{0} & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} )

where C_{0}(M(∞)) = (b_{0}, b_{1}, …)^{t} and M(∞)^{[1]} is the convolution matrix of the sequences (v_{i})_{i⩾0} and (w_{j})_{j⩾0}. If

A(W (x)) = B(x)/V (x),  (9)

then for any non-negative integer n, there holds

det(M(n)) = (−1)^{n}v_{0}^{n+1}w_{1}^{n(n+1)/2}a_{n+1},

where M(n) is the (n + 1) × (n + 1) upper left corner matrix of M(∞).

We are now in a position to prove the following theorem which is the second result of this paper.

Theorem 3. Let A(n) be defined as in Theorem 1 and let c be a constant. In the case when u = v = 1 and λ_{i} = (2^{i} − 1)c + 1, we have the following statements:

(a) if μ_{i} = (2^{i} + \frac{(i−2)(i+1)}{2}) c − \frac{i(i−3)}{2}, then det(A(n)) = F_{n+1}.

(b) if μ_{i} = (\frac{5·3^{i}}{4} − 2^{i} − \frac{2i+1}{4}) c + \frac{5(3^{i}−1)}{4} + \frac{i}{2}, then det(A(n)) = L_{n+1}.

(c) if μ_{i} = i^{2}c − i^{2} + 2i, then det(A(n)) = J_{n+1}.

(d) if μ_{i} = (2^{i+1} + \frac{(i+1)(i−4)}{2}) c + \frac{(5−i)i}{2}, then det(A(n)) = P_{n+1}.

Proof. Let μ = (μ_{i})_{i⩾0} be a sequence with μ_{0} = 0 and let c be a constant. Let λ = (λ_{i})_{i⩾0} be a sequence with λ_{i} = (2^{i} − 1)c + 1. We consider the infinite matrices A(∞) = [A_{i,j}]_{i,j⩾0} whose entries satisfy

A_{i,j} = A_{i−1,j} + A_{i,j−1} − (2^{i} − 1)c − 1 + μ_{i} − μ_{i−1} for i, j ⩾ 1,  (10)

with the initial conditions A_{i,0} = (2^{i} − 1)c + 1 and A_{0,i} = 1 + i, i ⩾ 0. By Theorem 2, we observe that

A(n) = L(n) · H(n) · U(n),

where

H(n) = ( \begin{matrix}1 & 1 & 0 & ⋯ & 0 \\ c \\ c \\ ⋮ & & & T_{(μ̂_{1},μ̂_{2},μ̂_{3},...),(μ̂_{1},v,0,0,...)}(n − 1) \\ c \end{matrix} ) .

Evidently det(A(n)) = det(H(n)), so it suffices to find det(H(n)). From the structure of matrix H(∞), we have

C_{0}(H(∞)) = (b_{i})_{i⩾0} = (1, c, c, …)^{t},

whose generating function is

B(x) = \frac{1 + (c − 1)x}{1 − x}.

(a) Let μ_{i} = (2^{i}+ \frac{(i−2)(i+1)}{2})c− \frac{i(i−3)}{2}. In this case, we have the following infinite dimensional matrices:

A(∞) = ( \begin{matrix}1 & 2 & 3 & 4 & ⋯ \\ c + 1 & 2c + 3 & 3c + 6 & 4c + 10 & ⋯ \\ 3c + 1 & 7c + 3 & 12c + 8 & 18c + 17 & ⋯ \\ 7c + 1 & 17c + 2 & 32c + 8 & 53c + 23 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and

H(∞) = ( 1 1 0  ⋯  0 ; c ; c  T_{(c+1,2c−1,c,c,...),(c+1,1,0,0,...)}(∞) ; ⋮ ) .

Note that the submatrix H(∞)^{[1]} is the convolution of sequences

(v_{i})_{i⩾0} = (1, c + 1, 2c − 1, c, c, …), and (w_{i})_{i⩾0} = (0, 1, 0, 0, 0, …), whose generating functions are

V (x) = \frac{1 + cx + (c − 2)x^{2} − (c − 1)x^{3}}{1 − x} and W (x) = x,

respectively. Plugging these generating functions into (9) yields

A(W (x)) = A(x) = \frac{\frac{1+(c−1)x}{1−x}}{\frac{1+cx+(c−2)x^{2}−(c−1)x^{3}}{1−x}} = 1 − x + 2x^{2} − ⋯ + (−1)^{n}F_{n+1}x^{n} + ⋯, and it follows by Proposition 2 that

det(H(n)) = (−1)^{n}v_{0}^{n+1}w_{1}^{n(n+1)/2}a_{n+1} = (−1)^{n}a_{n+1} = F_{n+1},

as required.

(b) Let μ_{i} = (\frac{5·3^{i}}{4} − 2^{i} − \frac{2i+1}{4}) c + \frac{5(3^{i}−1)}{4} + \frac{i}{2}. The infinite dimensional matrices created in this case are as follows:

A(∞) = ( \begin{matrix}1 & 2 & 3 & 4 & ⋯ \\ c + 1 & 2c + 5 & 3c + 10 & 4c + 16 & ⋯ \\ 3c + 1 & 9c + 13 & 16c + 30 & 24c + 53 & ⋯ \\ 7c + 1 & 31c + 36 & 62c + 88 & 101c + 163 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and

H(∞) = ( 1 1 0  ⋯  0 ; c ; c  T_{(c+3,4c+5,9c+10,19c+20,...),(c+3,1,0,0,...)}(∞) ; ⋮ ) .

Again, one can easily see that the submatrix H(∞)^{[1]} is the convolution of sequences (v_{i})_{i⩾0} = (1, c + 3, 4c + 5, 9c + 10, 19c + 20, …), (with general form v_{0} = 1, v_{1} = c + 3 and v_{i} = (5 · 2^{i−2})(c + 1) − c for i ⩾ 2), and

(w_{i})_{i⩾0} = (0, 1, 0, 0, 0, …).

The generating functions for these sequences are

V (x) = \frac{(1 + (c − 1)x)(−x^{2} + x + 1)}{(1 − x)(1 − 2x)}, and W (x) = x,

respectively. If B(x), V (x) and W (x) are substituted in (9), then we obtain A(W (x)) = A(x) = \frac{\frac{1+(c−1)x}{1−x}}{\frac{(1+(c−1)x)(−x^{2}+x+1)}{(1−x)(1−2x)}} = 1 − 3x + 4x^{2} − 7x^{3} + ⋯ + (−1)^{n}L_{n+1}x^{n} + ⋯, and by Proposition 2, it follows that

det(H(n)) = (−1)^{n}v_{0}^{n+1}w_{1}^{n(n+1)/2}a_{n+1} = (−1)^{n}a_{n+1} = L_{n+1},

as required.

(c) Let μ_{i} = i^{2}c − i^{2} + 2i. In this case, we have the following infinite dimensional matrices:

A(∞) = ( \begin{matrix}1 & 2 & 3 & 4 & ⋯ \\ c + 1 & 2c + 3 & 3c + 6 & 4c + 10 & ⋯ \\ 3c + 1 & 7c + 2 & 12c + 6 & 18c + 14 & ⋯ \\ 7c + 1 & 16c − 1 & 30c + 1 & 50c + 11 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

and

H(∞) = ( 1 1 0  ⋯  0 ; c ; c  T_{(c+1,2c−2,0,0,...),(c+1,1,0,0,...)}(∞) ; ⋮ ) .

Moreover, from the structure of H(∞), we see that the submatrix H(∞)^{[1]} is the convolution of sequences

(v_{i})_{i⩾0} = (1, c + 1, 2c − 2, 0, 0, …), and (w_{i})_{i⩾0} = (0, 1, 0, 0, …), with generating functions V (x) = 1 + (c + 1)x + (2c − 2)x^{2} and W (x) = x, respectively. Substituting the obtained generating functions in (9), we obtain

A(W (x)) = A(x) = \frac{\frac{1+(c−1)x}{1−x}}{1 + (c + 1)x + (2c − 2)x^{2}} = 1−x+3x^{2} −⋯+(−1)^{n}J_{n+1}x^{n} +· · · .

Therefore, it follows from Proposition 2 that

det(H(n)) = (−1)^{n}v_{0}^{n+1}w_{1}^{n(n+1)/2}a_{n+1} = (−1)^{n}a_{n+1} = J_{n+1},

as required.

(d) Let μ_{i} = (2^{i+1} + \frac{(i+1)(i−4)}{2}) c + \frac{(5−i)i}{2}. This time, we will deal with the following matrices:

A(∞) = ( \begin{matrix}1 & 2 & 3 & 4 & ⋯ \\ c + 1 & 2c + 4 & 3c + 8 & 4c + 13 & ⋯ \\ 3c + 1 & 8c + 5 & 14c + 13 & 21c + 26 & ⋯ \\ 7c + 1 & 21c + 5 & 41c + 17 & 68c + 42 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and

H(∞) = ( 1 1 0 ⋯ 0 ; c ; c T_{(c+2,3c−1,2c,2c,...),(c+2,1,0,0,...)}(∞) ; ⋮ ) .

In addition, the submatrix H(∞)^{[1]} of H(∞) is the convolution of sequences:

(v_{i})_{i⩾0} = (1, c + 2, 3c − 1, 2c, 2c, …) and (w_{i})_{i⩾0} = (0, 1, 0, 0, …). Note that the generating functions of these sequences are

V (x) = \frac{1 + (1 + c)x + (2c − 3)x^{2} − (c − 1)x^{3}}{1 − x} and W (x) = x,

respectively. After having substituted these generating functions in (9), we obtain A(W (x)) = A(x) = \frac{\frac{1+(c−1)x}{1−x}}{\frac{1+(1+c)x+(2c−3)x^{2}−(c−1)x^{3}}{1−x}} = 1 − 2x + 5x^{2} − ⋯ + (−1)^{n}P_{n+1}x^{n} + · · · . Now, by Proposition 2, we deduce that

det(H(n)) = (−1)^{n}v_{0}^{n+1}w_{1}^{n(n+1)/2}a_{n+1} = (−1)^{n}a_{n+1} = P_{n+1},

as required. This completes the proof.

3 Some remarks

In this section, we will explain how the sequences (λ_{i})_{i⩾0} and (μ_{i})_{i⩾0} in Theorem 3, are determined. Consider the following lower Hessenberg matrix

H(∞) = [H_{i,j}]_{i,j⩾0} = ( \begin{matrix}h_{0,0} & h_{0,1} & 0 & 0 & 0 & ⋯ \\ h_{1,0} & h_{1,1} & h_{1,2} & 0 & 0 & ⋯ \\ h_{2,0} & h_{2,1} & h_{1,1} & h_{1,2} & 0 & ⋯ \\ h_{3,0} & h_{3,1} & h_{2,1} & h_{1,1} & h_{1,2} & ⋯ \\ h_{4,0} & h_{4,1} & h_{3,1} & h_{2,1} & h_{1,1} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Let H(n) = [H_{i,j}]_{0⩽i,j⩽n}, and let d_{n} be the nth determinant of H(n). In what follows, we show that the sequence of principal minors of H(∞), i.e., D(H(∞)) = (d_{n})_{n⩾0}, satisfies a recurrence relation.

Proposition 4. With the above notation, we have

d_{n} = \{ \begin{matrix}h_{0,0}, & if n = 0, \\ (−1)^{n}h_{0,1}(h_{1,2})^{n−1}h_{n,0} + ∑_{k=0}^{n−1} h_{n−k,1}(−h_{1,2})^{n−k−1}d_{k}, & if n ⩾ 1. \end{matrix}

Proof. Obviously, d_{0} = h_{0,0}. Hence, from now on we assume n > 1. First, we apply the following row operations:

H_{1}(n) = ( ∏_{i=1}^{n} O_{i,0}(\frac{−h_{i,1}}{h_{0,1}} ))H(n),
H_{2}(n) = ( ∏_{i=1}^{n−1} O_{i+1,1}(\frac{−h_{i,1}}{h_{1,2}} ))H_{1}(n),
H_{3}(n) = ( ∏_{i=1}^{n−2} O_{i+2,2}(\frac{−h_{i,1}}{h_{1,2}} ))H_{2}(n),
⋮
H_{n}(n) = ( ∏_{i=1}^{1} O_{i+(n−1),n−1}(\frac{−h_{i,1}}{h_{1,2}} ))H_{n−1}(n).

It is obvious that, step by step, the columns are “emptied” until finally the following matrix

H_{n}(n) = ( \begin{matrix}h̃_{0,0} & h_{0,1} & 0 & 0 & 0 & ⋯ & 0 \\ h̃_{1,0} & 0 & h_{1,2} & 0 & 0 & ⋯ & 0 \\ h̃_{2,0} & 0 & 0 & h_{1,2} & 0 & ⋯ & 0 \\ h̃_{3,0} & 0 & 0 & 0 & h_{1,2} & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ h̃_{n−1,0} & 0 & 0 & 0 & 0 & ⋯ & h_{1,2} \\ h̃_{n,0} & 0 & 0 & 0 & 0 & ⋯ & 0 \end{matrix} )_{(n+1)×(n+1)} ,

is obtained, where

h̃_{i,0} = \{ \begin{matrix}h_{0,0}, & if & i = 0; \\ h_{1,0} − \frac{h_{1,1}}{h_{0,1}} h_{0,0}, & if & i = 1; \\ h_{i,0} − \frac{h_{i,1}}{h_{0,1}} h_{0,0} − \frac{1}{h_{1,2}} ∑_{k=1}^{i−1} h_{i−k,1}h̃_{k,0}, & if & i ⩾ 2. \end{matrix}  (11)

Evidently, d_{n} = det(H_{n}(n)). Expanding the determinant along the last row of det(H_{n}(n)), we obtain

d_{n} = (−1)^{n}h̃_{n,0}h_{0,1}(h_{1,2})^{n−1}, (n ⩾ 1).  (12)

Finally, after some simplification, it follows that

d_{n} = (−1)^{n}h̃_{n,0}h_{0,1}(h_{1,2})^{n−1}
= (−1)^{n}h_{0,1}(h_{1,2})^{n−1} [h_{n,0} − \frac{h_{n,1}}{h_{0,1}} h_{0,0} − \frac{1}{h_{1,2}} ∑_{k=1}^{n−1} h_{n−k,1}h̃_{k,0}] (by (11))
= (−1)^{n}h_{0,1}(h_{1,2})^{n−1}h_{n,0} + (−1)^{n+1}(h_{1,2})^{n−1}h_{n,1}h_{0,0}

+(−1)^{n+1}h_{0,1}(h_{1,2})^{n−2} ∑_{k=1}^{n−1} h_{n−k,1}h̃_{k,0}

= (−1)^{n}h_{0,1}(h_{1,2})^{n−1}h_{n,0} + (−1)^{n+1}(h_{1,2})^{n−1}h_{n,1}h_{0,0}

+ ∑_{k=1}^{n−1} h_{n−k,1}(−h_{1,2})^{n−k−1}d_{k} (by (12))

= (−1)^{n}h_{0,1}(h_{1,2})^{n−1}h_{n,0} + ∑_{k=0}^{n−1} h_{n−k,1}(−h_{1,2})^{n−k−1}d_{k}.

and the result follows.

In Proposition 4, if we take h_{0,0} = h_{0,1} = 1, h_{1,2} = 1, h_{i,0} = c and h_{i,1} = μ̂_{i} for i ⩾ 1, then we obtain

d_{n} = \{ \begin{matrix}1, & if & n = 0; \\ (−1)^{n}c + ∑_{k=0}^{n−1} μ̂_{n−k}(−1)^{n−k−1}d_{k}, & if & n ⩾ 1. \end{matrix}

Now, if (d_{n})_{n⩾0} ∈ {F, L, J , P}, then

μ̂_{n} = c + (−1)^{n−1}d_{n} + ∑_{k=1}^{n−1}(−1)^{k+1}μ̂_{n−k}d_{k},

from which we determine the sequence (μ̂_{i})_{i⩾1}. Now, we form

H(∞) = ( \begin{matrix}1 & 1 & 0 & ⋯ \\ c \\ c \\ ⋮ & & & T_{(μ̂_{1},μ̂_{2},μ̂_{3},...),(μ̂_{1},1,0,0,...)}(∞) \\ c \end{matrix} ) .

Finally, the sequences (λ_{i})_{i⩾0} and (μ_{i})_{i⩾0} are determined by the equation A(n) = L(n) · H(n) · U(n).

4 Acknowledgement

Our special thanks go to the Research Institute for Fundamental Sciences, Tabriz, Iran, for having sponsored this paper.

References

[1] A. R. Moghaddamfar and S. M. H. Pooya, Generalized Pascal triangles and Toeplitz matrices, Electron. J. Linear Algebra, 18 (2009), 564–588.

[2] A. R. Moghaddamfar and H. Tajbakhsh, Lucas numbers and determinants, Integers, 12 (2012), 21–51.

[3] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically

   at http://oeis.org, 2013.

[4] Y. Yang and M. Leonard, Evaluating determinants of convolution-like matrices via generating functions, Int. J. Inf. Syst. Sci., 3 (2007), 569–580.

2010 Mathematics Subject Classification: Primary 11C20; Secondary 15B36, 10A35. Keywords: determinant, generalized Pascal triangle, Toeplitz matrix, matrix factorization, convolution matrix, lower Hessenberg matrix.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000129}, and \underline{A001045}.)

Received December 3 2013; revised version received March 2 2014. Published in Journal of Integer Sequences, March 26 2014.

Return to Journal of Integer Sequences home page.