Some Toeplitz-Hessenberg Determinant Identities for the Tetranacci Numbers

Taras Goy Faculty of Mathematics and Computer Science Vasyl Stefanyk Precarpathian National University Ivano-Frankivsk Ukraine

                  tarasgoy@yahoo.com

Mark Shattuck^{1} Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

                 shattuck@math.utk.edu

Abstract

In this paper, we consider families of Toeplitz-Hessenberg determinants the entries of which are tetranacci numbers. In several cases, it is found that these determinants have simple closed form expressions in terms of well-known combinatorial sequences. Equivalently, the determinant formulas may be expressed as identities involving sums of products of tetranacci numbers and multinomial coefficients. In particular, we establish a connection between the tetranacci and both the Fibonacci and tribonacci number sequences via Toeplitz-Hessenberg determinants. Finally, combinatorial proofs that make use of sign-changing involutions and the formal definition of the determinant as a signed sum over the permutation group may be provided for several of the identities.

1Corresponding author.

1 Introduction

Over the years many generalizations of the Fibonacci numbers have been studied; see, for instance, [16] for a complete bibliography. Among the best known of these are the k-generalized Fibonacci numbers F_{n}^{(k)} satisfying the k-th order recurrence

F_{n}^{(k)} = F_{n−1}^{(k)} + F_{n−2}^{(k)} + ⋯ + F_{n−k}^{(k)},  n ≥ k,  (1)

with initial values

F_{0}^{(k)} = F_{1}^{(k)} = ⋯ = F_{k−2}^{(k)} = 0, F_{k−1}^{(k)} = 1.

These numbers are also known as Fibonacci k-sequences, generalized Fibonacci numbers of order k, Fibonacci k-step numbers, and k-bonacci numbers.

By subtraction, equation (1) is equivalent to the (k + 1)-st order recurrence F_{n}^{(k)} = 2F_{n−1}^{(k)} − F_{n−k−1}^{(k)} for all n ≥ k + 1. The F_{n}^{(k)} may be computed directly using the following “Binet-like” formula [10]

F_{n}^{(k)} = ∑_{i=1}^{k} \frac{(α_{i} − 1)α_{i}^{n−k+1}}{2 + (k + 1)(α_{i} − 2)}, n ≥ k − 1,

where α_{1}, …, α_{k} are the roots of x^{k} −x^{k−1}−⋯−x−1 = 0. The F_{n}^{(k)} are also given explicitly by the multinomial summation formula [24]

F_{n}^{(k)} = ∑_{\begin{matrix}i_{1},...,i_{k}≥0 \\ i_{1}+2i_{2}+···+ki_{k}=n−k+1 \end{matrix}} \binom{i_{1} + i_{2} + ⋯ + i_{k}}{i_{1}, i_{2}, …, i_{k}}.

The cases of F_{n}^{(k)} for 2 ≤ k ≤ 6 are known as the Fibonacci, tribonacci, tetranacci, pentanacci, and hexanacci numbers (and so on for larger k), and are denoted by F_{n}, T_{n}, t_{n}, p_{n}, and h_{n}, respectively. In this paper, we focus primarily on various combinatorial aspects of t_{n}, including a connection to both F_{n} and T_{n}. The sequences F_{n}, T_{n}, t_{n}, p_{n}, and h_{n} are indexed in the On-Line Encyclopedia of Integer Sequences [26], the first few terms of which are given below (see also entries \underline{A122189}, \underline{A079262}, \underline{A104144}):

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Seq. in [26]
F_{n} 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 \underline{A000045}
T_{n} 0 0 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 \underline{A000073}
t_{n} 0 0 0 1 1 2 4 8 15 29 56 108 208 401 773 1490 \underline{A000078}
p_{n} 0 0 0 0 1 1 2 4 8 16 31 61 120 236 464 912 \underline{A001591}
h_{n} 0 0 0 0 0 1 1 2 4 8 16 32 63 125 248 492 \underline{A001592}

In addition to their significance in combinatorics, the numbers F_{n}^{(k)} have applications to a wide variety of research areas such as physics [25], sorting algorithms [15], graph theory [2], coding theory [3, 18], and probability [9]. See also [1, 4, 5, 10, 12, 14, 22, 24] and references contained therein.

In the present paper, we investigate determinants of some families of Toeplitz-Hessenberg matrices whose entries belong to the tetranacci sequence and have successive, odd or even subscripts. Recall that the tetranacci numbers t_{n} = F_{n}^{(4)} are defined recursively by

t_{n} = t_{n−1} + t_{n−2} + t_{n−3} + t_{n−4}, n ≥ 4,

with t_{0} = t_{1} = t_{2} = 0 and t_{3} = 1. This sequence has been studied in its own right by several authors; see, for example, [13, 17, 27, 28].

The organization of this paper is as follows. In the next section, we introduce notation and remind the reader of some preliminary results. The subsequent two sections feature our main results concerning determinants of Toeplitz-Hessenberg matrices having tetranacci number entries, and extensions of several of the identities to F_{n}^{(k)} are observed. In the fifth section, multi-sum versions of the identities are presented that involve products of multinomial coefficients and powers of tetranacci numbers. In the final section, we provide combinatorial proofs of most of the preceding tetranacci determinant identities using a common tiling approach.

2 Toeplitz-Hessenberg matrices and determinants

A lower Hessenberg matrix H_{n} = (h_{ij}) is an n × n matrix whose entries above the superdiagonal are all zero, i.e.,

H_{n} = ( \begin{matrix}h_{11} & h_{12} & 0 & ⋯ & 0 & 0 \\ h_{21} & h_{22} & h_{23} & ⋯ & 0 & 0 \\ h_{31} & h_{32} & h_{33} & ⋯ & 0 & 0 \\ ⋯ & ⋯ & ⋯ & ... & ⋯ & ⋯ \\ h_{n−1,1} & h_{n−1,2} & h_{n−1,3} & ⋯ & h_{n−1,n−1} & h_{n−1,n} \\ h_{n1} & h_{n2} & h_{n3} & ⋯ & h_{n,n−1} & h_{nn} \end{matrix} ) .

Hessenberg matrices play an important role in both computational and applied mathematics (see, for example, [8, 19] and references therein). Perhaps one of the reasons for this is that det(H_{n}) may be calculated quickly using the recurrence [7]

det(H_{n}) = h_{nn} det(H_{n−1}) + ∑_{k=1}^{n−1}(−1)^{n−k}h_{nk} det(H_{k−1}) ∏_{i=k}^{n−1} h_{i,i+1},  n ≥ 1,  (2)

where, by definition, det(H_{0}) = 1.

With the special choice h_{ij} = a_{i−j+1} for all i and j, i.e., on each diagonal all the elements are the same, we have the Toeplitz-Hessenberg matrix

M_{n}(a_{0}; a_{1}, …, a_{n}) = ( \begin{matrix}a_{1} & a_{0} & 0 & ⋯ & 0 & 0 \\ a_{2} & a_{1} & a_{0} & ⋯ & 0 & 0 \\ a_{3} & a_{2} & a_{1} & ⋯ & 0 & 0 \\ ⋯ & ⋯ & ⋯ & ... & ⋯ & ⋯ \\ a_{n−1} & a_{n−2} & a_{n−3} & ⋯ & a_{1} & a_{0} \\ a_{n} & a_{n−1} & a_{n−2} & ⋯ & a_{2} & a_{1} \end{matrix} ) ,

where a_{0} ≠ 0 is assumed. Then, from (2), we obtain

det(M_{n}) = ∑_{k=1}^{n}(−a_{0})^{k−1}a_{k} det(M_{n−k}),  n ≥ 1,  (3)

with det(M_{0}) = 1.

We investigate particular cases of Toeplitz-Hessenberg matrices in which the superdiagonal element a_{0} is equal ±1. To simplify our notation, we write det(a_{0}; a_{1}, …, a_{n}) in place of det (M_{n}(a_{0}; a_{1}, …, a_{n})).

In proving the identities below, we determine a generating function (gf) formula for the sequence (det(M_{n}))_{n≥1} in question. Let

g(x) = ∑_{i≥1}(−a_{0})^{i−1}a_{i}x^{i} and f(x) = ∑_{n≥1} det(a_{0}; a_{1}, …, a_{n})x^{n}.

Then recurrence (3) may be expressed equivalently in terms of gf’s as

f(x) = \frac{g(x)}{1 − g(x)}.  (4)

Thus, it suffices to compute the gf for the sequence (a_{i})_{i≥1}. We find in several instances below where a_{i} corresponds to some translate of the tetranacci sequence (or half-sequence) that the n-th coefficient of f(x) assumes a particularly simple form.

3 Fibonacci and tribonacci numbers via tetranacci determinants

The next theorem provides a couple of connections between tetranacci and Fibonacci numbers in terms of Toeplitz-Hessenberg determinants.

Theorem 1. The following formulas hold:

det(1; t_{2}, t_{3}, …, t_{n+1}) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix}(−1)^{n−i}F_{n−2i+1}  (5)

= \begin{cases}F_{\frac{n−1}{2}} F_{\frac{n+1}{2}} , & if n is odd; \\ −(F_{n/2})^{2}, & if n is even, \end{cases}  n ≥ 1,  (6)
det(1; t_{5}, t_{7}, …, t_{2n+3}) = (−1)^{n−1}F_{n+2},  n ≥ 3.  (7)

Proof. First note that by standard methods, we have

∑_{n≥3} t_{n}x^{n} = \frac{x^{3}}{1 − x(1 + x + x^{2} + x^{3})},  (8)

which implies

g(x) = ∑_{n≥1} t_{n+1}(−1)^{n−1}x^{n} = −\frac{x^{2}}{1 + x(1 − x + x^{2} − x^{3})}.

By (4), we then have

∑_{n≥1} det(1; t_{2}, t_{3}, …, t_{n+1})x^{n} = \frac{g(x)}{1 − g(x)} = −\frac{x^{2}}{1 + x(1 + x^{2} − x^{3})}.

On the other hand,

∑_{n≥1} x^{n} (\begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix}(−1)^{n−i}F_{n−2i+1}) = ∑_{i≥1}(−1)^{i} ∑_{n≥2i} F_{n−2i+1}(−x)^{n}

= ∑_{i≥1}(−1)^{i}(−x)^{2i−1} ∑_{n≥1} F_{n}(−x)^{n} = \frac{x}{1 + x^{2}} · \frac{−x}{1 + x − x^{2}} = −\frac{x^{2}}{1 + x + x^{3} − x^{4}} ,

as before, which implies (5). The expression (6) follows from (5) and considering the underlying gf in each of the identities (26)–(29) from [6]. A proof similar to that given for (5) applies to (7) wherein one considers the even part of ∑_{n≥1} t_{n+3}x^{n}, the details of which we leave to the reader.

A proof comparable to the one given for Theorem 1 yields the following relation between tetranacci and tribonacci numbers.

Theorem 2. For all n ≥ 2,

det(1; t_{0}, t_{1}, …, t_{n−1}) = (−1)^{n−1}T_{n−2}.  (9)

4 Some Toeplitz-Hessenberg determinants with tetranacci entries

In this section, we feature the determinants of several Toeplitz-Hessenberg matrices whose entries are tetranacci numbers with consecutive, even or odd subscripts.

Theorem 3. Let n ≥ 1, except when noted otherwise. Then

det(−1; t_{0}, t_{1}, …, t_{n−1}) = (−1)^{⌊n/2⌋} · \frac{2 + (−1)^{n}}{10} + \frac{5(−1)^{n} + 2^{n}}{30}  (10)

= ∑_{i=1}^{n−3}(−1)^{i}(1 − 2^{n−i−2}) − \begin{matrix}⌊ & \frac{n−2}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix}(−1)^{i}(1 − 2^{n−2i−2}),  (11)

det(−1; t_{1}, t_{2}, …, t_{n}) = \begin{matrix}⌊ & \frac{n−3}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix} ∑_{j=0}^{n−2i−3} \binom{n − 3 − i − j}{i}\binom{2i}{j},  (12)

det(1; t_{3}, t_{4}, …, t_{n+2}) = (−1)^{n−1} \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix} \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{j}{2i + 3j − n + 1}\binom{2i + 3j − n + 1}{i}, (13)
det(1; t_{4}, t_{5}, …, t_{n+3}) = 0,  n ≥ 5,  (14)
det(1; t_{5}, t_{6}, …, t_{n+4}) = \frac{1 + (−1)^{⌊n/2⌋}}{2} ,  n ≥ 2,  (15)

det(1; t_{1}, t_{3}, …, t_{2n−1})

= \frac{\sqrt{17}}{17} ((4 + \sqrt{17}) (\frac{−3 − \sqrt{17}}{2})^{n−3} − (4 − \sqrt{17}) (\frac{−3 + \sqrt{17}}{2})^{n−3}) , n ≥ 3, (16)

det(1; t_{0}, t_{2}, …, t_{2n−2})

= \frac{\sqrt{21}}{42} ((5 + \sqrt{21}) (\frac{−3 − \sqrt{21}}{2})^{n−3} − (5 − \sqrt{21}) (\frac{−3 + \sqrt{21}}{2})^{n−3}) , n ≥ 3, (17)

det(1; t_{6}, t_{8}, …, t_{2n+4}) = 1,  n ≥ 4.  (18)

Proof. We provide proofs of formulas (12), (13), (15), and (16). Adapting the featured proofs will yield the remaining identities, the details of which we leave to the reader. First note that from (8), we have

g(x) = ∑_{n≥1}(−a)^{n−1}t_{n}x^{n} = \frac{a^{2}x^{3}}{1 + ax − (ax)^{2} + (ax)^{3} − (ax)^{4}} .  (19)

Let f(x) denote the gf for the determinant expression on the left side in each of the identities (12), (13), (15), and (16). We now show (12). Taking a = −1 in (19) implies

f(x) = ∑_{n≥1} det(−1; t_{1}, t_{2}, …, t_{n})x^{n} = \frac{g(x)}{1 − g(x)} = \frac{x^{3}}{1 − x − x^{2} − 2x^{3} − x^{4}} .

On the other hand, the right side of (12) has gf given by

∑_{n≥3} x^{n} ∑_{i=0}^{⌊ \frac{n−3}{2} ⌋} ∑_{j=0}^{n−2i−3} \binom{n − 3 − i − j}{i}\binom{2i}{j} = ∑_{i≥0} ∑_{j≥0} \binom{2i}{j} ∑_{n≥2i+j+3} \binom{n − 3 − i − j}{i}x^{n}

= ∑_{i≥0} ∑_{j≥0} \binom{2i}{j}x^{i+j+3} ∑_{n≥i} \binom{n}{i}x^{i} = ∑_{i≥0} ∑_{j=0}^{2i} \binom{2i}{j}x^{i+j+3} · \frac{x^{i}}{(1 − x)^{i+1}}

= ∑_{i≥0} \frac{x^{2i+3}}{(1 − x)^{i+1}} · (1 + x)^{2i} = \frac{x^{3}}{1 − x} · \frac{1}{1 − \frac{x^{2}(1+x)^{2}}{1−x}} = \frac{x^{3}}{1 − x − x^{2} − 2x^{3} − x^{4}} ,

as before.

For (13), note that taking a = 1 in (19) yields

∑_{n≥1} t_{n+2}(−1)^{n−1}x^{n} = \frac{1}{x^{2}} ∑_{n≥3} t_{n}(−1)^{n−1}x^{n} = \frac{x}{1 + x − x^{2} + x^{3} − x^{4}} ,

and thus f(x) = \frac{x}{1−x^{2}+x^{3}−x^{4}} , by (4). As for the right-hand side of (13), first note that one may assume 0 ≤ i ≤ j in the sum and thus may write

\begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix} \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{j}{2i + 3j − n + 1}\binom{2i + 3j − n + 1}{i} = \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} ∑_{i=0}^{j} \binom{j}{i}\binom{j − i}{i + 3j − n + 1}.

Multiplying this last expression by (−1)^{n−1}x^{n}, summing over n ≥ 1, and interchanging summation gives

− ∑_{j≥0} ∑_{i=0}^{j} \binom{j}{i} ∑_{n≥1} \binom{j − i}{n − 1 − 2i − 2j}(−x)^{n} = − ∑_{j≥0} ∑_{i=0}^{j} \binom{j}{i}(−x)^{2j+2i+1} ∑_{n≥0} \binom{j − i}{n}(−x)^{n}

= ∑_{j≥0} ∑_{i=0}^{j} \binom{j}{i}x^{2j+2i+1} · (1 − x)^{j−i} = ∑_{j≥0} x^{2j+1} ∑_{i=0}^{j} \binom{j}{i}x^{2i}(1 − x)^{j−i}

= ∑_{j≥0} x^{2j+1} · (1 − x + x^{2})^{j} = \frac{x}{1 − x^{2}(1 − x + x^{2})},

as before.

For (15), first observe that

∑_{n≥1} t_{n+4}x^{n} = \frac{1}{x^{4}} ∑_{n≥5} t_{n}x^{n} = \frac{1}{x^{4}} (\frac{x^{3}}{1 − x(1 + x + x^{2} + x^{3})} − x^{3} − x^{4})

= \frac{(1 + x)(1 + x + x^{2} + x^{3}) − 1}{1 − x(1 + x + x^{2} + x^{3})}.

This gives

∑_{n≥1} t_{n+4}(−1)^{n−1}x^{n} = \frac{1 − (1 − x)(1 − x + x^{2} − x^{3})}{1 + x(1 − x + x^{2} − x^{3})},

and thus by (4),

f(x) = ∑_{n≥1} det(1; t_{5}, t_{6}, …, t_{n+4})x^{n} = \frac{1 − (1 − x)(1 − x + x^{2} − x^{3})}{1 − x + x^{2} − x^{3}}

= \frac{(2x − 2x^{2} + 2x^{3} − x^{4})(1 + x)}{1 − x^{4}}

= \frac{2x + x^{4} − x^{5}}{1 − x^{4}} = (2x + x^{5} + x^{9} + x^{13} + ⋯) + (x^{4} + x^{8} + x^{12} + ⋯) .

Extracting the coefficient of x^{n} for n ≥ 2 in the last expression yields (15). Finally, for (16), note that taking the odd part of the gf formula

∑_{n≥1} t_{n}x^{n} = \frac{x^{3}(1 − x)}{1 − 2x + x^{5}}

gives

∑_{n≥1} t_{2n−1}x^{2n−1} = \frac{1}{2} (\frac{x^{3}(1 − x)}{1 − 2x + x^{5}} + \frac{x^{3}(1 + x)}{1 + 2x − x^{5}} ) = \frac{x^{3} − 2x^{5} + x^{9}}{1 − 4x^{2} + 4x^{6} − x^{10}} ,

whence

∑_{n≥1} t_{2n−1}x^{n} = \frac{x^{2} − 2x^{3} + x^{5}}{1 − 4x + 4x^{3} − x^{5}} .

Then by (4),

∑_{n≥1} det(1; t_{1}, t_{3}, …, t_{2n−1})x^{n} = −\frac{x^{2} + 2x^{3} − x^{5}}{1 + 4x + x^{2} − 2x^{3}} ,

and thus

∑_{n≥3} det(1; t_{1}, t_{3}, …, t_{2n−1})x^{n} = \frac{2x^{3} + x^{4} − x^{5}}{1 + 4x + x^{2} − 2x^{3}} = \frac{x^{3}(2 − x)}{1 + 3x − 2x^{2}} .

On the other hand, a straightforward calculation gives

\frac{\sqrt{17}}{17} ((4 + \sqrt{17}) ∑_{n≥3} (\frac{−3 − \sqrt{17}}{2})^{n−3} x^{n} − (4 − \sqrt{17}) ∑_{n≥3} (\frac{−3 + \sqrt{17}}{2})^{n−3} x^{n})

= \frac{2x^{3} − x^{4}}{1 + 3x − 2x^{2}} ,

which implies (16).

Remark 4. Extensions of formulas (9), (10), and (13) above in terms of the generalized Fibonacci numbers F_{n}^{(k)} were given in [11] where combinatorial proofs are provided. When k = 4 in the extensions of (10) and (13), one gets equivalently ⌊\frac{2^{n}+14}{30}⌋ for the right side of (10) and (−1)^{n−1}q_{n} for the right side of (13), where q_{n} is the sequence defined recursively by q_{n} = q_{n−2} + q_{n−3} + q_{n−4} for n ≥ 4, with initial conditions q_{0} = 0, q_{1} = 1, q_{2} = 0, q_{3} = 1. The equivalence between q_{n} and the binomial expression above will be apparent with the combinatorial proof of (13) given in the final section.

Furthermore, generalizing the combinatorial proof yields the following extension of (7) in terms of F_{n}^{(k)} for k ≥ 3:

(−1)^{n−1} det (1; F_{k+1}^{(k)}, F_{k+3}^{(k)}, …, F_{2n+k−1}^{(k)})

= \begin{cases}∑_{i=1}^{\frac{k}{2}} iF (\frac{k}{2})_{n−i+ \frac{k−2}{2}} + ∑_{i=1}^{\frac{k−2}{2}} iF (\frac{k}{2})_{n+i− \frac{k+2}{2}} , & if n ≥ k − 1, k even; \\ ∑_{i=1}^{\frac{k+1}{2}} iF (\frac{k−1}{2})_{n−i+ \frac{k−3}{2}} + ∑_{i=1}^{\frac{k−1}{2}} iF (\frac{k−1}{2})_{n+i− \frac{k+3}{2}} , & if n ≥ k, k odd. \end{cases} (20)

Taking k = 4 in (20) gives (7), while taking k = 3 gives det(1; T_{4}, T_{6}, …, T_{2n+2}) = 4(−1)^{n−1} for n ≥ 3, which occurs in [11]. Finally, the combinatorial argument for formula (14) may be readily generalized to yield

det (1; F_{k}^{(k)}, F_{k+1}^{(k)}, …, F_{n+k−1}^{(k)}) = 0,  n ≥ k + 1.  (21)

5 Applications by Trudi’s formula

In this section, we consider multinomial versions of Theorems 1–3 above using the following result, known as Trudi’s formula. See, for example, [20, Theorem 1] and [21].

Lemma 5. Let n be a positive integer. Then

det(M_{n}) = ∑_{\begin{matrix}s_{1},...,s_{n}≥0 \\ s_{1}+2s_{2}+···+ns_{n}=n \end{matrix}} \binom{s_{1} + ⋯ + s_{n}}{s_{1}, …, s_{n}}(−a_{0})^{n−s_{1}−···−s_{n}}a_{1}^{s_{1}}a_{2}^{s_{2}} ⋯ a_{n}^{s_{n}}  (22)

or, equivalently,

det(M_{n}) = ∑_{k=1}^{n}(−a_{0})^{n−k} ∑_{\begin{matrix}i_{1},...,i_{k}≥1 \\ i_{1}+i_{2}+···+i_{k}=n \end{matrix}} a_{i_{1}}a_{i_{2}} ⋯ a_{i_{k}}.

The case a_{0} = 1 of Trudi’s formula is known as Brioschi’s formula [23]. Note that the sum in (22) may be regarded as being over the set of partitions of the positive integer n.

We may use Trudi’s formula to obtain some new tetranacci identities involving multinomial coefficients. Formula (22), when taken together with Theorems 1–3 above, yields the following identities.

Corollary 6. Let n ≥ 1, except when noted otherwise, and let σ_{n} = s_{1} + 2s_{2} + ⋯ + ns_{n}, |s| = s_{1} + s_{2} + ⋯ + s_{n}, and m_{n}(s) = \binom{s_{1}+···+s_{n}}{s_{1},...,s_{n}} where s_{i} ≥ 0 for all i. Then

∑_{σ_{n}=n}(−1)^{|s|}m_{n}(s)t_{2}^{s_{1}}t_{3}^{s_{2}} ⋯ t_{n+1}^{s_{n}} = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix}(−1)^{i}F_{n−2i+1},
∑_{σ_{n}=n}(−1)^{|s|}m_{n}(s)t_{5}^{s_{1}}t_{7}^{s_{2}} ⋯ t_{2n+3}^{s_{n}} = −F_{n+2},  n ≥ 3,
∑_{σ_{n}=n}(−1)^{|s|}m_{n}(s)t_{0}^{s_{1}}t_{1}^{s_{2}} ⋯ t_{n−1}^{s_{n}} = −T_{n−2},  n ≥ 2,

∑_{σ_{n}=n} m_{n}(s)t_{0}^{s_{1}}t_{1}^{s_{2}} ⋯ t_{n−1}^{s_{n}} = (−1)^{⌊n/2⌋} · \frac{2 + (−1)^{n}}{10} + \frac{5(−1)^{n} + 2^{n}}{30} ,

∑_{σ_{n}=n} m_{n}(s)t_{1}^{s_{1}}t_{2}^{s_{2}} ⋯ t_{n}^{s_{n}} = \begin{matrix}⌊ & \frac{n−3}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix} ∑_{j=0}^{n−2i−3} \binom{n − 3 − i − j}{i}\binom{2i}{j},

∑_{σ_{n}=n}(−1)^{|s|}m_{n}(s)t_{3}^{s_{1}}t_{4}^{s_{2}} ⋯ t_{n+2}^{s_{n}} = − \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix} \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{j}{2i + 3j − n + 1}\binom{2i + 3j − n + 1}{i},
∑_{σ_{n}=n}(−1)^{|s|}m_{n}(s)t_{4}^{s_{1}}t_{5}^{s_{2}} ⋯ t_{n+3}^{s_{n}} = 0,  n ≥ 5,

∑_{σ_{n}=n}(−1)^{|s|}m_{n}(s)t_{5}^{s_{1}}t_{6}^{s_{2}} ⋯ t_{n+4}^{s_{n}} = \frac{(−1)^{n} + (−1)^{⌊3n/2⌋}}{2} ,  n ≥ 2,

∑_{σ_{n}=n}(−1)^{|s|}m_{n}(s)t_{1}^{s_{1}}t_{3}^{s_{2}} ⋯ t_{2n−1}^{s_{n}}

= \frac{\sqrt{17}}{17} ((4 − \sqrt{17}) (\frac{3 − \sqrt{17}}{2})^{n−3} − (4 + \sqrt{17}) (\frac{3 + \sqrt{17}}{2})^{n−3}) , n ≥ 3,

∑_{σ_{n}=n}(−1)^{|s|}m_{n}(s)t_{0}^{s_{1}}t_{2}^{s_{2}} ⋯ t_{2n−2}^{s_{n}}

= \frac{\sqrt{21}}{42} ((5 − \sqrt{21}) (\frac{3 − \sqrt{21}}{2})^{n−3} − (5 + \sqrt{21}) (\frac{3 + \sqrt{21}}{2})^{n−3}) , n ≥ 3,

∑_{σ_{n}=n}(−1)^{|s|}m_{n}(s)t_{6}^{s_{1}}t_{8}^{s_{2}} ⋯ t_{2n+4}^{s_{n}} = (−1)^{n}, n ≥ 4.

6 Combinatorial proofs

Recall that the determinant of an n × n matrix A = (a_{i,j}) is given by

det(A) = ∑_{σ∈S_{n}}(−1)^{sgn(σ)}a_{1,σ(1)}a_{2,σ(2)} ⋯ a_{n,σ(n)},

where S_{n} is the set of permutations σ of size n and sgn(σ) denotes the sign of σ. Assume permutations are expressed in the standard cycle form; i.e., the smallest element is first in each cycle with cycles arranged from left to right in increasing order of first elements. In the case when A is Toeplitz-Hessenberg, the only permutations σ making a potentially nonzero contribution towards the determinant are those in which each cycle comprises a set of consecutive integers in increasing order. Note that otherwise the product corresponding to σ would contain an a_{i,j} factor for some j > i + 1.

If P_{n} denotes the set of all such permutations σ of length n, then one may replace S_{n} by P_{n} in the definition of det(A) above when A is Toeplitz-Hessenberg. Recall that a composition of n is a sequence of positive integers, called parts, whose sum is n. Note that σ ∈ P_{n} may be regarded as a composition ρ of n, upon identifying the sequence of cycle lengths as a sequence of parts. Assume that the sign of ρ is the same as that of the associated σ; i.e., let ρ have sign (−1)^{n−ν(ρ)}, where ν(ρ) denotes the number of parts of ρ.

For a composition ρ = (x_{1}, …, x_{m}) of n, define the (signed) weight by (−1)^{n−m} ∏_{i=1}^{m} a_{x_{i}}, where (a_{i})_{i≥0} is the sequence associated with A. If A is of size n with superdiagonal entry a_{0} = 1, then det(A) gives the sum of the (signed) weights of all compositions of n. In what follows, it will be convenient to view compositions ρ of n as linear tilings of length n where parts are identified as tiles of various lengths. Here, it is understood that all tiles of the same length are indistinguishable. The tilings themselves may be viewed as coverings of the members of [n] = {1, 2, …, n}, written consecutively in a row.

Tiles covering a single, two consecutive, or three consecutive numbers are known as squares, dominos, and trominos, respectively. Let s, d, t, q denote respectively a square, domino, tromino, or 4-tile. We will refer to tilings using only pieces from {s, d, t, q} as quaternary. Let Q_{n} denote the set of quaternary tilings of length n. From the recurrence, it is seen that there are t_{n+3} members of Q_{n} for all n ≥ 0. Here, we will make frequent use of this interpretation for t_{n} in providing bijective proofs of several of the foregoing determinant identities. More generally, F_{n+k−1}^{(k)} for k ≥ 2 counts the tilings of length n where one is allowed to use any tile of length up to and including k. When k = 2, this gives the familiar square-and-domino tilings enumerated by F_{n+1}; see, e.g., [6, Chapter 1]. Benjamin and Heberle [5] proved combinatorially some k-generalized Fibonacci identities that had been shown algebraically by Howard and Cooper [12] employing a tiling approach, which has been used subsequently in deducing tetranacci identities [13].

Note that generalizations of identities (9)–(11) above appear in [11], where combinatorial proofs were given. Below, we provide combinatorial proofs of all the remaining identities in Theorems 1–3 above with the exception of (16) and (17). In the first group of identities, the determinant in question can be viewed as a sum of signs of “marked” members of Q_{n} wherein certain tiles may be designated.

6.1 Proofs of identities (5), (6), (7), and (14)

For (5) and (6), we may assume n ≥ 2, the n = 1 case being obvious. For (5), first let A = A_{n} denote the set of quaternary tilings of length n in which d’s may be marked and ending in a marked d. Define the sign by (−1)^{n−(# of marked d’s)}. Note that a cycle of length i within σ ∈ P_{n} whose contribution towards det(1; t_{2}, t_{3}, …, t_{n+1}) is nonzero must have i ≥ 2 and be associated with a tiling (of length i − 2) enumerated by t_{i+1}. Putting a marked d at the end of each such tiling and concatenating the resulting tilings yields a member λ_{σ} ∈ A for each possible σ. Since the sign of λ_{σ} equals sgn(σ) for all σ, it follows that det(1; t_{2}, t_{3}, …, t_{n+1}) gives the sum of the signs of all members of A.

We define a sign-changing involution on A by identifying the rightmost d within λ ∈ A, excluding the final d, and either marking or unmarking it. Let A′ denote the set of survivors of this involution. Then members of A′ contain a single d (at the end) and thus have sign (−1)^{n−1}. Furthermore, they may be identified as tilings that use only s, t or q pieces. Let L denote the set of tilings of length n − 2 using {s, d} and ending in an even number (possibly zero) of d. Then the replacements d^{2} ↦ q, ds ↦ t, with all other s pieces staying the same within each member of L, defines a bijection between L and A′ and hence |A′| = |L|.

To complete the proof of (5), it suffices to show that the product of |L| with (−1)^{n−1} is given by the right-hand side. To do so, we consider the set of ordered pairs (α, β) where α is a square-and-domino tiling of length n−2i for some 1 ≤ i ≤ ⌊n/2⌋ and β = d^{i}, with the sign taken to be (−1)^{n−i}. Then ∑_{i=1}^{⌊n/2⌋}(−1)^{n−i}F_{n−2i+1} gives the sum of the signs of all possible (α, β). Define an involution as follows. If α ends in an odd number of d’s, then remove a d from α and add it to β, and vice versa, if α ends in an even number of d’s and β = d^{i} with i ≥ 2. The survivors of this involution each have sign (−1)^{n−1} and are synonymous with the members of L, as desired.

To show (6), we consider the parity of n. First assume n = 2m. If m = 2t for some t ≥ 1, then members of L in this case are of the form ρ = ρ′sd^{2ℓ} where 0 ≤ ℓ ≤ t − 1. Thus ρ′ is of length 4t − 4ℓ − 3 and considering all possible ℓ gives

|L| = ∑_{ℓ=0}^{t−1} F_{4t−4ℓ−2} = F_{2t}^{2},

where the second equality follows from [6, Identity 27], which was explained combinatorially there. Note that since each survivor had sign (−1)^{n−1}, the n = 4t case of (6) follows. If m = 2t + 1 where t ≥ 0, then ρ ∈ L implies ρ = d^{2t} or ρ = ρ′sd^{2ℓ} where 0 ≤ ℓ ≤ t − 1 and ρ′ is of length 4t − 4ℓ − 1. This implies

|L| = 1 + ∑_{ℓ=0}^{t−1} F_{4t−4ℓ} = 1 + F_{2t}F_{2t+2} = F_{2t+1}^{2},

where the last two equalities, which themselves have combinatorial proofs, follow from Identities 29 and 8 respectively in [6]. This then completes the even case of (6). The odd case of (6) follows in a similar fashion and makes use of Identities 26 and 28 from [6].

To show (7), first let B = B_{n} denote the set of quaternary tilings of length 2n in which tiles terminating in even-numbered positions (including squares) may be marked, with the terminal tile always marked. Define the sign by (−1)^{n−(# of marked tiles)}. Note that a cycle of length i within σ ∈ P_{n} is associated with a quaternary tiling of length 2i for each i ≥ 1. Upon marking the final piece within each of these associated tilings and concatenating, one obtains for each σ ∈ P_{n} a unique λ_{σ} ∈ B. Since σ and λ_{σ} have the same sign for all σ, it follows that det(1; t_{5}, t_{7}, …, t_{2n+3}) gives the sum of the signs of all members of B.

Let B′ ⊆ B consist of those tilings λ of the form λ = sαs, sαt, tαs, or tαt, where α contains no s or t. Note that members of B′ contain no piece ending in an even-numbered position (other than the terminal) and thus have sign (−1)^{n−1}. Since n ≥ 3, it is seen upon halving that

|B′| = F_{n} + 2F_{n−1} + F_{n−2} = 2F_{n} + F_{n−1} = F_{n+2}.

Furthermore, all members of B that do not contain a tile terminating in an even-numbered position other than the last are of one of the four aforementioned forms and hence belong to B′. To complete the proof of (7), define a sign-changing involution of B−B′ by identifying the rightmost piece terminating at position 2i for some i < n and either marking or unmarking that piece.

For (14), let C denote the set of quaternary tilings of length n in which any tile may be marked, with the final tile always marked and the sign defined as in the proof of (7). Then we have that det(1; t_{4}, t_{5}, …, t_{n+3}) gives the sum of the signs of all members of C. Define an involution by either marking or unmarking the penultimate tile. Note that n ≥ 5 implies that this involution is defined on all of C, whence the determinant is zero.

6.2 Identities (12) and (13)

We may assume n ≥ 3 in the proof of (12), the n = 1, 2 cases being easily verified. Let D denote the set of quaternary tilings of length n in which trominos may be marked, with the final piece a marked tromino. Within the contribution of each σ ∈ P_{n} towards the determinant sum, the product of the superdiagonal −1’s is the same as sgn(σ). Since each cycle C within a contributing σ has length at least 3 in this case and is associated with a quaternary tiling of length |C| − 3 (to which we append a marked tromino prior to concatenating the various tilings that result), it is seen that det(−1; t_{1}, t_{2}, …, t_{n}) gives the cardinality of the set D.

We now show that the right side of (12) also counts the members of D, but in a different way. To do so, note that members of D may be formed as follows. Given 0 ≤ j ≤ n − 3, we first form a square-and-domino tiling ρ of length n − 3 − j having exactly i dominos, which can be effected in \binom{n−3−i−j}{i} ways. Then select exactly j of the 2i numbered positions within ρ that are covered by the i dominos, which can be done in \binom{2i}{j} ways. Let d denote an arbitrary domino of ρ. If both halves of d correspond to chosen positions, then replace d with a q. If only one of the halves of d was chosen, then replace d with a t, which we mark if the first half of d was chosen and leave unmarked if not. If neither half of d corresponds to a chosen position, then leave d unchanged. Finally, we leave all squares of ρ unchanged and add a marked t to the end of the resulting tiling. In this way, ρ is transformed to ρ′ ∈ D in which there are exactly i + 1 pieces of length at least two altogether (counting the last piece) and (# of t) + 2(# of q) = j + 1. Since the operation converting ρ to ρ′ may be reversed, considering all possible i and j implies |D| is given by the right side of (12), as desired.

For (13), let E denote the set of quaternary tilings of length n in which squares may be marked and ending in a marked square. Define the sign as (−1)^{n−(# of marked s’s)}. Then det(1; t_{3}, t_{4}, …, t_{n+2}) gives the sum of the signs of all members of E. Define an involution on E by identifying the rightmost non-terminal square and either marking or unmarking it. Then the set E′ of survivors are synonymous with the tilings of length n − 1 that use {d, t, q}, with each member of E′ having sign (−1)^{n−1}. To complete the proof, we must show that the sum on the right side gives |E′|. Note that we may assume i ≤ j in this sum, with 0 ≤ n − 1 − 2i − 2j ≤ j, for otherwise the product of the binomial coefficients is zero. Consider members of E′ containing i q’s and j tiles altogether. Then there are n−1−2i−2j t’s and thus

\binom{j}{i, n − 1 − 2i − 2j, i + 3j − n + 1} = \binom{j}{2i + 3j − n + 1}\binom{2i + 3j − n + 1}{i}

such members of E′. Summing over all possible i and j implies (13).

We conclude with proofs of formulas (15) and (18), where we regard the determinant in each case as a signed sum over sets of configurations whose members are vectors with quaternary tiling components where the sum of component lengths now depends upon the number of components.

6.3 Identities (15) and (18)

To show (15), first let F_{n,j} for n ≥ 2 and 1 ≤ j ≤ n be given by

F_{n,j} = {(λ_{1}, …, λ_{j}) : ∑_{i=1}^{j}(|λ_{i}| − 1) = n, where λ_{i} is quaternary with |λ_{i}| ≥ 2 for all i}.

Define the sign of members of F_{n,j} by (−1)^{n−j} and let F_{n} = ∪_{j=1}^{n}F_{n,j}. Then, by the definition of the determinant, we have that det(1; t_{5}, t_{6}, …, t_{n+4}) gives the sum of the signs of all members of F_{n}.

We define a sign-changing involution on F_{n} for n ≥ 3. To do so, we pair members of F_{n,j} for the various j with members of F_{n,j−1} by changing in several cases the final few components of λ = (λ_{1}, …, λ_{j}) ∈ F_{n,j} as indicated (only the relevant components being shown):

• λ_{j−1} = α, λ_{j} = d ⟷ λ_{j−1} = αs,

• λ_{j−1} = α, λ_{j} = t ⟷ λ_{j−1} = αd,

• λ_{j−1} = α, λ_{j} = q ⟷ λ_{j−1} = αt,

• λ_{j−1} = βd, λ_{j} = sd ⟷ λ_{j−1} = βq,

• λ_{j−1} = d, λ_{j} = sd ⟷ λ_{j−1} = st,

• λ_{j−2} = α, λ_{j−1} = s^{2}, λ_{j} = sd ⟷ λ_{j−2} = αs, λ_{j−1} = sd,

• λ_{j−2} = α, λ_{j−1} = q, λ_{j} = sd ⟷ λ_{j−2} = αt, λ_{j−1} = sd,

• λ_{j−2} = α, λ_{j−1} = sq, λ_{j} = sd ⟷ λ_{j−2} = αq, λ_{j−1} = sd,

where α and β denote tilings of length at least 2 and 1, respectively.

We now describe more fully the cases for 2 ≤ n ≤ 6. If n = 2, then the determinant is zero in this case and we define the pairings on F_{2} as follows: (s^{3}) ↔ (s^{2}, d), (ds) ↔ (d, d), (sd) ↔ (d, s^{2}), and (t) ↔ (s^{2}, s^{2}). If n = 3, then we may apply the general pairings given above for n ≥ 3, noting that the following cases are missed: λ = (q), λ = (s^{2}, sd), or λ = (λ′, s^{2}) where λ′ ∈ F_{2} (written without parenthesization within λ). We may then pair the first two cases since they are of opposite sign, with members λ in the third case contributing zero towards the overall sum of signs by virtue of the pairings given in the n = 2 case. This implies that for n = 3 the determinant is also zero. If n = 4, then members of F_{4} that are not matched in the general pairings above are λ = (t, sd) or of the form λ = (λ′, s^{2}) where λ′ ∈ F_{3}. Since the contribution in the second case is zero by virtue of the n = 3 pairings, the n = 4 case is established.

If n = 5, then the unpaired λ ∈ F_{5} are those of the form (i) λ = (λ′, s^{2}) where λ′ ∈ F_{4}, (ii) λ = (s^{2}, t, sd) or (d, t, sd), or (iii) λ = (st, sd) or (q, sd). Since the cases (ii) and (iii) cancel, applying the n = 4 pairings to (i) implies that the determinant is also 1 when n = 5. Finally, if n = 6, then the unpaired λ ∈ F_{6} are those of the form (i) λ = (λ′, s^{2}) where λ′ ∈ F_{5}, (ii) λ = (λ′, t, sd) where λ′ ∈ F_{2}, or (iii) λ = (s^{2}, st, sd), (d, st, sd), or (sq, sd). Note that case (ii) contributes zero towards the sum of signs, while the unpaired λ in case (i), namely (t, sd, s^{2}, s^{2}), may be matched with (s^{2}, st, sd), and (d, st, sd) with (sq, sd), which implies that the determinant is zero when n = 6. Thus, the required involution has been defined completely for 2 ≤ n ≤ 6.

If n ≥ 7, then the set of survivors of the involution above are those λ whose last component is γ = (s^{2}) or whose last two components are either δ = (t, sd) or ε = (st, sd). In this case, we look to the rightmost component of λ, say λ_{s}, where this does not hold and apply one of the pairings given above, provided ∑_{i=1}^{s}(|λ_{i}| − 1) ≥ 7. If not, then λ may be expressed as λ = ρ ∪ τ, where ρ ∈ F_{i} for some 2 ≤ i ≤ 6 and τ is a sequence in {γ, δ, ε} such that ρ ∪ x has length at least 7, with x denoting the first “letter” of τ.

We may define an involution for λ = ρ ∪ τ of the stated form as follows. First suppose ρ ∈ F_{2}. Then x = ε and we may pair λ accordingly using ρ and the n = 2 case above. Henceforth, we may assume ρ ∉ F_{2}. Suppose that there exists a δ, γ string within τ. Then we may replace the rightmost occurrence of such a string by ε, and vice versa, which reverses the sign as the number of components of λ changes by one. Note that ρ ∉ F_{2} implies that this operation is well-defined, for it would never be the case then that we would be replacing an initial ε letter with δ, γ such that ρ ∪ δ ∈ F_{6}. Now assume τ has the form γ^{k}δ^{ℓ} for some k and ℓ. If k ≥ 1, then ρ must belong to F_{6} and so we may apply the n = 6 case to ρ. Thus, the only survivors of this last involution (taken together with all of the previous ones) are those λ of the form λ = ρ ∪ δ^{ℓ} such that ρ ∈ F_{r} where 3 ≤ r ≤ 6 and r ≡ n (mod 4). Note that ρ and λ have the same sign and thus applying the pairings from the 3 ≤ r ≤ 6 cases above to ρ implies for all n ≥ 7 that det(1; t_{5}, t_{6}, …, t_{n+4}) = det(1; t_{5}, t_{6}, …, t_{r+4}) where r is as given, which completes the proof of (15).

To show (18), define H_{n,j} for n ≥ 4 and 1 ≤ j ≤ n by

H_{n,j} = {(λ_{1}, …, λ_{j}) : ∑_{i=1}^{j} |λ_{i}| = 2n + j, where λ_{i} is quaternary with |λ_{i}| ≥ 3 odd for all i}.

Let members of H_{n,j} have sign (−1)^{n−j} and H_{n} = ∪_{j=1}^{n}H_{n,j}. Then it is seen from the definitions that det(1; t_{6}, t_{8}, …, t_{2n+4}) gives the sum of the signs of all members of H_{n}.

We define a sign-changing involution on H_{n}. To do so, we pair members of H_{n,j} with members of H_{n,j−1} by changing in several cases the final few components of λ = (λ_{1}, …, λ_{j}) ∈ H_{n,j} as indicated (only the relevant components being shown):

• λ_{j−1} = α, λ_{j} = s^{3} ⟷ λ_{j−1} = αd,

• λ_{j−1} = α, λ_{j} = sd ⟷ λ_{j−1} = αs^{2},

• λ_{j−1} not ending in q, λ_{j} = ds ⟷ λ′_{j−1}, • λ_{j−2} = γd, λ_{j−1} = t, λ_{j} = t ⟷ λ_{j−2} = γq, λ_{j−1} = ds,

• λ_{j−2} = βs, λ_{j−1} = t, λ_{j} = t ⟷ λ_{j−2} = βt, λ_{j−1} = t,

• λ_{j−2} = α, λ_{j−1} = sq, λ_{j} = t ⟷ λ_{j−2} = αq, λ_{j−1} = t,

• λ_{j−1} = βs, λ_{j} = t ⟷ λ_{j−1} = βt,

• λ_{j−1} = γd, λ_{j} = t ⟷ λ_{j−1} = γq,

where α, β and γ represent arbitrary tilings of lengths at least 3, 2 and 1, respectively, and λ′_{j−1} in the third case is obtained from λ_{j−1} by increasing the length of the last tile by one and then appending s. Note that the sixth case above requires n ≥ 4.

Let H_{n}^{∗} denote the set comprising those members of H_{n} not covered by one of the preceding pairings. Then λ ∈ H_{n}^{∗} implies either (i) the final three or more components of λ are each equal to the tiling consisting of a single t, preceded by a tiling that ends in s or d, (ii) the final two or more components of λ equal t, preceded by a tiling that ends in t or q and containing at least two pieces, or (iii) λ = (t, …, t) ∈ H_{n,n}. One may pair tilings in (i) with those in (ii) by changing the final s or d piece in the rightmost tiling that is not t to t or q, respectively, and deleting one of the terminal components t. This pairing, taken together with those preceding it, implies that each member of H_{n} is paired with another of opposite sign except for λ = (t, …, t) whose sign is positive, which yields (18).

References

[1] M. R. Alfuraidan and I. N. Joudah, On a new formula for Fibonacci’s family m-step numbers and some applications, Mathematics 7 (2019), 805.

[2] S. Alikhani and Y.-H. Peng, Chromatic zeros and generalized Fibonacci numbers, Appl. Anal. Discrete Math. 3 (2009), 330–335.

[3] M. Basu and M. Das, Coding theory on Fibonacci n-step numbers, Discrete Math. Algorithms Appl. 6 (2014), 1450017.

[4] M. Basu and M. Das, On Fibonacci n-step numbers, Asian-Eur. J. Math. 8 (2015), 1550067.

[5] A. T. Benjamin and C. R. Heberle, Counting on r-Fibonacci numbers, Fibonacci Quart. 52 (2014), 121–128.

[6] A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

[7] N. D. Cahill, J. R. D’Errico, D. A. Narayan, and J. Y. Narayan, Fibonacci determinants, College Math. J. 3 (2002), 221–225.

[8] Y. H. Chen and C. Y. Yu, A new algorithm for computing the inverse and the determinant of a Hessenberg matrix, Appl. Math. Comput. 218 (2011), 4433–4436.

[9] S. Christensen, Generalized Fibonacci numbers and Blackwell’s renewal theorem, Statist. Probab. Lett. 82 (2012), 1665–1668.

[10] G. P. B. Dresden and Z. Du, A simplified Binet formula for k-generalized Fibonacci numbers, J. Integer Seq. 17 (2014), Article 14.4.7.

[11] T. Goy and M. Shattuck, Determinant identities for Toeplitz-Hessenberg matrices with tribonacci number entries, Trans. Comb., to appear, 2020.

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

[13] Z. Jin, Tetranacci identities with squares, dominoes, and hexagonal double-strips,

preprint, 2019, http://arXiv:1907.09935v1.

[14] E. Karaduman, On determinants of matrices with general Fibonacci numbers entries, Appl. Math. Comput. 167 (2005), 670–676.

[15] D. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, 1998.

[16] T. Koshy, Fibonacci and Lucas Numbers and Applications, 2nd ed., John Wiley & Sons, 2017.

[17] R. Li, Convolution identities for tetranacci numbers, preprint, 2016, http://arxiv.

org/abs/1609.05272v1.

[18] S. K. Lucas, Representing numbers using Fibonacci variants, in J. Beineke and J. Rosenhouse, eds., The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2015, pp. 245–260.

[19] J. Maroulas, Factorization of Hessenberg matrices, Linear Algebra Appl. 506 (2016), 226–243.

[20] M. Merca, A note on the determinant of a Toeplitz-Hessenberg matrix, Spec. Matrices 1 (2013), 10–16.

[21] M. Merca, A generalization of the symmetry between complete and elementary symmetric functions, Indian J. Pure Appl. Math. 45 (2014), 75–89.

[22] E. P. Miles, Jr., Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly 67 (1960), 745–752.

[23] T. Muir, The Theory of Determinants in the Historical Order of Development, Vol. 3, Dover Publications, 1960.

[24] A. N. Philippou and A. A. Muwafi, Waiting for the kth consecutive success and the Fibonacci sequence of order k, Fibonacci Quart. 20 (1982), 28–32.

[25] M. Rachidi, E. H. Saidi, and J. Zerouaoui, Fractional statistics in terms of the rgeneralized Fibonacci sequences, Int. J. Mod. Phys. A 18 (2003), 159–171.

[26] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2019. Available

    at https://oeis.org.

[27] M. E. Waddill, The tetranacci sequence and generalizations, Fibonacci Quart. 30 (1992), 9–20.

[28] M. E. Waddill, Some properties of the tetranacci sequence modulo m, Fibonacci Quart. 30 (1992), 232–238.

2010 Mathematics Subject Classification: Primary 15A15; Secondary 05A19, 15B05. Keywords: tetranacci number, Toeplitz-Hessenberg matrix, Trudi’s formula, generating function, Fibonacci number, tribonacci number.

(Concerned with sequences \underline{A000045}, \underline{A000073}, \underline{A000078}, \underline{A001591}, \underline{A001592}, \underline{A079262}, \underline{A104144}, and \underline{A122189}.)

Received December 9 2019; revised version received April 2 2020. Published in Journal of Integer Sequences, June 11 2020.

Return to Journal of Integer Sequences home page.