\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\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 \LARGE\bf Determinants and Recurrence Sequences  \\
\vskip .1in } \vskip 1cm \large {
Milan Janji\'c \\
Department of Mathematics and Informatics\\
University of Banja Luka \\
Republic of Srpska\\
Bosnia and Herzegovina\\
\href{mailto:agnus@blic.net}{\tt agnus@blic.net}\\
}
\end{center}

\vskip .2in

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

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

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

Also, several relationships among terms of sequences defined by
the same recurrence equation are derived.
\end{abstract}




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

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

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

In Section~\ref{sec5}, we consider $3$-determinants which connect terms of
three sequences given by the same
 recurrence equation.

   The obtained results are concerned with several sequences from \cite{slo}.

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

Let $n$ and $r$ be  positive integers. We consider the following
$n+r-1$ by $r$ matrix
\begin{equation}\label{mpa}P=\begin{pmatrix}
p_{1,1}&p_{1,2}&\cdots&p_{1,r-1}&p_{1,r}\\
p_{2,1}&p_{2,2}&\cdots&p_{2,r-1}&p_{2,r}\\
\vdots&\vdots&\cdots&\vdots&\vdots\\
p_{n,1}&p_{n,2}&\cdots&p_{n,r-1}&p_{n,r}\\
-1&p_{n+1,2}&\cdots&p_{n+1,r-1}&p_{n+1,r}\\
0&-1&\cdots&p_{n+2,r-1}&p_{n+2,r}\\
\vdots&\vdots&\cdots&\vdots&\vdots\\
0&0&\cdots&p_{n+r-2,r-1}&p_{n+r-2,r}\\
0&0&\cdots&-1&p_{n+r-1,r}
\end{pmatrix}.\end{equation}
Note that entries $(n+i,i),\;(i=1,\ldots,r-1)$ in $P$ equal $-1.$
\begin{definition}
 If   $Q$ is a  submatrix of order $r$ of $P,$ we say that $\det Q$ is an $n$-determinant.
\end{definition}

We connect matrix (\ref{mpa}) with a recursively given sequence of
vector-columns in the following way: Let $A$ be a square matrix of
order $n.$  We define a block matrix
$A_r=[A|A_{n+1}|\cdots|A_{n+r}]$ of $n$ rows and $n+r$ columns
(where $A_{n+j},\;(j=1,2,\ldots,r)$ are vector -columns) as
follows:
\begin{equation}\label{r1} A_{n+j}=\sum_{i=1}^{n+j-1}p_{i,j}A_i,\;(j=1,2,\ldots,r).\end{equation}
We shall establish a relationship of $n$-determinants and minors
of order $n$ of $A_r.$

For a  sequence  $1\leq j_1<j_2<\cdots<j_r<n+r$ of positive
integers, we
 let $M=M(\widehat{j_1},\widehat{j_2},\ldots,\widehat{j_r})$ denote  the  minor of $A_r$ of order $n,$  obtained  by deleting  columns  $j_1,j_2,\ldots,j_r$ of $A_r.$
 We shall also write $M(\widehat{j_1},\ldots,\widehat{j_r},A_{i_1},A_{i_2},\ldots,A_{i_k})$ if we want to stress that $M$ contains  $i_1,i_2,\ldots,i_k$ columns of $A_r.$

Note that the last column of $A_r$ cannot be deleted.

The sign $\sigma(M)$ of $M$  is defined as
      \[\sigma(M)=(-1)^{nr+j_1+j_2+\cdots+j_r+\frac{(r-1)r}{2}}.\]
We let  $Q=Q(j_1,\ldots,j_r)$ denote the submatrix of order $r,$
laying in $j_1,j_2,\ldots,j_r$ rows of $P.$ Hence, $\det Q$ is an
$n$-determinant.



We now prove the following result.
\begin{theorem}\label{th1} Let $1\leq j_1<\cdots<j_r<r+n$ be a sequence of positive integers.
Then,
\begin{equation}\label{ttt}M(\widehat{j_1},\ldots,\widehat{j_r})=\sigma(M)\cdot \det Q\cdot \det A.\end{equation}
\end{theorem}
\begin{proof}
The proof is by induction on  $r.$ For  $r=1,$ we have  $1\leq
j_1\leq n,$ since the case $j_1>r$ makes no sense. It follows that
$M=M(\widehat{j_1}).$ Taking $i=1$ in (\ref{r1}), we obtain
\[A_{n+1}=\sum_{m=1}^n p_{m,1}A_{m}.\]
Hence, we obtain $M(\widehat{j_1})$ as a sum of $n$ terms. It is
clear that this sum reduces to a single term, in which $m=j_1.$
We conclude that
\[M(\widehat{j_1})=p_{j_1,1}M(\widehat{j_1},A_{j_1}),\]
where $M(\widehat{j_1},A_{j_1})$ denotes the minor of order $n$ of
$A_r,$ in which the $j_1$th column is shifted at the $n$th place.
In $M(\widehat{j_1},A_{j_1}),$ we interchange the last column with
the preceding one and repeat this until the  $j_1$th column takes
the $j_1$th place.
 For this, we need  $n-j_1$ interchanges. It follows  that
 \[M(\widehat j_1)=(-1)^{n+j_1}p_{j_1,1}\cdot \det A.\]
On the other hand, we obviously have $\det Q=p_{j_1,1},$ and
 $\sigma(M)=(-1)^{n+j_1},$ which proves the theorem, for $r=1.$

Assume  that the theorem is true for  $1\leq k<r.$ The last column
of the minor  $M(\widehat{j_1},\ldots,\widehat{j_r})$ is column
$n+r$ of $A_r.$ The condition  (\ref{r1}) implies
\[ M(\widehat{j_1},\ldots,\widehat{j_r})=\sum_{m=1}^{n+r-1}p_{m,r}
 M(\widehat{j_1},\ldots,\widehat{j_r},A_m).\]
Note that the column $A_m$ is the last column in each minor on the
right-hand side of the preceding equation. Hence, in the sum on
the right-hand side only terms obtained for
$j_m\in\{j_1,\ldots,j_r\}$ remain. They  are of the form:
\[S(t)=p_{j_t,r}M(\widehat{j_1},\ldots,\widehat{j_t},\ldots \widehat{j_r},A_{j_t}),\;(t=1,2,\ldots,r),\]
that is,
\[S(t)=(-1)^{n+r-1-j_t}p_{j_t,r}M(\widehat{j_1},\ldots,A_{j_t},\ldots \widehat{j_r}).\]

Applying the induction hypothesis yields
 \[S(t)=(-1)^{n+t-1-j_t}\sigma(M(\widehat{j_1},\ldots,A_{j_t},\ldots \widehat{j_r}))p_{j_t,r}
 Q(j_1,\ldots,\widehat{j_t},\ldots,j_r)\cdot \det A.\]
By a simple calculation, we obtain
\[(-1)^{n+t-1-j_t}\sigma(M(\widehat{j_1},\ldots,A_{j_t},\ldots \widehat{j_r}))=(-1)^{r+t}
\sigma(M),\] hence,
\[S(t)=\sigma(M)(-1)^{r+t}Q(j_1,\ldots,\widehat{j_t},\ldots,j_r)\cdot \det A.\]

Summing over all $t$ gives
\[\sum_{t=1}^rS(t)=\sigma(M)\bigg[\sum_{t=1}^r(-1)^{r+t}p_{j_t,r}Q(j_1,\ldots,\widehat{j_t},\ldots,j_r)\bigg]\cdot \det A.\]
The expression in the square brackets is the expansion  of $\det
Q$ by elements of the last column, and the theorem is proved.
\end{proof}


We now investigate a particular class of $n$-determinants, arising
from an $n+r-1$ by $r$  block-matrix $P$ of the form
\begin{equation}\label{matp}P=\left[\frac{S}{T}\right],\end{equation}
where
\[S=\begin{pmatrix}
p_{1,1}&p_{1,2}&\cdots&p_{1,r-1}&p_{1,r}\\
p_{2,1}&p_{2,2}&\cdots&p_{2,r-1}&p_{2,r}\\
\vdots&\vdots&\cdots&\vdots&\vdots\\
p_{n,1}&p_{n,2}&\cdots&p_{n,r-1}&p_{n,r}\\
\end{pmatrix},\;T=\begin{pmatrix}-1&0&\cdots&0&0\\
\vdots&\vdots&\cdots&\vdots&\vdots\\
0&0&\cdots&-1&0
\end{pmatrix}.\]

\begin{proposition} Each $n$-determinant of the matrix (\ref{matp}) equals, up to the sign, a minor of $S.$
\end{proposition}
\begin{proof}
We obtain an $n$-determinant by deleting $n-1$ rows of $P.$  It
follows that each $n$-determinant must contain at least one row of
$S.$ Let $1\leq j_1<j_2<\cdots<j_k\leq n<j_{k+1}<\cdots<j_r<
n+r,\;(k\geq 1)$ be arbitrary, and consider the submatrix $Q$
laying in $j_1,j_2,\ldots,j_r$ rows of $P.$ It has the following
form \[Q=\left(\frac{Q_1}{Q_2}\right),\] where $Q_1$ lies in rows
$j_1,j_2,\ldots,j_k$ of $S,$ and $Q_2$ lies in rows
$j_{k+1}-n,\ldots, j_r-n$ of $T.$ If $k=r,$ then $Q=Q_1,$
therefore $\det Q$ is a minor of $S.$

Thus, we may assume that  $k<r.$ We  calculate $\det Q$ by
expansion across the rows of $Q_2.$ The matrix $Q_2$ has a unique
nonzero minor $D$ of order $r-k,$ which lies in $k+1,\ldots,r$
rows of $Q.$ Its value obviously equals   $(-1)^{r-k}.$ The sum of
the indices of rows of $Q,$  in which $D$ lies, is
\[(k+1)+(k+2)+\cdots+r=\frac{(r-k)(r+k+1)}{2}.\]
The sum of indices of columns in which $D$ lies equals
          \[(j_{k+1}-n)+\cdots+(j_{r}-n)=j_{k+1}+\cdots+j_r-(r-k)n.\]
We thus obtain that
\[\det Q=(-1)^\tau\det Q_4,\]
where $\tau= \frac{(r-k)(k+r+3-2n)}{2}+j_{k+1}+\cdots+j_r,$ and
$\det Q_4$ is the complement minor of $D,$ laying in columns
different from $j_{k+1},\ldots,j_{r}.$ Clearly, $\det Q_4$ is a
minor of $S,$ and the proposition is true.
\end{proof}
As a consequence of Theorem (\ref{ttt}) we obtain
\begin{proposition}
Let $A$ be arbitrary matrix of order $n,$ let $B$ be arbitrary $n$
by $r$ matrix. Consider the block matrix $A_r=[A|AB].$ Let $1\leq
j_1<j_2<\cdots<j_k\leq n<j_{k+1}<\cdots<j_r< n+r,\;(k\geq 1)$ be
arbitrary. If $M(\widehat{j_1},\ldots,\widehat{j_r})$ has the same
meaning as before, then
\begin{equation}\label{Q4}(-1)^{\sigma}M=\det A\cdot \det{Q_4},\end{equation}
where $\sigma=\frac{k^2-2kn+k}{2}+j_1+j_2+\cdots+j_k,$ and
 the submatrix $Q_4$  lies in $j_1,j_2,\ldots,j_k$ rows, and  in columns different from $j_{k+1},j_{k+2},\ldots,j_r$ of $B.$
\end{proposition}
\begin{proof} It is easy to see that the matrix $A_r,$ corresponding to the matrix (\ref{matp}), has the form
\[A_r=[A|AB].\] After a simple calculation we obtain $\sigma=\frac{k^2-2kn+k}{2}+j_1+j_2+\cdots+j_k,$ and the assertion follows from the preceding proposition.
\end{proof}
\begin{remark}
Note that equation (\ref{Q4}) is a generalization of the theorem
of the product of two determinants.
\end{remark}
Namely, in the  case $r=n=k,$ and $j_i=i,\;(i=1,2,\ldots,n),$ we
have $\det Q=\det B,\;M=\det A B,$ and $\sigma(M)=1,$  so that
equation
 (\ref{Q4})  becomes \[\det(AB)=\det A\cdot\det B.\]




\section{$1$-determinants}
\label{sec3}
In this case,  $A$ is a matrix of order $1$, that is, a single
element.
 We also have  $j_1=1,j_2=2,\ldots,j_r=r,$ hence,
the minor $M(\widehat{j_1},\widehat{j_2},\ldots,\widehat{j_r})$
must be of the form:
 $M(\hat 1,\hat 2,\ldots,\hat r).$ We easily obtain that $\sigma(M)=1.$
The matrix $P$ is as follows:
 \begin{equation}\label{mp1}P=\begin{pmatrix}
p_{1,1}&p_{1,2}&p_{1,3}&\cdots&p_{1,r-1}&p_{1,r}\\
-1&p_{2,2}&p_{2,3}&\cdots&p_{2,r-1}&p_{2,r}\\
0&-1&p_{3,3}&\cdots&p_{3,r-1}&p_{3,r}\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&p_{r-1,r-1}&p_{r-1,r}\\
0&0&0&\cdots&-1&p_{r,r}\end{pmatrix}.\end{equation}

 We see that  $Q=P.$ Therefore,  each $1$-determinant is an  upper Hessenberg
 determinant. Applying Theorem \ref{th1}, we obtain the following result.
\begin{proposition}\label{tn1}
Let  $a_1,a_2,\ldots$ be a sequence  such that
\begin{equation}\label{fn}a_{1+r}=\sum_{i=1}^rp_{i,r}a_i.\end{equation}
Then,
\[a_{r+1}=a_1\det P.\]
\end{proposition}
This result is known. For instance, it follows from Theorem
4.20,\cite{hh}.
\begin{remark}
In the paper \cite{mil}, we  found a combinatorial interpretation
for the coefficients of the characteristic polynomials of some
$1$-determinants.
\end{remark}
We give a number of examples for sequences given by the formula
(\ref{fn}). Some of them are well-known. In all examples, we take
$a_1=1.$
\begin{enumerate}
\item[$1^\circ$] \textbf{ Catalan numbers} (\seqnum{A000108}).  We
let $C_n$ denote the $n$th Catalan number. If we take
$p_{i,j}=C_{j-i},$ then equation (\ref{fn}) becomes
\[a_{1+r}=\sum_{i=1}^rC_{r-i}a_i.\]
The Segner's recurrence formula for Catalan numbers implies that
$a_{r+1}=C_r.$ Hence, a way to write the Segner's formula in terms
of determinants is
\[C_r=\begin{vmatrix}
C_0&C_1&C_2&\cdots&C_{r-2}&C_{r-1}\\
-1&C_0&C_1&\cdots&C_{r-3}&C_{r-1}\\
0&-1&C_0&\cdots&C_{r-4}&C_{r-3}\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&C_0&C_1\\
0&0&0&\cdots&-1&C_0\end{vmatrix}.\]

\item[$2^\circ$]\textbf{ Bell numbers} (\seqnum {A000110}). If one
takes $p_{i,j}={j-1\choose i-1}$ in (\ref{mp1}), then (\ref{fn})
becomes the recursion for the Bell numbers.
    Thus, a determinantal expression for the Bell number $B_r$ is
\[B_r=\begin{vmatrix}
\left({0\atop 0}\right)&\left({1\atop 0}\right)&\left({2\atop 0}\right)&\cdots&\left({r-2\atop 0}\right)
&\left({r-1\atop 0}\right)\vspace{1mm}\\
-1&\left({1\atop 1}\right)&\left({2\atop 1}\right)&\cdots&\left({r-2\atop 1}\right)
&\left({r-1\atop 1}\right)\vspace{1mm}\\
0&-1&\left({2\atop 2}\right)&\cdots&\left({r-2\atop 2}\right)&\left({r-1\atop 2}\right)\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&\left({r-2\atop r-2}\right)&\left({r-1\atop r-2}\right)\vspace{1mm}\\
0&0&0&\cdots&-1&\left({r-1\atop r-1}\right)\end{vmatrix}.\]

The order of the determinant equals $r.$

\item[$3^\circ$]\textbf{ Eigensequences for Stirling numbers}
 (\seqnum{A003659}). If $\left\{{n\atop k}\right\}$ is the Stirling
number of the second kind, and $p_{i,j}=\left\{{j-1\atop
i-1}\right\}$ in (\ref{mp1}),
 then (\ref{fn}) becomes the recursion for the so-called eigensequence $(E_1,E_2,\ldots)$ of the Stirling number of the second kind.
 Therefore,
\[E_r=\begin{vmatrix}
\left\{{0\atop 0}\right\}&\left\{{1\atop 0}\right\}&\left\{{2\atop 0}\right\}&\cdots&
\left\{{r-2\atop 0}\right\}&\left\{{r-1\atop 0}\right\}\vspace{1mm}\\
-1&\left\{{1\atop 1}\right\}&\left\{{2\atop
1}\right\}&\cdots&\left\{{r-2\atop 1}\right\}&
\left\{{r-1\atop 1}\right\}\vspace{1mm}\\
0&-1&\left\{{2\atop 2}\right\}&\cdots&\left\{{r-2\atop 2}\right\}&\left\{{r-1\atop 2}\right\}\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&\left\{{r-2\atop r-2}\right\}&\left\{{r-1\atop r-2}\right\}\vspace{1mm}\\
0&0&0&\cdots&-1&\left\{{r-1\atop r-1}\right\}\end{vmatrix}.\]

Note that analogous identity holds for the unsigned Stirling
numbers of the first kind  (\seqnum{A143805}). \item[$4^\circ$]
\textbf{ Factorials} (\seqnum{A000142}). Let $k$ be a positive
integer. Consider the following $1$-de\-ter\-mi\-nant $D$  of
order $r>1$:
\[D=\begin{vmatrix}
1&1&1&1&\cdots&1&1\\
-1&k&k&k&\cdots&k&k\\
0&-1&k+1&k+1&\cdots&k+1&k+1\\
0&0&-1&k+2&\cdots&k+2&k+2\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\
0&0&0&\cdots&-1&k+r-3&k+r-3\\
0&0&0&\cdots&0&-1&k+r-2\end{vmatrix}.\] In this case, the formula
(\ref{fn}) becomes
\[a_{r+1}=1+\sum_{i=2}^r(k+i-2)a_i.\]
Subtracting the equation
\[a_{r+2}=1+\sum_{i=2}^{r+1}(k+i-2)a_i\] from the preceding easily yields
\[a_{r+2}=(k+r)a_{r+1},\] which is the recursion for the falling factorials. Hence,
\[D=\frac{(k+r-1)!}{k!}.\]


\item[$5^\circ$] {\bf Derangements} (\seqnum{A000166}). We let
$D_r$ denote the number of derangements of $r.$ The recurrence
equation for the derangements is
\[D_2=1,D_3=2,\;D_r=(r-1)(D_{r-2}+D_{r-1}),\;(r\geq 4).\] Hence,
\[D_{r+1}= \begin{vmatrix}
1&1&0&0&\cdots&0&0\\
-1&1&2&0&\cdots&0&0\\
0&-1&2&3&\cdots&0&0\\
0&0&-1&3&\cdots&0&0\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&0&r-1&r\\
0&0&0&\cdots&0&-1&r\end{vmatrix}.\]

\item[$6^\circ$]{\bf Fibonacci polynomials}. In this case, we
consider the recurrence equation
\[a_1=1,a_2=x,\;a_{k+1}=a_{k-1}+xa_k,\;(k\geq 2)\]
 for Fibonacci polynomials.
 Hence, for  Fibonacci polynomial $F_{r+1}(x)$  we have
\[F_{r+1}(x)=
\begin{vmatrix}
x&1&0&\cdots&0&0\\
-1&x&1&\cdots&0&0\\
0&-1&x&\cdots&0&0\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&x&1\\
0&0&0&\cdots&-1&x\end{vmatrix}.\] The order of the determinant
equals $r.$ Taking $x=1,$, in particular, we obtain the well-known
determinantal expression for Fibonacci numbers.


\item[$7^\circ$] {\bf Tchebychev polynomials of the first kind}.
The recurrence relation for the  Tchebychev polynomials of the
first kind is
\[T_0(x)=1,\;T_1(x)=x,\; T_{k}(x)=-T_{k-2}(x)+2xT_{k-1}(x),\;(k>2).\]
Theorem \ref{tn1} now implies the following equation:
\[T_{r}(x)=\begin{vmatrix}
x&-1&0&\cdots&0&0\\
-1&2x&-1&\cdots&0&0\\
0&-1&2x&\cdots&0&0\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&2x&-1\\
0&0&0&\cdots&-1&2x\end{vmatrix}.\] The order of the determinant is
$r.$ A similar formula holds for Tchebychev polynomials $U_r(x)$
of the second kind. \item[$8^\circ$]{\bf Hermite polynomials.} For
the Hermite polynomials $H_r(x),$ we have the following recurrence
equation:
\[H_0(x)=1,\;H_1(x)=2x,\; H_{r+1}(x)=-2rH_{r-1}(x)+2xH_{r}(x),\;(r\geq 2).\]
Applying Theorem \ref{tn1},  we obtain the following expression:
\[H_{r}(x)=
\begin{vmatrix}
2x&-2&0&\cdots&0&0\\
-1&2x&-4&\cdots&0&0\\
0&-1&2x&\cdots&0&0\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&2x&-2(r-1)\\
0&0&0&\cdots&-1&2x\end{vmatrix}.\]


\item[$9^\circ$] {\bf Continuants}. Take in (\ref{fn})
$p_{k,k}=p_k,\;p_{k-1,k}=1,$ and  $p_{i,j}=0$ otherwise.  We
obtain the recursion:
\[a_1=1,p_1,\;a_{1+k}=a_{k-1}+p_ka_k,\;(k=2,\ldots).\]
The terms of this sequence are the continuants, and are denoted by
$(p_1,p_2,\ldots,p_r).$ We thus obtain the following well-known
formula:
\begin{equation}\label{kon}(p_1,p_2,\ldots,p_r)=\begin{vmatrix}
p_1&1&0&\cdots&0&0\\
-1&p_2&1&\cdots&0&0\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
0&0&0&\cdots&p_{r-1}&1\\
0&0&0&\cdots&-1&p_r\end{vmatrix}.\end{equation}


\item[$10^\circ$] {\bf Linear homogenous recurrence equation}. Let
$b_1,b_2,\ldots,b_k$ be given elements. Consider the sequence
$1,a_2,a_3,\ldots$ defined as follows:
\[a_2=b_1,\ldots,a_{k+1}=b_k,\;a_{r+1}=\sum_{i=r-k+1}^rp_{i,r}a_i,\;(r>k).\]
We thus have a linear homogenous recurrence equation of order $k.$
From Theorem \ref{th1} follows
\[a_{r+1}=\begin{vmatrix}
b_1&b_2&\cdots&b_k&0&0&\cdots&\cdots&0\\
-1&0&\cdots&0&p_{k+1,1}&0&\cdots&\cdots&0\\
0&-1&\cdots&0&p_{k+1,2}&p_{k+2,2}&\cdots&\cdots&0\\
\vdots&\vdots&\cdots&\vdots&\vdots&\vdots&\cdots&\cdots&\vdots\\
0&0&\cdots&0&p_{k+1,k-1}&p_{k+2,k-1}&\cdots&\cdots&0\\
0&0&\cdots&-1&p_{k+1,k}&p_{k+2,k}&\cdots&\cdots&0\\
\vdots&\vdots&\cdots&\vdots&\vdots&\vdots&\cdots&\cdots&0\\
0&0&\cdots&0&\vdots&\vdots&\cdots&\cdots&\cdots\\
0&0&\cdots&0&\vdots&\vdots&\cdots&-1&p_{k,r}
\end{vmatrix}.\]

\item[$11^\circ$] {\bf Generalized Fibonacci numbers}. Taking in
the preceding formula that each $p_{i,j}$ equals $1,$ we obtain
$k$-step Fibonacci numbers dependent on the initial conditions.
The standard $k$-step Fibonacci numbers $F^{(k)}_{n+k}$ are
obtained for $b_1=b_2=\cdots=b_{k-1}=0,\;b_k=1.$ We thus have
\[F^{(k)}_{r+k}=\begin{vmatrix}
1&1&\cdots&1&0&\cdots&0&0&0\\
-1&1&\cdots&1&1&\cdots&0&0&0\\
0&-1&\cdots&1&1&\cdots&0&0&0\\
\vdots&\vdots&\cdots&\vdots&\vdots&\cdots&\vdots&\vdots&\vdots\\
0&0&\cdots&0&0&\cdots&\cdots&\vdots&\vdots\\
0&0&\cdots&0&0&\cdots&\cdots&-1&1
\end{vmatrix},\]
where the size of the determinant is $r+k.$


\item[$12^\circ$]{\bf Fibonacci numbers} (\seqnum{A000045})
Consider the sequence given by
\[a_1=1,\;a_2=1,\;a_r=\sum_{i=1}^{r-2}a_i,\;(r>2).\] This, in
fact, is a recursion for the Fibonacci numbers. To show this, we
first replace $r$ by $r+1$ to obtain
 \[a_{r+1}=\sum_{i=1}^{r-1}a_i.\]
 Subtracting two last equations yields
 \[a_{r+1}=a_{r}+a_{r-1},\] which is the standard recursion for the Fibonacci numbers.

Proposition \ref{tn1} implies
\[F_{r-1}=\begin{vmatrix}
1&1&\cdots&1&\cdots&1&1\\
-1&0&\cdots&1&\cdots&1&1\\
0&-1&\cdots&1&\cdots&1&1\\
\vdots&\vdots&\cdots&\vdots&\cdots&\vdots&\vdots\\
0&0&\cdots&0&\cdots&0&1\\
0&0&\cdots&0&\cdots&-1&0
\end{vmatrix}.\]
The order of the determinant equals $r.$



\item[$13^\circ$]{\bf Fibonacci numbers. } We define a matrix
$Q_r=(q_{ij})$ of order $r$ as follows:
\[q_{ij}=\begin{cases}
-1, & \text{if }i=j+1;\\
i+j+1\,\bmod 2, & \text{if } i\leq j;\\
0,&\text{otherwise}.
\end{cases}\]
We find the recursion which, as in Proposition \ref{tn1}, produces
this matrix. Obviously, $a_1=1,\;a_2=1,\;a_3=1,\;a_4=2,$ and
\[a_{2r}=a_1+\cdots+a_{2r-1}.\] Also, \[a_{2r+2}=a_1+\cdots+a_{2r-1}+a_{2r+1}.\]
Subtracting two last equation yields $a_{2r+2}=a_{2r+1}+a_{2r}.$
Similarly, $a_{2r+1}=a_{2r}+a_{2r-1}.$  The recursion for the
Fibonacci numbers is thus obtained. It follows that $F_{r-1}=\det
Q_r,\;(r>1).$


 \item[$14^\circ$]{\bf Fibonacci numbers with odd
indices} (\seqnum{A001519}). Define a matrix $Q_r=(q_{ij})$ of
order $r$ as follows:
\[q_{ij}=\begin{cases}
-1, & \text{if } i=j+1,\\
2, & \text{if } i=j,\\
1, & \text{if } i<j, \\ 
0, &\text{otherwise}.
\end{cases}.\]

In this case, we have the recursion
$a_1=1,\;a_{2}=2,\;a_3=5,\;a_{r+1}=\sum_{i=1}^{r-1}+2a_r,\;(r\geq
2).$ From this, we easily obtain the recursion
\[a_{r+2}=3a_{r+1}-a_r.\] The identity 7, proved in \cite{bk}, shows that we have a recursion for the Fibonacci numbers with odd indices.
It follows that  $F_{2r+1}=\det Q_r.$

Note that we described in \cite{mil} a connection of this
determinant with a particular kind of composition of natural
numbers.

\item[$15^\circ$] {\bf Fibonacci numbers with even indices}
(\seqnum{A001906 }). For the matrix
\[Q_r=\begin{vmatrix}
1&2&3&\cdots&r-1&r\\
-1&1&2&\cdots&r-2&r-1\\
0&-1&1&\cdots&r-3&r-2\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
0&0&0&\cdots&1&2\\
0&0&0&\cdots&-1&1\end{vmatrix},\] the corresponding recursion has
the form:
\[a_1=1,\;a_2=3,\;
a_{1+r}=\sum_{i=1}^r(r-i+1)a_i,\;(r\geq 2).\] Also,
\[a_{2+r}=\sum_{i=1}^{r+1}(r-i+1)a_i+\sum_{i=1}^{r+1}a_i.\]
Subtracting this equation from the preceding one, we obtain
\[a_{2+r}-a_{1+r}=\sum_{i=1}^{r+1}a_i.\]
In the same, way we obtain
\[a_{3+r}-a_{2+r}=\sum_{i=1}^{r+2}a_i.\]
Again, we subtract this equation from the preceding one to obtain
\[a_{3+r}=3a_{2+r}-a_{1+r}.\]  This is a recursion for Fibonacci numbers, by   Identity 7 in  \cite{bk}. Taking into count the initial conditions, we have $\det Q_r=F_{2r}.$
\end{enumerate}


\section{$2$-determinants}
\label{sec4}
In this section we consider the case $n=2.$ We first investigate
the case that $p_{i,j}=0,\;(j>i).$ Then, $P $ has at most three
nonzero diagonals, and  may be written in the form:
\begin{equation}\label{pa2}P=\begin{vmatrix}
b_{1}&0&0&\cdots&0&0\\
c_{2}&b_{2}&0&\cdots&0&0\\
-1&c_{3}&b_{3}&\cdots&0&0\\
0&-1&c_{4}&\cdots&0&0\\
\vdots&\vdots&\vdots&\cdots&\vdots&\vdots\\
0&0&\vdots&\cdots&c_{r}&b_{r}\\
0&0&\vdots&\cdots&-1&c_{r+1}
\end{vmatrix}.\end{equation}
The corresponding $2$-determinant $\det Q$ is a lower triangular
block determinant of the form:
\begin{equation}\label{mq}\left|\begin{array}{c|c}Q_{11}&0\\\hline Q_{12}&Q_{22}\end{array}\right|.\end{equation}
Here,   $Q_{11}$ is a lower triangular determinant lying in the
first $k$ rows and the first $k$ columns of $Q.$ It follows that
$Q_{11}=b_{1}\cdots b_{k}.$
 The order of $Q_{22}$ is $r-k$ and it is of the same form as the determinant of the  matrix $P$ in (\ref{mp1}).

As a consequence of Theorem \ref{th1}, we obtain
\begin{proposition}\label{dvan} Let $(b_1,b_2,\ldots),\;(c_2,c_3,\ldots)$ be any two sequences. Let  \[(a_1^{(i)},a_2^{(i)},\ldots)\;(i=1,2)\] be two sequences defined by the same
recurrence equation of  the second order:
\[ a_r^{(i)}=b_{r-2}a^{(i)}_{r-2}+c_{r-1}a^{(i)}_{r-1},\;(r>2),\;(i=1,2)..\] Then,
\[\begin{vmatrix}a_{k+1}^{(1)}&a_{r+2}^{(1)}\\a_{k+1}^{(2)}&a_{r+2}^{(2)}\end{vmatrix}=(-1)^{k}b_1\cdots b_k
\cdot d_{r-k+1}\cdot
\begin{vmatrix}a_{1}^{(1)}&a_{2}^{(1)}\\a_{1}^{(2)}&a_{2}^{(2)}\end{vmatrix},\]
 where
 \[d_1=1,\;d_2=c_{k+2},\;d_i=b_{k+i-1}d_{i-2}+c_{k+i}d_{i-1},\;(i>2)..\]
\end{proposition}

We illustrate the preceding proposition with  some examples.
\begin{enumerate}
\item[$1^\circ$] {\bf Fibonacci polynomials}. Take
$x_{1}^{(1)}=F_u(x),\;x_{2}^{(1)}=F_{u+1}(x),\;x_{1}^{(2)}=F_{v}(x),\;x_{2}^{(2)}=F_{v+1}(x),\;b_i=1,\;c_{i+1}=x,\;(i=1,2,\ldots).$

Note that, in this case, the $2$-determinant equals the Fibonacci
polynomial $F_{r-k}(x).$ From Proposition \ref{dvan}, we obtain
the following identity:
\begin{equation}\label{xxy}\begin{vmatrix}F_{u+k}(x)&F_{u+r}(x)\\F_{v+k}(x)&F_{v+r}(x)\end{vmatrix}=(-1)^{k}
F_{r-k}(x)\cdot
\begin{vmatrix}F_{u}(x)&F_{u+1}(x)\\F_{v}(x)&F_{v+1}(x)\end{vmatrix}.\end{equation}
Several well-known formulas may be obtained from this.

Taking $u=1,v=0$ yields
\[F_{k+1}(x)F_r(x)-F_k(x)F_{r+1}(x)=(-1)^{k}F_{r-k}(x),\]
which is the  Ocagne's identity for the Fibonacci polynomials.
Applying this identity on the right-hand side of (\ref{xxy}),  we
obtain
\[\begin{vmatrix}F_{u+m}(x)&F_{u+r}(x)\\F_{v+m}&F_{v+r}(x)\end{vmatrix}=(-1)^{m+u+1}F_{r-m}(x)F_{v-u}(x).\]


We now may easily derive the index-reduction formula for the
Fibonacci polynomials. Namely, replacing $m$ by $m-t$ and $r$ by
$r-t,$ we get
\[\begin{vmatrix}F_{u+k-t}(x)&F_{u+r-t}(x)\\F_{v+k-t}(x)&F_{v+r-t}(x)\end{vmatrix}=(-1)^{k-t+u+1}F_{r-k}(x)
F_{v-u}(x).\] Comparing the last two equations produces
\[\begin{vmatrix}F_{u+k-t}(x)&F_{u+r-t}(x)\\F_{v+k-t}(x)&F_{v+r-t}(x)\end{vmatrix}=(-1)^t
\begin{vmatrix}F_{u+k}(x)&F_{u+r}(x)\\F_{v+k}(x)&F_{v+r}(x)\end{vmatrix},\]
which is the index reduction formula.

Note that such a formula for the Fibonacci numbers is proved  in
\cite{Jo}.


\item[$2^\circ$] {\bf Fibonacci and Lucas polynomials}. The Lucas
polynomials $L_r(x)$ satisfy the same recurrence relation as do
the  Fibonacci polynomials with different initial conditions. In
this case, also, the $1$-determinant equals a Fibonacci
polynomial. We state two equations, one for mixed Lucas and
Fibonacci polynomials, another for Lucas polynomials:
\[\begin{vmatrix}F_{u+k}(x)&F_{u+r}(x)\\L_{v+k}(x)&L_{v+r}(x)\end{vmatrix}=(-1)^{k}F_{r-k}(x)\cdot
\begin{vmatrix}F_{u}(x)&F_{u+1}(x)\\L_{v}(x)&L_{v+1}(x)\end{vmatrix},\]
and
\[\begin{vmatrix}L_{u+k}(x)&L_{u+r}(x)\\L_{v+k}(x)&L_{v+r}(x)\end{vmatrix}=(-1)^{k}F_{r-k}(x)\cdot
\begin{vmatrix}L_{u}(x)&L_{u+1}(x)\\L_{v}(x)&L_{v+1}(x)\end{vmatrix}.\]
\item[$3^\circ$] {\bf Tchebychev polynomials.} Tchebychev
polynomials of the first and second kind also satisfy the same
recursion with different initial conditions. Here, the
$1$-determinant equals a Tchebychev polynomial of the second kind.
 We  state the following three identities, which are a consequence of Proposition \ref{dvan}.
  \[\begin{vmatrix}U_{u+k}(x)&U_{u+r}(x)\\U_{v+k}(x)&U_{v+r}(x)\end{vmatrix}=U_{r-k-1}(x)
\begin{vmatrix}U_u(x)&U_{u+1}(x)\\U_v(x)&U_{v+1}(x)\end{vmatrix},\]

\[\begin{vmatrix}T_{u+k}(x)&T_{u+r}(x)\\T_{v+k}(x)&T_{v+r}(x)\end{vmatrix}=U_{r-k-1}(x)
\begin{vmatrix}T_u(x)&T_{u+1}(x)\\T_v(x)&T_{v+1}(x)\end{vmatrix},\]

\[\begin{vmatrix}U_{u+k}(x)&U_{u+r}(x)\\T_{v+k}(x)&T_{v+r}(x)\end{vmatrix}=U_{r-k-1}(x)
\begin{vmatrix}U_u(x)&U_{u+1}(x)\\T_v(x)&T_{v+1}(x)\end{vmatrix}.\]


\item[$4^\circ$] {\bf Continued fractions}. Up until now, the
division was not used. We might therefore  assume that the
elements of the concerned sequences belong to any commutative ring
with $1.$ In this part, we suppose that they are positive real
numbers. Let $A_2$ be the identity matrix of order $2,$ and let
$(c_1,c_2,\ldots)$ be an arbitrary sequence of positive real
numbers.
   Form the matrix  $A_{r}$
by the following rule:
\[A_{2+k}=A_{k}+c_kA_{k+1},\;(k=1,2,\ldots,r).\]
It is easy to see that $A_r$  has the form:
     \[A_r=\begin{pmatrix}1&0&1&c_2&\ldots&(c_2,c_3,\ldots,c_{r})\\
0&1&c_1&(c_1,c_2)
&\ldots&(c_1,c_2,c_3,\ldots,c_{r})\end{pmatrix},\] where
$(c_m,c_{m+1},\ldots,c_p)$ are the continuants. The
$1$-determinant equals the  continuant
$(c_{k+2},c_{k+3},\ldots,c_{r}).$

The fundamental recurrence relation for the continued fractions
gives an expression  for the difference between two consecutive
convergents. Equation \ref{dvan} allows us to derive a formula for
the difference between two arbitrary convergents. The following
formula holds:
\[\begin{vmatrix}(c_2,c_3,\ldots,c_{k})&(c_2,c_3,\ldots,c_{r})\\(c_1,c_2,c_3,\ldots,c_{k})&(c_1,c_2,c_3,\ldots,c_{r})
\end{vmatrix}=(-1)^{k+1}(c_{k+2},c_{k+3},\ldots,c_{r}),\]
or, equivalently,
\[\frac{(c_1,c_2,c_3,\ldots,c_{r})}{(c_2,c_3,\ldots,c_{r})}-
\frac{(c_1,c_2,c_3,\ldots,c_{k})}{(c_2,c_3,\ldots,c_{k})}=
(-1)^{k+1}\frac{(c_{k+2},c_{k+3},\ldots,c_{r})}{(c_2,c_3,\ldots,c_{k})\cdot
(c_2,c_3,\ldots,c_{r})},\] with the convention that for $r=k+1$
the expression    $(c_{k+2},c_{k+3},\ldots,c_{r})$ equals $1.$

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

\item[$5^\circ$]{\bf Derangements.} Take
$A=\begin{pmatrix}1&0\\1&1\end{pmatrix}.$ Let the matrix $A_r$ be
formed by the recursion
\[A_{2+r}=r(A_{1+r}+A_{r}),\;(r\geq 1).\]
 It is obvious that the $r$th element of the first row of $A_r$ equals $D_{r-1}.$ Also, the $r$th term of
 the second row of $A_r$ equals
  $(r-1)!.$
It follows that
\[M(k+1,r+1)=\begin{vmatrix}D_k&D_r\\k!&r!\end{vmatrix}.\]
We thus obtain the following identity:
\[\begin{vmatrix}D_k&D_r\\k!&r!\end{vmatrix}=
(-1)^{k}k! \begin{vmatrix}
k+1&k+2&0&\cdots&0&0\\
-1&k+2&k+3&\cdots&0&0\\
0&-1&k+3&\cdots&0&0\\
0&0&-1&\cdots&0&0\\
\vdots&\vdots&\vdots&\vdots&\vdots\\
0&0&0&\cdots&r-1&r\\
0&0&0&\cdots&-1&r\end{vmatrix}.\] In particular, for $r=k+1,$ we
have the standard recursion $D_{k+1}=kD_k+(-1)^k$ for the
derangements.
\end{enumerate}
The preceding identities are derived from homogenous recurrence
equations of order two. We shall now consider the case of a
recurrence equation of order three.

\begin{theorem}
Let $r$ be a positive integer, and let
$(a_i),(b_{i+1}),(c_{i+2}),\;(i=1,2,\ldots)$ be arbitrary
sequences. Let $A$ be a matrix of order $2,$ and let the matrix
$A_r$ be defined as follows:
 \[A_{3}=b_1A_1+c_2A_2,\;A_{3+j}=a_jA_j+b_{j+1}A_{j+1}+c_{j+2}A_{j+2},\;(1<j<r-2).\]
Then, the corresponding $2$-determinant $Q$  is determined by two
homogenous recurrence equations of order $3.$
\end{theorem}
\begin{proof}
In this case the matrix $P$ has the following form:
 \[P=\begin{pmatrix}
b_1&a_1&0&\cdots&0&0&0\\
c_2&b_2&a_2&\cdots&0&0&0\\
-1&c_3&b_3&\dots&0&0&0\\
0&-1&c_4&\dots&0&0&0\\
\vdots&\vdots&\vdots&\cdots&\vdots&\vdots&\vdots\\
0&0&0&\cdots&c_{r-1}&b_{r-1}&a_{r-1}\\
0&0&0&\cdots&-1&c_{r}&b_{r}\\
0&0&0&\cdots&0&-1&c_{r+1}
\end{pmatrix}.\]
The $2$-determinant  $\det Q$ is  obtained from $P$ by deleting
the $(k+1)$th  row of $P,$
 where $(0\leq k<r).$  We let $D(i_1,\ldots,i_t)$ denote the minor of $P,$ the main diagonal of which is $(i_1,i_2,\ldots,i_t).$ Hence, \[\det Q=D(b_1,\ldots,b_k,c_{k+2},\ldots,c_{r+1}).\]

In the  expansion of  $\det Q$ across the first $k$ rows all terms
are zero, except eventually two. Hence,
\[\det Q=D(b_1,\ldots,b_k)D(c_{k+2},\ldots,c_{r+1})+a_kD(b_1,\ldots,b_{k-1})D(c_{k+3},\ldots,c_{r+1}).\]
Furthermore, we have
\[D(b_1)=b_1,\;
D(b_1,b_2)=\begin{vmatrix}b_{1}&a_{1}\\c_{2}&b_{2}\end{vmatrix},\;D(b_1,b_2,b_3)=\begin{vmatrix}b_{1}&a_{1}&0\\c_{2}&b_{2}&a_{2}\\
 -1&c_{3}&b_3\end{vmatrix}.\]

Assume $k>3.$
 Expanding $D(b_1,\ldots,b_k)$ by the elements of the last column, we obtain
\begin{equation}\label{tri1}D(b_1,\ldots,b_k)=b_{k}D(b_1,\ldots,b_{k-1})-
a_{k-1}c_kD(b_1,\ldots,b_{k-2})-a_{k-1}a_{k-2}D(b_1,\ldots,b_{k-3}).\end{equation}

Also, \[D(c_{k+2})=c_{k+2},\;
D(c_{k+2},c_{k+3})=\begin{vmatrix}c_{k+2}&b_{k+2}\\-1&c_{k+3}\end{vmatrix},\]
and
\[D(c_{k+2},c_{k+3},c_{k+4})=\begin{vmatrix}c_{k+2}&b_{k+2}&a_{k+2}\\-1&c_{k+3}&b_{k+3}\\
 0&-1&c_{k+4}\end{vmatrix}.\]

If $k>3,$ then by expanding $D(c_{k+2},\ldots,c_{r+1})$ along the
first column, we obtain
\begin{equation}\label{tri2}\begin{aligned}D(c_{k+2},\ldots,c_{r+1})\\&=c_{k+3}D(c_{k+3},\ldots,c_{r+1})
+b_{k+2}D(c_{k+4},\ldots,c_{r+1})\\&+a_{k+2}D(c_{k+5},\ldots,c_{r+1}).\end{aligned}\end{equation}

It follows that the $2$-determinant $\det Q$ is uniquely
determined by the recurrence equations  (\ref{tri1}) and
(\ref{tri2}).
\end{proof}


We illustrate the preceding considerations with two particular
cases. We first  assume that all $a$'s, $b$'s, and $c$'s equal
$1.$ Then,
\[D(b_1)=1,\;D(b_1,b_2)=0,\;D(b_1,b_2,b_3)=-2,\]
and, for $s>3,$
\[D(b_1,b_2,\ldots,b_s)=D(b_1,\ldots,b_{s-1})-D(b_1,\ldots,b_{s-2})
-D(b_1,\ldots,b_{s-3}).\] This recursion designates the so-called
\textbf{reflected Tribonacci numbers} (\seqnum{A057597}). We
denote these numbers by $RT_i\;(i=1,2,\ldots).$ Also,
\[D(c_1)=1,\;D(c_1,c_2)=2,\;D(c_1,c_2,c_3)=4,\]
and, for $s>3,$
\[D(c_1,c_2,\ldots,c_s)=D(c_1,\ldots,c_{s-1})+D(c_1,\ldots,c_{s-2})
+D(c_1,\ldots,c_{s-3}).\] Hence, if we denote by
$T_i,\;i=0,1,2,\ldots$ the Tribonacci numbers (\seqnum{A000073})
we have
\[D(c_1,c_2,\ldots,c_s)=T_{s+2},\;(s=1,2,\ldots).\]
Hence, our $2$-determinant $Q$ consists of Tribonacci and
reflected Tribonacci numbers. On the other hand, if $A$ is the
identity matrix of order $2,$ then the first row of $A_r$ consists
of the above  Tribonacci numbers. The second rows consists of
Tribonacci numbers $\tilde T_i,\;(i=0,1,\ldots)$ with the initial
conditions given by $\tilde T(0)=1,\;\tilde T(1)=0,\;\tilde
T(2)=1,$ (\seqnum{A001590}). As a consequence of Theorem
\ref{th1}, we have
\begin{corollary} Let $k<r$ be nonnegative integers.  The following identity holds
\[\begin{vmatrix}\tilde T_{k+1}&\tilde T_{r+2}\\T_{k+1}&T_{r+2}\end{vmatrix}=(-1)^k
\begin{vmatrix}RT_{k-1}&-RT_{k}\\T_{r-k}&T_{r-k-1}\end{vmatrix}.\]
\end{corollary}
Assume now that the $b$'s are all equal zero and the $a$'s and the
$c$'s are all equal $1.$ Then the recursion (\ref{tri1}) gives the
sequence $x_1,x_2,\ldots,$ such that $x_n=\seqnum{A077962}(n).$
Also, the recursion (\ref{tri2}) produces the sequence
$y_1,y_2,\ldots,$ such that $y_n=\seqnum{A000930}(n).$

Next, the rows of $A_r$ form sequences
$a^{(i)}_1,a^{(i)}_2,\ldots\;(i=1,2)$ such that, for $n\geq 4$ we
have
$a^{(1)}_n=\seqnum{A000930}(n-4),\;a^{(2)}_n=\seqnum{A000930}(n-2).$
We thus obtain
\begin{corollary} For integers $3\leq k<r$ we have
\[\begin{vmatrix}y_{k-3}&y_{r-2}\\y_{k-1}&y_r\end{vmatrix}=(-1)^k
\begin{vmatrix}x_{k-1}&-x_k\\y_{r-k}&y_{r-k-1}\end{vmatrix}.\]



\end{corollary}

\section{$3$-determinants}
\label{sec5}

In this section, the order of the matrix $A$ is $3.$ We
investigate in detail the particular case when
$p_{i,j}=0,\;(j>i).$  Then, the matrix $P$ is of order
$(r+2)\times r,$  may have at most four nonzero diagonals, and has
the form:
 \[P=\begin{pmatrix}
a_1&0&0&\cdots&0&0&0\\
b_2&a_2&0&\cdots&0&0&0\\
c_3&b_3&a_3&\dots&0&0&0\\
-1&c_4&b_4&\dots&0&0&0\\
0&-1&c_5&\cdots&0&0&0\\
\vdots&\vdots&\vdots&\cdots&\vdots&\vdots&\vdots\\
0&0&0&\cdots&c_r&b_r&a_r\\
0&0&0&\cdots&-1&c_{r+1}&b_{r+1}\\
0&0&0&\cdots&0&-1&c_{r+2}
\end{pmatrix}.\]
The corresponding $3$-determinant $\det Q$   is  obtained by
deleting rows $k+1$ and $m+1$ of $P,$  where $(0\leq k<m\leq
r+1).$ The matrix $Q$ is a lower triangular block matrix of the
form (\ref{mq}),
  with $\det Q_{11}=a_1\cdot a_2\cdots a_k.$
 The order of the matrix  $Q_{22}$ is $r-k.$


 We denote $\det Q_{22}=D_k(s,r),$ where $s=m-k.$ Note that $s\geq 1.$
 For the columns of $A_r$ we have the following recursion:
  \begin{equation}\label{rekk}A_{3+i}=a_iA_{i}+b_{i+1}A_{1+i}+c_{i+2}A_{i+2},\;(i\geq 1).\end{equation}
  It follows that the sequences in the rows of $A_r$ satisfy recurrence equations of order $3,$
 with the initial conditions given by the rows of $A.$
The set $\{j_1,\ldots,j_r\}$ equals
$\{1,2,\ldots,k,k+2,\ldots,m,m+2,\ldots,r+2\}.$  A simple
calculation shows that $\sigma(M)=(-1)^{m+k+1}.$ As a consequence
of  Theorem \ref{th1}, we have
\begin{proposition}\label{cetiri} Let $A$ be any matrix of order $3$, let $(a_i),(b_{i+1}),(c_{i+2}),\;(i=1,2,\ldots)$
 be any sequences.
Then,
\[M(k+1,m+1,r+2)=(-1)^{m+k+1}a_1\cdots a_k\det Q \cdot\det A.
\]
\end{proposition}
We next prove the following Proposition 12.
\begin{proposition}
The determinant $\det Q_{22}$ is determined with three recurrence
relations.
\end{proposition}
\begin{proof}
 The matrix
$Q_{22}$ has at most  five nonzero   diagonals. Assume that $s\geq
3.$ 1) The main  diagonal of $Q_{22}$ is
 \[b_{k+2},\ldots,b_{k+s},\widehat{k+s+1},c_{k+s+2},\ldots,c_{r+2},\]
where there are $s-1$ of $b$'s and $r+1-k-s$ of $a$'s\\
2) The first superdiagonal  is
\[a_{k+2},\ldots,a_{k+s},\widehat{k+s+1},b_{k+s+2}\ldots,b_{r+1},\] where
there are  $s-1$ of $a$'s and $r-k-s$ of $b$'s.\\
 3) The first subdiagonal is
 \[c_{k+3},\ldots,c_{k+s},\widehat{k+s+1},-1,\ldots,-1,\]
where  there are  $s-2$ of $c$'s and $r+1-k-s$ of $-1$'s.\\
 4) The second superdiagonal is
  \[0,\ldots,0,\widehat{k+s+1},a_{k+s+2},\ldots,a_r,\]
  where  there are $s-1$ of $0$'s and $r-k-s-1$ of $a$'s.\\
 5) The second subdiagonal is
 \[-1,\ldots,-1,\widehat{k+s+1},0,\dots,0,\]
 where  there are $s-3$ of $-1$'s and $r+1-k-s$ of $0$'s.


{\bf Case $s=1$}. We begin with
\[D_k(1,k)=1,\;D_k(1,k+1)=c_{k+3},\;D_k(1,k+2)= \begin{vmatrix}c_{k+3}&b_{k+3}
 \\-1&c_{k+4}\end{vmatrix}.\]
 For $t>2,$ expanding $D_k(1,k+t)$ by elements from the last row yields the following recursion:
\begin{equation}\label{rek1}\begin{aligned}D_k(1,k+t)\\&=c_{k+t+2}D_k(1,k+t-1)+b_{k+t+1}D_k(1,k+t-2)\\&
+a_{k+t}D_k(1,k+t-3).\end{aligned}\end{equation}


{\bf Case $s=2$}. We have
\[D_k(2,k+1)=b_{k+2},\;D_k(2,k+2)= \begin{vmatrix}b_{k+2}&a_{k+2}
 \\-1&c_{k+4}\end{vmatrix},\]\[
 D_k(2,k+3)=\begin{vmatrix}b_{k+2}&a_{k+2}&0\\-1&c_{k+4}&b_{k+4}\\
 0&-1&c_{k+5}\end{vmatrix}.\]
For $t\geq 4,$  we calculate $D_k(2,k+t)$ by the recursion
(\ref{rek1}).

{\bf Case $s=3$}. We now have $D_k(3,k+2)=b_{k+2},$
\[D_k(3,k+3)= \begin{vmatrix}b_{k+2}&a_{k+2}
 \\c_{k+3}&b_{k+3}\end{vmatrix},\;
 D_k(3,k+4)=
 \begin{vmatrix}b_{k+2}&a_{k+2}&0\\c_{k+3}&b_{k+3}&a_{k+3}\\
 0&-1&c_{k+5}\end{vmatrix},
 \]
 \[D_k(3,k+5)=\begin{vmatrix}b_{k+2}&a_{k+2}&0&0\\c_{k+3}&b_{k+3}&a_{k+3}&0\\
 0&-1&c_{k+5}&b_{k+5}\\0&0&-1&c_{k+6}\end{vmatrix}.\]
For $t>5,$ we calculate $D_k(3,k+t)$ again by the recursion
(\ref{rek1}).

{\bf Case $s\geq 4.$} The minors  $D_k(s,k+s-1),\ldots,D_k(s,
k+2s-1)$ may be obtained as follows:
\[D_k(s,k+s-1)=b_{k+2},\;
  D_k(s,k+s)=\begin{vmatrix}b_{k+2}&a_{k+2}
 \\c_{k+3}&b_{k+3}\end{vmatrix},\]\[
 D_k(s,k+s+1)=\begin{vmatrix}b_{k+2}&a_{k+2}&0\\c_{k+3}&b_{k+3}&a_{k+3}\\
 -1&c_{k+4}&b_{k+4}\end{vmatrix}
 .\]  When $1<t\leq s-1,$  we have the following recursion:
 \begin{equation}\label{post}\begin{aligned}D_k(s,k+s+t)\\&=b_{t+k+2}D_k(s,k+s+t-1)-
 a_{t+k+1}c_{t+k+2}D_k(s,k+s+t-2)\\&-
a_{t+k+1}a_{t+k}D_k(s,k+s+t-3).\end{aligned}\end{equation}

 Next, we have
  \[D_k(s,k+2s)=c_{s+k+2}D_k(s,k+2s-1)+a_{s+k}D_k(s,k+2s-2).\]
  If $s<r-k,$ then
 \[ D_k(s,k+2s+1)=c_{s+k+3}D_k(s,k+2s)+b_{s+k+2}D_k(s,k+2s-1).\]
 If $s+1<r-k,$ then for $t$, where $s+1<t\leq r-k,$ we have the recursion (\ref{rek1}).

The recursion with respect to $k$ is backward. The minimal value
that $r$ can take is $r=k.$ Then,
\[D_k(1,k)=1,\;D_k(2,k+1)=D_{k}(3,k+2)=b_{k+2}.\]
 Assume that $s>3.$ Expanding $D_k(s,r)$ by elements of the first row, we obtain the following recursion:
\begin{equation}\label{pok}\begin{aligned}D_k(s,r)=b_{k+2}D_{k+1}(s-1,r-1)\\&-a_{k+2}c_{k+3}D_{k+2}(s-2,r-2)\\&
-a_{k+2}a_{k+3}D_{k+3}(s-3,r-3)\end{aligned}.
   \end{equation}
We have thus proved that $\det Q$ is uniquely determined by the
formulas (\ref{rek1}), (\ref{post}), and (\ref{pok}).
\end{proof}

 We state some particular cases.
\begin{enumerate}
\item[$1^\circ$] All $a$'s equal $0.$
 It follows from (\ref{cetiri})  that all minors $M(k+1,m+1,r+3)$ are zeros, except the case $k=0,$
when we have the same situation as in the preceding section.

\item[$2^\circ$]  All $b$'s equal $0,$ and all $a$'s and $c$'s
equal $1$. The formula (\ref{rekk}) has the form:
\[A_{3+i}=A_{i}+A_{i+2},\;(i\geq 1).\]

If $A$ is the identity matrix, then the rows of $A_r$ make the
so-called {\bf middle sequence}\\(\seqnum{A000930}). For a fixed
$k$ the first three rows of the array $\det Q_{22}$ are obtained
by the recursion (\ref{rek1}), hence they are also formed from the
numbers of the middle sequence. If $s>3,$ then the first $s-1$
elements in row $s$  are obtained by the recursion
 (\ref{post}). The remaining terms are again obtained from (\ref{rek1}).
Therefore, Proposition (\ref{cetiri}) gives  an identity for the
numbers of the middle sequence.

\item[$3^\circ$]  All $c$'s equal $0$, and all $a$'s
 and $b$'s equal $1$.
In this case, we have
\[A_{3+i}=A_{i}+A_{i+1},\;(i\geq 1),\] which is
the recursion for the {\bf Padovan} sequence (\seqnum{A000931}).
From Proposition \ref{cetiri}, we obtain an assertion for the
Padovan numbers.

\item[$4^\circ$]  All $a$'s, $b$'s and $c$'s equal $1$. The rows
of $A_r$ are made of Tribonacci numbers, with the initial
conditions given by the rows of $A.$ Proposition \ref{cetiri}
produces an identity for Tribonacci numbers.

Assume that $A$ is the identity matrix of order $3.$ Let
$T_{t_1,t_2,t_3}(n),\;(n=1,2,\ldots)$  denote Tribonacci numbers
with initial conditions
$T_{t_1,t_2,t_3}(1)=t_1,T_{t_1,t_2,t_3}(2)=t_2,T_{t_1,t_2,t_3}(3)=t_3.$
\end{enumerate}

We then have

\begin{proposition}
Let $0\leq k<m<r+2$ be integers. Then,
\[
\begin{vmatrix} T_{1,0,0}(k)&T_{1,0,0}(m)&T_{1,0,0}(r+2)\\
T_{0,1,0}(k)&T_{0,1,0}(m)&T_{0,1,0}(r+2)\\
T_{0,0,1}(k)&T_{0,0,1}(m)&T_{0,0,1}(r+2)\\
\end{vmatrix}=(-1)^{m+k+1}D_k(m-k,r).\]
\end{proposition}
Note that the nature of numbers $D_k(m-k,r)$ depends on values of
$k,m-k$ and $r.$
\begin{thebibliography}{11}

\bibitem{hh} R. Vein and P. Dale, \textit{Determinants and Their Applications in Mathematical Physics},
 Springer-Verlag, 1999.

\bibitem{bk} A. T. Benjamin and J. J. Quinn, \textit{Proofs that Really
Count}, Mathematical Association of America, 2003.

\bibitem{mil}  M, Janji\'c, Hessenberg matrices and integer sequences,
\textit{J. Integer Sequences}, {\bf 10} (2010), 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Janjic/janjic33.html}{Article 10.7.8}.

\bibitem{Jo} R. C. Johnson, Fibonacci numbers and matrices, manuscript 
available at\\
\url{http://www.dur.ac.uk/bob.johnson/fibonacci/}, 2008.


\bibitem{slo}
 N. J. A. Sloane, Online Encyclopedia of Integer Sequences,
 \url{http://oeis.org}. 

\bibitem{sta} R. P. Stanley, \textit{Enumerative Combinatorics},
Vol.\ 2, Cambridge University Press, 1999.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11P99; Secondary 11B39.

\noindent \emph{Keywords: } determinant, recurrence equation,
Fibonacci number, convergent, derangements.


\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  December 20 2011;
revised version received  March 13 2012.
Published in {\it Journal of Integer Sequences}, March 13 2012.

\bigskip
\hrule
\bigskip

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


\end{document}