\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