\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf
Some Toeplitz-Hessenberg Determinant Identities for the Tetranacci Numbers\\
\vskip .1in } \vskip 1cm \large
Taras Goy\\
Faculty of Mathematics and Computer Science\\
Vasyl Stefanyk Precarpathian National University \\
Ivano-Frankivsk\\
Ukraine\\
\href{mailto:tarasgoy@yahoo.com}{\tt tarasgoy@yahoo.com} \\
\vskip .2 in
Mark Shattuck\footnote{Corresponding author.}\\
Department of Mathematics\\
University of Tennessee\\
Knoxville, TN 37996\\
USA\\
\href{mailto:shattuck@math.utk.edu}{\tt shattuck@math.utk.edu} 
\end{center}

\vskip .2 in

\begin{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.
\end{abstract}


\section{Introduction}

Over the years many generalizations of the Fibonacci numbers have been studied; see, for instance, \cite{Koshy} for a complete bibliography.
Among the best known of these are the $k$\emph{-generalized Fibonacci numbers} $F^{(k)}_n$ satisfying the $k$-th order recurrence
\begin{equation}\label{F_k}
F_{n}^{(k)}=F_{n-1}^{(k)}+F_{n-2}^{(k)}+\cdots + F_{n-k}^{(k)}, \qquad n \geq k,
\end{equation}
with initial values
\begin{equation*}
F_{0}^{(k)}=F_{1}^{(k)}=\cdots=F_{k-2}^{(k)}=0,\quad F_{k-1}^{(k)}=1.
\end{equation*}
These numbers are also known as \emph{Fibonacci $k$-sequences}, \emph{generalized Fibonacci numbers of order} $k$, \emph{Fibonacci $k$-step numbers}, and \emph{$k$-bonacci numbers}.

By subtraction, equation \eqref{F_k} is equivalent to the $(k+1)$-st order recurrence  $F_{n}^{(k)}=2F_{n-1}^{(k)}-F_{n-k-1}^{(k)}$
for all $n\geq k+1$. The $F_n^{(k)}$ may be computed directly using the following ``Binet-like'' formula \cite{Dresden}
$$
F_{n}^{(k)}=\sum_{i=1}^{k}\frac{(\alpha_i-1)\alpha_i^{n-k+1}}{2+(k+1)(\alpha_i-2)}, \qquad n \geq k-1,
$$
where $\alpha_1,\ldots,\alpha_k$ are the roots of $x^k - x^{k-1} -\cdots - x - 1 = 0$.  The $F_n^{(k)}$ are also given explicitly by the multinomial summation formula \cite{Philippou}
$$
F^{(k)}_{n}=
\sum\limits_{
\begin{smallmatrix}
i_1,\ldots,i_{k}\geq0\\
i_1+2i_2+\cdots+ki_{k}=n-k+1
\end{smallmatrix}}
{i_1+i_2+\cdots+i_k\choose i_1,i_2,\ldots,i_k}.
$$

The cases of $F_n^{(k)}$ for $2 \leq k \leq 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 \cite{Sloane}, the first few terms of which are given below (see also entries \seqnum{A122189}, \seqnum{A079262}, \seqnum{A104144}):

\medskip\noindent
	\begin{tabular}{ | c || c | c | c | c  |c |c |c |c |c |c |c |c |c |c |c |c |c |c |} \hline
		$n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $12$ & $13$ & $14$ & $15$ &\small{Seq. in \cite{Sloane}}\\\hline\hline
		$F_n$ & $0$ & $1$ & $1$ & $2$ & $3$ & $5$ & $8$ & $13$ & $21$ & $34$ & $55$ & $89$ & $144$ & $233$ & $377$ & $610$ &\seqnum{A000045}\\\hline
		$T_n$ & $0$ & $0$ & $1$ & $1$ & $2$ & $4$ & $7$ & $13$ & $24$ & $44$ & $81$ & $149$ & $274$ & $504$ & $927$ & $1705$ & \seqnum{A000073}\\\hline
		$t_n$ & $0$ & $0$ & $0$ & $1$ & $1$ & $2$ & $4$ & $8$ & $15$ & $29$ & $56$ & $108$ & $208$ & $401$ & $773$ & $1490$ &\seqnum{A000078}\\\hline
		$p_n$ & $0$ & $0$ & $0$ & $0$ & $1$ & $1$ & $2$ & $4$ & $8$ & $16$ & $31$ & $61$ & $120$ & $236$ & $464$ & $912$ &\seqnum{A001591}\\\hline
		$h_n$ & $0$ & $0$ & $0$ & $0$ & $0$ & $1$ & $1$ & $2$ & $4$ & $8$ & $16$ & $32$ & $63$ & $125$ & $248$ & $492$ &\seqnum{A001592}\\\hline
	\end{tabular}\medskip

In addition to their significance in combinatorics, the numbers $F_{n}^{(k)}$ have applications to a wide variety of research areas such as physics \cite{Rachidi}, sorting algorithms \cite{Knuth}, graph theory \cite{Alikhani}, coding theory \cite{Basu-Coding,Lucas}, and probability \cite{Christensen}.  See also \cite{Alfuraidan,Basu,BH,Dresden,Howard,Karaduman,Miles,Philippou} 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
\begin{equation*}
t_n = t_{n-1} + t_{n-2} + t_{n-3} + t_{n-4}, \qquad n \geq 4,
\end{equation*}
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, \cite{Jin,Li,Waddill1,Waddill2}.

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.

\section{Toeplitz-Hessenberg matrices and determinants}

A \emph{lower Hessenberg matrix} $H_n=(h_{ij})$ is an $n\times n$ matrix whose entries above the superdiagonal are all zero, i.e.,
\begin{equation*}
H_n=\left(\begin{array}{ccccccc}
h_{11}        & h_{12}      & 0   &  \cdots       & 0     & 0 \\
h_{21}        & h_{22}       & h_{23}   & \cdots        & 0     & 0 \\
h_{31}        & h_{32}       & h_{33}      & \cdots        & 0     & 0 \\
\cdots     & \cdots    & \cdots & \ddots & \cdots & \cdots \\
h_{n-1,1}   & h_{n-1,2}  & h_{n-1,3} & \cdots  & h_{n-1,n-1}    & h_{n-1,n} \\
h_{n1}     & h_{n2}& h_{n3}   & \cdots & h_{n,n-1}    & h_{nn}
\end{array}\right).
\end{equation*}
Hessenberg matrices play an important role in both computational and applied mathematics (see, for example, \cite{Chen,Maroulas} and references therein). Perhaps one of the reasons for this is that $\det(H_n)$ may be calculated quickly using the recurrence \cite{Cahill}
\begin{equation}\label{DetHess}
\det(H_n) =h_{nn}\det(H_{n-1}) + \sum_{k=1}^{n-1}(-1)^{n-k}h_{nk}\det(H_{k-1}) \prod_{i=k}^{n-1}h_{i,i+1}, \qquad n \geq 1,
\end{equation}
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 \emph{Toeplitz-Hessenberg matrix}
\begin{equation*}
M_n(a_0; a_1,\ldots,a_n)=\left(\begin{array}{ccccccc}
a_1        & a_0      & 0   &  \cdots       & 0      & 0 \\
a_2        & a_1       & a_0   & \cdots        & 0      & 0 \\
a_3        & a_2       & a_1      & \cdots        & 0      & 0 \\
\cdots     & \cdots    & \cdots & \ddots & \cdots & \cdots \\
a_{n-1}   & a_{n-2}  & a_{n-3} & \cdots  & a_1    & a_0 \\
a_{n}     & a_{n-1}& a_{n-2}   & \cdots & a_2    & a_1
\end{array}\right),
\end{equation*}
where $a_0\ne0$ is assumed. Then, from (\ref{DetHess}), we obtain
\begin{equation}\label{Det-Hess}
\det(M_n) =\sum_{k=1}^{n}(-a_0)^{k-1}a_k\det(M_{n-k}), \qquad n \geq 1,
\end{equation}
with $\det(M_0)=1$.

We investigate particular cases of Toeplitz-Hessenberg matrices in 
which the superdiagonal element $a_0$ is equal $\pm1$.  To  simplify our notation, we write $\det(a_0;a_1,\ldots,a_n)$ in place of $\det\left(M_n(a_0;a_1,\ldots,a_n)\right)$.

In proving the identities below, we determine a generating function (gf) formula for the sequence $(\det(M_n))_{n\geq1}$ in question.  Let
$$g(x)=\sum_{i\geq 1}(-a_0)^{i-1}a_ix^i  \quad \text{ and }\quad f(x)=\sum_{n\geq1}\det(a_0;a_1,\ldots,a_n)x^n.$$
Then recurrence \eqref{Det-Hess} may be expressed equivalently in terms of gf's as
\begin{equation}\label{gfrel}
f(x)=\frac{g(x)}{1-g(x)}.
\end{equation}
Thus, it suffices to compute the gf for the sequence $(a_i)_{i\geq1}$.  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.


\section{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.
\begin{theorem}\label{Theo1}
	The following formulas hold:
	\begin{align}
 \det(1;t_2,t_3,\ldots,t_{n+1})&=\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^{n-i}F_{n-2i+1}\label{tetr-fib1}\\
	&=\begin{cases}
	F_{\frac{n-1}{2}}F_{\frac{n+1}{2}}, &\text{\emph{if $n$ is odd}};\\[3 pt]
	-(F_{n/2})^2, &\text{\emph{if $n$ is even},}
	\end{cases}\qquad n\geq 1,\label{tetr-fib1.5}\\
	\label{tetr-fib2}
	\det(1;t_5,t_7,\ldots,t_{2n+3})&=(-1)^{n-1}F_{n+2},\qquad n\geq 3.
	\end{align}
\end{theorem}
\begin{proof}
First note that by standard methods, we have
\begin{equation}\label{tngf}
\sum_{n\geq 3}t_nx^n=\frac{x^3}{1-x(1+x+x^2+x^3)},
\end{equation}
which implies
$$
g(x)=\sum_{n\geq1}t_{n+1}(-1)^{n-1}x^n=-\frac{x^2}{1+x(1-x+x^2-x^3)}.
$$
By \eqref{gfrel}, we then have
$$\sum_{n\geq1}\det(1;t_2,t_3,\ldots,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,
\begin{align*}
&\sum_{n\geq1}x^n\left(\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^{n-i}F_{n-2i+1}\right)=\sum_{i\geq1}(-1)^i\sum_{n\geq 2i}F_{n-2i+1}(-x)^n\\
&=\sum_{i\geq 1}(-1)^i(-x)^{2i-1}\sum_{n\geq1}F_n(-x)^n=\frac{x}{1+x^2}\cdot \frac{-x}{1+x-x^2}=-\frac{x^2}{1+x+x^3-x^4},
\end{align*}
as before, which implies \eqref{tetr-fib1}.  The expression \eqref{tetr-fib1.5} follows from \eqref{tetr-fib1} and considering the underlying gf in each of the identities (26)--(29) from \cite{BQ}.  A proof similar to that given for \eqref{tetr-fib1} applies to \eqref{tetr-fib2} wherein one considers the even part of $\sum_{n\geq 1}t_{n+3}x^n$, the details of which we leave to the reader.
\end{proof}

A proof comparable to the one given for Theorem \ref{Theo1} yields the following relation between tetranacci and tribonacci numbers.
\begin{theorem}\label{Theo2}
	For all $n\geq 2$,
	\begin{equation}
	\label{tetr-trib}
	\det(1;t_0,t_1,\ldots,t_{n-1})=(-1)^{n-1}T_{n-2}.
	 \end{equation}
\end{theorem}


\section{Some Toeplitz-Hessenberg determinants with  tetra\-nacci entries}

In this section, we feature the determinants of several Toeplitz-Hessenberg  matrices whose entries are tetranacci numbers with  consecutive, even or odd subscripts.
\begin{theorem} \label{Theo3}
	Let $n\geq 1$, except when noted otherwise. Then
	\begin{align}
	\det(-1;t_0,t_1,\ldots,t_{n-1})&=(-1)^{\left\lfloor n/2\right\rfloor}\cdot\frac{2+(-1)^n}{10}+\frac{5(-1)^n+2^n}{30}\label{Theo3e0}\\
 &=\sum_{i=1}^{n-3}(-1)^i(1-2^{n-i-2})-\sum_{i=1}^{\left\lfloor\frac{n-2}{2}\right\rfloor}(-1)^i(1-2^{n-2i-2}),\label{Theo3e1}
     \end{align}
     \begin{align}
 \det(-1;t_1,t_2,\ldots,t_{n})&=\sum_{i=0}^{\left\lfloor\frac{n-3}{2}\right\rfloor}\sum_{j=0}^{n-2i-3}{n-3-i-j\choose i}{2i\choose j},\label{Theo3e2}\\
\det(1;t_3,t_4,\ldots,t_{n+2})&=(-1)^{n-1}\sum_{i=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor}\sum_{j=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor}{j\choose 2i+3j-n+1}{2i+3j-n+1\choose i},\label{Theo3e3}\\
\det(1;t_4,t_5,\ldots,t_{n+3})&=0,\qquad n\geq5,\label{Theo3e4}\\
	\det(1;t_5,t_6,\ldots,t_{n+4})&=\frac{1+(-1)^{\left\lfloor n/2 \right\rfloor}}{2},\qquad n\geq2,\label{Theo3e5}
	\end{align}
\begin{multline}
\det(1;t_1,t_3,\ldots,t_{2n-1}) \label{Theo3e6} \\
 =\frac{\sqrt{17}}{17}\left((4+\sqrt{17})\left(\frac{-3-\sqrt{17}}{2}\right)^{n-3}-(4-\sqrt{17})\left(\frac{-3+\sqrt{17}}{2}\right)^{n-3}\right),\quad n\geq 3,
 \end{multline}
	\begin{multline}
 	\det(1;t_0,t_2,\ldots,t_{2n-2})\label{Theo3e7} \\
 =\frac{\sqrt{21}}{42}\left((5+\sqrt{21})\left(\frac{-3-\sqrt{21}}{2}\right)^{n-3}-(5-\sqrt{21})\left(\frac{-3+\sqrt{21}}{2}\right)^{n-3}\right),\quad n\geq 3,
 \end{multline}
	\begin{equation}
\det(1;t_6,t_8,\ldots,t_{2n+4})=1,\qquad n\geq4. \label{Theo3e8}
	\end{equation}
	\end{theorem}
\begin{proof}
We provide proofs of formulas \eqref{Theo3e2}, \eqref{Theo3e3}, \eqref{Theo3e5}, and \eqref{Theo3e6}.  Adapting the featured proofs will yield the remaining identities, the details of which we leave to the reader.  First note that from \eqref{tngf}, we have
\begin{equation}\label{Theo3pe1}
g(x)=\sum_{n\geq 1}(-a)^{n-1}t_nx^n=\frac{a^2x^3}{1+ax-(ax)^2+(ax)^3-(ax)^4}.
\end{equation}
Let $f(x)$ denote the gf for the determinant expression on the left side in each of the identities \eqref{Theo3e2}, \eqref{Theo3e3}, \eqref{Theo3e5}, and \eqref{Theo3e6}.  We now show \eqref{Theo3e2}.  Taking $a=-1$ in \eqref{Theo3pe1} implies
$$f(x)=\sum_{n\geq1}\det(-1;t_1,t_2,\ldots,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 \eqref{Theo3e2} has gf given by
\begin{align*}
&\sum_{n\geq 3}x^n\sum_{i=0}^{\lfloor\frac{n-3}{2}\rfloor}\sum_{j=0}^{n-2i-3}\binom{n-3-i-j}{i}\binom{2i}{j}=\sum_{i\geq0}\sum_{j\geq0}\binom{2i}{j}\sum_{n\geq 2i+j+3}\binom{n-3-i-j}{i}x^n\\
&=\sum_{i\geq0}\sum_{j\geq0}\binom{2i}{j}x^{i+j+3}\sum_{n\geq i}\binom{n}{i}x^i=\sum_{i\geq0}\sum_{j=0}^{2i}\binom{2i}{j}x^{i+j+3}\cdot\frac{x^i}{(1-x)^{i+1}}\\
&=\sum_{i\geq0}\frac{x^{2i+3}}{(1-x)^{i+1}}\cdot(1+x)^{2i}=\frac{x^3}{1-x}\cdot \frac{1}{1-\frac{x^2(1+x)^2}{1-x}}=\frac{x^3}{1-x-x^2-2x^3-x^4},
\end{align*}
as before.

For \eqref{Theo3e3}, note that taking $a=1$ in \eqref{Theo3pe1} yields
$$\sum_{n\geq1}t_{n+2}(-1)^{n-1}x^n=\frac{1}{x^2}\sum_{n\geq 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 \eqref{gfrel}. As for the right-hand side of \eqref{Theo3e3}, first note that one may assume $0 \leq i \leq j$ in the sum and thus may write
$$\sum_{i=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor}\sum_{j=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor}{j\choose 2i+3j-n+1}{2i+3j-n+1\choose i}=\sum_{j=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor}\sum_{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 \geq 1$, and interchanging summation gives
\begin{align*}
&-\sum_{j\geq0}\sum_{i=0}^j\binom{j}{i}\sum_{n\geq1}\binom{j-i}{n-1-2i-2j}(-x)^n=-\sum_{j\geq0}\sum_{i=0}^j\binom{j}{i}(-x)^{2j+2i+1}\sum_{n\geq0}\binom{j-i}{n}(-x)^n\\
&=\sum_{j\geq0}\sum_{i=0}^j\binom{j}{i}x^{2j+2i+1}\cdot(1-x)^{j-i}=\sum_{j\geq0}x^{2j+1}\sum_{i=0}^j \binom{j}{i}x^{2i}(1-x)^{j-i}\\
&=\sum_{j\geq0}x^{2j+1}\cdot(1-x+x^2)^j=\frac{x}{1-x^2(1-x+x^2)},
\end{align*}
as before.

For \eqref{Theo3e5}, first observe that
\begin{align*}
\sum_{n\geq 1}t_{n+4}x^n&=\frac{1}{x^4}\sum_{n\geq 5}t_nx^n=\frac{1}{x^4}\left(\frac{x^3}{1-x(1+x+x^2+x^3)}-x^3-x^4\right)\\
&=\frac{(1+x)(1+x+x^2+x^3)-1}{1-x(1+x+x^2+x^3)}.
\end{align*}
This gives
$$\sum_{n\geq 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 \eqref{gfrel},
\begin{align*}
f(x)&=\sum_{n\geq1}\det(1;t_5,t_6,\ldots,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}=\left(2x+x^5+x^9+x^{13}+\cdots\right)+\left(x^4+x^8+x^{12}+\cdots\right).
\end{align*}
Extracting the coefficient of $x^n$ for $n \geq 2$ in the last expression yields \eqref{Theo3e5}.

Finally, for \eqref{Theo3e6}, note that taking the odd part of the gf formula $$\sum_{n\geq 1}t_nx^n=\frac{x^3(1-x)}{1-2x+x^5}$$
gives
$$\sum_{n\geq 1}t_{2n-1}x^{2n-1}=\frac{1}{2}\left(\frac{x^3(1-x)}{1-2x+x^5}+\frac{x^3(1+x)}{1+2x-x^5}\right)=\frac{x^3-2x^5+x^9}{1-4x^2+4x^6-x^{10}},$$
whence
$$\sum_{n\geq 1}t_{2n-1}x^n=\frac{x^2-2x^3+x^5}{1-4x+4x^3-x^5}.$$
Then by \eqref{gfrel},
$$\sum_{n\geq 1}\det(1;t_1,t_3,\ldots,t_{2n-1})x^n=-\frac{x^2+2x^3-x^5}{1+4x+x^2-2x^3},$$
and thus
$$
\sum_{n\geq 3}\det(1;t_1,t_3,\ldots,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
\begin{align*}
\frac{\sqrt{17}}{17}&\left((4+\sqrt{17})\sum_{n\geq 3}\left(\frac{-3-\sqrt{17}}{2}\right)^{n-3}x^n-(4-\sqrt{17})\sum_{n\geq 3}\left(\frac{-3+\sqrt{17}}{2}\right)^{n-3}x^n\right)\\
&=\frac{2x^3-x^4}{1+3x-2x^2},
\end{align*}
which implies \eqref{Theo3e6}.
\end{proof}

\begin{remark}
 Extensions of formulas \eqref{tetr-trib}, \eqref{Theo3e0}, and \eqref{Theo3e3} above in terms of the generalized Fibonacci numbers $F_n^{(k)}$ were given in \cite{GS} where combinatorial proofs are provided.  When $k=4$ in the extensions of \eqref{Theo3e0} and \eqref{Theo3e3}, one gets equivalently $\lfloor \frac{2^n+14}{30} \rfloor$ for the right side of \eqref{Theo3e0} and $(-1)^{n-1}q_{n}$ for the right side of \eqref{Theo3e3}, where $q_n$ is the sequence defined recursively by $q_n=q_{n-2}+q_{n-3}+q_{n-4}$ for $n \geq 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 \eqref{Theo3e3} given in the final section.
\end{remark}

Furthermore, generalizing the combinatorial proof yields the following extension of \eqref{tetr-fib2} in terms of $F_n^{(k)}$ for $k\geq 3$:
\begin{multline}
(-1)^{n-1}\det\left(1;F_{k+1}^{(k)},F_{k+3}^{(k)},\ldots,F_{2n+k-1}^{(k)}\right)\label{remeq1} \\
=\begin{cases}\displaystyle
\sum_{i=1}^{\frac{k}{2}}iF_{n-i+\frac{k-2}{2}}^{\left(\frac{k}{2}\right)}+\sum_{i=1}^{\frac{k-2}{2}}iF_{n+i-\frac{k+2}{2}}^{\left(\frac{k}{2}\right)}, &\text{if}~{n\geq k-1,~k \text{ even}};\\[.2in]
\displaystyle \sum_{i=1}^{\frac{k+1}{2}}iF_{n-i+\frac{k-3}{2}}^{\left(\frac{k-1}{2}\right)}+\sum_{i=1}^{\frac{k-1}{2}}iF_{n+i-\frac{k+3}{2}}^{\left(\frac{k-1}{2}\right)}, &\text{if}~{\displaystyle n\geq k,~k \text{ odd}}.
\end{cases}
\end{multline}
Taking $k=4$ in \eqref{remeq1} gives \eqref{tetr-fib2}, while taking $k=3$ gives $\det(1;T_4,T_6,\ldots,T_{2n+2})=4(-1)^{n-1}$ for $n \geq 3$, which occurs in \cite{GS}.  Finally, the combinatorial argument for formula \eqref{Theo3e4} may be readily generalized to yield
\begin{equation}\label{remeq2}
\det\left(1;F_k^{(k)},F_{k+1}^{(k)},\ldots,F_{n+k-1}^{(k)}\right)=0, \qquad n \geq k+1.
\end{equation}


\section{Applications by Trudi's formula}

In this section, we consider multinomial versions of Theorems \ref{Theo1}--\ref{Theo3} above using the following result, known as \emph{Trudi's formula}.  See, for example, \cite[Theorem 1]{MM1} and \cite{MM2}.
\begin{lemma}
Let $n$ be a positive integer. Then
 \begin{equation}\label{Trudi}
\det(M_n)=\sum_{\begin{smallmatrix} s_1,\ldots,s_n\geq0\\ s_1+2s_2+\cdots+ns_{n}=n \end{smallmatrix}}{s_1+\cdots+s_{n}\choose s_1,\ldots,s_{n}}(-a_0)^{n-s_1-\cdots-s_n}a_1^{s_1}a_2^{s_2}\cdots a_{n}^{s_n}
\end{equation}
or, equivalently,
\begin{equation*}
\det(M_n) =\sum_{k=1}^n(-a_0)^{n-k}\sum\limits_{\begin{smallmatrix} i_1,\ldots,i_k\geq1\\ i_1+i_2+\cdots+i_{k}=n \end{smallmatrix}}a_{i_1}a_{i_2}\cdots a_{i_k}.
\end{equation*}
\end{lemma}
\noindent The case $a_0=1$ of Trudi's formula is known as \emph{Brioschi's formula} \cite{Muir}. Note that the sum in \eqref{Trudi} 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 \eqref{Trudi}, when taken together with Theorems  \ref{Theo1}--\ref{Theo3} above, yields the following identities.
\begin{corollary} \emph{Let $n\geq1$, except when noted otherwise, and let
$\sigma_n=s_1+2s_2+\cdots+ns_{n}$, $|s|=s_1+s_2+\cdots+s_{n}$, and $m_n(s)={s_1+\cdots+s_{n}\choose s_1,\ldots,s_{n}}$ where $s_i\geq0$ for all $i$. Then}
\begin{align*}
\sum_{\sigma_n=n}(-1)^{|s|}m_n(s)t_2^{s_1}t_3^{s_2}\cdots t_{n+1}^{s_n}&=\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^{i}F_{n-2i+1},\\
\sum_{\sigma_n=n}(-1)^{|s|}m_n(s)t_5^{s_1}t_7^{s_2}\cdots t_{2n+3}^{s_n}&=-F_{n+2},\qquad n\geq 3,\\
\sum_{\sigma_n=n}(-1)^{|s|}m_n(s)t_0^{s_1}t_1^{s_2}\cdots t_{n-1}^{s_n}&=-T_{n-2},\qquad n\geq 2,\\
\sum_{\sigma_n=n}m_n(s)t_0^{s_1}t_1^{s_2}\cdots t_{n-1}^{s_n}&=(-1)^{\left\lfloor n/2\right\rfloor}\cdot\frac{2+(-1)^n}{10}+\frac{5(-1)^n+2^n}{30},\\
\sum_{\sigma_n=n}m_n(s)t_1^{s_1}t_2^{s_2}\cdots t_{n}^{s_n}&=\sum_{i=0}^{\left\lfloor\frac{n-3}{2}\right\rfloor}\sum_{j=0}^{n-2i-3}{n-3-i-j\choose i}{2i\choose j},\\
\sum_{\sigma_n=n}(-1)^{|s|}m_n(s)t_3^{s_1}t_4^{s_2}\cdots t_{n+2}^{s_n}&=
-\sum_{i=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor}\sum_{j=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor}{j\choose 2i+3j-n+1}{2i+3j-n+1\choose i},\\
\sum_{\sigma_n=n}(-1)^{|s|}m_n(s)t_4^{s_1}t_5^{s_2}\cdots t_{n+3}^{s_n}&=0,\qquad n\geq5,\\
\sum_{\sigma_n=n}(-1)^{|s|}m_n(s)t_5^{s_1}t_6^{s_2}\cdots t_{n+4}^{s_n}&=\frac{(-1)^n+(-1)^{\lfloor 3n/2\rfloor}}{2},\qquad n\geq2,
\end{align*}
\begin{multline*}
\sum_{\sigma_n=n}(-1)^{|s|}m_n(s)t_1^{s_1}t_3^{s_2}\cdots t_{2n-1}^{s_n} \\
=\frac{\sqrt{17}}{17}\left((4-\sqrt{17})\left(\frac{3-\sqrt{17}}{2}\right)^{n-3}-(4+\sqrt{17})\left(\frac{3+\sqrt{17}}{2}\right)^{n-3}\right),\qquad n\geq 3,
\end{multline*}
\begin{multline*}
\sum_{\sigma_n=n}(-1)^{|s|}m_n(s)t_0^{s_1}t_2^{s_2}\cdots t_{2n-2}^{s_n} \\
=\frac{\sqrt{21}}{42}\left((5-\sqrt{21})\left(\frac{3-\sqrt{21}}{2}\right)^{n-3}-(5+\sqrt{21})\left(\frac{3+\sqrt{21}}{2}\right)^{n-3}\right),\qquad n\geq 3,
\end{multline*}
\begin{equation*}
\sum_{\sigma_n=n}(-1)^{|s|}m_n(s)t_6^{s_1}t_8^{s_2}\cdots t_{2n+4}^{s_n}=(-1)^n,\qquad n\geq4.
\end{equation*}
\end{corollary}


\section{Combinatorial proofs}

Recall that the determinant of an $n \times n$ matrix $A=(a_{i,j})$ is given by
$$
\det(A)=\sum_{\sigma \in \mathcal{S}_n}(-1)^{\text{sgn}(\sigma)}a_{1,\sigma(1)}a_{2,\sigma(2)}\cdots a_{n,\sigma(n)},
$$
where $\mathcal{S}_n$ is the set of permutations $\sigma$ of size $n$ and $\text{sgn}(\sigma)$ denotes the sign of $\sigma$.  Assume permutations are expressed in the \emph{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 $\sigma$ 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 $\sigma$ would contain an $a_{i,j}$ factor for some $j>i+1$.

If $\mathcal{P}_n$ denotes the set of all such permutations $\sigma$ of length $n$, then one may replace $\mathcal{S}_n$ by $\mathcal{P}_n$ in the definition of $\det(A)$ above when $A$ is Toeplitz-Hessenberg.  Recall that a \emph{composition} of $n$ is a sequence of positive integers, called \emph{parts}, whose sum is $n$.  Note that $\sigma\in\mathcal{P}_n$ may be regarded as a composition $\rho$ of $n$, upon identifying the sequence of cycle lengths as a sequence of parts.  Assume that the sign of $\rho$ is the same as that of the associated $\sigma$; i.e., let $\rho$ have sign $(-1)^{n-\nu(\rho)}$, where $\nu(\rho)$ denotes the number of parts of $\rho$.

For a composition $\rho=(x_1,\ldots,x_m)$ of $n$, define the (signed) weight by $(-1)^{n-m}\prod_{i=1}^ma_{x_i}$, where $(a_i)_{i\geq0}$ 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 $\rho$ 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,\ldots,n\}$, written consecutively in a row.

Tiles covering a single, two consecutive, or three consecutive numbers are known as \emph{squares}, \emph{dominos}, and \emph{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 \emph{quaternary}.  Let $\mathcal{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 $\mathcal{Q}_n$ for all $n \geq 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\geq 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., \cite[Chapter~1]{BQ}.   Benjamin and Heberle \cite{BH} proved combinatorially some $k$-generalized Fibonacci identities that had been shown algebraically by Howard and Cooper \cite{Howard} employing a tiling approach, 
which has been used subsequently in deducing tetranacci identities \cite{Jin}.

Note that generalizations of identities \eqref{tetr-trib}--\eqref{Theo3e1} above appear in \cite{GS}, where combinatorial proofs were given.  Below, we provide combinatorial proofs of all the remaining identities in Theorems \ref{Theo1}--\ref{Theo3} above with the exception of \eqref{Theo3e6} and \eqref{Theo3e7}.  In the first group of identities, the determinant in question can be viewed as a sum of signs of ``marked'' members of $\mathcal{Q}_n$ wherein certain tiles may be designated.

\subsection{Proofs of identities \eqref{tetr-fib1}, \eqref{tetr-fib1.5}, \eqref{tetr-fib2}, and  \eqref{Theo3e4}}

For \eqref{tetr-fib1} and \eqref{tetr-fib1.5}, we may assume $n \geq 2$, the $n=1$ case being obvious.  For \eqref{tetr-fib1}, first let $\mathcal{A}=\mathcal{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-(\#\text{ of marked } d\text{'s})}$. Note that a cycle of length $i$ within $\sigma \in \mathcal{P}_n$ whose contribution towards $\det(1;t_2,t_3,\ldots,t_{n+1})$ is nonzero must have $i\geq 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 $\lambda_\sigma \in \mathcal{A}$ for each possible $\sigma$.  Since the sign of $\lambda_\sigma$ equals $\text{sgn}(\sigma)$ for all $\sigma$, it follows that $\det(1;t_2,t_3,\ldots,t_{n+1})$ gives the sum of the signs of all members of $\mathcal{A}$.

We define a sign-changing involution on $\mathcal{A}$ by identifying the rightmost $d$ within $\lambda \in \mathcal{A}$, excluding the final $d$, and either marking or unmarking it.  Let $\mathcal{A}'$ denote the set of survivors of this involution.  Then members of $\mathcal{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 $\mathcal{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\mapsto q$, $ds \mapsto t$, with all other $s$ pieces staying the same within each member of $\mathcal{L}$, defines a bijection between $\mathcal{L}$ and $\mathcal{A}'$ and hence $|\mathcal{A}'|=|\mathcal{L}|$.

To complete the proof of \eqref{tetr-fib1}, it suffices to show that the product of $|\mathcal{L}|$ with $(-1)^{n-1}$ is given by the right-hand side.  To do so, we consider the set of ordered pairs $(\alpha,\beta)$ where $\alpha$ is a square-and-domino tiling of length $n-2i$ for some $1 \leq i \leq \lfloor n/2 \rfloor$ and $\beta
=d^i$, with the sign taken to be $(-1)^{n-i}$.  Then $\sum_{i=1}^{\lfloor n/2 \rfloor} (-1)^{n-i}F_{n-2i+1}$ gives the sum of the signs of all possible $(\alpha,\beta)$.  Define an involution as follows.  If $\alpha$ ends in an odd number of $d$'s, then remove a $d$ from $\alpha$ and add it to $\beta$, and vice versa, if $\alpha$ ends in an even number of $d$'s and $\beta=d^i$ with $i \geq 2$.  The survivors of this involution each have sign $(-1)^{n-1}$ and are synonymous with the members of $\mathcal{L}$, as desired.

To show \eqref{tetr-fib1.5}, we consider the parity of $n$.  First assume $n=2m$.  If $m=2t$ for some $t \geq 1$, then members of $\mathcal{L}$ in this case are of the form $\rho=\rho'sd^{2\ell}$ where $0 \leq \ell \leq t-1$.  Thus $\rho'$ is of length $4t-4\ell-3$ and considering all possible $\ell$ gives
$$|\mathcal{L}|=\sum_{\ell=0}^{t-1}F_{4t-4\ell-2}=F_{2t}^2,$$
where the second equality follows from \cite[Identity 27]{BQ}, which was explained combinatorially there.  Note that since each survivor had sign $(-1)^{n-1}$, the $n=4t$ case of \eqref{tetr-fib1.5} follows.  If $m=2t+1$ where $t\geq 0$, then $\rho \in \mathcal{L}$ implies $\rho=d^{2t}$ or $\rho=\rho'sd^{2\ell}$ where $0 \leq \ell \leq t-1$ and $\rho'$ is of length $4t-4\ell-1$.  This implies
$$|\mathcal{L}|=1+\sum_{\ell=0}^{t-1}F_{4t-4\ell}=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 \cite{BQ}.  This then completes the even case of \eqref{tetr-fib1.5}.  The odd case of \eqref{tetr-fib1.5} follows in a similar fashion and makes use of Identities 26 and 28 from \cite{BQ}.

To show \eqref{tetr-fib2}, first let $\mathcal{B}=\mathcal{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-(\#\text{ of marked tiles})}$.  Note that a cycle of length $i$ within $\sigma \in \mathcal{P}_n$ is associated with a quaternary tiling of length $2i$ for each $i \geq 1$.  Upon marking the final piece within each of these associated tilings and concatenating, one obtains for each $\sigma \in \mathcal{P}_n$ a unique $\lambda_\sigma \in \mathcal{B}$.  Since $\sigma$ and $\lambda_\sigma$ have the same sign for all $\sigma$, it follows that $\det(1;t_5,t_7,\ldots,t_{2n+3})$ gives the sum of the signs of all members of $\mathcal{B}$.

Let $\mathcal{B}'\subseteq \mathcal{B}$ consist of those tilings $\lambda$ of the form $\lambda=s\alpha s$, $s\alpha t$, $t\alpha s$, or $t\alpha t$, where $\alpha$ contains no $s$ or $t$.  Note that members of $\mathcal{B}'$ contain no piece ending in an even-numbered position (other than the terminal) and thus have sign $(-1)^{n-1}$.  Since $n \geq 3$, it is seen upon halving that
$$|\mathcal{B}'|=F_n+2F_{n-1}+F_{n-2}=2F_n+F_{n-1}=F_{n+2}.$$
Furthermore, all members of $\mathcal{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 $\mathcal{B}'$.  To complete the proof of \eqref{tetr-fib2}, define a sign-changing involution of $\mathcal{B}-\mathcal{B}'$ by identifying the rightmost piece terminating at position $2i$ for some $i<n$ and either marking or unmarking that piece.

For \eqref{Theo3e4}, let $\mathcal{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 \eqref{tetr-fib2}.  Then we have that $\det(1;t_4,t_5,\ldots,t_{n+3})$ gives the sum of the signs of all members of $\mathcal{C}$.  Define an involution by either marking or unmarking the penultimate tile.  Note that $n \geq 5$ implies that this involution is defined on all of $\mathcal{C}$, whence the determinant is zero.  \hfill \qed

\subsection{Identities \eqref{Theo3e2} and \eqref{Theo3e3}}

We may assume $n \geq 3$ in the proof of \eqref{Theo3e2}, the $n=1,2$ cases being easily verified.  Let $\mathcal{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 $\sigma \in \mathcal{P}_n$ towards the determinant sum, the product of the superdiagonal $-1$'s is the same as $\text{sgn}(\sigma)$.  Since each cycle $C$ within a contributing $\sigma$ 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,\ldots,t_n)$ gives the \emph{cardinality} of the set $\mathcal{D}$.

We now show that the right side of \eqref{Theo3e2} also counts the members of $\mathcal{D}$, but in a different way.  To do so, note that members of $\mathcal{D}$ may be formed as follows.  Given $0 \leq j \leq n-3$, we first form a square-and-domino tiling $\rho$ 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 $\rho$ that are covered by the $i$ dominos, which can be done in $\binom{2i}{j}$ ways.  Let $d$ denote an arbitrary domino of $\rho$.  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 $\rho$ unchanged and add a marked $t$ to the end of the resulting tiling.   In this way, $\rho$ is transformed to $\rho' \in \mathcal{D}$ in which there are exactly $i+1$ pieces of length at least two altogether (counting the last piece) and $(\# \text{ of } t)+2(\# \text{ of } q)=j+1$.  Since the operation converting $\rho$ to $\rho'$ may be reversed, considering all possible $i$ and $j$ implies $|\mathcal{D}|$ is given by the right side of \eqref{Theo3e2}, as desired.

For \eqref{Theo3e3}, let $\mathcal{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-(\#\text{ of marked } s\text{'s})}$.  Then $\det(1;t_3,t_4,\ldots,t_{n+2})$ gives the sum of the signs of all members of $\mathcal{E}$.  Define an involution on $\mathcal{E}$ by identifying the rightmost non-terminal square and either marking or unmarking it.  Then the set $\mathcal{E}'$ of survivors are synonymous with the tilings of length $n-1$ that use $\{d,t,q\}$, with each member of $\mathcal{E}'$ having sign $(-1)^{n-1}$.  To complete the proof, we must show that the sum on the right side gives $|\mathcal{E}'|$.  Note that we may assume $i\leq j$ in this sum, with $0 \leq n-1-2i-2j \leq j$, for otherwise the product of the binomial coefficients is zero.  Consider members of $\mathcal{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 $\mathcal{E}'$.  Summing over all possible $i$ and $j$ implies \eqref{Theo3e3}.  \hfill \qed \medskip

We conclude with proofs of formulas \eqref{Theo3e5} and \eqref{Theo3e8}, 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.

\subsection{Identities \eqref{Theo3e5} and \eqref{Theo3e8}}

To show \eqref{Theo3e5}, first let $\mathcal{F}_{n,j}$ for $n \geq 2$ and $1 \leq j \leq n$ be given by
$$\mathcal{F}_{n,j}=\{(\lambda_1,\ldots,\lambda_j):\sum_{i=1}^j(|\lambda_i|-1)=n, \text{ where } \lambda_i \text{ is quaternary with } |\lambda_i|\geq 2 \text{ for all } i\}.$$
Define the sign of members of $\mathcal{F}_{n,j}$ by $(-1)^{n-j}$ and let $\mathcal{F}_n=\cup_{j=1}^n\mathcal{F}_{n,j}$.  Then, by the definition of the determinant, we have that $\det(1;t_5,t_6,\ldots,t_{n+4})$ gives the sum of the signs of all members of $\mathcal{F}_n$.

We define a sign-changing involution on $\mathcal{F}_n$ for $n \geq 3$.   To do so, we pair members of $\mathcal{F}_{n,j}$ for the various $j$ with members of $\mathcal{F}_{n,j-1}$ by changing in several cases the final few components of $\lambda=(\lambda_1,\ldots,\lambda_j) \in \mathcal{F}_{n,j}$ as indicated (only the relevant components being shown):
\begin{itemize}
\item $\lambda_{j-1}=\alpha,~\lambda_j=d\longleftrightarrow\lambda_{j-1}=\alpha s$,
\item $\lambda_{j-1}=\alpha,~\lambda_j=t\longleftrightarrow\lambda_{j-1}=\alpha d$,
\item $\lambda_{j-1}=\alpha,~\lambda_j=q\longleftrightarrow\lambda_{j-1}=\alpha t$,
\item $\lambda_{j-1}=\beta d,~\lambda_j=sd\longleftrightarrow\lambda_{j-1}=\beta q$,
\item $\lambda_{j-1}=d,~\lambda_j=sd\longleftrightarrow\lambda_{j-1}=st$,
\item $\lambda_{j-2}=\alpha,~\lambda_{j-1}=s^2,~\lambda_j=sd\longleftrightarrow\lambda_{j-2}=\alpha s,~\lambda_{j-1}=sd$,
\item $\lambda_{j-2}=\alpha,~\lambda_{j-1}=q,~\lambda_j=sd\longleftrightarrow\lambda_{j-2}=\alpha t,~\lambda_{j-1}=sd$,
\item $\lambda_{j-2}=\alpha,~\lambda_{j-1}=sq,~\lambda_j=sd\longleftrightarrow\lambda_{j-2}=\alpha q,~\lambda_{j-1}=sd$,
\end{itemize}
where $\alpha$ and $\beta$ denote tilings of length at least $2$ and $1$, respectively.

We now describe more fully the cases for $2 \leq n \leq 6$.  If $n=2$, then the determinant is zero in this case and we define the pairings on $\mathcal{F}_2$ as follows: $(s^3)\leftrightarrow(s^2,d)$, $(ds)\leftrightarrow(d,d)$,
$(sd)\leftrightarrow(d,s^2)$, and $(t)\leftrightarrow(s^2,s^2)$.  If $n = 3$, then we may apply the general pairings given above for $n \geq 3$, noting that the following cases are missed:  $\lambda=(q)$, $\lambda=(s^2,sd)$, or $\lambda=(\lambda',s^2)$ where $\lambda' \in \mathcal{F}_2$ (written without parenthesization within $\lambda$).  We may then pair the first two cases since they are of opposite sign, with members $\lambda$ 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 $\mathcal{F}_4$ that are not matched in the general pairings above are $\lambda=(t,sd)$ or of the form $\lambda=(\lambda',s^2)$ where $\lambda' \in \mathcal{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 $\lambda \in \mathcal{F}_5$ are those of the form (i) $\lambda=(\lambda',s^2)$ where $\lambda' \in \mathcal{F}_4$, (ii) $\lambda=(s^2,t,sd)$ or $(d,t,sd)$, or (iii) $\lambda=(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 $\lambda \in \mathcal{F}_6$ are those of the form (i) $\lambda=(\lambda',s^2)$ where $\lambda'\in\mathcal{F}_5$, (ii) $\lambda=(\lambda',t,sd)$ where $\lambda' \in \mathcal{F}_2$, or (iii) $\lambda=(s^2,st,sd)$, $(d,st,sd)$, or $(sq,sd)$.  Note that case (ii) contributes zero towards the sum of signs, while the unpaired $\lambda$ 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 \leq n \leq 6$.

If $n \geq 7$, then the set of survivors of the involution above  are those $\lambda$ whose last component is $\gamma=(s^2)$ or whose last two components are either $\delta=(t,sd)$ or $\varepsilon=(st,sd)$.  In this case, we look to the rightmost component of $\lambda$, say $\lambda_s$, where this does not hold and apply one of the pairings given above, provided $\sum_{i=1}^s(|\lambda_i|-1) \geq 7$.  If not, then $\lambda$ may be expressed as $\lambda=\rho\cup\tau$, where $\rho \in \mathcal{F}_i$ for some $2 \leq i \leq 6$ and $\tau$ is a sequence in $\{\gamma,\delta,\varepsilon\}$ such that $\rho\cup x$ has length at least $7$, with $x$ denoting the first ``letter'' of $\tau$.

We may define an involution for $\lambda=\rho \cup \tau$ of the stated form as follows.  First suppose $\rho \in \mathcal{F}_2$.  Then $x=\varepsilon$ and we may pair $\lambda$ accordingly using $\rho$ and the $n=2$ case above.  Henceforth, we may assume $\rho \notin \mathcal{F}_2$.  Suppose that there exists a $\delta,\gamma$ string within $\tau$.  Then we may replace the rightmost occurrence of such a string by $\varepsilon$, and vice versa, which reverses the sign as the number of components of $\lambda$ changes by one.  Note that $\rho \notin \mathcal{F}_2$ implies that this operation is well-defined, for it would never be the case then that we would be replacing an initial $\varepsilon$ letter with $\delta,\gamma$ such that $\rho\cup\delta \in \mathcal{F}_6$.  Now assume $\tau$ has the form $\gamma^k\delta^\ell$ for some $k$ and $\ell$.  If $k \geq 1$, then $\rho$ must belong to $\mathcal{F}_6$ and so we may apply the $n=6$ case to $\rho$. Thus, the only survivors of this last involution (taken together with all of the previous ones) are those $\lambda$ of the form $\lambda=\rho \cup \delta^\ell$ such that $\rho \in \mathcal{F}_r$ where $3 \leq r \leq 6$ and  $r \equiv n$ (mod $4$).  Note that $\rho$ and $\lambda$ have the same sign and thus applying the pairings from the $3 \leq r \leq 6$ cases above to $\rho$ implies for all $n \geq 7$ that $\det(1;t_5,t_6,\ldots,t_{n+4})=\det(1;t_5,t_6,\ldots,t_{r+4})$ where $r$ is as given, which completes the proof of \eqref{Theo3e5}.

To show \eqref{Theo3e8}, define $\mathcal{H}_{n,j}$ for $n \geq 4$ and $1\leq j \leq n$ by
$$\mathcal{H}_{n,j}=\{(\lambda_1,\ldots,\lambda_j):\sum_{i=1}^j|\lambda_i|=2n+j, \text{ where } \lambda_i \text{ is quaternary with } |\lambda_i|\geq 3 \text{ odd for all } i\}.$$
Let members of $\mathcal{H}_{n,j}$ have sign $(-1)^{n-j}$ and $\mathcal{H}_n=\cup_{j=1}^n \mathcal{H}_{n,j}$.  Then it is seen from the definitions that $\det(1;t_6,t_8,\ldots,t_{2n+4})$ gives the sum of the signs of all members of $\mathcal{H}_n$.

We define a sign-changing involution on $\mathcal{H}_n$.  To do so, we pair members of $\mathcal{H}_{n,j}$ with members of $\mathcal{H}_{n,j-1}$ by changing in several cases the final few components of $\lambda=(\lambda_1,\ldots,\lambda_j) \in \mathcal{H}_{n,j}$ as indicated (only the relevant components being shown):
\begin{itemize}
\item $\lambda_{j-1}=\alpha,~\lambda_j=s^3\longleftrightarrow \lambda_{j-1}=\alpha d$,
\item $\lambda_{j-1}=\alpha,~\lambda_j=sd\longleftrightarrow \lambda_{j-1}=\alpha s^2$,
\item $\lambda_{j-1}$ not ending in $q,~\lambda_j=ds \longleftrightarrow \lambda_{j-1}'$,
\item $\lambda_{j-2}=\gamma d,~\lambda_{j-1}=t,~\lambda_j=t\longleftrightarrow\lambda_{j-2}=\gamma q,~\lambda_{j-1}=ds$,
\item $\lambda_{j-2}=\beta s,~\lambda_{j-1}=t,~\lambda_j=t \longleftrightarrow \lambda_{j-2}=\beta t,~ \lambda_{j-1}=t$,
\item $\lambda_{j-2}=\alpha,~\lambda_{j-1}=sq,~\lambda_j=t \longleftrightarrow\lambda_{j-2}=\alpha q,~ \lambda_{j-1}=t$,
\item $\lambda_{j-1}=\beta s,~\lambda_j=t \longleftrightarrow\lambda_{j-1}=\beta t$,
\item $\lambda_{j-1}=\gamma d,~\lambda_j=t \longleftrightarrow\lambda_{j-1}=\gamma q$,
\end{itemize}
where $\alpha$, $\beta$ and $\gamma$ represent arbitrary tilings of lengths at least $3$, $2$ and $1$, respectively, and $\lambda_{j-1}'$ in the third case is obtained from $\lambda_{j-1}$ by increasing the length of the last tile by one and then appending $s$.  Note that the sixth case above requires $n \geq 4$.

Let $\mathcal{H}_n^*$ denote the set comprising those members of $\mathcal{H}_n$ not covered by one of the preceding pairings.  Then $\lambda \in \mathcal{H}_n^*$ implies either (i) the final three or more components of $\lambda$ 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 $\lambda$ equal $t$, preceded by a tiling that ends in $t$ or $q$ and containing at least two pieces, or (iii) $\lambda=(t,\ldots,t)\in \mathcal{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 $\mathcal{H}_n$ is paired with another of opposite sign except for $\lambda=(t,\ldots,t)$ whose sign is positive, which yields \eqref{Theo3e8}. \hfill \qed

\begin{thebibliography}{99}


\bibitem{Alfuraidan}
M.~R.~Alfuraidan and I.~N.~Joudah, On a new formula for Fibonacci's family
$m$-step numbers and some applications, \textit{Mathematics} \textbf{7}
(2019), 805.

\bibitem{Alikhani}
S.~Alikhani and Y.-H.~Peng, Chromatic zeros and generalized Fibonacci
numbers, \textit{Appl. Anal. Discrete Math.} \textbf{3} (2009), 330--335.

\bibitem{Basu-Coding}
M.~Basu and M.~Das, Coding theory on Fibonacci $n$-step numbers,
\textit{Discrete Math. Algorithms Appl.} \textbf{6} (2014), 1450017.

\bibitem{Basu}
M.~Basu and M.~Das, On Fibonacci $n$-step numbers,
\textit{Asian-Eur. J. Math.} \textbf{8} (2015), 1550067.

\bibitem{BH}
A.~T.~Benjamin and C.~R.~Heberle, Counting on $r$-Fibonacci numbers, \textit{Fibonacci Quart.} \textbf{52} (2014), 121--128.

\bibitem{BQ}
A.~T.~Benjamin and J.~J.~Quinn, \textit{Proofs that Really Count: The Art of Combinatorial Proof}, Mathematical Association of America, 2003.

\bibitem{Cahill}
N.~D.~Cahill, J.~R.~D'Errico, D.~A.~Narayan, and J.~Y.~Narayan,
Fibonacci determinants, \textit{College Math. J.} \textbf{3} (2002), 221--225.

\bibitem{Chen}
Y.~H.~Chen and C.~Y.~Yu,
A new algorithm for computing the inverse and the determinant of a Hessenberg matrix,
\textit{Appl. Math. Comput.} \textbf{218} (2011), 4433--4436.

\bibitem{Christensen}
S.~Christensen, Generalized Fibonacci numbers and Blackwell's renewal theorem,
\textit{Statist. Probab. Lett.} \textbf{82} (2012), 1665--1668.

\bibitem{Dresden}
G.~P.~B.~Dresden and Z.~Du, A simplified Binet formula for $k$-generalized Fibonacci numbers,
\textit{J. Integer Seq.} \textbf{17} (2014), \,\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Dresden/dresden6.html}{Article 14.4.7}.

\bibitem{GS}
T.~Goy and M.~Shattuck, Determinant identities for Toeplitz-Hessenberg matrices with tribonacci number entries, \textit{Trans. Comb.}, to appear, 2020.

\bibitem{Howard}
F.~T.~Howard and C.~Cooper,  Some identities for $r$-Fibonacci numbers, \textit{Fibonacci Quart.} \textbf{49} (2011), 231--243.

\bibitem{Jin}
Z.~Jin, Tetranacci identities with squares, dominoes, and hexagonal double-strips, preprint, 2019,
\url{http://arXiv:1907.09935v1}.

\bibitem{Karaduman}
E.~Karaduman, On determinants of matrices with general Fibonacci numbers entries,
\textit{Appl. Math. Comput.} \textbf{167} (2005), 670--676.

\bibitem{Knuth}
D.~Knuth, \textit{The Art of Computer Programming, Vol. 3: Sorting and Searching}, Addison-Wesley, 1998.

\bibitem{Koshy}
T.~Koshy, \textit{Fibonacci and Lucas Numbers and Applications}, 2nd ed., John Wiley \& Sons, 2017.

\bibitem{Li}
R.~Li, Convolution identities for tetranacci numbers, preprint, 2016, \url{http://arxiv.org/abs/1609.05272v1}.

\bibitem{Lucas}
S.~K.~Lucas, Representing numbers using Fibonacci variants, in J.~Beineke and J.~Rosenhouse, eds., \emph{The Mathematics of Various Entertaining Subjects: Research in Recreational Math}, Princeton University Press, 2015,
pp.\ 245--260.

\bibitem{Maroulas}	
J.~Maroulas, Factorization of Hessenberg matrices,
\textit{Linear Algebra Appl.} \textbf{506} (2016), 226--243.

\bibitem{MM1}
M.~Merca, A note on the determinant of a Toeplitz-Hessenberg matrix,
\textit{Spec. Matrices} \textbf{1} (2013), 10--16.

\bibitem{MM2}
M.~Merca, A generalization of the symmetry between complete and elementary symmetric functions, \textit{Indian J. Pure Appl. Math.} \textbf{45} (2014), 75--89.

\bibitem{Miles}
E.~P.~Miles, Jr., Generalized Fibonacci numbers and associated matrices,
\textit{Amer. Math. Monthly} \textbf{67} (1960), 745--752.

\bibitem{Muir}
T.~Muir, \textit{The Theory of Determinants in the Historical Order of Development, Vol.~3}, Dover Publications, 1960.

\bibitem{Philippou}
A.~N.~Philippou and A.~A.~Muwafi, Waiting for the $k$th consecutive success and the Fibonacci sequence of order  $k$, \textit{Fibonacci Quart.} \textbf{20} (1982), 28--32.

\bibitem{Rachidi}
M.~Rachidi, E.~H.~Saidi, and J.~Zerouaoui, Fractional statistics in terms of the $r$-generalized Fibonacci sequences, \textit{	Int. J. Mod. Phys. A} \textbf{18} (2003), 159--171.

\bibitem{Sloane} N.~J.~A.~Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2019. Available at \url{https://oeis.org}.

\bibitem{Waddill1}
M.~E.~Waddill, The tetranacci sequence and generalizations, \textit{Fibonacci Quart.} \textbf{30} (1992), 9--20.

\bibitem{Waddill2}
M.~E.~Waddill, Some properties of the tetranacci sequence modulo $m$, \textit{Fibonacci Quart.} \textbf{30} (1992), 232--238.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 15A15; Secondary 05A19, 15B05.



\noindent \emph{Keywords:} tetranacci number, Toeplitz-Hessenberg matrix, Trudi's formula, generating function, Fibonacci number, tribonacci number.

\bigskip
\hrule
\bigskip

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


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 9 2019; 
revised version received April 2 2020.
Published in {\it Journal of Integer Sequences}, June 11 2020.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in





\end{document}



