Infinite Linear Recurrence Relations and Superposition of Linear Recurrence Equations

Taras Goy and Roman Zatorsky Vasyl Stefanyk Precarpathian National University Department of Mathematics and Informatics 57 Shevchenko str. 76018 Ivano-Frankivsk Ukraine

                      tarasgoy@yahoo.com
                    romazatorsky@gmail.com

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.

1 Introduction

In a previous paper [11], 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 [9, 10].

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 [11, Corollary 7]. 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.

2 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 [4, 6, 7, 8, 9, 10, 11] for more details and examples).

A triangular number table

A_{n} = (\begin{matrix}a_{11} \\ a_{21} & a_{22} \\ ⋯ & ⋯ & ... \\ a_{n1} & a_{n2} & ⋯ & a_{nn} \end{matrix})  (1)

is called a triangular matrix of order n. We shall also denote the matrix (1) briefly by (a_{ij})_{1≤j≤i≤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 (1) we assign (i − j + 1) elements a_{ik}, where k = j, …, i, which are called the derived elements of the matrix determined by the key element a_{ij}.

The product of all derived elements determined by an element a_{ij} is denoted by {a_{ij}} and called the factorial product of the key element a_{ij}; thus

{a_{ij}} = a_{ij}a_{i,j+1} ⋯ a_{ii}.

A tuple of key elements of matrix (1) is called a 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 ℙ(n) be the set of all ordered partitions of a positive integer n into positive integer summands [1, p. 54]. Tarakanov and Zatorsky [7] established a one-to-one correspondence between elements of ℙ(n) and normal tuples of key elements of matrix (1).

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

The paradeterminant ddet(A_{n}) and the parapermanent pper(A_{n}) of the triangular matrix (1) are defined as

ddet(A_{n}) = ∑_{(m_{1},...,m_{r})∈ℙ(n)}(−1)^{ε(a)} ∏_{s=1}^{r}{a_{i(s),j(s)}},

pper(A_{n}) = ∑_{(m_{1},...,m_{r})∈ℙ(n)} ∏_{s=1}^{r}{a_{i(s),j(s)}},

where a_{i(s),j(s)} is the key element corresponding to the s-th component of the partition (m_{1}, …, m_{r}) ∈ ℙ(n).

In the sequel, we use the term parafunction both for paradeterminant and parapermanent.

It is well known that |ℙ(n)| = 2^{n−1}, hence the parafuctions of a triangular matrix of order n consist of 2^{n−1} summands.

Ganyushkin et al. [3] obtained the following equalities:

ddet(A_{n}) = ∑_{r=1}^{n} ∑_{m_{1}+···+m_{r}=n}(−1)^{n−r} ∏_{s=1}^{r}{a_{m_{1}+···+m_{s}, m_{1}+···+m_{s−1}+1}},

pper(A_{n}) = ∑_{r=1}^{n} ∑_{m_{1}+···+m_{r}=n} ∏_{s=1}^{r}{a_{m_{1}+···+m_{s}, m_{1}+···+m_{s−1}+1}},

where m_{1}, …, m_{r} are positive integers, and {a_{ij}} is the factorial product of the element a_{ij} ∈ A_{n}. For example,

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

\begin{matrix}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} + \\ + 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{matrix}

Theorem 1. [10] Parafunctions of the triangular matrix (1) can be decomposed by elements of the last row, i.e.,

ddet(A_{n}) = ∑_{s=1}^{n} {a_{ns}} ddet(A_{s−1}),

pper(A_{n}) = ∑_{s=1}^{n} {a_{ns}} pper(A_{s−1}),  (2)

where, by definition, ddet(A_{0}) = pper(A_{0}) = 1.

Lemma 2. [12] For all n ≥ 1, the system of equations

b_{n} = pper (τ_{sr} \frac{a_{s−r+1}}{a_{s−r}} )_{1≤r≤s≤n}

has the solution

a_{n} = (−1)^{n−1} ddet (\frac{1}{τ_{s,s−r+1}} · \frac{b_{s−r+1}}{b_{s−r}} )_{1≤r≤s≤n} .

3 Infinite linear recurrence relations

Let

a = (a_{1}, a_{2}, a_{3}, …)  (3)

be an infinite-dimensional number vector.

A linear recurrence relation

u_{n} = ∑_{i=1}^{∞} a_{i}u_{n−i},  (4)

where u_{0} = 1, u_{<0} = 0, is called an infinite recurrence relation.

Below we consider the following three cases for the sequence (3):

(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 (4) will be called periodic, mixed periodic, and non-periodic recurrence relation.

Theorem 3. For the sequence (u_{n})_{n≥0} the infinite recurrence equation (4) with u_{0} = 1 and u_{<0} = 0 is equivalent to the following three equations:

u_{n} = pper (\begin{matrix}a_{1} \\ \frac{a_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ... \\ \frac{a_{n−1}}{a_{n−2}} & \frac{a_{n−2}}{a_{n−3}} & ⋯ & a_{1} \\ \frac{a_{n}}{a_{n−1}} & \frac{a_{n−1}}{a_{n−2}} & ⋯ & \frac{a_{2}}{a_{1}} & a_{1} \end{matrix}) ,  (5)

where u_{0} = 1;

u_{n} = ∑_{λ_{1}+2λ_{2}+···+nλ_{n}=n} \frac{(λ_{1} + λ_{2} + ⋯ + λ_{n})!}{λ_{1}!λ_{2}! ⋯ λ_{n}!}a_{1}^{λ_{1}}a_{2}^{λ_{2}} ⋯ a_{n}^{λ_{n}};  (6)

1 + ∑_{n=1}^{∞} u_{n}x^{n} = \frac{1}{1 − a_{1}x − a_{2}x^{2} − a_{3}x^{3} − ⋯},  (7)

for all n ≥ 1.

Remark 4. If some number a_{i} in (5) equals zero, then the zeros cancel out in the evaluation of parapermanent (or paradeterminant) and the indefiniteness disappears.

Proof of Theorem 3. The equivalence of the recurrence equations (4) and (5) follows from the decomposition of the parapermanent in (5) by elements of the last row, by (2).

Let us prove the equivalence of the recurrence equations (5) and (6). To do this, we find parapermanent values in (5). Taking into account {a_{ij}} = a_{i−j+1}, for the component m_{i} of the ordered partition m_{1}+m_{2}+⋯+m_{n} = n we have the factorial product that is equal to a_{m_{i}}; for the whole ordered partition (m_{1}, m_{2}, …, m_{n}) we have the vector (a_{m_{1}}, a_{m_{2}}, …, a_{m_{n}}). For all ordered partitions, the mentioned elements form the multiset with the primary specification [1^{λ_{1}}, 2^{λ_{2}}, …, n^{λ_{n}}], in the parapermanent we obtain the summand a_{1}^{λ_{1}}a_{2}^{λ_{2}} ⋯ a_{n}^{λ_{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 λ_{1} + λ_{2} + ⋯ + λ_{n}, the number of all possible orderings of multisets with this primary specification, according to multinomial theorem, is equal to \frac{(λ_{1}+λ_{2}+···+λ_{n})!}{λ_{1}!λ_{2}!···λ_{n}!}. Thus equality (6) is proved.

The equivalence of the recurrence equations (4) and (7) follows from identity

(1 − ∑_{i=1}^{∞} a_{i}x^{i})·(1 + ∑_{j=1}^{∞} u_{j}x^{j}) = 1 + ∑_{n=1}^{∞} (u_{n} − a_{1}u_{n−1} − a_{2}u_{n−2} − ⋯ − a_{n}u_{0}) x^{n},

the both sides of which are equal to 1 only if

u_{n} − a_{1}u_{n−1} − a_{2}u_{n−2} − ⋯ − a_{n}u_{0} = 0,

for n ≥ 1.

Theorem 3 reduces to [11, Theorem 5] if a_{k+1} = a_{k+2} = ⋯ = 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 3 is also true for the recurrence equations (4) with variable coefficients.

Theorem 5. Let the components of vector (3) form an s-periodic number sequence, i.e.,

a = (b_{1}, b_{2}, …, b_{s}, b_{1}, b_{2}, …, b_{s}, b_{1}, …).

If the sequence (u_{n})_{n≥1} satisfies the recurrence equation (4), then its generating function is

f(x) = \frac{1 − x^{s}}{1 − b_{1}x − b_{2}x^{2} − ⋯ − (b_{s} + 1)x^{s}} .  (8)

Proof. From Theorem 3, it follows that the generating function of the sequence (u_{n})_{n≥1}, which satisfies the recurrence equation (4), is

f(x) = \frac{1}{1 − b_{1}x − b_{2}x^{2} − b_{3}x^{3} − ⋯}.

Using s-periodicity of each vector components (3), in view of the fact that

(1 − x^{s})(1 + x^{s} + x^{2s} + ⋯) = 1,

we have

f(x) =\frac{1}{1 − (b_{1}x + b_{2}x^{2} + ⋯ + b_{s}x^{s}) − (b_{1}x^{s+1} + b_{2}x^{s+2} + ⋯ + b_{s}x^{2s}) − b_{1}x^{2s+1} − ⋯} =
=\frac{1}{1 − (b_{1}x + b_{2}x^{2} + ⋯ + b_{s}x^{s})(1 + x^{s} + x^{2s} + ⋯)} =
=\frac{1}{1 − \frac{b_{1}x+b_{2}x^{2}+···+b_{s}x^{s}}{1−x^{s}}} =
=\frac{1 − x^{s}}{1 − b_{1}x − b_{2}x^{2} − ⋯ − (b_{s} + 1)x^{s}} .

This proves (8).

Example 6. Let a = (1, 2, 3, 1, 2, 3, 1, …). Then s = 3 and the generating function of the sequence (u_{n})_{n≥1} = {1, 1, 3, 8, 18, 46, 114, 278, 690, …}, which satisfies the recurrence equation

u_{n} = u_{0} + 2u_{1} + 3u_{2} + u_{3} + 2u_{4} + 3u_{5} + u_{6} + ⋯,

where u_{0} = 1, according to (8), is

f(x) = \frac{1 − x^{3}}{1 − x − 2x^{2} − 4x^{3}} .

Theorem 7. Let the components of vector (3) form a mixed s-periodic sequence, i.e.,

a = (c_{1}, c_{2}, …, c_{r}, b_{1}, b_{2}, …, b_{s}, b_{1}, b_{2}, …, b_{s}, b_{1}, …).

If the sequence (u_{n})_{n≥1} satisfies the recurrence equation (4), then its generating function is

f(x) = \frac{1 − x^{s}}{(1 − c_{1}x − c_{2}x^{2} − ⋯ − c_{r}x^{r})(1 − x^{s}) − x^{r+1}(b_{1} + b_{2}x + ⋯ + b_{s}x^{s−1})}. (9)

Proof. Similarly to the proof of Theorem 5, we have

f(x) =\frac{1}{1 − c_{1}x − ⋯ − c_{r}x^{r} − (b_{1}x^{r+1} + ⋯ + b_{s}x^{r+s}) − (b_{1}x^{r+s+1} + ⋯ + b_{s}x^{r+2s}) − ⋯} =
=\frac{1}{1 − c_{1}x − ⋯ − c_{r}x^{r} − (b_{1}x + b_{2}x^{2} + ⋯ + b_{s}x^{s})(x^{r} + x^{r+s} + x^{r+2s} + ⋯)} =
=\frac{1}{1 − c_{1}x − ⋯ − c_{r}x^{r} − \frac{x^{r}}{1−x^{s}} (b_{1}x + b_{2}x^{2} + ⋯ + b_{s}x^{s})} =
=\frac{1 − x^{s}}{(1 − c_{1}x − ⋯ − c_{r}x^{r})(1 − x^{s}) − x^{r+1}(b_{1} + b_{2}x + ⋯ + b_{s}x^{s−1})}.

Example 8. Let a = (1, 2, 3, 2, 3, 2, 3, …). Then r = 1 and s = 3. The generating function of the sequence (u_{n})_{n≥1} = {1, 1, 3, 8, 19, 49, 122, 307, 771, …}, which satisfies the recurrence equation

u_{n} = u_{0} + 2u_{1} + 3u_{2} + 2u_{3} + 3u_{4} + 2u_{5} + 3u_{6} + ⋯,

where u_{0} = 1, according to (9), is

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

Theorem 9. Suppose that each component of vector (3) satisfies the recurrence equation

a_{n} = ω_{1}a_{n−1} + ω_{2}a_{n−2} + ⋯ + ω_{k}a_{n−k}, n ≥ 1,  (10)

where a_{0} = 1, a_{<0} = 0. The generating function of sequence (u_{n})_{n≥1}, which satisfies the infinite recurrence equation

u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2} + a_{3}u_{n−3} + ⋯,  (11)

where u_{0} = 1, is

f(x) = \frac{1 − ω_{1}x − ω_{2}x^{2} − ⋯ − ω_{k}x^{k}}{1 − (a_{1} + ω_{1})x − ⋯ − (a_{k−1} − ω_{1}a_{k−2} − ⋯ − ω_{k−2}a_{1} + ω_{k−1})x^{k−1} − 2ω_{k}x^{k}} . (12)

The theorem is established in [12]; we just give the proof for the reader’s convenience.

Proof. According to Theorem 3, the sequence (u_{n})_{n≥1}, which satisfies the recurrence equation (11), have the generating function

f(x) = \frac{1}{1 − a_{1}x − a_{2}x^{2} − a_{3}x^{3} − ⋯}.

Then, using (10), we obtain

\frac{1}{f(x)} = 1 − ∑_{i=1}^{∞} a_{i}x^{i} =

= 1 − ∑_{n=1}^{k−1} a_{n}x^{n} − ω_{1}x ∑_{n=k}^{∞} a_{n−1}x^{n−1} − ⋯ − ω_{k}x^{k} ∑_{n=k}^{∞} a_{n−k}x^{n−k} =

= 1 − ∑_{n=1}^{k−1} a_{n}x^{n} − ω_{1}x ∑_{n=k−1}^{∞} a_{n}x^{n} − ⋯ − ω_{k}x^{k} ∑_{n=0}^{∞} a_{n}x^{n} =

= 1 − ∑_{n=1}^{k−1} a_{n}x^{n} + ω_{1}x (−1 + a_{1}x + a_{2}x^{2} + ⋯ + a_{k−2}x^{k−2} + \frac{1}{f(x)}) +

+ ω_{2}x^{2}(−1 + a_{1}x + ⋯ + a_{k−3}x^{k−3} + \frac{1}{f(x)})+ ⋯ + ω_{k−1}x^{k−1}(−1 + \frac{1}{f(x)}) +

+ ω_{k}x^{k}(−2 + \frac{1}{f(x)}).

Therefore,

\frac{1}{f(x)} = \frac{1 − (a_{1} + ω_{1})x − ⋯ − (a_{k−1} − ω_{1}a_{k−2} − ⋯ − ω_{k−2}a_{1} + ω_{k−1})x^{k−1} − 2ω_{k}x^{k}}{1 − ω_{1}x − ω_{2}x^{2} − ⋯ − ω_{k}x^{k}} ,

which completes the proof.

Example 10. The coefficients of the infinite recurrence equation

u_{n} = u_{n−1} + 3u_{n−2} + 8u_{n−3} + 21u_{n−4} + ⋯ + F_{2k}u_{n−k} + ⋯,

where F_{2k} are Fibonacci numbers with even indices (sequence \underline{A001906} in the OEIS [5]), satisfy the recurrence second-order equation a_{n} = 3a_{n−1}−a_{n−2}. Thus ω_{1} = 3, ω_{2} = −1, k = 1, and the generating function of the sequence (u_{n})_{n≥1} = {1, 1, 4, 15, 56, 209, 780, 2911, …} (sequence \underline{A001353}), according to (12), is

f(x) = \frac{1 − 3x + x^{2}}{1 − 4x + x^{2}} .

The sequence (u_{n})_{n≥0}, defined as

u_{0} = 1, u_{1} = pper(a_{1}), u_{2} = pper \binom{a_{1}}{\frac{a_{2}}{a_{1}} a_{1}} , u_{3} = pper ( \begin{matrix}a_{1} \\ \frac{a_{2}}{a_{1}} & a_{1} \\ \frac{a_{3}}{a_{2}} & \frac{a_{2}}{a_{1}} & a_{1} \end{matrix} ) , …, (13)

is called the normal sequence of (a_{1}, a_{2}, …).

Theorem 11. The terms of the normal sequence (13) satisfy the infinite recurrence equation

u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2} + a_{3}u_{n−3} + ⋯,  (14)

where

a_{i} = (−1)^{i−1} ddet (\begin{matrix}u_{1} \\ \frac{u_{2}}{u_{1}} & u_{1} \\ ⋯ & ⋯ & ... \\ \frac{u_{i}}{u_{i−1}} & \frac{u_{i−1}}{u_{i−2}} & ⋯ & u_{1} \end{matrix}) , i ≥ 1  (15)

Proof. By Theorem 3,

u_{i} = pper (\begin{matrix}a_{1} \\ \frac{a_{2}}{a_{1}} & a_{1} \\ ⋯ & ⋯ & ... \\ \frac{a_{i}}{a_{i−1}} & \frac{a_{i−1}}{a_{i−2}} & ⋯ & a_{1} \end{matrix}) , i ≥ 1.

The last system, according to Lemma 2, has the solution (15).

Example 12. 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≥0} (see \underline{A000041}):

f(x) = 1 + x + 2x^{2} + 3x^{3} + 5x^{4} + 7x^{5} + 11x^{6} + 15x^{7} + 22x^{8} + 30x^{9} + 42x^{10} +
+ 56x^{11} + 77x^{12} + 101x^{13} + 135x^{14} + 176x^{15} + 231x^{16} + 297x^{17} + 385x^{18} +
+ 490x^{19} + 627x^{20} + 792x^{21} + 1002x^{22} + 1255x^{23} + 1575x^{24} + · · · .

Using (15), find the first 24 coefficients of the desired recurrence equation (sequence \underline{A257628}):

1, 1, 0, 0, −1, 0 − 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, −1, 0, 0, ….

Let us write few initial nonzero terms of the recurrence equation:

u_{n} = u_{n−1} + u_{n−2} − u_{n−5} − u_{n−7} + u_{n−12} + u_{n−15} − u_{n−22} − · · · .

So, we obtain enough evidence for Euler’s pentagonal formula [2, p. 246]

u_{n} = ∑_{k=1}^{∞}(−1)^{k−1} (u_{n− \frac{3k^{2}−k}{2}} + u_{n− \frac{3k^{2}+k}{2}} ) , n ≥ 1.

4 Superposition of linear recurrence equations

Now we introduce the following concept.

Define the k-superposition S_{i=1}^{k}(u_{n}^{(i)}) of the linear recurrence equations

u_{n}^{(i)} = u_{1}^{(i+1)}u_{n−1}^{(i)} + u_{2}^{(i+1)}u_{n−2}^{(i)} + ⋯ + u_{n−1}^{(i+1)}u_{1}^{(i)} + u_{n}^{(i+1)},  (16)

where i = 1, 2, …, k and k ≥ 2, as linear recurrence equation, which generates the sequence (u_{j}^{(1)})_{j≥1}, whose terms are expressed via the sequence (u_{j}^{(k+1)})_{j≥1}.

Note that the coefficients appearing in the k-th recurrence relation (16) 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 S(u_{n}^{(1)}, u_{n}^{(2)}).

Example 13. For k = 2, result of the 2-superposition S(u_{n}^{(1)}, u_{n}^{(2)}) of recurrence equations

u_{n}^{(1)} = u_{1}^{(2)}u_{n−1}^{(1)} + u_{2}^{(2)}u_{n−2}^{(1)} + ⋯ + u_{n−1}^{(2)}u_{1}^{(1)} + u_{n}^{(2)}

and

u_{n}^{(2)} = u_{1}^{(3)}u_{n−1}^{(2)} + u_{2}^{(3)}u_{n−2}^{(2)} + ⋯ + u_{n−1}^{(3)}u_{1}^{(2)} + u_{n}^{(3)},

according to Theorems 3, is the linear recurrence equation

u_{n}^{(1)} = ∑_{i=1}^{n} pper(A_{i}) u_{n−i}^{(1)},

where u_{0}^{(1)} = 1 and

A_{i} = (\begin{matrix}u_{1}^{(3)} \\ \frac{u_{2}^{(3)}}{u_{1}^{(3)}} & u_{1}^{(3)} \\ ⋯ & ⋯ & ... \\ \frac{u_{i}^{(3)}}{u_{i−1}^{(3)}} & \frac{u_{i−1}^{(3)}}{u_{i−2}^{(3)}} & … & u_{1}^{(3)} \end{matrix}) .

Lemma 14. The result of 2-superposition S(u_{n}^{(1)}, u_{n}^{(2)}), where

u_{n}^{(1)} = u_{1}^{(2)}u_{n−1}^{(1)} + u_{2}^{(2)}u_{n−2}^{(1)} + ⋯ + u_{n−1}^{(2)}u_{1}^{(1)} + u_{n}^{(2)},
u_{n}^{(2)} = u_{1}^{(3)}u_{n−1}^{(2)} + u_{2}^{(3)}u_{n−2}^{(2)} + ⋯ + u_{n−1}^{(3)}u_{1}^{(2)} + u_{n}^{(3)},

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

u_{n}^{(1)} = 2 (u_{1}^{(3)}u_{n−1}^{(1)} + u_{2}^{(3)}u_{n−2}^{(1)} + ⋯ + u_{n−1}^{(3)}u_{1}^{(1)}) + u_{n}^{(3)},

where u_{0}^{(1)} = 1, u_{1}^{(1)} = u_{1}^{(3)}.

Proof. Since

u_{n}^{(1)} = ∑_{i=1}^{n} u_{i}^{(2)}u_{n−i}^{(1)},

u_{i}^{(2)} = ∑_{j=1}^{i} u_{j}^{(3)}u_{i−j}^{(2)},

we see that

u_{n}^{(1)} = ∑_{i=1}^{n} (∑_{j=1}^{i} u_{j}^{(3)}u_{i−j}^{(2)}) u_{n−i}^{(1)} =

= ∑_{j=1}^{n−1} u_{j}^{(3)} (u_{n−j}^{(1)} + ∑_{i=1}^{n−j} u_{i}^{(2)}u_{n−j−i}^{(1)}) + u_{n}^{(3)} =

= 2 ∑_{j=1}^{n−1} u_{j}^{(3)}u_{n−j}^{(1)} + u_{n}^{(3)}.

Theorem 15. The result of k-superposition S_{i=1}^{k}(u_{n}^{(i)}), where u_{n}^{(i)} is defined by recurrence equation (16), and u_{0}^{(s)} = 1, u_{1}^{(s)} = u_{1}^{(s+1)}, s = 1, 2, …, k, is the linear recurrence equation

u_{n}^{(1)} = k ·(u_{1}^{(k+1)}u_{n−1}^{(1)} + u_{2}^{(k+1)}u_{n−2}^{(1)} + ⋯ + u_{n−1}^{(k+1)}u_{1}^{(1)}) + u_{n}^{(k+1)}.  (17)

Proof. The proof is by induction on k. For k = 2, according to Lemma 14, formula (17) holds. Assume (17) holds for k = m − 1 and prove its validity for k = m. To do this, find the result of 2-superposition S(u_{n}^{(1)}, u_{n}^{(m)}), where

u_{n}^{(1)} = (m − 1) ∑_{i=1}^{n−1} u_{i}^{(m)}u_{n−i}^{(1)} + u_{n}^{(m)},

u_{n}^{(m)} = ∑_{j=1}^{n−1} u_{j}^{(m+1)}u_{n−j}^{(m)} + u_{n}^{(m+1)}.

Since

u_{i}^{(m)} = ∑_{j=1}^{i−1} u_{j}^{(m+1)}u_{i−j}^{(m)} + u_{i}^{(m+1)},

we obtain

u_{n}^{(1)} = (m − 1) ∑_{i=1}^{n−1} (∑_{j=1}^{i−1} u_{j}^{(m+1)}u_{i−j}^{(m)} + u_{i}^{(m+1)}) u_{n−i}^{(1)} + u_{n}^{(m)}.

Group the terms with u_{j}^{(m+1)}; then

u_{n}^{(1)} = ∑_{j=1}^{n−2} u_{j}^{(m+1)} ((m − 1)u_{n−j}^{(1)} + (m − 1) ∑_{i=1}^{n−j−1} u_{i}^{(m)}u_{n−j−i}^{(1)} + u_{n−j}^{(m)}) +
+ u_{n−1}^{(m+1)} ((m − 1)u_{1}^{(1)} + u_{1}^{(m)}) + u_{n}^{(m+1)}.

Since

(m − 1) ∑_{i=1}^{n−j−1} u_{i}^{(m)}u_{n−j−i}^{(1)} + u_{n−j}^{(m)} = u_{n−j}^{(1)},

we finally obtain

u_{n}^{(1)} = m ∑_{j=1}^{n−1} u_{j}^{(m+1)}u_{n−j}^{(1)} + u_{n}^{(m+1)}.

Example 16. Consider the linear recurrence equation of n order

u_{n} = u_{n−1} + 2u_{n−2} + ⋯ + (n − 1)u_{1} + nu_{0},  (18)

where u_{0} = 1 and a_{k} = k. We claim that equation (18) generates the Fibonacci numbers with even indices (sequence \underline{A001906}). Indeed,

u_{1} = F_{2} = 1, u_{2} = F_{4} = 3, u_{3} = F_{6} = 8, ….

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

Using (15), we get

a_{1} = ddet(1) = 1, a_{2} = − ddet \binom{1}{2 1} = 1, a_{3} = ddet ( \begin{matrix}1 \\ 2 & 1 \\ \frac{3}{2} & 2 & 1 \end{matrix} ) = 0,

a_{4} = −1, a_{5} = −1, a_{6} = 0,

and, in general,

a_{3k} = 0, a_{3k+1} = (−1)^{k}, a_{3k+2} = (−1)^{k}.

Thus, we obtain recurrent equation of infinite order

v_{n} = v_{n−1} + v_{n−2} + 0 · v_{n−3} − v_{n−4} − v_{n−5} + 0 · v_{n−6} + v_{n−7} + v_{n−8} + ⋯  (19)

with the periodic sequence of coefficients: 1, 1, 0, −1, −1, 0, 1, 1, 0, −1, −1, 0, 1, . . ..

Now, application of Lemma (14) to recurrence equations (18), (19) yields the recurrence equation

u_{n} = 2(u_{n−1} + u_{n−2} − u_{n−4} − u_{n−5} + ⋯ + a_{n−1}u_{1}) + a_{n}u_{0},  (20)

where u_{0} = 1 and

a_{3m} = 0, a_{3m−1} = (−1)^{m−1}, a_{3m−2} = (−1)^{m−1},

for m ≥ 1.

Equation (20) generates the same sequence of Fibonacci numbers with even indices:

u_{1} = u_{0} = 1, u_{2} = 2u_{1} + u_{0} = 3, u_{3} = 2u_{2} + 2u_{1} + 0 · u_{0} = 8,
u_{4} = 2u_{3} + 2u_{2} + 0 · u_{1} − u_{0} = 21, u_{5} = 2u_{4} + 2u_{3} + 0 · u_{2} − 2u_{1} − u_{0} = 55,

and so on.

The recurrence equation (20) can be reduced to the generating function of the sequence (u_{n})_{n≥1} as follows:

1 + ∑_{n=1}^{∞} u_{n}x^{n} = \frac{x + x^{2}}{1 − 2x − 2x^{2} + x^{3}} .

After obvious transformations, we get the generating function

∑_{n=1}^{∞} u_{n}x^{n} = \frac{x}{1 − 3x + x^{2}} ,

which yields second-order recurrence equation u_{n} = 3u_{n−1} − u_{n−2} with initial condition u_{0} = 1.

5 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.

References

[1] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1984.

[2] L. Euler, Introduction to Analysis of the Infinite. Book I, Springer-Verlag, 1988.

[3] O. G. Ganyushkin, R. A. Zatorsky, and I. I. Lishchinskii, On paradeterminants and parapermanents of triangular matrices, Bull. Kyiv Univ. Ser. Phys. Math. 1 (2005), 40–45.

[4] T. P. Goy and R. A. Zatorsky, Using triangular matrices for construction of ordinary differential equations for the known fundamental system of solutions, NaUKMA Sci. Notes. Ser. Phys. Math. 165 (2015), 3–6.

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electroni-

cally at https://oeis.org.

[6] S. Stefluk and R. Zatorsky, Parafunctions of triangular matrices and m-ary partitions of numbers, Algebra Discrete Math. 21 (2016), 144–152.

[7] V. E. Tarakanov and R. A. Zatorskii, A relationship between determinants and permanents, Math. Notes 85 (2009), 267–273.

[8] R. A. Zatorsky, Determinants of triangular matrices and trajectories on Ferre diagrams, Math. Notes 72 (2002), 768–783.

[9] R. Zatorsky, Introduction to the theory of triangular matrices (tables), in I. I. Kyrchei, ed., Advances in Linear Algebra Research, Nova Sci. Publ., 2015, pp. 185–238.

[10] R. A. Zatorsky, Theory of paradeterminants and its applications, Algebra Discrete Math. 1 (2007), 109–138.

[11] R. Zatorsky and T. Goy, Parapermanents of triangular matrices and some general theorems on number sequences, J. Integer Sequences 19 (2016), Article 16.2.2.

[12] R. A. Zatorsky and A. R. Malarchuk. The infinite linear recurrent equations and paradeterminants, Carpathian Math. Publ. 1 (2009), 35–46.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 15A15. Keywords: triangular matrix, paradeterminant, parapermanent, superposition of recurrence equations, recurrence relation, generating function.

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

Received August 24 2016; revised versions received August 27 2016; January 14 2017; March 2 2017; March 3 2017. Published in Journal of Integer Sequences, March 26 2017.

Return to Journal of Integer Sequences home page.