<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}}}

\DeclareMathOperator{\ddet}{ddet}
\DeclareMathOperator{\pper}{pper}

\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
Infinite Linear Recurrence Relations and Superposition of Linear Recurrence Equations\\
\vskip .1in } \vskip 1cm \large
Taras Goy and Roman Zatorsky \\
Vasyl Stefanyk Precarpathian National University \\
Department of Mathematics and Informatics \\
57 Shevchenko str. \\
76018 Ivano-Frankivsk \\
Ukraine\\
\href{mailto:tarasgoy@yahoo.com}{\tt tarasgoy@yahoo.com} \\
\href{mailto:romazatorsky@gmail.com}{\tt romazatorsky@gmail.com} \\
\end{center}


\vskip .2 in

\begin{abstract} We consider the applications of triangular matrices
and functions of them to the study of number sequences generated by
infinite-order linear recurrence equations with constant coefficients.
We also introduce the concept of superposition of linear recurrence
equations  and establish some of its properties.
\end{abstract}

\section{Introduction}

In a previous paper \cite{JIS},
the authors considered several concepts and theorems related to number
sequences generated by linear recurrence equations of order $n$. The
main research tool was parapermanents of triangular matrices
\cite{Mono2, ADM}.

In this article we continue to explore number sequences generated by
linear recurrence relations. However, the generating linear recurrence
equations for these sequences are infinite. In particular, we consider
an infinite-dimensional analogue of \cite[Corollary 7]{JIS}. Given
a normal number sequence, we construct an infinite linear recurrence
equation and the generating function of this sequence. Notions of
periodic, mixed periodic, and non-periodic infinite linear recurrence
are introduced, as well as a concept of superposition of linear
recurrence equations. Some formulas for these objects are established.

\section{Functions of triangular matrices}

In this section, we compile some basic facts of the theory of functions of triangular matrices.

Functions of triangular matrices are widely used in many diverse fields such as algebra, combinatorics, number theory, and theory of ordinary differential equations (see \cite{K_Mog, Stefluk, Tarakan, Ferre, Mono2, ADM, JIS} for more details and examples).

A triangular number table
\begin{equation} \label{trmatr}
A_n= \left(
  \begin{matrix}
    a_{11} &amp;  &amp;  &amp;  \\[0 pt]
    a_{21} &amp; a_{22} &amp;  &amp;  \\[0 pt]
    \cdots &amp; \cdots &amp; \ddots &amp;  \\[0 pt]
    a_{n1} &amp; a_{n2} &amp; \cdots &amp; a_{nn}
  \end{matrix}
\right)
\end{equation}
is called a \emph{triangular matrix} of order $n$. We shall also denote the matrix (\ref{trmatr}) briefly by $\left(a_{ij}\right)_{1\leq j\leq i\leq n}$.

We notice that a triangular matrix defined this way is not a matrix in the usual sense because it is a triangular rather than a rectangular table of numbers.

To each element $a_{ij}$ of matrix (\ref{trmatr}) we assign $(i-j+1)$ elements $a_{ik}$, where $k=j,\ldots, i$, which are called the \emph{derived elements} of the matrix determined by the \emph{key element} $a_{ij}$.

The product of all derived elements determined by an element $a_{ij}$ is denoted by $\{a_{ij}\}$ and called the \emph{factorial product} of the key element $a_{ij}$; thus
\begin{equation*}
\{a_{ij}\}=a_{ij}a_{i,j+1}\cdots a_{ii}.
\end{equation*}

A tuple of key elements of matrix (\ref{trmatr}) is called a \emph{normal tuple} for this matrix if the derived elements of these key elements form a monotransversal, i.e., they form a set of elements of cardinality $n$, no two of which belong to the same column of the matrix.

Let $\mathbb{P}(n)$ be the set of all ordered partitions of a positive integer $n$ into positive integer summands \cite[p.\ 54]{Andrews}. Tarakanov and Zatorsky \cite{Tarakan} established a one-to-one correspondence between elements of $\mathbb{P}(n)$ and normal tuples of key elements of matrix (\ref{trmatr}).

We associate each normal tuple $a$ of key elements with the sign $(-1)^{\varepsilon(a)}$, where $\varepsilon(a)$ is the sum of all indices of key elements from this tuple.

The \emph{paradeterminant}  $\ddet(A_n)$ and the \emph{parapermanent} $\pper(A_n)$ of the triangular matrix (\ref{trmatr}) are defined as
\begin{equation*}
\ddet(A_n)=
\sum\limits_{(m_{1},\ldots,m_{r})\in\mathbb{P}(n)}(-1)^{\varepsilon(a)}
\prod\limits_{s=1}^{r}\{a_{i(s),j(s)}\},\\
\end{equation*}
\begin{equation*}
\pper(A_n)=\sum\limits_{(m_{1},\ldots, m_{r})\in\mathbb{P}(n)} \prod\limits_{s=1}^{r}\{a_{i(s),j(s)}\},
\end{equation*}
where $a_{i(s),j(s)}$ is the key element corresponding to the $s$-th component of the partition $(m_1,\ldots, m_r)\in \mathbb{P}(n)$.

In the sequel, we use the term \emph{parafunction} both for paradeterminant and parapermanent.

It is well known that $|\mathbb{P}(n)|= 2^{n-1}$, hence the parafuctions of a triangular matrix of order $n$ consist of $2^{n-1}$ summands.

Ganyushkin et al. \cite{Ganyushkin} obtained the following equalities:
\begin{equation*}
\ddet(A_n)=\sum_{r=1}^{n}\sum_{m_{1}+\cdots+m_{r}=n} (-1)^{n-r}\prod_{s=1}^{r}\{a_{m_{1}+\cdots+m_{s},\,m_{1}+\cdots+m_{s-1}+1}\},
\end{equation*}
\begin{equation*}
\pper(A_n)=\sum_{r=1}^{n}\sum_{m_{1}+\cdots+m_{r}=n} \prod_{s=1}^{r}\{a_{m_{1}+\cdots+m_{s},\,m_{1}+\cdots+m_{s-1}+1}\},
\end{equation*}
where $m_{1},\ldots, m_{r}$ are positive integers, and $\left\{a_{ij}\right\}$ is the factorial product of the element $a_{ij}\in A_n$. For example,
\begin{equation*}
\ddet(A_3)=a_{11}a_{22}a_{33} - a_{21}a_{22}a_{33} - a_{11}a_{32}a_{33} + a_{31}a_{32}a_{33};
\end{equation*}
\begin{equation*}
\begin{array}{cc}
\pper(A_4)=a_{41}a_{42}a_{43}a_{44} + a_{31}a_{32}a_{33}a_{44} + a_{21}a_{22}a_{43}a_{44} +  a_{21}a_{22}a_{33}a_{44}\, +\\[6 pt]
    +\, a_{11}a_{42}a_{43}a_{44} +a_{11}a_{32}a_{33}a_{44} + a_{11}a_{22}a_{43}a_{44} + a_{11}a_{22}a_{33}a_{44}.
  \end{array}
\end{equation*}
\begin{theorem} \label{theoRozklddet} \emph{\cite{ADM}} Parafunctions of the triangular matrix \emph{(\ref{trmatr})} can be decomposed by elements of the last row, i.e.,
\begin{equation*}
\ddet(A_n)=\sum\limits_{s=1}^n {\left\{ {a_{ns}}\right\}\ddet(A_{s-1})},
\end{equation*}
\begin{equation}\label{rozkladpper}
\pper(A_n)=\sum\limits_{s=1}^n\left\{ {a_{ns}}\right\}\pper(A_{s-1}),
\end{equation}
where, by definition, $\ddet(A_0)=\pper(A_0)=1$.
\end{theorem}

\begin{lemma} \emph{\cite{Malarchuk}} \label{lem1}
For all $n\geq 1$, the system of equations
\begin{equation*}
 b_{n}=\pper\left(
\tau_{sr}\frac{a_{s-r+1}}{a_{s-r}}\right)_{1\leq r\leq
s\leq n}
\end{equation*}
has the solution
\begin{equation*}
a_{n}=(-1)^{n-1}\ddet\left(
\frac{1}{\tau_{s,s-r+1}}\cdot\frac{b_{s-r+1}}{b_{s-r}}\right)_{1\leq
r\leq s\leq n}.
\end{equation*}
\end{lemma}

\section{Infinite linear recurrence relations}

Let
\begin{equation} \label{vektorinfty}
\emph{\textbf{a}} = (a_1,a_2,a_3,\ldots)
\end{equation}
be an infinite-dimensional number vector.

A linear recurrence relation
\begin{equation}\label{recinfty}
u_n=\sum_{i=1}^{\infty}a_iu_{n-i},
\end{equation}
where $u_0=1$, $u_{&lt;0}=0$, is called an \emph{infinite recurrence relation}.

Below we consider the following three cases for the sequence (\ref{vektorinfty}):

(1)~the sequence is periodic;

(2)~the sequence is periodic with some pre-period;

(3)~the sequence is non-periodic.

Accordingly, the infinite recurrence relation (\ref{recinfty}) will be
called \emph{periodic}, \emph{mixed periodic}, and \emph{non-periodic}
recurrence relation.

\begin{theorem}\label{theorecinfty} For the sequence $(u_n)_{n\geq 0}$
the infinite recurrence equation \emph{(\ref{recinfty})} with $u_0=1$
and $u_{&lt;0}=0$ is equivalent to the following three equations\emph{:}

\begin{equation}\label{pperrecinfty}
 u_n=\pper\left(
\begin{matrix}
a_1  &amp;  &amp;  &amp;  &amp;   \\[1 pt]
\frac{a_2}{a_1} &amp; a_1 &amp;  &amp;  &amp;   \\[1 pt]
\cdots &amp; \cdots &amp; \ddots &amp;  &amp;  \\[2 pt]
\frac{a_{n-1}}{a_{n-2}} &amp; \frac{a_{n-2}}{a_{n-3}} &amp; \cdots &amp; a_1 \\[2 pt]
\frac{a_n}{a_{n-1}} &amp; \frac{a_{n-1}}{a_{n-2}} &amp; \cdots &amp; \frac{a_2}{a_1} &amp;  a_1
\end{matrix}\right),
\end{equation}
where $u_0=1$\emph{;}

\begin{equation}\label{polrozbrecinfty}
u_n=\sum_{\lambda_1+2\lambda_2+\cdots+n\lambda_n=n}\frac{(\lambda_{1}+\lambda_{2}+\cdots+\lambda_{n})!}{\lambda_{1}!
    \lambda_{2}!\cdots\lambda_{n}!}a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_n^{\lambda_n};
\end{equation}
\begin{equation}\label{genrecinfty}
1+\sum_{n=1}^{\infty}u_n x^n = \frac{1}{1-a_1x-a_2x^2-a_3x^3-\cdots},
\end{equation}
for all $n\geq1$.
\end{theorem}
\begin{remark} If some number $a_i$ in (\ref{pperrecinfty}) equals zero, then the zeros cancel out in the evaluation of parapermanent (or paradeterminant) and the indefiniteness disappears.
\end{remark}
\begin{proof}[Proof of Theorem \ref{theorecinfty}] The equivalence of the recurrence equations  (\ref{recinfty}) and (\ref{pperrecinfty}) follows from the decomposition of the parapermanent in (\ref{pperrecinfty}) by elements of the last row, by (\ref{rozkladpper}).

Let us prove the equivalence of the recurrence equations (\ref{pperrecinfty}) and (\ref{polrozbrecinfty}). To do this, we find parapermanent values in (\ref{pperrecinfty}). Taking into account $\{a_{ij}\}=a_{i-j+1}$, for the component $m_{i}$ of the ordered partition $m_{1}+m_{2}+\cdots+m_{n}=n$ we have the factorial product that is equal to $a_{m_{i}}$; for the whole ordered partition $(m_{1},m_{2},\ldots,m_{n})$ we have the vector $(a_{m_{1}},a_{m_{2}},\ldots,a_{m_{n}})$. For all ordered partitions, the mentioned elements form the multiset with the primary specification  $[1^{\lambda_{1}},2^{\lambda_{2}},\ldots,n^{\lambda_{n}}]$, in the parapermanent we obtain the summand $a_{1}^{\lambda_{1}}a_{2}^{\lambda_{2}}\cdots a_{n}^{\lambda_{n}}$.

Now we compute analogously the number of the summands in the parapermanent. Since the number of non-zero elements of the ordered partition is equal to $\lambda_{1}+\lambda_{2}+\cdots+\lambda_{n}$, the number of all possible orderings of multisets with this primary specification, according to multinomial theorem, is equal to $\frac{(\lambda_{1}+\lambda_{2}+\cdots+\lambda_{n})!}{\lambda_{1}!
\lambda_{2}!\cdots\lambda_{n}!}.$ Thus equality (\ref{polrozbrecinfty}) is proved.

The equivalence of the recurrence equations (\ref{recinfty}) and (\ref{genrecinfty}) follows from identity
\begin{equation*}
\left(1-\sum_{i=1}^{\infty}a_{i}x^{i}\right)\!\cdot\!\left(1+\sum_{j=1}^{\infty}u_{j}x^{j}\right)=
1+\sum_{n=1}^{\infty}\left(u_{n}-a_{1}u_{n-1}-a_{2}u_{n-2}-\cdots-a_{n}u_{0}\right)x^{n},
\end{equation*}
the both sides of which are equal to $1$ only if
\begin{equation*}
u_{n}-a_{1}u_{n-1}-a_{2}u_{n-2}-\cdots-a_{n}u_{0}=0,
\end{equation*}
for $n\geq 1$.
\end{proof}

Theorem \ref{theorecinfty} reduces to \cite[Theorem 5]{JIS} if $a_{k+1}=a_{k+2}=\cdots=0$. Indeed, in this case it is easy to show that all the numbers $c_i$  from (9) of [11] are equal to $1$.

Note that Theorem \ref{theorecinfty} is also true for the recurrence equations (\ref{recinfty}) with variable coefficients.

\begin{theorem}\label{theorecperiod}
Let the components of vector \emph{(\ref{vektorinfty})} form an $s$-periodic number sequence, i.e.,  \begin{equation*}
\textbf{a}=(b_1,b_2,\ldots,b_s,b_1,b_2,\ldots,b_s,b_1,\ldots).
\end{equation*}
If the sequence $(u_n)_{n\geq 1}$ satisfies the recurrence equation \emph{(\ref{recinfty})}, then its generating function is
\begin{equation}\label{theo4}
f(x)=\frac{1-x^s}{1-b_1x-b_2x^2-\cdots-(b_s+1)x^s}.
\end{equation}
\end{theorem}
\begin{proof} From Theorem \ref{theorecinfty}, it follows that the generating function of the sequence $(u_n)_{n\geq 1}$,  which satisfies the recurrence equation (\ref{recinfty}), is
\begin{equation*}
f(x)=\frac{1}{1-b_1x-b_2x^2-b_3x^3-\cdots}.
\end{equation*}

Using  $s$-periodicity of each vector components (\ref{vektorinfty}), in view of the fact that
\begin{equation*}
(1-x^s)(1+x^s+x^{2s}+\cdots)=1,
\end{equation*}
we have
\begin{align*}
f(x)=&amp;\frac{1}{1-(b_1x+b_2x^2+\cdots+ b_s x^s)-(b_1 x^{s+1} + b_2 x^{s+2}+\cdots + b_s x^{2s})-b_1x^{2s+1}-\cdots}=\\
=&amp;\frac{1}{1-(b_1x+b_2x^2+\cdots+ b_sx^s)(1+x^s+x^{2s}+\cdots)}=\\
=&amp;\frac{1}{1-\frac{b_1x+b_2x^2+\cdots+ b_sx^s}{1-x^s}}=\\
=&amp;\frac{1-x^s}{1-b_1x-b_2x^2-\cdots-(b_s+1)x^s}.
\end{align*}

This proves (\ref{theo4}).
\end{proof}
\begin{example}
Let $\emph{\textbf{a}}=(1,2,3, 1,2,3,1,\ldots)$. Then $s=3$ and the generating function of the sequence $(u_n)_{n\geq 1}=\{1,1,3,8,18,46,114,278,690,\ldots\}$, which satisfies the recurrence equation
\begin{equation*}
u_n=u_{0}+2u_{1}+3u_{2}+u_{3}+2u_{4}+3u_{5}+u_{6}+\cdots,
\end{equation*}
where $u_0=1$, according to (\ref{theo4}), is
\begin{equation*}
f(x)=\frac{1-x^3}{1-x-2x^2-4x^3}.
\end{equation*}
\end{example}
\begin{theorem} Let the components of vector \emph{(\ref{vektorinfty})} form a mixed $s$-periodic  sequence, i.e.,
\begin{equation*}
\textbf{a}=(c_1,c_2,\ldots,c_r,b_1,b_2,\ldots,b_s,b_1,b_2,\ldots,b_s,b_1,\ldots).
\end{equation*}
If the sequence $(u_n)_{n\geq 1}$ satisfies the recurrence equation \emph{(\ref{recinfty})}, then its generating function is
\begin{equation}\label{theo6}
f(x)=\frac{1-x^s}{(1-c_1x-c_2x^2-\cdots-c_rx^r)(1-x^s)-x^{r+1}(b_1+b_2x+\cdots+b_sx^{s-1})}.
\end{equation}
\end{theorem}
\begin{proof} Similarly to the proof of Theorem \ref{theorecperiod}, we have
\begin{align*}
f(x)=&amp;\frac{1}{1-c_1x-\cdots-c_rx^r-(b_1x^{r+1}+\cdots+b_sx^{r+s})-(b_1x^{r+s+1}+\cdots+b_sx^{r+2s})-\cdots}=\\
=&amp;\frac{1}{1-c_1x-\cdots-c_rx^r-(b_1x+b_2x^2+\cdots+b_sx^s)(x^r+x^{r+s}+x^{r+2s}+\cdots)}=\\
=&amp;\frac{1}{1-c_1x-\cdots-c_rx^r-\frac{x^r}{1-x^s}(b_1x+b_2x^2+\cdots+b_sx^s)}=\\
=&amp;\frac{1-x^s}{(1-c_1x-\cdots-c_rx^r)(1-x^s)-x^{r+1}(b_1+b_2x+\cdots+b_sx^{s-1})}.
\end{align*}
\end{proof}
\begin{example}
Let $\emph{\textbf{a}}=(1, 2, 3, 2, 3, 2, 3, \ldots)$. Then $r=1$ and $s=3$. The generating function of the sequence $(u_n)_{n\geq 1}=\{1,1,3,8,19,49,122,307,771,\ldots\}$, which satisfies the recurrence equation
\begin{equation*}
u_n=u_{0}+2u_{1}+3u_{2}+2u_{3}+3u_{4}+2u_{5}+3u_{6}+\cdots,
\end{equation*}
where $u_0=1$, according to (\ref{theo6}), is
\begin{equation*}
f(x)=\frac{1-x^2}{(1-x)(1-x^2)-x(2x+3x^2)}=\frac{1-x^2}{1-x-3x^2-2x^3}.
\end{equation*}
\end{example}
\begin{theorem} \label{examvektorizrecurdoheneratr}
Suppose that each component of vector \emph{(\ref{vektorinfty})} satisfies the recurrence equation
\begin{equation}\label{omega}
a_{n}=\omega_{1}a_{n-1}+\omega_{2}a_{n-2}+\cdots+\omega_{k}a_{n-k},\quad n\geq 1,
\end{equation}
where $a_{0}=1$, $a_{&lt;0}=0$. The generating function of sequence $(u_{n})_{n\geq 1}$, which satisfies the infinite recurrence equation
\begin{equation}\label{recinfty1}
u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+a_{3}u_{n-3}+\cdots,
\end{equation}
where $u_{0}=1$, is
\begin{equation}\label{fz}
f(x)=\frac{1-\omega_{1}x-\omega_{2}x^{2}-\cdots-\omega_{k}x^k}
{1-(a_{1}+\omega_{1})x-\cdots-(a_{k-1}-\omega_{1}a_{k-2}- \cdots-\omega_{k-2}a_{1}+\omega_{k-1})x^{k-1}-2\omega_{k}x^{k}}.
\end{equation}
\end{theorem}
The theorem is established in \cite{Malarchuk}; we just give the proof for the reader's  convenience.
\begin{proof} According to Theorem \ref{theorecinfty}, the sequence $(u_{n})_{n\geq 1}$, which satisfies  the recurrence equation (\ref{recinfty1}), have the generating function
\begin{equation*}
f(x)=\frac{1}{1-a_{1}x-a_{2}x^2-a_{3}x^3-\cdots}.
\end{equation*}
Then, using (\ref{omega}), we obtain
\begin{align*}
\frac{1}{f(x)}&amp;=\,1-\sum_{i=1}^{\infty}a_{i}x^{i}=\\
&amp;=\,1-\sum_{n=1}^{k-1}a_{n}x^{n}-\omega_{1}x\sum_{n=k}^{\infty}a_{n-1}x^{n-1}-\cdots-\omega_{k}x^{k}\sum_{n=k}^{\infty}a_{n-k}x^{n-k}=\\
&amp;=\,1-\sum_{n=1}^{k-1}a_{n}x^{n}-\omega_{1}x\sum_{n=k-1}^{\infty}a_{n}x^{n}-\cdots-\omega_{k}x^{k}\sum_{n=0}^{\infty}a_{n}x^{n}=\\
&amp;=\,1-\sum_{n=1}^{k-1}a_{n}x^{n}+\omega_{1}x\left(-1+a_{1}x+a_{2}x^{2}+\cdots+a_{k-2}x^{k-2}+\frac{1}{f(x)}\right)+\\
&amp;+\,\omega_{2}x^{2}\!\left(-1+a_{1}x+\cdots+a_{k-3}x^{k-3}+\frac{1}{f(x)}\right)\!+\cdots+\omega_{k-1}x^{k-1}\!\left(-1+\frac{1}{f(x)}\right)+\\
&amp;+\omega_{k}x^{k}\!\left(-2+\frac{1}{f(x)}\right)\!.
\end{align*}

Therefore,
\begin{equation*}
\frac{1}{f(x)}=\frac{1-(a_{1}+\omega_{1})x-\cdots-(a_{k-1}-\omega_{1}a_{k-2}- \cdots-\omega_{k-2}a_{1}+\omega_{k-1})x^{k-1}-2\omega_{k}x^{k}}{1-\omega_{1}x-\omega_{2}x^{2}-\cdots-\omega_{k}x^{k}},
\end{equation*}
which completes the proof.
\end{proof}
\begin{example} The coefficients of the infinite recurrence equation
\begin{equation*}
u_n=u_{n-1}+3u_{n-2}+8u_{n-3}+21u_{n-4}+\cdots+F_{2k}u_{n-k}+\cdots,
\end{equation*}
where $F_{2k}$ are Fibonacci numbers with even indices (sequence \seqnum{A001906} in the OEIS \cite{Sloane}), satisfy the recurrence second-order equation $a_n=3a_{n-1}-a_{n-2}$. Thus $\omega_1=3$, $\omega_2=-1$, $k=1$, and the generating  function of the sequence  $(u_n)_{n\geq 1}=\{1,1,4,15,56,209, 780,2911,\ldots\}$ (sequence \seqnum{A001353}), according to (\ref{fz}), is
\begin{equation*}
f(x)=\frac{1-3x+x^2}{1-4x+x^2}.
\end{equation*}
\end{example}

The sequence $(u_n)_{n\geq 0}$, defined as
\begin{equation}\label{u0u1u2}
u_0=1,\,\,
u_1=\pper(a_1),\,\,
u_2=\pper\left(\begin{array}{cc}
a_1 &amp;  \\
\frac{a_2}{a_1} &amp; a_1
\end{array}\right),\,\,
u_3=\pper\left(\begin{array}{ccc}
a_1 &amp;  &amp; \\
\frac{a_2}{a_1} &amp; a_1 &amp; \\
\frac{a_3}{a_2} &amp; \frac{a_2}{a_1}&amp; a_1
\end{array}\right),\,\ldots,
\end{equation}
is called the \emph{normal sequence} of $(a_1,a_2,\ldots)$.
\begin{theorem}\label{theootposledovndorecurrivn}
The terms of the normal sequence \emph{(\ref{u0u1u2})} satisfy the infinite recurrence equation
\begin{equation}\label{neskinchrecurrivn}
u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+a_{3}u_{n-3}+\cdots,
\end{equation}
where
\begin{equation}\label{koeficientrecurrivn}
a_{i}=(-1)^{i-1}\ddet
\left(\begin{matrix}
u_{1} &amp; &amp; &amp;\\[1 pt]
\frac{u_{2}}{u_{1}}&amp; u_{1} &amp; &amp;\\[0 pt]
\cdots &amp;\cdots &amp;\ddots &amp;\\[0 pt]
\frac{u_{i}}{u_{i-1}} &amp;\frac{u_{i-1}}{u_{i-2}} &amp;\cdots &amp; u_{1}
\end{matrix}\right),\quad i\geq 1
\end{equation}
\end{theorem}
\begin{proof}
By Theorem  \ref{theorecinfty},
\begin{equation*}
u_{i}=\pper\left(\begin{matrix}
 a_{1}&amp;&amp;&amp;\\[0 pt]
\frac{a_{2}}{a_{1}} &amp; a_{1} &amp; &amp; \\[0 pt]
\cdots &amp; \cdots &amp; \ddots &amp;\\[0 pt]
\frac{a_{i}}{a_{i-1}} &amp;\frac{a_{i-1}}{a_{i-2}}&amp;\cdots&amp;a_{1}
\end{matrix}\right),\quad i\geq 1.
\end{equation*}

The last system, according to Lemma \ref{lem1}, has the solution (\ref{koeficientrecurrivn}).
\end{proof}
\begin{example} Let $p_n$ be the number of possible partitions of a positive integer number $n$, i.e., the number of distinct ways of representing $n$ as a sum of positive integer  numbers (with order irrelevant). The first 25 terms of the generating function of the sequence $(p_n)_{n\geq 0}$ (see \seqnum{A000041}):
\begin{equation*}
\begin{array}{c}
f(x)= 1+x+2x^2+3x^3+5x^4+7x^5+11x^6+15x^7+22x^8+30x^9+42x^{10}\,+ \\[5 pt]
  +\,56x^{11}+77x^{12}+101x^{13}+135x^{14}+176x^{15}+231x^{16}+297x^{17}+385x^{18}\,+\\[5 pt]
  +\,490x^{19}+627x^{20}+792x^{21}+1002x^{22}+1255x^{23}+1575x^{24}+\cdots.
\end{array}
\end{equation*}

Using (\ref{koeficientrecurrivn}), find the first 24 coefficients of the desired recurrence equation (sequence  \seqnum{A257628}):
\begin{equation*}
1,\,1,\,0,\,0,\,-1,\,0\,-1,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,0,\,0,\,-1,\,0,\,0,\ldots.
\end{equation*}

Let us write few initial nonzero terms of the recurrence equation:
\begin{equation*}
u_{n}=u_{n-1}+u_{n-2}-u_{n-5}-u_{n-7}+u_{n-12}+u_{n-15}-u_{n-22}-\cdots.
\end{equation*}

So, we obtain enough evidence for Euler's pentagonal formula \cite[p.\ 246]{Euler}
\begin{equation*}
u_n=\sum_{k=1}^{\infty}(-1)^{k-1}\left(u_{n-\frac{3k^2-k}{2}}+u_{n-\frac{3k^2+k}{2}}\right),\quad n\geq 1.
\end{equation*}
\end{example}

\section{Superposition of linear recurrence equations}

Now we introduce the following concept.

Define the $k$-\emph{superposition} $\mathcal{S}_{i=1}^k(u_n^{(i)})$ of the linear recurrence equations
\begin{equation}\label{ksuperrec}
u_n^{(i)}=u_1^{(i+1)}u_{n-1}^{(i)}+u_2^{(i+1)}u_{n-2}^{(i)}+\cdots+u_{n-1}^{(i+1)}u_1^{(i)}+u_n^{(i+1)}, \end{equation}
where $i=1,2,\ldots,k$ and $\,k\geq 2$, as linear  recurrence equation, which generates the sequence $(u_j^{(1)})_{j\geq 1}$, whose terms are expressed via the sequence $(u_j^{(k+1)})_{j\geq 1}$.

Note that the coefficients appearing in the $k$-th recurrence relation (\ref{ksuperrec}) do not depend on the terms of the first $k-1$ recurrence relations.

The superposition of two recurrence equations (or $2$-superposition) we denote also by
$\mathcal{S}(u_n^{(1)}, u_n^{(2)})$.
\begin{example} For $k=2$, result of the 2-superposition $\mathcal{S}(u_n^{(1)}, u_n^{(2)})$ of recurrence equations
\begin{equation*}
u_n^{(1)}=u_1^{(2)}u_{n-1}^{(1)}+u_2^{(2)}u_{n-2}^{(1)}+\cdots+u_{n-1}^{(2)}u_1^{(1)}+u_n^{(2)}
\end{equation*}
and
\begin{equation*}
u_n^{(2)}=u_1^{(3)}u_{n-1}^{(2)}+u_2^{(3)}u_{n-2}^{(2)}+\cdots+u_{n-1}^{(3)}u_1^{(2)}+u_n^{(3)},
\end{equation*}
according to Theorems \ref{theorecinfty}, is the linear recurrence equation  \begin{equation*}\label{2Spper}
u_n^{(1)}=\sum_{i=1}^n \pper(A_i)\,u_{n-i}^{(1)},
\end{equation*}
where $u_0^{(1)}=1$ and
\begin{equation*}
A_i=\left(
    \begin{matrix}
    u_1^{(3)} &amp;  &amp;  &amp;  \\[0 pt]
    \frac{u_2^{(3)}}{u_1^{(3)}} &amp; u_1^{(3)} &amp;  &amp;  \\[0 pt]
    \cdots &amp; \cdots &amp; \ddots &amp;  \\[0 pt]
    \frac{u_i^{(3)}}{u_{i-1}^{(3)}} &amp; \frac{u_{i-1}^{(3)}}{u_{i-2}^{(3)}} &amp; \ldots &amp; u_1^{(3)}
    \end{matrix}
    \right).
\end{equation*}
\end{example}
\begin{lemma}\label{lemsuper2}
The result of 2-superposition $\mathcal{S}(u_n^{(1)}, u_n^{(2)})$, where
\begin{equation*}
u_n^{(1)}=u_1^{(2)}u_{n-1}^{(1)}+u_2^{(2)}u_{n-2}^{(1)}+\cdots+u_{n-1}^{(2)}u_1^{(1)}+u_n^{(2)}, \end{equation*}
\begin{equation*}
u_n^{(2)}=u_1^{(3)}u_{n-1}^{(2)}+u_2^{(3)}u_{n-2}^{(2)}+\cdots+u_{n-1}^{(3)}u_1^{(2)}+u_n^{(3)},
\end{equation*}
and $u_0^{(1)}=1$, $u_1^{(1)}=u_1^{(2)}$, $u_0^{(2)}=1$, $u_1^{(2)}=u_1^{(3)}$, is the linear recurrence equation
\begin{equation*}
u_n^{(1)}=2\left(u_1^{(3)}u_{n-1}^{(1)}+u_2^{(3)}u_{n-2}^{(1)}+\cdots+u_{n-1}^{(3)}u_1^{(1)}\right)+u_n^{(3)}, \end{equation*}
where $u_0^{(1)}=1$, $u_1^{(1)}=u_1^{(3)}$.
\end{lemma}
\begin{proof} Since
\begin{equation*}
u_n^{(1)}=\sum_{i=1}^nu_i^{(2)}u_{n-i}^{(1)},
\end{equation*}
\begin{equation*}
u_i^{(2)}=\sum_{j=1}^iu_j^{(3)}u_{i-j}^{(2)},
\end{equation*}
we see that
\begin{align*}
u_n^{(1)}&amp;=\sum_{i=1}^n\left(\sum_{j=1}^iu_j^{(3)}u_{i-j}^{(2)}\right)u_{n-i}^{(1)}=\\
&amp;=\sum_{j=1}^{n-1}u_j^{(3)}\left(u_{n-j}^{(1)}+\sum_{i=1}^{n-j}u_i^{(2)}u_{n-j-i}^{(1)}\right)+u_{n}^{(3)}=\\
&amp;=2\sum_{j=1}^{n-1}u_j^{(3)}u_{n-j}^{(1)}+u_n^{(3)}.
\end{align*}
\end{proof}
\begin{theorem}\label{theosupernrec}
The result of $k$-superposition $\mathcal{S}_{i=1}^k(u_n^{(i)})$, where $u_n^{(i)}$ is defined by recurrence equation \emph{(\ref{ksuperrec})}, and $u_0^{(s)}=1$,  $u_1^{(s)}=u_1^{(s+1)}$, $s=1,2,\ldots,k$, is the linear recurrence equation
\begin{equation}\label{theo15}
u_n^{(1)}=k\cdot\!\left(u_1^{(k+1)}u_{n-1}^{(1)}+u_2^{(k+1)}u_{n-2}^{(1)}+\cdots+u_{n-1}^{(k+1)}u_1^{(1)}\right)+u_{n}^{(k+1)}.
\end{equation}
\end{theorem}
\begin{proof} The proof is by induction on $k$. For $k=2$, according to Lemma \ref{lemsuper2}, formula (\ref{theo15}) holds. Assume (\ref{theo15}) holds for $k=m-1$ and prove its validity for $k=m$. To do this, find the result of 2-superposition $\mathcal{S}(u_n^{(1)},u_n^{(m)})$, where
\begin{equation*}
u_n^{(1)}=(m-1)\sum_{i=1}^{n-1}u_i^{(m)}u_{n-i}^{(1)}+u_n^{(m)},
\end{equation*}
\begin{equation*}
u_n^{(m)}=\sum_{j=1}^{n-1}u_j^{(m+1)}u_{n-j}^{(m)}+u_n^{(m+1)}.
\end{equation*}

Since
\begin{equation*}
u_i^{(m)}=\sum_{j=1}^{i-1}u_j^{(m+1)}u_{i-j}^{(m)}+u_i^{(m+1)},
\end{equation*}
we obtain
\begin{equation*}
u_n^{(1)}=(m-1)\sum_{i=1}^{n-1}\left(\sum_{j=1}^{i-1}u_j^{(m+1)}u_{i-j}^{(m)}+u_i^{(m+1)}\right)u_{n-i}^{(1)}+u_n^{(m)}.
\end{equation*}

Group the terms with $u_j^{(m+1)}$; then
\begin{align*}
u_n^{(1)}&amp;=\sum_{j=1}^{n-2}u_j^{(m+1)}\left((m-1)u_{n-j}^{(1)}+(m-1)\sum_{i=1}^{n-j-1}u_i^{(m)}u_{n-j-i}^{(1)}+u_{n-j}^{(m)}\right)+\\
&amp;+u_{n-1}^{(m+1)}\left((m-1)u_1^{(1)}+u_1^{(m)}\right)+u_n^{(m+1)}.
\end{align*}
Since
\begin{equation*}
(m-1)\sum_{i=1}^{n-j-1}u_i^{(m)}u_{n-j-i}^{(1)}+u_{n-j}^{(m)}=u_{n-j}^{(1)},
\end{equation*}
we finally obtain
\begin{equation*}
u_n^{(1)}=m\sum_{j=1}^{n-1}u_j^{(m+1)}u_{n-j}^{(1)}+u_n^{(m+1)}.
\end{equation*}
\end{proof}
\begin{example}
Consider the linear recurrence equation of $n$ order
\begin{equation}\label{recur1}
u_n= u_{n-1}+2 u_{n-2}+\cdots+(n-1)u_1+nu_0,
\end{equation}
where $u_0=1$ and $a_k=k$. We claim that equation (\ref{recur1}) generates the Fibonacci numbers with even indices (sequence \seqnum{A001906}). Indeed,
\begin{equation*}
u_1=F_2=1,\,\,\, u_2=F_4=3,\,\,\, u_3=F_6=8,\ldots\,.
\end{equation*}

Let us obtain the linear recurrence equation generating  the sequence $\{1,\,2,\,3,\ldots\}$.

Using (\ref{koeficientrecurrivn}), we get
\begin{equation*}
a_1=\ddet(1)=1,\,\,\,\,\,\,
a_2=-\ddet\left(
\begin{array}{cc}
1 &amp;  \\
2 &amp; 1 \\
\end{array}\right)=1,\,\,\,\,\,
a_3=\ddet\left(\begin{array}{ccc}
 1 &amp;  &amp;  \\
 2 &amp; 1 &amp;  \\
 \frac{3}{2} &amp; 2 &amp;  1\\\end{array}\right)=0,
\end{equation*}
\begin{equation*}
a_4=-1,\,\,\,\,\, a_5=-1,\,\,\,\,\, a_6=0,
\end{equation*}
and, in general,
\begin{equation*}
a_{3k}=0,\quad a_{3k+1}=(-1)^k,\quad a_{3k+2}=(-1)^k.
\end{equation*}

Thus, we obtain recurrent equation of infinite order
\begin{equation}\label{recur2}
v_n=v_{n-1}+v_{n-2}+0\cdot v_{n-3}-v_{n-4}-v_{n-5}+0\cdot v_{n-6}+v_{n-7}+v_{n-8}+\cdots
\end{equation}
with the periodic sequence of coefficients:
$1,\,1,\,0,\,-1,\,-1,\,0,\,1,\,1,\,0,\,-1,\,-1,\,0,1,\ldots$.

Now, application of Lemma (\ref{lemsuper2}) to recurrence equations (\ref{recur1}), (\ref{recur2}) yields the recurrence equation
\begin{equation}\label{last}
u_n=2(u_{n-1}+u_{n-2}-u_{n-4}-u_{n-5}+\cdots+a_{n-1}u_{1})+a_nu_0,
\end{equation}
where $u_0=1$ and
\begin{equation*}
a_{3m}=0,\quad a_{3m-1}=(-1)^{m-1},\quad a_{3m-2}=(-1)^{m-1},
\end{equation*}
for $m\geq 1$.

Equation (\ref{last}) generates the same sequence of Fibonacci numbers with even indices:
\begin{equation*}
u_1=u_0=1,\quad u_2=2u_1+u_0=3,\quad u_3=2u_2+2u_1+0\cdot u_0=8,
\end{equation*}
\begin{equation*}\label{lasteq}
u_4=2u_3 + 2u_2+ 0\cdot u_1-u_0=21,\quad u_5=2u_4+2u_3+0\cdot u_2-2u_1-u_0=55,
\end{equation*}
and so on.

The recurrence equation (\ref{last}) can be reduced to the generating function of the sequence $(u_n)_{n\geq 1}$ as follows:
\begin{equation*}
1+\sum_{n=1}^{\infty}u_nx^n=\frac{x+x^2}{1-2x-2x^2+x^3}.
\end{equation*}

After  obvious transformations, we get the generating function
\begin{equation*}
\sum_{n=1}^{\infty}u_nx^n=\frac{x}{1-3x+x^2},
\end{equation*}
 which yields second-order recurrence equation $u_n=3u_{n-1}-u_{n-2}$ with initial condition $u_0=1$.
\end{example}

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

\begin{thebibliography}{99}

\bibitem{Andrews} G.~E.~Andrews,  \textit{The Theory of Partitions},
Cambridge University Press,  1984.

\bibitem{Euler} L.~Euler,  \textit{Introduction to Analysis of the
Infinite. Book I},  Springer-Verlag,  1988.

\bibitem{Ganyushkin} O.~G.~Ganyushkin, R.~A.~Zatorsky, and
I.~I.~Lishchinskii,  On paradeterminants and parapermanents of
triangular matrices,  \textit {Bull. Kyiv Univ. Ser. Phys. Math.}
\textbf{1} (2005), 40--45.

\bibitem{K_Mog} T.~P.~Goy and R.~A.~Zatorsky,  Using triangular
matrices for construction of ordinary differential equations for the
known fundamental system of solutions,  \textit {NaUKMA Sci. Notes.
Ser. Phys. Math.} \textbf{165} (2015), 3--6.

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

\bibitem{Stefluk} S.~Stefluk and R.~Zatorsky, Parafunctions of
triangular matrices and $m$-ary partitions of numbers, \textit{Algebra
Discrete Math}.  \textbf{21} (2016), 144--152.

\bibitem{Tarakan} V.~E.~Tarakanov and  R.~A.~Zatorskii, A relationship
between determinants and permanents, \textit{Math. Notes} \textbf{85}
(2009), 267--273.

\bibitem{Ferre} R.~A.~Zatorsky, Determinants of triangular matrices and
trajectories on Ferre diagrams, \textit{Math. Notes} \textbf{72}
(2002), 768--783.

\bibitem{Mono2} R.~Zatorsky, Introduction to the theory of triangular
matrices (tables), in I.~I.~ Kyrchei, ed., \emph{Advances in Linear
Algebra Research}, Nova Sci. Publ., 2015,  pp.~185--238.

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

\bibitem{JIS} R.~Zatorsky and T.~Goy, Parapermanents of triangular
matrices and some general theorems on number sequences, \textit{J.
Integer Sequences} \textbf{19} (2016),
\,\href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Goy/goy2.html}{Article
16.2.2}.

\bibitem{Malarchuk} R.~A.~Zatorsky and A.~R.~Malarchuk. The infinite
linear recurrent equations and paradeterminants, \textit {Carpathian
Math. Publ.} \textbf{1} (2009), 35--46.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords:} triangular matrix, paradeterminant, parapermanent, superposition of recurrence equations, recurrence relation, generating function.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000041}, \seqnum{A001353}, \seqnum{A001906} and \seqnum{A257628}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 24 2016;
revised versions received August 27 2016; January 14 2017;
March 2 2017; March 3 2017.
Published in {\it Journal of Integer Sequences}, March 26 2017.

\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>