<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}{-.1in}
\setlength{\textheight}{8.4in}

\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
Parapermanents of Triangular Matrices and  Some General Theorems on Number Sequences\\
\vskip .1in } \vskip 1cm \large
Roman Zatorsky and Taras Goy\\
Vasyl Stefanyk Precarpathian National University \\
Department of Mathematics and Informatics \\
Shevchenko str., 57 \\
Ivano-Frankivsk \\
Ukraine\\
\href{mailto:romazatorsky@gmail.com}{\tt romazatorsky@gmail.com} \\
\href{mailto:tarasgoy@yahoo.com}{\tt tarasgoy@yahoo.com} \\
\end{center}

\vskip .2 in


\begin{abstract} 
Applying the apparatus of triangular matrices, this
paper determines general relations between the terms of the sequences
generated by linear homogeneous recurrence equations.  We single out,
in particular, the class of
normal linear recurrence equations, for which
the corresponding number sequences have
some interesting number-theoretic properties.
\end{abstract}

\section{Introduction}

At present, quite a few general theorems have been proved for linear recurrence relations. In fact, their content is similar to corresponding theorems from the theory of linear homogeneous and nonhomogeneous systems of equations with constant coefficients and the theory of homogenous and nonhomogeneous ordinary differential equations with constant coefficients. But so far there are no general methods of solution even for linear homogenous recurrence equations with variable coefficients.

Linear recurrence sequences with constant coefficients are efficiently used in different fields of mathematics (see, for example, \cite{Cull, Rosen, Sedgewick, Taher}). It is necessary, however, to find the exact roots of a corresponding characteristic equation, which can cause considerable difficulties.

The theoretical research tool for studying linear recurrent equations in this paper is parapermanents of triangular matrices \cite{ZatADM, ZatMono}. The paper aims at applying  parapermanents of triangular matrices to solution of linear recurrence equations, determination of general relations between the terms of the sequences generated by these equations, and isolation of the class of normal linear recurrence equations, the number sequences of which have some general number-theoretic properties. The method makes it possible to investigate linear recurrence equations without solving corresponding characteristic equations. Here, the bijection is established between the number sequence defined by linear recurrence relation, its generating function and its $n$-th term given as a parapermanent of some $n$-th order triangular matrix.

\section{Preliminaries and notations}

A triangular table of  numbers
\begin{equation} \label{trmatr}
A= \left(\begin{matrix}
a_{11}\\
a_{21} &amp; a_{22}\\
\cdots &amp; \cdots &amp;\ddots\\
a_{n1} &amp; a_{n2} &amp; \cdots &amp; a_{nn}
\end{matrix}\right)_n
\end{equation}
is called \emph{a triangular matrix}, and the number $n$ is called its order \cite{ZatADM, ZatMono}. Note that a triangular matrix (\ref{trmatr}) is not a triangular matrix in the usual sense of this term as it is not a square matrix.

To every element $a_{ij}$ of the triangular matrix (\ref{trmatr}), we correspond $(i-j+1)$ elements $a_{ik}$, $k=j,j+1,\ldots,i$, which are called \emph{derived elements}, generated by element $a_{ij}$.

The product of all derived elements of the matrix (\ref{trmatr}) generated by element $a_{ij}$ is denote by $\{a_{ij}\}$ and called the \emph{factorial product} of the element $a_{ij}$, i.e.,
$\{a_{ij}\}=a_{ij}\,a_{i,j+1}\cdots a_{ii}$.

To each element $a_{ij}$  of a matrix (\ref{trmatr}) we associate the triangular table of elements of matrix $A$ that has $a_{ij}$ in the bottom left corner. We call this table a \emph{corner} of the matrix and denote it by $R_{ij}(A)$. Corner $R_{ij}(A)$ is a triangular matrix of order $(i-j+1)$, and it contains only elements $a_{rs}$ of matrix (\ref{trmatr}) whose indices satisfy the inequalities $j \leqslant s \leqslant r\leqslant i$.

The \emph{parapermanent} $\emph{\emph{pper}}(A)$ of a triangular matrix (\ref{trmatr}) is the number
\begin{equation}\label{pper}
\emph{\emph{pper}}(A)= \left[
\begin{matrix}
a_{11}\\
a_{21} &amp; a_{22} \\
\cdots &amp; \cdots &amp;\ddots\\
a_{n1} &amp; a_{n2} &amp; \cdots &amp; a_{nn}
\end{matrix}\right]_n =\sum_{r=1}^{n}\sum_{p_{1}+\cdots+p_{r}=n} a_{p_{1},1}\prod_{s=2}^{r}\{a_{p_{1}+\cdots+p_{s},\,\,p_{1}+\cdots+p_{s-1}+1}\},
\end{equation}
where $p_{1},p_{2},\ldots, p_{r}$ are positive integers, $\left\{a_{ij}\right\}$ is the factorial product of the element $a_{ij}$ of the matrix $A$. We shall also denote a parapermanent of the matrix (\ref{trmatr}) briefly by $\left[a_{ij}\right]_{1\leq j\leq i \leq n}$.

The rectangular table $T(i)$ of elements of the triangular matrix (\ref{trmatr}) is \emph{inscribed} in matrix (\ref{trmatr}) if one of its vertex  coincides with the element $a_{n1}$, and its opposite one coincides with the element $a_{ii}$, $i=1,2,\ldots,n$. \cite{ZatDopovidi}

The \emph{parapermanent algebraic complement} $P_{ij}$ to the factorial product $\{a_{ij}\}$ of the element $a_{ij}$ of the matrix (\ref{trmatr}) is the number \cite{ZatADM}
\begin{equation}\label{Pij}
P_{ij}=\emph{\emph{pper}}(R_{j-1,1})\cdot
\emph{\emph{pper}}(R_{n,i+1}),
\end{equation}
where $R_{j-1,1}$ and $R_{n,i+1}$ are corners of the matrix (\ref{trmatr}), and $\emph{\emph{pper}}(R_{01})\equiv 1$, $\emph{\emph{pper}}(R_{n,n+1})\equiv 1$.
\begin{theorem} \label{theoRozklddet} \emph{\cite{ZatADM}}
\emph{(Decomposition of a parapermanent by elements of an inscribed rectangular table)}. Let $A$ be a triangular matrix \emph{(\ref{trmatr})}, and $T(i)$ be some inscribed  rectangular table. Then
\begin{equation}\label{rozkl1}
\emph{pper}(A)=\sum\limits_{s = 1}^i {\sum\limits_{r = i}^n {\left\{ {a_{rs} } \right\}P_{rs}}},
\end{equation}
where $P_{rs}$ is a parapermanent algebraic complement to the factorial product of element $a_{rs}$, which belongs to $T(i)$.
\end{theorem}
\begin{corollary}
For $i=n$ we get decomposition of the parapermanent \emph{pper(}A\emph{)} by elements of the last row:
\begin{equation}\label{rozkladinp}
\text{\em pper}(A)=\sum\limits_{s = 1}^n {\left\{ {a_{ns}}\right\}\cdot\text{\em pper}(R_{s-1,1})}.
\end{equation}
\end{corollary}
\begin{lemma} {\em\cite{ZatMono}} \label{statsystemyrivn1}
The system of equations
\begin{equation*}
x_{i}=a_{ii}b_{1}x_{i-1}+a_{ii}a_{i,i-1}b_{2}x_{i-2}+
\cdots+a_{ii}\cdots a_{i1}b_{i},\quad i=1,2,\ldots,n,
\end{equation*}
has the solution $ x_{i}=\left[a_{sr}\frac{b_{s-r+1}}{b_{s-r}}\right]_{1\leqslant r\leqslant
s\leqslant i}$, where $b_0\equiv 1$.
\end{lemma}
\begin{lemma} {\em \cite{ZatMono}} \label{statsystemyrivn2} The system of equations
\begin{equation*}
\left[
\bigl(1+\delta_{sr}(x_{s}-1)\bigr)\frac{a_{s-r+1}}{a_{s-r}}\right]_{1\leqslant
r\leqslant s\leqslant i}=b_{i}, \quad i=1,2,\ldots,n,
\end{equation*}
where
$\delta_{sr}$ is the Kronecker symbol, $a_{0}=1$, has the solution
\begin{equation*}
\label{rozviazokpopravkybi}
x_{i}=\frac{b_{i}}{a_{i}b_{0}+a_{i-1}b_{1}+a_{i-2}b_{2}+\cdots+a_{1}b_{i-1}} \quad (b_0\equiv 1).
\end{equation*}
\end{lemma}

\section{Parapermanents and $k$-th order linear recurrence equations}

Let us consider the linear recurrence equation of $k$-th order
\begin{equation}\label{linrecurrivnk} u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+\cdots+a_{k}u_{n-k},
\end{equation}
with initial conditions
\begin{equation}
\label{pochatkoviumovy}
u_{0}=1,\,\,\,u_{1}=b_{1},\,\,\,u_{2}=b_{2},\,\ldots,\,\,u_{k-1}=b_{k-1}.
\end{equation}

If it is difficult to solve a characteristic equation of the recurrence
equation (\ref{linrecurrivnk}) then the following proposition can be
useful, as it significantly complements Stanley's theorem
(\cite[p.~202]{Stanley}):

\begin{theorem}\emph{\cite{ZatKPI}.}
\label{theorozvrecurrivnkpochatkovumov} For the sequence
$(u_{n})_{n\geq 0}$ the following three equations are equivalent:

\medskip

{\emph{(1)}} the linear recurrence equation \emph{(\ref{linrecurrivnk})} with initial conditions \emph{(\ref{pochatkoviumovy})};

\medskip

\emph{(2)}
\begin{equation}\label{rozrivzum}
u_{n}=\left[\begin{array}{cccccccc} a_{1}c_{1}&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\
\frac{a_{2}}{a_{1}}&amp;a_{1}c_{2}&amp;&amp;&amp;&amp;&amp;&amp;\\
\cdots&amp;\cdots&amp;\ddots&amp;&amp;&amp;&amp;&amp;\\
\frac{a_{k-1}}{a_{k-2}}&amp;\frac{a_{k-2}}{a_{k-3}}&amp;\cdots&amp;a_{1}c_{k-1}&amp;&amp;&amp;&amp;\\
\frac{a_{k}}{a_{k-1}}&amp;\frac{a_{k-1}}{a_{k-2}}&amp;\cdots&amp;\frac{a_{2}}{a_{1}}&amp;a_{1}&amp;&amp;&amp;\\
0&amp;\frac{a_{k}}{a_{k-1}}&amp;\cdots&amp;\frac{a_{3}}{a_{2}}&amp;\frac{a_{2}}{a_{1}}&amp;a_{1}&amp;&amp;\\
\cdots&amp;\cdots&amp;\cdots&amp;\cdots&amp;\cdots&amp;\cdots&amp;\ddots&amp;\\
0&amp;0&amp;\cdots&amp;0&amp;\frac{a_{k}}{a_{k-1}}&amp;\cdots&amp;\frac{a_{2}}{a_{1}}&amp;a_{1}
\end{array}\right]_{n}
\end{equation}
with $u_0=1$, $a_i\ne 0$ for $i=1,2,\ldots, k-1$, where
\begin{equation}
\label{popravky}
c_{i}=\frac{b_{i}}{a_{i}b_{0}+a_{i-1}b_{1}+\cdots+ a_{1}b_{i-1}},\quad i=1,2,\ldots,k-1,
\end{equation}
with $b_0=1$;

\medskip

\emph{(3)}
\begin{equation}\label{generatrysarecurrivnk}\displaystyle
  1+\sum\limits_{i=1}^{\infty}u_{i}z^{i}=\frac{1+b_1\left(1-\frac{1}{c_1}\right)z+b_2\left(1-\frac{1}{c_2}\right)
  z^{2}+\cdots+b_{k-1}\left(1-\frac{1}{c_{k-1}}\right)z^{k-1}}{1-a_{1}z-a_{2}z^{2}-\cdots-a_{k}z^{k}}, \\
\end{equation}
where $c_i\ne0$ for $i=1,2,\ldots,k - 1$.
\end{theorem}

The theorem is established in \cite{ZatKPI}; we just give the proof for
convenience of the reader.

\begin{proof}  Equivalence of the recurrence equation (\ref{linrecurrivnk}), (\ref{pochatkoviumovy}) and the equation (\ref{rozrivzum}) follows from the fact that numbers $c_{1}, c_{2},\ldots, c_{k-1}$, according to Lemma \ref{statsystemyrivn2}, are solutions of the system of equations
$$
\left[\bigl(1+\delta_{sr}(c_{s}-1)\bigr)\frac{a_{s-r+1}}{a_{s-r}}\right]_{1\leqslant
r\leqslant s\leqslant i}=b_{i},\quad\,i=1,2,\ldots,k-1,
$$
and the decomposition of the parapermanent in (\ref{rozrivzum}) for $n\geq k$ by elements of the last row (see Corollary \ref{rozkladinp}).

Let us now prove the equivalence of the recurrence equation (\ref{linrecurrivnk}) with initial conditions (\ref{pochatkoviumovy}) and the equation (\ref{generatrysarecurrivnk}). To do this, we use the equality
\begin{eqnarray*}
&amp;\left(1-\sum\limits_{i=1}^{k}a_{i}x^{i}\right)\left(1+\sum\limits_{j=1}^{\infty}u_{j}x^{j}\right)=\\
&amp;=1+(u_{1}-a_{1})x+(u_{2}-a_{1}u_{1}-a_{2})x^{2}+(u_{3}-a_{1}u_{2}-a_{2}u_{1}-a_{3})x^{3}+\cdots\\
&amp;\cdots +(u_{k-1}-a_{1}u_{k-2}-a_{2}u_{k-3}-\cdots-a_{k-2}u_{1}-a_{k-1})x^{k-1}+\\
&amp;+\sum\limits_{i=k}^{\infty}(u_{i}-a_{1}u_{i-1}-a_{2}u_{i-2}-\cdots-a_{k}u_{i-k}).
\end{eqnarray*}

In the right hand of above equality, we shall replace $u_{i}$ with $b_{1}, b_2,\ldots, b_{k-1}$, and factor out $b_{1}$ from the first parentheses, $b_{2}$ from the second parentheses, and so on. If we denote 
$$ c_{1}=\frac{b_{1}}{a_{1}},\quad
c_{2}=\frac{b_{2}}{a_{2}+a_{1}b_{1}},\quad
c_{3}=\frac{b_{3}}{a_{3}+a_{2}b_{1}+a_{1}b_{2}},\,\ldots,
$$
then
\begin{eqnarray*}
&amp;\left(1-\sum\limits_{i=1}^{k}a_{i}x^{i}\right)\left(1+\sum\limits_{j=1}^{\infty}u_{j}x^{j}\right)\\
&amp;=1 + b_1\left(1-\frac{1}{c_1}\right)x+b_2\left(1-\frac{1}{c_2}\right)
x^{2}+\cdots+b_{k-1}\left(1-\frac{1}{c_{k-1}}\right) x^{k-1}+\\
&amp;+\sum\limits_{i=k}^{\infty}\left(u_{i}-a_{1}u_{i-1}-a_{2}u_{i-2}
-\cdots-a_{k}u_{i-k}\right).
\end{eqnarray*}
\end{proof}

Note that Theorem \ref{theorozvrecurrivnkpochatkovumov} is also true for the recurrence equations of the form (\ref{linrecurrivnk}) with variable coefficients.

The right hand of the equality (\ref{generatrysarecurrivnk}) is called the \emph{generating function} of the sequence (\ref{linrecurrivnk}).
\begin{example}
For the Tribonacci sequence $u_n=u_{n-1}+u_{n-2}+u_{n-3}$, $u_0=u_1=u_2=1$ (\seqnum{A000213}) from (\ref{popravky}) we shall find the numbers $c_1=\frac{b_1}{a_1}=1$, $c_2=\frac{b_2}{a_2+a_1b_1}=\frac12$, from (\ref{rozrivzum})~--- the $n$-th term of the sequence written with help of the parapermanent of the triangular matrix
\begin{equation} \label{trmatrTribo}
u_n = \left[\begin{matrix}
1\\
1 &amp; \frac12 \\
1 &amp; 1 &amp; 1\\
0 &amp; 1 &amp; 1 &amp; 1 \\
\cdots &amp; \cdots &amp; \cdots &amp; \cdots &amp;\ddots\\
0 &amp; \cdots &amp; 0 &amp; 1 &amp; 1 &amp; 1\end{matrix}\right]_n,
\end{equation}
and from (\ref{generatrysarecurrivnk})~--- the generating function $F(x)=\frac{1-x^2}{1-x-x^2-x^3}$.
\end{example}

Let us consider the case when in (\ref{popravky}) $c_{1}=c_{2}=\cdots=c_{k-1}$. Then from (\ref{popravky}) we get the system
\begin{equation*}\label{newformula}
b_{i}=a_{1}b_{i-1}+a_{2}b_{i-2}+\cdots+a_{i-1}b_{1}+a_{i},\quad\,i=1,2,\ldots,k-1,
\end{equation*}
which, according to Lemma \ref{statsystemyrivn1}, has the solution
\begin{equation}\label{bi}
b_{i}=\left[\begin{array}{cccc} a_{1}&amp;&amp;&amp;\\
\frac{a_{2}}{a_{1}}&amp;a_{1}&amp;&amp;\\
\cdots&amp;\cdots&amp;\ddots&amp;\\
\frac{a_{i}}{a_{i-1}}&amp;\frac{a_{i-1}}{a_{i-2}}&amp;\cdots&amp;a_{1}
\end{array}\right]_{i},\quad\,i=1,2,\ldots,k,
\end{equation}
and the initial conditions (\ref{pochatkoviumovy}) for the recurrence equation (\ref{linrecurrivnk}) becomes
\begin{equation}
\label{normpochum}
u_0=1,\quad u_{i}=\left[\begin{array}{cccc} a_{1}&amp;&amp;&amp;\\
\frac{a_{2}}{a_{1}}&amp;a_{1}&amp;&amp;\\
\cdots&amp;\cdots&amp;\ddots&amp;\\
\frac{a_{i}}{a_{i-1}}&amp;\frac{a_{i-1}}{a_{i-2}}&amp;\cdots&amp;a_{1}
\end{array}\right]_{i},\quad\,i=1,2,\ldots,k-1.
\end{equation}

The initial conditions (\ref{normpochum}) for the recurrence equation (\ref{linrecurrivnk}) are called \emph{normal initial conditions},  and the sequence generated by normal initial conditions is called \emph{a normal sequence.}
\begin{corollary}
\label{consrozvrecurrivnnormum} For the sequence $(u_{n})_{n\geq 0}$ the following three equations are equivalent:

\medskip

\emph{(1)}~the linear recurrence equation
\emph{(\ref{linrecurrivnk})} with the conditions
\emph{(\ref{pochatkoviumovy})}, where numbers $b_i$ are defined by
\emph{(\ref{bi})}\emph{;}

\medskip

\emph{(2)}
\begin{equation}
\label{rozriwnormum}
u_{n}=\left[\begin{array}{ccccccc} a_{1}&amp;&amp;&amp;&amp;&amp;&amp;\\
\frac{a_{2}}{a_{1}}&amp;a_{1}&amp;&amp;&amp;&amp;&amp;\\
\cdots&amp;\cdots&amp;\ddots&amp;&amp;&amp;&amp;\\
\frac{a_{k}}{a_{k-1}}&amp;\frac{a_{k-1}}{a_{k-2}}&amp;\cdots&amp;a_{1}&amp;&amp;&amp;\\
0&amp;\frac{a_{k}}{a_{k-1}}&amp;\cdots&amp;\frac{a_{2}}{a_{1}}&amp;a_{1}&amp;&amp;\\
\cdots&amp;\cdots&amp;\cdots&amp;\cdots&amp;\cdots&amp;\ddots&amp;\\
0&amp;\ldots&amp;0&amp;\frac{a_{k}}{a_{k-1}}&amp;\ldots&amp;\frac{a_{2}}{a_{1}}&amp;a_{1}
\end{array}\right]_{n}
\end{equation}
with $u_0 = 1$, $a_i\ne 0$ for $i=1,2,\ldots, k-1$;

\medskip

\emph{(3)}
\begin{equation} \label{generatrysarecurrivnnormum}
1+\sum_{i=1}^{\infty}u_{i}x^{i}=\frac{1}{1-a_{1}x-a_{2}x^{2}-\cdots-a_{k}x^{k}}.
\end{equation}
\end{corollary}
\begin{proof} If the initial conditions of the recurrence equation (\ref{linrecurrivnk}) are normal, then it is obvious that all the numbers $c_1, c_2,\ldots, c_n$ in the Theorem \ref{theorozvrecurrivnkpochatkovumov} are equal to one. So, the normal initial conditions (\ref{normpochum}) together with the equation (\ref{rozrivzum}) for $c_{i}=1,\,i=1,2,\ldots,k-1$, gives
(\ref{rozriwnormum}).
\end{proof}
\begin{example} For the Jacobsthal sequence (\seqnum{A001045}) $u_n=u_{n-1}+2u_{n-2}, \,u_0=u_1=1$, from (\ref{popravky}) we shall find $c_1=\frac{b_1}{a_1}=1$, from (\ref{rozriwnormum})
--- the recurrence equation
\begin{equation*}
u_n= \left[\begin{matrix}
1\\
2 &amp; 1 \\
0 &amp; 2 &amp; 1\\
0 &amp; 0 &amp; 2 &amp; 1 \\
\cdots &amp; \cdots &amp; \cdots &amp; \cdots &amp;\ddots\\
0 &amp; \cdots &amp; 0 &amp; 0 &amp; 2 &amp; 1\end{matrix}\right]_n,
\end{equation*}
and from (\ref{generatrysarecurrivnnormum}) --- the generating function $F(x)=\frac{1}{1-x-2x^2}$.
\end{example}
\begin{example}
For Narayana's cows sequence (\seqnum{A000930}) $u_n=u_{n-1}+u_{n-3},\,u_0=u_1=u_2=1$, from (\ref{popravky}) we shall find $c_1=\frac{b_1}{a_1}=1$, $c_2=\frac{b_2}{a_2+a_1b_1}=1$, and from (\ref{generatrysarecurrivnnormum})~--- the generating function $F(x)=\frac{1}{1-x-x^3}$.
\end{example}
\begin{example}
For Chebyshev polynomials of the second kind $u_n(x)=2xu_{n}(x) - u_{n-1}(x)$, $u_0(x)=1$,  $u_1(x)=2x$, similarly to the preceding example, we shall find the number $c_1=1$, the recurrence equation
\begin{equation*}
u_n(x)=\left[\begin{matrix}
2x\\
-\frac{1}{2x} &amp; 2x\\
0 &amp; -\frac{1}{2x} &amp; 2x\\
0 &amp; 0 &amp; -\frac{1}{2x} &amp; 2x \\
\cdots &amp; \cdots &amp; \cdots &amp; \cdots &amp;\ddots\\
0 &amp; \cdots &amp; 0 &amp; 0 &amp; -\frac{1}{2x} &amp; 2x\end{matrix}\right]_n,
\end{equation*}
and the generating function
$\sum\limits_{i=0}^{\infty}u_i(x)z^i=\frac{1}{1 - 2xz + z^2}$.
\end{example}

The next theorem makes it possible to reestablish an appropriate recurrence equation with initial conditions by using a known generating function.
\begin{theorem}\label{statotheneratrdorecriv}
Suppose we are given the generating function
\begin{equation}\label{generatrysa}
f(z)=\frac{1+d_{1}z+d_{2}z^{2}+\cdots+d_{k-1}z^{k-1}}{1-a_{1}z-a_{2}z^{2}-\cdots-a_{k}z^{k}}
\end{equation}
of the sequence $(u_{n})_{n\geq 0}$. Then the sequence $(u_{n})_{n\geq 0}$ satisfies the recurrence equation \emph{(\ref{linrecurrivnk})} with initial conditions
\begin{equation}\label{ui}
u_0=1,\quad\, u_{i}=\left[\begin{array}{cccc} a_{1}+d_{1}&amp;&amp;&amp;\\
\frac{a_{2}+d_{2}}{a_{1}}&amp;a_{1}&amp;&amp;\\
\cdots&amp;\cdots&amp;\ddots&amp;\\
\frac{a_{i}+d_{i}}{a_{i-1}}&amp;\frac{a_{i-1}}{a_{i-2}}&amp;\cdots&amp;a_{1}
\end{array}\right]_{i},\quad\,i=1,2,\ldots,k-1,
\end{equation}
with $a_0\ne 0$ for $i=1,2,\ldots,k-1$.
\end{theorem}
\begin{proof} The generating function of the sequence $(u_{n})_{n\geq 0}$, which satisfies the recurrence equation (\ref{linrecurrivnk}), follows from Theorem \ref{theorozvrecurrivnkpochatkovumov}. According to Theorem \ref{theorozvrecurrivnkpochatkovumov}, we also have the system $b_{i}\left(1-\frac{1}{c_{i}}\right)=d_{i},\,i=1,2,\ldots,k-1$,
which, after considering (\ref{popravky}), we shall reduce to the system
\begin{equation}\label{the06}
b_{i}=a_{1}b_{i-1}+a_{2}b_{i-2}+\cdots+a_{i-1}b_{1}+a_{i}b_{0}+d_{i},\quad\,i=1,2,\ldots,k-1,
\end{equation}
with $b_0=1$.

The proof of the theorem follows from the system (\ref{the06}) being decomposition of the right side of (\ref{ui}) by elements of the last row (see (\ref{rozkladinp})).
\end{proof}

\section{Number-theoretic properties of sequences}

Recurrences and sequences of numbers or polynomials generated by them arise in different fields of mathematics, and many problems in number theory and algebra come down to studying their properties \cite{Cull, Rosen, Taher}. But often, the properties of recurrence sequences are investigated regardless of the relevant equation, which complicates the process of studies.

Let us consider now general properties of sequences using linear recurrence equations generating them and the apparatus of triangular matrices.
\begin{theorem}\emph{\cite{ZatMono}} \label{theorec2}
Let the sequences $(u_{n}^{*})_{n\geq 1}$ and $(u_{n})_{n\geq 1}$ satisfy the recurrence equations
\begin{equation*}
u_n^{*}=a_1u_{n-1}^{*}+a_2u_{n-2}^{*}+\cdots+a_ku_{n-k}^{*},
\end{equation*}
\begin{equation*}
u_n=a_1u_{n-1}+a_2u_{n-2}+\cdots+a_ku_{n-k},
\end{equation*}
with general initial conditions $u_{1}^{*}=b_1,\,\,u_{2}^{*}=b_{2},\,\ldots,\, u_{k}^{*}=b_{k}$ and normal initial conditions
\begin{equation*}
u_1=1,\quad\,u_{i}=\left[\begin{array}{cccc} a_{1}&amp;&amp;&amp;\\
\frac{a_{2}}{a_{1}}&amp;a_{1}&amp;&amp;\\
\cdots&amp;\cdots&amp;\ddots&amp;\\
\frac{a_{i-1}}{a_{i-2}}&amp;\frac{a_{i-2}}{a_{i-3}}&amp;\cdots&amp;a_{1}
\end{array}\right]_{i-1},\quad\,i=2,3,\ldots,k,
\end{equation*}
respectively, with $a_i\ne0$ for $i=1,2,\ldots,k-1$. Then
\begin{equation}
\label{rec2}
u_{r+s}^{*}=\sum_{i=1}^{k}a_{i}\sum_{j=r-i+1}^{r}u_{j}^{*}u_{r+s-i-j+1},
\end{equation}
where $r+s&gt;k$.
\end{theorem}
\begin{proof} From Corollary \ref{consrozvrecurrivnnormum} it follows that the parapermanent (\ref{rozriwnormum}) is the solution of equation (\ref{linrecurrivnk}) with initial conditions (\ref{pochatkoviumovy}). Let us decompose the parapermanent (\ref{rozriwnormum}) for $n=r+s$ by elements of the inscribed rectangular table $T(r)$. If $b_{ij}$ is some element of the table $T(r)$, then the first corner $R_{j-1,1}$ of its parapermanent algebraic complement
\begin{equation*}
P_{ij}=\emph{\emph{pper}}(R_{j-1,1})\cdot\emph{\emph{pper}}(R_{r+s-1,i+1}),
\end{equation*}
besides the coefficients of equation (\ref{linrecurrivnk}), will include the numbers $c_{1}, c_{2},\ldots,c_{k}$, which are defined by (\ref{popravky}). That is why the parapermanent of the corner $R_{j-1,1}$ is the $j$-th term of the sequence $(u_{n}^{*})_{n\geq 1}$. 
In the second corner, all the numbers $c_i=1$, and that is why its parapermanent is the $(r+s-i)$-th term of the sequence $(u_{n})_{n\geq 1}$. It is obvious that $b_{ij}=0$, if $k-1&lt;i-j$ and $b_{ij}=a_{i-j+1}$, if $0\leq i-j\leq k$. If $i-j=k-1$, then $b_{ij}=a_{k},\,i=j+k-1$, and the number $j$ gets the value from $r-k+1$ to $r$. Thus, all the summands from the decomposition of the parapermanent $u_{r+s}$ by elements of the table $T(r)$, which contain the coefficients $a_{k}$ of the equation (\ref{linrecurrivnk}), will be part of the sum $a_{k}\cdot\!\!\sum\limits_{j=r-k+1}^{r}u_{j}^{*}u_{r+s-j-k+1}$.

If $i-j=k-2$, then $b_{ij}=a_{k-1},\,i=j+k-2,\,j=r-k+2,\ldots,r$, and the similar sum is $a_{k-1}\cdot\!\!\sum\limits_{j=r-k+2}^{r}u_{j}^{*}u_{r+s-j-k+2}$. Continuing the process of calculating the sums like these, in $(k-1)$ steps we 
get the equality $i=j$, which means we
shall come to the sum $a_{1}\cdot\!\!\sum\limits_{j=r}^{r}u_{j}^{*}u_{r+s-j}$.

Thus, the index $i$ of coefficients $a_{i}$ will get the value from 1 to $k$, and the decomposition of the parapermanent $u_{r+s}^{*}$ by elements of the inscribed rectangular table $T(r)$ will be (\ref{rec2}).
\end{proof}

Let us write the equality (\ref{rec2}) for $k=1$, $k=2$, and $k=3$ respectively:
\begin{eqnarray}\label{rs}
u^{*}_{r+s}&amp;=&amp;a_1u_r^{*}u_s,\nonumber\\
u^{*}_{r+s}&amp;=&amp;a_1u^{*}_{r}u_s+a_2(u_{r-1}^{*}u_s+u^{*}_ru_{s-1}),\nonumber\\
u^{*}_{r+s}&amp;=&amp;a_1u_r^{*}u_s+a_2(u_{r-1}^{*}u_s+u_r^{*}u_{s-1})+
a_3(u_{r-2}^{*}u_s+u_{r-1}^{*}u_{s-1}+u_{r}^{*}u_{s-2}).
\end{eqnarray}

Replacing in (\ref{rs}) $r$ with $r+q$, we get the equality
\begin{equation}\label{rqs}
u_{r+q+s}^{*}=u_{r+1}^{*}u_{q+1}u_s+a_2u_{r}^{*}u_qu_s+a_2u_{r+1}^{*}u_qu_{s-1}+a_2^{2}u_{r}^{*}u_{q-1}u_{s-1}.
\end{equation}
\begin{corollary}
\label{consrec3} If the sequence $(u_{n})_{n\geq 1}$ satisfies the recurrence equality \emph{(\ref{linrecurrivnk})} with normal initial conditions \emph{(\ref{normpochum})}, then for its terms the following relations hold:
 \begin{equation}
 \label{rec3}
u_{r+s}=\sum_{i=1}^{k}a_{i}\sum_{j=r-i+1}^{r}u_{j}u_{r+s-i-j+1}.
 \end{equation}
\end{corollary}

The validity of Corollary \ref{consrec3} is immediate from Theorem \ref{theorec2}.

Let us write (\ref{rec3}) for $k=1$, $k=2$, and $k=3$ respectively:
\begin{eqnarray*}
u_{r+s}&amp;=&amp;a_1u_ru_s,\\
u_{r+s}&amp;=&amp;a_1u_ru_s+a_2(u_{r-1}u_s+u_ru_{s-1}),\\
u_{r+s}&amp;=&amp;a_1u_ru_s+a_2(u_{r-1}u_s+u_ru_{s-1})+a_3(u_{r-2}u_s+u_{r-1}u_{s-1}+u_ru_{s-2}).
\end{eqnarray*}

The first ten terms of the normal number sequence, which are generated by linear second-order recurrence equation
\begin{equation}\label{recriv2por}
u_{n+2}=a_{1}u_{n+1}+a_{2}u_{n},\quad a_{1}, a_{2}\in
\mathbb{Z}\backslash\{0\},
\end{equation}
are as follows:
\begin{eqnarray*}
u_1&amp;=&amp;1,\\
u_2&amp;=&amp;a_1,\\
u_3&amp;=&amp;a_1^2+a_2,\\
u_4&amp;=&amp;a_1^3+2a_1a_2,\\
u_5&amp;=&amp;a_1^4+3a_1^2a_2+a_2^2,\\
u_6&amp;=&amp;a_1^5+4a_1^3a_2+3a_1a_2^2,\\
u_7&amp;=&amp;a_1^6+5a_1^4a_2+6a_1^2a_2^2+a_2^3,\\
u_8&amp;=&amp;a_1^7+6a_1^5a_2+10a_1^3a_2^2+4a_1a_2^3,\\
u_9&amp;=&amp;a_1^8+7a_1^6a_2+15a_1^4a_2^2+10a_1^2a_2^3+a_2^4,\\
u_{10}&amp;=&amp;a_1^9+8a_1^7a_2+21a_1^5a_2^2+20a_1^3a_2^3+5a_1a_2^4.
\end{eqnarray*}

For $n\geq 2$ we get
\begin{equation*}
u_n=\left[\begin{array}{cccccc}
  a_1 &amp;  &amp;  &amp; &amp;&amp; \\
  \frac{a_2}{a_1} &amp; a_1 &amp;  &amp; &amp;&amp; \\
  0 &amp; \frac{a_2}{a_1} &amp; a_1 &amp; &amp;&amp; \\
  0 &amp; 0 &amp; \frac{a_2}{a_1} &amp; a_1  &amp;&amp; \\
  \cdots &amp; \cdots &amp; \cdots &amp; \cdots &amp; \ddots &amp;\\
  0&amp;\cdots&amp;0&amp;0&amp;\frac{a_2}{a_1}&amp;a_1
\end{array}\right]_{n-1}=\sum_{k_1+2k_2\,=\,n-1}\frac{(k_1+k_2)!}{k_1!\,k_2!}a_1^{k_1}a_2^{k_2}.
\end{equation*}

The first ten terms of the normal number sequence, which are generated by third order linear recurrence equation
$$
u_{n+3}=a_{1}u_{n+2}+a_{2}u_{n+1}+a_3u_{n},\quad a_1,\, a_2,\,a_3\in \mathbb{Z}\backslash\{0\},
$$
are as follows:
\begin{eqnarray*}
u_1&amp;=&amp;1,\\
u_2&amp;=&amp;a_1,\\
u_3&amp;=&amp;a_1^2+a_2,\\
u_4&amp;=&amp;a_1^3+2a_1a_2+a_3,\\
u_5&amp;=&amp;a_1^4+3a_1^2a_2+a_2^2+2a_1a_3,\\
u_6&amp;=&amp;a_1^5+4a_1^3a_2+3a_1a_2^2+3a_1^2a_3+2a_2a_3,\\
u_7&amp;=&amp;a_1^6+5a_1^4a_2+6a_1^2a_2^2+4a_1^3a_3+6a_1a_2a_3+a_2^3+a_3^2,\\
u_8&amp;=&amp;a_1^7+6a_1^5a_2+5a_1^4a_3+10a_1^3a_2^2+12a_1^2a_2a_3+4a_1a_2^3+3a_1a_3^2+3a_2^2a_3,\\
u_9&amp;=&amp;a_1^8+7a_1^6a_2+6a_1^5a_3+15a_1^4a_2^2+20a_1^3a_2a_3+10
a_1^2a_2^3+6a_1^2a_3^2+12a_1a_2^2a_3+a_2^4+3a_2a_3^2,
\end{eqnarray*}
and for $n\geq 2$ we get
\begin{eqnarray*}
u_n&amp;=&amp;\left[\begin{array}{ccccccc}
  a_1 &amp;  &amp;  &amp; &amp;&amp;&amp; \\
  \frac{a_2}{a_1} &amp; a_1 &amp;  &amp; &amp;&amp;&amp; \\
  \frac{a_3}{a_2} &amp; \frac{a_2}{a_1} &amp; a_1 &amp; &amp;&amp; &amp;\\
  0&amp; \frac{a_3}{a_2} &amp; \frac{a_2}{a_1} &amp;a_1 &amp;&amp;&amp;\\
  \vdots &amp; \cdots &amp; \cdots &amp; \cdots &amp;\ddots&amp;&amp;\\
  0&amp;0&amp;0&amp;0&amp;\cdots&amp;a_1&amp;\\
  0&amp;0&amp;0&amp;0&amp;\cdots&amp;\frac{a_2}{a_1}&amp;a_1
\end{array}\right]_{n-1}
=\sum_{k_1+2k_2+3k_3\,=\,n-1}\frac{(k_1+k_2+k_3)!}{k_1!\,k_2!\,k_3!}a_1^{k_1}a_2^{k_2}a_3^{k_3}.
\end{eqnarray*}
\begin{theorem}\emph{\cite{ZatMono}}
\label{theoteorchysel1} Let the sequence $(u_{n})_{n\geq 1}$ satisfy the 
second-order recurrence equation \emph{(\ref{recriv2por}) } with normal initial conditions $u_{1}=1$, $u_{2}=a_{1}$. Then

\medskip

\emph{(1)} the following equalities hold:
\begin{eqnarray} \label{rec4}
&amp;u_{r+s}=u_{r+1}u_{s}+a_{2}u_{r}u_{s-1},\\[1 pt]
\label{rec5} &amp;u_{sr}\equiv 0\,(\bmod\,u_{r});
\end{eqnarray}

\medskip

\emph{(2)} if in the equation \emph{(\ref{recriv2por})} the coefficients are relatively prime, then
\begin{equation}
\label{rec6}\gcd(u_{s},u_{r})=u_{\gcd(s,r)}.
\end{equation}
\end{theorem}
\begin{proof}

Let us first prove (\ref{rec4}). To do this, we shall use the method of mathematical induction. We apply the Corollary \ref{consrec3} to the equation (\ref{recriv2por}) with initial conditions $u_{1}=1$, $u_{2}=a_{1}$. For $k=2$ the equality (\ref{rec3}) is
\begin{equation}
\label{rec7}
u_{r+s}=a_{2}u_{r-1}u_{s}+a_{1}u_{r}u_{s}+a_{2}u_{r}u_{s-1}.
\end{equation}

From (\ref{rec7}), considering (\ref{recriv2por}), we get
\begin{equation*}
u_{r+s}=u_{s}(a_{1}u_{r}+a_{2}u_{r-1})+a_{2}u_{r}u_{s-1}=u_{r+1}u_{s}+a_{2}u_{r}u_{s-1}.
\end{equation*}

Let us prove (\ref{rec5}). For $s=r$ the equality (\ref{rec4}) is
\begin{equation}
u_{2r}=u_{r}(u_{r+1}+a_{2}u_{r-1}),
\end{equation}
that is (\ref{rec5}) holds for $s=1$ and $s=2$. Let us assume (\ref{rec5}) holds for $s=1,2,\ldots,m-1$, and prove its validity for $s=m$. As
$u_{mr}=u_{(m-1)r+r}=u_{(m-1)r+1}u_{r}+a_{2}u_{(m-1)r}u_{r-1}$,
and $u_{(m-1)r}\equiv0\,(\bmod\, u_{r})$, then
$u_{mr}=u_{(m-1)r+1}u_{r}$, i.e., (\ref{rec5}) holds for $s=m$.

In order to prove the equality (\ref{rec6}), let us first prove that
\begin{eqnarray}
\label{rec8}
&amp;\gcd(u_{n},u_{n+1})=1,\\[1 pt]
\label{rec9} &amp;\gcd(a_{2},u_{n})=1.
\end{eqnarray}

For $n=1$ the equality (\ref{rec8}) is obvious. Let us assume that (\ref{rec8}) holds for $n=k$ and prove it for $n=k+1$. Let, conversely, $\gcd(u_{k+1},u_{k+2})=d&gt;1$. Then from (\ref{recriv2por}) for $n=k$ it follows that either $u_{k}\equiv 0 \ (\bmod \,d)$ or $a_{2}\equiv 0 \ (\bmod\,d)$. In the first case, we come to a contradiction with the assumption that (\ref{rec8}) holds for $n=k$, and in the second case from (\ref{recriv2por}) for $n=k$ it follows that $a_{1}\equiv 0 \ (\emph{\emph{mod}}\,d)$, and this contradicts the fact that the coefficients of equation (\ref{recriv2por}) are relatively prime. Thus, the equality (\ref{rec8}) holds for an arbitrary $n\in\mathbb{N}$.

The validity of the equality (\ref{rec9}) follows from the fact that assumption of the contrary proposition together with (\ref{recriv2por}) for $n=s-1$ leads to contradiction with (\ref{rec8}).

Now let $s&lt;r$. Then considering the equality (\ref{rec4}), we have
\begin{eqnarray*}
&amp;\gcd(u_{r},u_{s})=\gcd(u_{r-s+s},u_{r})=\\[1 pt]
&amp;=\gcd(u_{r-s+1}u_{s}+a_{2}u_{r-s}u_{s-1}
,u_{s})=\gcd(a_{2}u_{r-s}u_{s-1},u_{s}).
\end{eqnarray*}

From (\ref{rec8}), (\ref{rec9}) it follows that $\gcd(a_{2}u_{s-1},u_{s})=1$. Therefore $\gcd(u_{r},u_{s})=\gcd(u_{r-s},u_{s})$, and we get the equality (\ref{rec6}).
\end{proof}

Note that Theorem \ref{theoteorchysel1} also holds when the coefficients of linear recurrence equation (\ref{recriv2por}) are functions of some variables.
\begin{example}\label{examNOD}
Let us consider the normal sequence of polynomials $w_n(x)=\frac{x^n-1}{x-1}, $ which is generated by the recurrence equation $w_{n+2}(x)=(x+1)w_{n+1}(x)-xw_n(x)$. Polynomials $w_n(x)$ do not have real roots, and for prime values $n&gt;3$, they are connected with the problem of circle division into $n$ equal parts. Gauss showed that the roots of polynomials $w_n(x)$ are expressed as square radicals only when $n$ is a Fermat prime, that is $n=2^{2^k}+1$ (\seqnum{A000215}). Only for these values of $n$, a circle can be divided into $n$ equal parts with the help of a ruler and compass. According to Theorem \ref{theoteorchysel1}, $\gcd\bigl(w_n(x), w_m(x)\bigr)= \frac{x^{\gcd}(n,m)-1}{x-1}$.
\end{example}
\begin{corollary}
\label{cons0} If the sequence $(u_{k})_{k\geq 1}$ satisfies the hypotheses of Theorem \emph{\ref{theoteorchysel1}} and $u_{k}\neq1$, $k\geq 2$, then the term $u_{s}$ is a prime only when $s$ is a prime.
\end{corollary}
The proof follows from (\ref{rec5}).
\begin{corollary}
\label{cons1} Let the sequence $(u_{k})_{k\geq 1}$ satisfy the hypotheses of Theorem \emph{\ref{theoteorchysel1}} and $p$ is a prime. Then $u_{p}$ has no common divisor with any of the preceding terms of sequence $(u_{k})_{k\geq 1}$.
\end{corollary}
The proof follows from (\ref{rec5}).
\begin{corollary}
\label{cons2} Let the sequence $(u_{k})_{k\geq 1}$ satisfy the hypotheses of Theorem \emph{\ref{theoteorchysel1}} and $a_{2}=b^{2}$, where $b\in \mathbb{Z}$. Then each term $u_{2m+1}$, $m&gt;1$, can be written as the sum of squares of two nonnegative integers, namely
$$
u_{2m+1}=u_{m+1}^{2}+(bu_{m})^{2}.
$$
\end{corollary}

The validity of Corollary \ref{cons2}  follows from (\ref{rec4}) for $r=n$ and $s=n+1$.
\begin{example} \label{e2} The recurrence equation $u_{n+2}=(k+1)u_{n+1}-ku_{n}$ with normal initial conditions $u_{1}=1,\,u_{2}=k+1,\,k\geq 1$, generates the number sequence $\left(\frac{k^{n}-1}{k-1}\right)_{n\geq 1}$. The condition $k\geq 1$ satisfies the condition $u_{s}\neq 1,\, s\geq 2$, of Corollary \ref{cons0}. According to Corollary \ref{cons0} the number $\frac{k^{n}-1}{k-1}$ is a prime, if $n$ is a prime. For $k=2$ we get a well known fact that Mersenne primes (\seqnum{A001348}) are among the numbers of the form $2^{p}-1$, where $p$ is some prime. For $k=10$ we get a famous proposition that repunits (primes which are 
written as $\underbrace{11\cdots1}_{n}$ in the decimal system; see \seqnum{A002275}), are also sought for prime $n$.
\end{example}

As the recurrence equation $u_{n+2}=u_{n+1}+u_{n}$ with normal initial conditions $u_{1}=u_{2}=1$ generates the Fibonacci sequence, then Theorem \ref{theoteorchysel1} can be seen as generalization of some relations for Fibonacci numbers.

There are various generalizations of Fibonacci numbers. Some generalizations are connected with preservation of the recurrence relation $F_{n+1}=F_{n}+F_{n-1}$ and replacement of initial conditions \cite{Horadam1961, Klein, Walton}, others are based on a more general recurrence relation of the second order without changing the first two terms of the Fibonacci sequence \cite{Bolat, Catarino, Cerda, Edson, Falcon, Sahin, Sbultari, Yayenie}. There are generalizations of the Fibonacci sequence when the recurrence relation has a more general form generalizing the initial conditions with that \cite{Atanassov, Bilgici, Dujella, Irmak, Horadam1987,  Melham, Ozgur}. In particular, generalizations of the Fibonacci sequence for recurrence relations of higher orders were studied in \cite{Belbachir, Dresden, Howard, Kuhapatanakul, Levesque, Taher, Tasci}.

Among the terms of number sequences, which satisfy one and the same recurrence equation but with different initial conditions, there are some interesting relations. Therefore studying the properties of the terms of one sequence, it is possible to draw some conclusions concerning the properties of the terms of another sequence.

As a consequence of Theorem 12 (when $k=2$, $r=1$, and $s=n-1$), we have:
\begin{theorem} \label{theouu}
If the sequences $(u_{n})_{n\geq 1}$, $(u_{n}^{*})_{n\geq 1}$  satisfy the linear second-order recurrence equation
\begin{equation}\label{recriv2order}
u_{k+2}=a_{1}u_{k+1}+a_{2}u_{k}
\end{equation}
with initial conditions
\begin{equation}\label{pochumovyu}
u_{1}=1,\,\,u_{2}=a_{1};\,\,\,\,u_{1}^{*}=b_1,\,\,u_{2}^{*}=b_{2},
\end{equation}
respectively, then
\begin{equation}\label{uu}
u_{n}^{*}=b_2u_{n-1}+a_2b_1u_{n-2}.
\end{equation}
\end{theorem}

The next theorem singles out some classes of number sequences, whose odd-numbered terms can be written as the sum of several squares.
\begin{theorem}\emph{\cite{ZatADM}} \label{t7} Let the sequences $(u_{n})_{n\geq 1}$, $(u_{n}^{*})_{n\geq 1}$ satisfy the linear second-order recurrence equation \emph{(\ref{recriv2order})} with initial conditions
\begin{equation}
\label{30} u_{1}=1,\,\,
u_{2}=a_{1};\,\,\,\,u_{1}^{*}=k,\,\,u_{2}^{*}=a_{1}.
\end{equation}
Then

\medskip

\emph{(1)} for $n\geq 3$ the following relation holds:
\begin{equation}
\label{31} u_{n}^{*}=u_{n}+(k-1)a_{2}u_{n-2};
\end{equation}

\medskip

\emph{(2)} if
\begin{equation}
\label{32} k=a_{2}=s^{2}+1
\end{equation} and  $a_{1}&gt;0$, then for $n\geq 3$ the number $u_{2n-1}^{*}$ is the sum of three squares:
\begin{equation}
\label{33} u_{2n-1}^{*}=u_{n}^2+\bigl((s^{2}+1)
u_{n-1}\bigr)^{2}+\bigl((s^{3}+s) u_{n-2}\bigr)^{2};
\end{equation}

\emph{(3)} if
\begin{equation}
\label{34} k=s^{2}+1,\quad\,a_{2}=b^{2},
\end{equation}
then for $n\geq 2$ the number $u_{2n+1}^{*}$ is the sum of four squares:
\begin{equation}\label{35}
u_{2n+1}^{*}=u_{n+1}^{2}+(bu_{n})^{2}+(sbu_{n})^{2}+(sb^{2}u_{n-1})^{2}.
\end{equation}
\end{theorem}
\begin{proof}

The equality (\ref{31}) follows from (\ref{uu}):
\begin{eqnarray*}
&amp;u_n^{*}=b_2u_{n-1}+a_2b_1u_{n-2}=a_1u_{n-1}+a_2ku_{n-2}=\\
&amp;=a_1u_{n-1}+a_2u_{n-2}+a_2(k-1)u_{n-2}=u_n+a_2(k-1)u_{n-2}.
\end{eqnarray*}

Let us prove (\ref{33}). From (\ref{rec2}) for $k=2$ we have
\begin{equation*}
u_{r+s}^{*}=a_{1}u_{r}^{*}u_{s}+a_{2}(u_{r-1}^{*}u_{s}+
u_{r}^{*}u_{s-1})=u_{r+1}^{*}u_{s}+a_{2}u_{r}^{*}u_{s-1}.
\end{equation*}
In the last equality we substitute $r=n-1$ and $s=n$. Then, using (\ref{31}), we obtain
\begin{eqnarray*}
&amp;u_{2n-1}^{*}=(a_{1}u_{n-1}^{*}+a_{2}u_{n-2}^{*})
u_{n}+a_{2}u_{n-1}^{*}u_{n-1}=u_{n}^{*}u_{n}+a_{2}u_{n-1}^{*}u_{n-1}=\\[1pt]
&amp;=(u_{n}+(k-1)a_{2}u_{n-2}) u_{n}+a_{2}(u_{n-1}+(k-1)a_{2}u_{n-3})u_{n-1}=\\[1pt]
&amp;=u_{n}^{2}+(k-1)a_{2}u_{n-2}u_{n}+a_{2}u_{n-1}^{2}+(k-1)a_{2}^{2}u_{n-3}u_{n-1}=\\[1pt]
&amp;=u_{n}^{2}+(k-1)a_{2}u_{n-2}(a_{1}u_{n-1}+a_{2}u_{n-2})+a_{2}u_{n-1}^{2}+(k-1)a_{2}^{2}u_{n-3}u_{n-1}=\\[1pt]
&amp;=u_{n}^{2}+a_{2}u_{n-1}^{2}+(k-1)a_{2}^{2}u_{n-2}^{2}+(k-1)a_{2}u_{n-1}^{2}=u_{n}^{2}+ka_{2}u_{n-1}^{2}
+(k-1)a_{2}^{2}u_{n-2}^{2}.
\end{eqnarray*}
Hence, using (\ref{32}), we get (\ref{33}).

To prove (\ref{35}) we shall write (\ref{31}) for $n=2m+1$:
\begin{equation*}
u_{2m+1}^{*}=u_{2m+1}+(k-1)a_{2}u_{2m-1}.
\end{equation*}
Hence, using (\ref{rec4}) for $r=m$ and $s=m+1$ and the condition (\ref{34}), after simple transformations we obtain (\ref{35}).
\end{proof}
\begin{example}\label{consfibon} If $s=0$ we get $k=a_2=1$ and the equality (\ref{33}) is written as
\begin{equation}\label{fib1}
u_{2n-1}=u_n^2+u_{n-1}^2.
\end{equation}
Thus, all the terms of the normal number sequence with odd numbers, not less than 3, which are generated by the recurrence equation $u_{n+2}=au_{n+1}+u_n$, can be written as the sum of two squares, e.g.,
\begin{eqnarray*}\label{u2n122}
u_3&amp;=&amp;a^2+1=a^2+1^2,\\
u_5&amp;=&amp;a^4+3a^2+1=(a^2+1)^2+a^2,\\
u_7&amp;=&amp;a^6+5a^4+6a^2+1=(a^3+2a)^2+(a^2+1)^2,\\
u_9&amp;=&amp;a^8+7a^6+15a^4+10a^2+1=(a^4+3a^2+1)^2+(a^3+2a)^2,\\
u_{11}&amp;=&amp;a^{10}+9a^8+28a^6+35a^4+15a^2+1=(a^5+4a^3+3a)^2+(a^4+3a^2+1)^2.\\
\end{eqnarray*}

In general,
\begin{eqnarray*}
&amp;\displaystyle u_{2n-1}=\sum\limits_{i=2}^{n+1}{{2n-i}\choose{2(n-i+1)}}a^{2(n-i+1)}=\\[1pt]
&amp;\displaystyle=\left(\sum\limits_{i=1}^{\lfloor\frac{n+1}{2}\rfloor}{n-i\choose
n-2i+1}a^{n-2i+1}\right)^{2}+
\left(\sum\limits_{i=1}^{\lfloor\frac{n}{2}\rfloor}{n-i-1\choose
n-2i}a^{n-2i}\right)^{2}.
\end{eqnarray*}

Note that for $a = 1$ the equality (\ref{fib1}) is written as $F_{2n-1}=F_n^2+F_{n-1}^2$, where $F_n$ are Fibonacci numbers, and
\begin{equation*}
F_n=\sum\limits_{i=1}^{\lfloor\frac{n+1}{2}\rfloor}{n-i\choose
n-2i+1}.
\end{equation*}
\end{example}
\begin{example}
\label{e3} In item 2 of Theorem \ref{t7}, let $a_{1}=4$, $s=2$. Then $u_{1}=a_{2}=k=5$,
\begin{equation*}
  u_{n}^{*}=\frac{3\cdot5^{n-1}+7\,(-1)^{n-1}}{2},\,\quad
  u_{n}=\frac{5^{n}+(-1)^{n-1}}{6},
\end{equation*}
and the equality (\ref{33}) becomes
$$
\frac{3\cdot5^{2n-2}+7}{2}=\left(\frac{5^{n}+(-1)^{n-1}}{6}\right)^{2}+\left(\frac{5(5^{n-1}+(-1)^{n})}{6}\right)^{2}+
  \left(\frac{5(5^{n}+(-1)^{n-1})}{3}\right)^{2}.
$$
For example, for $n=16$ we have decomposition of the prime $396983861923217773441$ into the sum of three different squares of positive integers, two of which are sequential:
\begin{equation*}
396983861923217773441=25431315104^{2}+25431315105^{2}+10172526040^{2}.
\end{equation*}
\end{example}
\begin{example} \label{e4}
If in item 3 of Theorem \ref{t7} $a_{1}=3$, $a_{2}=4$, $b=2$, $s=1$, then
\begin{equation*}
u_{n}^{*}=4^{n-1}+(-1)^{n-1},\,\quad u_{n}=\frac{4^{n}+(-1)^{n-1}}{5}
\end{equation*}
and the equality (\ref{35}) becomes
\begin{equation*}
  2^{4m}+1=\left(\frac{4^{m+1}+(-1)^{m}}{5}\right)^{2}+
  \left(\frac{2^{2m+1}+2(-1)^{m-1}}{5}\right)^{2}+
  $$$$+ \left(\frac{2^{2m+1}+2(-1)^{m-1}}{5}\right)^{2}
  +\left(\frac{2^{2m}+4(-1)^{m}}{5}\right)^{2}.
\end{equation*}

For $m=2^{n-2}$ we obtain Fermat numbers $\mathcal{F}_{n}=2^{4m}+1=2^{2^{n}}+1$ (\seqnum{A000215}). The last equality can now be written as
\begin{equation}\label{Ferma}
  2^{2^{n}}+1 = \left(\frac{2^{2^{n-1}+2}+1}{5}\right)^{2}+
  \left(\frac{2^{2^{n-1}+1}-2}{5}\right)^{2}+\left(\frac{2^{2^{n-1}+1}-2}{5}\right)^{2}
  +\left(\frac{2^{2^{n-1}}+4}{5}\right)^{2},
\end{equation}
where $n\geqslant 3$. For example,
$$
\mathcal{F}_6=2^{64} + 1
=3435973837^2+1717986918^2+1717986918^2+858993460^2.
$$
\end{example}

Using (\ref{Ferma}), with the help of simple transformations, Fermat numbers can be written (I.~V.~Fedak) as the sum of three squares:
\begin{equation*}
\mathcal{F}_n=2^{2^n}+1=a_n^2+1=\left(\frac{2a_n-2}{3}\right)^2+
\left(\frac{2a_n+1}{3}\right)^2+\left(\frac{a_n+2}{3}\right)^2.
\end{equation*}
For example, $\mathcal{F}_6=2863311530^2+2863311531^2+1431655766^2$.

\section{Generalization of the Cassini formula}

Over 300 years have passed since the discovery of the Cassini formula for Fibonacci numbers
\begin{equation*}
F_{n-1}F_{n+1}-F_n^2=(-1)^n.
\end{equation*}
During this time, many studies have appeared presenting new similar formulae for other number sequences, which have become classical. But the methods proposed in the preceding sections make it possible to unify researches in this direction. It turns out that normal number sequences mostly have the same properties as Fibonacci numbers. It can be illustrated with the results of Theorem \ref{theoteorchysel1}, Corollary \ref{cons1}, etc. In this section we shall prove some general theorems, which generalize the Cassini identity.

Consider normal number sequences of the second order
\begin{equation}\label{recrimKassini}
u_0=0,\,\,\,u_1=1,\,\,\,u_{n+2}=a_1u_{n-1}+a_2u_{n}.
\end{equation}
For these sequences, the following equality holds \cite{ZatADM}:
\begin{equation}\label{urs}
u_{r+s}=u_{r+1}u_s+a_2u_ru_{s-1},
\end{equation}
where $r\geq 1$, $s\geq 2$. Let in (\ref{urs}) $r=n$, $s=n-1$. Then
\begin{equation*}
u_{2n-1}=u_{n+1}u_{n-1}+a_2u_nu_{n-2}.
\end{equation*}
For $r=n-1$, $s=n$ from (\ref{urs}) we have
\begin{equation*}
u_{2n-1}=u_{n}^2+a_2u_{n-1}^2.
\end{equation*}

By subtracting two last equalities, we obtain the relation
\begin{equation*}
u_{n+1}u_{n-1}-u_n^2=-a_2(u_nu_{n-2}-u_{n-1}^2).
\end{equation*}

Thus, we get the sequence of equalities
\begin{eqnarray*}
(-a_2)^0(u_{n+1}u_{n-1}-u_n^2)&amp; = &amp;(-a_2)^1(u_nu_{n-2}-u_{n-1}^2),\\[1 pt]
(-a_2)^1(u_{n+1}u_{n-1}-u_n^2)&amp;=&amp;(-a_2)^2(u_nu_{n-2}-u_{n-1}^2),\\[1 pt]
&amp; \vdots &amp; \\
(-a_2)^{n-3}(u_4u_2-u_3^2)&amp;=&amp;(-a_2)^{n-2}(u_3u_1-u_2^2),
\end{eqnarray*}
by adding which, we get the generalized Cassini formula
\begin{equation*}
u_{n+1}u_{n-1}-u_n^2=(-1)^{n}a_2^{n-1}.
\end{equation*}

In the equality (\ref{urs}), let $r=n-1$, $s=n-3$. Then
\begin{equation*}
u_{2n-4}=u_{n}u_{n-3}+a_2u_{n-1}u_{n-4}.
\end{equation*}
If $r=n-2$, $s=n-2$, then from above equality we get
\begin{equation*}
u_{2n-4}=u_{n-1}u_{n-2}+a_2u_{n-2}u_{n-3}.
\end{equation*}

By subtracting two last equalities, we obtain
\begin{equation*}
u_{n}u_{n-3}-u_{n-1}u_{n-2}=-a_2(u_{n-1}u_{n-4}-u_{n-2}u_{n-3}).
\end{equation*}

Thus, we get the equalities
\begin{eqnarray*}
(-a_2)^0(u_{n}u_{n-3}-u_{n-1}u_{n-2})&amp;=&amp;(-a_2)^1(u_{n-1}u_{n-4}-u_{n-2}u_{n-3}),\\[1 pt]
(-a_2)^1(u_{n-1}u_{n-4}-u_{n-2}u_{n-3})&amp;=&amp;(-a_2)^2(u_{n-2}u_{n-5}-u_{n-3}u_{n-4}),\\[1 pt]
&amp;\vdots &amp; \\
(-a_2)^{n-5}(u_5u_2-u_4u_3)&amp;=&amp;(-a_2)^{n-4}(u_4u_1-u_3u_2).
\end{eqnarray*}

Hence, by adding all these equalities, we finally get the equality
\begin{equation*}
u_nu_{n-3}-u_{n-1}u_{n-2}=(-1)^{n}a_1a_2^{n-3}.
\end{equation*}

In this way, we prove the following proposition.
\begin{theorem}\label{theoKassini}
For normal number sequences of the second order (\ref{recrimKassini}) the following equalities are true:
\begin{eqnarray}
\label{Kassini}&amp;u_{n+1}u_{n-1}-u_n^2=(-1)^{n}a_2^{n-1},\\[1 pt]
\label{Kas2}&amp;u_nu_{n-3}-u_{n-1}u_{n-2}=(-1)^{n}a_1a_2^{n-3}.
\end{eqnarray}
\end{theorem}

For the sequences $(u_n)_{n\geq1}, (u_n^*)_{n\geq1}$, which are generated by the
second-order recurrence relation with initial conditions $u_1=1$, $u_2=a_1$ ł $u^{*}_1=b_1$, $u^{*}_2=b_2$ respectively, the following equality is true
\begin{equation}\label{un}
u^{*}_n=b_2u_{n-1}+a_2b_1u_{n-2}.
\end{equation}

Let us apply (\ref{un}) to determine the Cassini formula for the sequence $(u_n^{*})_{n\geq 1}$:
\begin{eqnarray*}
&amp;u_{n+1}^{*}u_{n-1}^{*}-(u^{*}_{n})^2=\\[1 pt]
&amp;=(b_2u_{n}+a_2b_1u_{n-1})(b_2u_{n-2}+a_2b_1u_{n-3})-(b_2u_{n-1}+a_2b_1u_{n-2})^2=\\[1 pt]
&amp;=b_2^2(u_nu_{n-2}-u_{n-1}^2)+a_2^2b_1^2(u_{n-1}u_{n-3}-u_{n-2}^2)+a_2b_2b_1(u_nu_{n-3}-u_{n-1}u_{n-2}).
\end{eqnarray*}

Using (\ref{Kassini}), (\ref{Kas2}), we shall substitute relevant values instead of parentheses in the last equalities
\begin{eqnarray*}
&amp;u_{n+1}^{*}u_{n-1}^{*}-(u^{*}_{n})^2=(-1)^{n-1}b_2^2a_2^{n-2}+
(-1)^{n}a_2^2b_1^2a_2^{n-3}+(-1)^{n}a_2b_1b_2a_1a_2^{n-3}=\\[1 pt]
&amp;=(-1)^{n-1}a_2^{n-2}(b_2^2-a_2b_1^2-a_1b_1b_2).
\end{eqnarray*}
\begin{theorem}\label{theonk}
For normal number sequences
\begin{eqnarray}\label{norm2order1a1}
u_1=1,\,\, u_2=a_1,\,\,u_n=a_1u_{n-1}+a_2u_{n-2}
\end{eqnarray}
the following equalities hold:
\begin{equation}\label{(nk)}
u_nu_{n-k}-u_{n-1}u_{n-(k-1)}=(-1)^{n+k(\!\!\bmod\,
2)-1}a_2^{n-k}u_{k-1},
\end{equation}
where $k\geq 2$, $n\geq k+1$.
\end{theorem}
\begin{proof} We shall prove the theorem by induction for $k$. For $k=2$ the proposition of the theorem is true based on the equality (\ref{Kassini}). Assume that the proposition of the theorem is true for $n=k$ and we shall prove that the proposition of the theorem is also true for $n=k+1$. We get
\begin{eqnarray*}
&amp;u_nu_{n-(k+1)}-u_{n-1}u_{n-k}=(a_1u_{n-1}+a_2u_{n-2})u_{n-(k+1)}-(a_1u_{n-2}+a_2u_{n-3})u_{n-k}=\\[1 pt]
&amp;=a_1\left(u_{n-1}u_{(n-1)-k}-u_{n-2}u_{(n-1)-(k-1)}\right)+a_2\left(u_{n-2}u_{(n-2)-(k-1)}-u_{n-3}u_{(n-2)-(k-2)}\right)=\\[1 pt]
&amp;=a_1(-1)^{(n-1)+(k \bmod 2)-1}a_{2}^{(n-1)-k}u_{k-1}+a_2(-1)^{(n-2)+(k-1)
(\!\!\bmod\,2)-1}a_2^{(n-2)-(k-1)}u_{k-2}=\\[1 pt]
&amp;=(-1)^{n+(k \bmod 2)}a_2^{n-(k+1)}(a_1u_{k-1}+a_2u_{k-2})=(-1)^{n+
(k\bmod 2)}a_2^{n-(k+1)}u_k.
\end{eqnarray*}
\end{proof}
\begin{theorem}\label{theonks} The terms of the normal number sequence (\ref{norm2order1a1}) satisfy the relation
\begin{equation}\label{(nks)}
u_nu_{n-k}-u_{n-s}u_{n-(k-s)}=(-1)^{n+(k\bmod 2)-1}a_2^{n-k}u_su_{k-s}.
\end{equation}
\end{theorem}
\begin{proof} We shall prove by induction for $s$. For $s=1$ (\ref{(nks)}) is written as the equality (\ref{(nk)}) from Theorem \ref{theonk}. We shall denote $U(n,k,s)=u_nu_{n-k}-u_{n-s}u_{n-(k-s)}$. Then
\begin{eqnarray*}
&amp;U(n,k,s+1)=u_nu_{n-k}-u_{n-(s+1)}u_{n-(k-(s+1))}=\\[1 pt]
&amp;=\left(a_1u_{n-1}+a_2u_{n-2}\right)u_{n-k}-u_{n-(s+1)}\left(a_1u_{(n-1)-((k-1)-s)}+a_2u_{(n-2)-((k-1)-s)}\right)=\\[1 pt]
&amp;=a_1U(n-1,k-1,s)+a_2U(n-2,k-2,s-1)=\\[1 pt]
&amp;= (-1)^{(n-1)+((k-1) \bmod 2)
-1}a_1a_2^{(n-1)-(k-1)}u_su_{(k-1)-s}+\\[1 pt]
&amp;+(-1)^{(n-2)+((k-2)\bmod 2)-1}a_2a_2^{(n-2)-(k-2)}u_{s-1}u_{(k-2)-(s-1)}=\\[1 pt]
&amp;=(-1)^{n+(k\bmod 2)-1}a_2^{n-k}u_{k-(s+1)}(a_1u_s+a_2u_{s-1})=
(-1)^{n+(k\bmod 2)-1}a_2^{n-k}u_{s+1}u_{k-(s+1)}.
\end{eqnarray*}
\end{proof}
\begin{theorem}\label{theonks} For the sequences $(u_{n})_{n\geq 1}$ and $(u_{n}^{*})_{n\geq 1}$, which satisfy the linear recurrence equation (\ref{recriv2order}) with initial conditions $u_{1}=a_{1}$, $u_{2}=a_{2}$ and $u_{1}^{*}=b_1$, $u_{2}^{*}=b_{2}$ respectively, the following identity is true:
$$
u_n^{*}u_{n-k}^{*}-u_{n-s}^{*}u_{n-(k-s)}^{*}=(-1)^{n+ (k\bmod 2)}a_2^{n-k-1}\left(b_2^2-a_2b_1^2-a_1b_1b_2\right)u_su_{k-s}.
$$
\end{theorem}
\begin{proof} To prove this we shall use the identity (\ref{uu}):
\begin{eqnarray*}
&amp;u_n^{*}u_{n-k}^{*}-u_{n-s}^{*}u_{n-(k-s)}^{*}=(b_2u_{n-1}+a_2b_1u_{n-2})(b_2u_{n-k-1}+a_2b_1u_{n-k-2})-\\[2pt]
&amp;-(b_2u_{n-s-1}+a_2b_1u_{n-s-2})\left(b_2u_{n-(k-s)-1}+a_2b_1u_{n-(k-s)-2}\right)=\\[2pt]
&amp;=b_2^2U(n-1,k,s)+a_2^2b_1^2U(n-2,k,s)+\\[2pt]
&amp;+\,a_2b_2b_1U(n-1,k+1,s)+a_2b_2b_1U(n-2,k-1,s)=\\[2pt]
&amp;=(-1)^{n-1+(k bmod 2)-1}b_2^2a_2^{n-1-k}u_su_{k-s}+(-1)^{n-2+(k \bmod 2)-1}a_2^2b_1^2a_2^{n-2-k}u_su_{k-s}+\\[2pt]
&amp;+(-1)^{n-1+((k+1)\bmod 2)-1}a_2b_2b_1a_2^{(n-1)-(k+1)}u_su_{(k+1)-s}+\\[2pt]
&amp;+(-1)^{(n-2)+((k-1)\bmod 2)-1}a_2b_2b_1a_2^{(n-2)-(k-1)}u_su_{(k-1)-s}=\\[2pt]
&amp;=(-1)^{n+(k\bmod 2)}a_2^{n-k-2}u_s\left(a_2b_2^2u_{k-s}-a_2^2b_1^2u_{k-s}-a_2b_1b_2u_{k-s+1}+a_2^2b_1b_2u_{k-s-1}\right)=\\[2pt]
&amp;=(-1)^{n+(k\bmod 2)}a_2^{n-k-1}\left(b_2^2-a_2b_1^2-a_1b_1b_2\right)u_su_{k-s}.
\end{eqnarray*}
\end{proof}


\section{Acknowledgments}
The authors would like to thank the anonymous referee for valuable comments and suggestions that improved the original version of the article.



\begin{thebibliography}{99}

\bibitem{Atanassov} K. T. Atanassov, On a generalization of the Fibonacci sequence in
                the case of three sequences, \textit{Fibonacci Quart.} \textbf{27} (1989), 7--10.

\bibitem{Belbachir}  H. Belbachir and F. Bencherif, Linear recurrent sequences and powers of a
                square matrix, \textit{Integers} \textbf{6} (2006), \#A12.

\bibitem{Bilgici} G. Bilgici, New generalizations of Fibonacci and Lucas sequences, \textit{Appl.
                Math. Sci.} \textbf{8} (2014), 1429--1437.

\bibitem{Bolat} C. Bolat and H. K\"ose, On the properties of $k$-Fibonacci numbers, \textit{Int.
                J. Contemp. Math. Sci.} \textbf{22} (2010), 1097--1105.

\bibitem{Catarino} P. Catarino, On some identities for $k$-Fibonacci sequence, \textit{Int.
                J. Contemp. Math. Sci.} \textbf{9} (2014), 37--42.

\bibitem{Cerda} G. Cerda, Matrix methods in Horadam sequences, \textit{Bol. Mat.} \textbf{19}
                (2012), 97--106.

\bibitem{Cull} P. Cull, M. Flahive, and R. Robson,  \textit{Difference Equations: From Rabbits to
                Chaos}, Springer, 2005.

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

\bibitem{Dujella} A. Dujella, Generalized Fibonacci numbers and the problem of Diophantus,
                \textit{Fibonacci Quart.} \textbf{34} (1996), 164--175.

\bibitem{Edson} M. Edson, S. Lewis, and O. Yayenie, The $k$-periodic Fibonacci sequences and
                extended Binet's formula, \textit{Integers} \textbf{11} (2011), \#A32.

\bibitem{Falcon} S. Falc\'on and A. Plaza, On the Fibonacci $k$-numbers, \textit{Chaos Solutions
                Fractals} \textbf{32} (2007), 1615--1624.

\bibitem{Graham} R. L. Graham, D. E. Knuth, and O. Patashnik, \textit{Concrete Mathematics. A
                Foundation for Computer Science}, Addison-Wesley, 1994.

\bibitem{Horadam1961} A. F. Horadam, A generalized Fibonacci sequence, \textit{Amer. Math.
                Monthly} \textbf{68} (1961), 455--459.

\bibitem{Horadam1987} A. F. Horadam and A. G. Shannon, Generalization of identities of Catalan
                and others, \textit{Port. Math.} \textbf{44} (1987), 137--148.

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

\bibitem{Irmak} N. Irmak and M. Apl, Some indentities for generalized Fibonacci and Lucas
                sequences, \textit{Hacet. J. Math. Stat.} \textbf{42} (2013), 331--338.

\bibitem{Klein} S. T. Klein,  Combinatorial representation of generalized Fibonacci numbers,
              \textit{Fibonacci Quart.} \textbf{29} (1991), 124--131.

\bibitem{Koshy} T. Koshy, \textit{Fibonacci and Lucas Numbers with Applications}, Wiley,
               2001.

\bibitem{Kuhapatanakul} K. Kuhapatanakul and L. Sukruan, The generalized Tribonacci numbers with
              negative subscripts, \textit{Integers} \textbf{14} (2014), \#A32.

\bibitem{Levesque} C. Levesque, \textit{On $m$-th order linear recurrences},
              \textit{Fibonacci Quart.} \textbf{23} (1985), 290--293.

\bibitem{Melham} R. S. Melham, A Fibonacci identity in the spirit of Simson and
               Gelin-Cesaro, \textit{Fibonacci Quart.} \textbf{41} (2003), 142--143.

\bibitem{Ozgur} N. Y. \"{O}zg\"{u}r, On the sequences related to Fibonacci and Lucas numbers,
              \textit{J. Korean Math. Soc.} \textbf{42} (2005), 135--151.

\bibitem{Pethe} S. P. Pethe and C. N. Phadte, A generalization of the Fibonacci sequence, in
              G.~E.~Bergum, A.~N.~Philippou, and A.~F.~Horadam, eds., \textit{Applications of Fibonacci Numbers}, Vol.~5, Kluwer Academic Publishers,
	      1993, pp.~465--472.

\bibitem{Rabinowitz} S. Rabinowitz, Algorithmic manipulation of 
second order linear recurrences,
              \textit{Fibonacci Quart.} \textbf{37} (1999), 162--177.

\bibitem{Rosen} K. H. Rosen,  \textit{Discrete Mathematics and its Applications},
              McGraw-Hill, 2011.

\bibitem{Sahin} M. Sahin, The Gelin-Cesaro identity in some conditional sequences, \textit{Hacet.
              J. Math. Stat.} \textbf{40} (2011), 855--861.

\bibitem{Sbultari} G. Sbultari, Generalized Fibonacci sequence and linear congruences,
              \textit{Fibonacci Quart.} \textbf{40} (2002), 446--452.

\bibitem{Sedgewick} R. Sedgewick and P. Flajolet,  \textit{An Introduction to the Analysis of
              Algorithms}, Addison-Wesley, 2013.

\bibitem{Stanley} R. P. Stanley, \textit{Enumerative Combinatorics}, Vol.~1, Cambridge University
              Press, 1997.

\bibitem{Taher} R. B. Taher and M. Rachidi, Linear recurrence relations in the algebra of
              matrices and applications, \textit{Linear Algebra Appl.} \textbf{330} (2001), 15--24.

\bibitem{Tasci} D. Tasci and M. C. Firengiz, Incomplete Fibonacci and Lucas
              $p$-numbers, \textit{Math. Comput. Modelling} \textbf{52} (2010), 1763--1770.

\bibitem{Yayenie} O. Yayenie, A note on generalized Fibonacci sequences, \textit{Appl. Math.
              Comput.} \textbf{217} (2011), 5603--5611.

\bibitem{Walton} J. E. Walton and A. F. Horadam, Some further identities for the generalized
              Fibonacci sequences $\{H_n\}$, \textit{Fibonacci Quart.} \textbf{12} (1974), 272--280.

\bibitem{ZatADM} R. A. Zatorsky, Theory of paradeterminants and its applications,
              \textit{Algebra Discrete Math}.  \textbf{1} (2007), 109--138.

\bibitem{ZatMono} R. A. Zatorsky, \textit{Calculus of Triangular Matrices}, Simyk, 2010.

\bibitem{ZatKPI} R. A. Zatorsky and I. \`{I}. Lytvynenko,  Applications of parapermanents of linear
              recurrent sequences, \textit{Research Bulletin of NTUU ``KPI''} \textbf{5} (2008), 122--128.

\bibitem{ZatDopovidi} R. A. Zatorsky, Paradeterminants and parapermanents of triangular
              matrices, \textit{Reports of the National Academy of Sciences of Ukraine} \textbf{8} (2002), 21--25.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 15A15; Secondary 11B37, 11B39.

\noindent \emph{Keywords: } triangular matrix, parapermanent, recurrence equation, generating function.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A000213},
\seqnum{A000215},
\seqnum{A000930},
\seqnum{A001045},
\seqnum{A001348}, and
\seqnum{A002275}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 23 2015;
revised version received December 20 2015.
Published in {\it Journal of Integer Sequences}, January 10 2016.

\bigskip
\hrule
\bigskip

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


\end{document}
</pre></body></html>