General Convolution Sums Involving Fibonacci m-Step Numbers

Robert Frontczak 72762 Reutlingen Germany

                          robert.frontczak@web.de

Karol Gryszka Institute of Mathematics University of the National Education Commission, Krakow Podchora̧żych 2 30-084 Kraków Poland

                        karol.gryszka@uken.krakow.pl

Abstract In this paper, using a generating function approach, we derive several new convolution sum identities involving the Fibonacci m-step numbers. As special instances of the results derived herein, we obtain many new and known results involving the Fibonacci, Tribonacci, Tetranacci, and Pentanacci numbers. In addition, we establish some general results providing insights into the inner structure of such convolutions. Finally, we state some mixed convolutions involving the Fibonacci m-step, Jacobsthal, and Pell numbers.

1 Motivation and preliminaries

The motivation for writing this paper comes from three recently published papers by Dresden and his collaborators: Dresden and Wang [3, 5] and Dresden and Tulskikh [4]. In these papers, convolutions involving important number sequences like the Fibonacci numbers (F_{n})_{n≥0}, the Lucas numbers (L_{n})_{n≥0}, the Pell numbers (P_{n})_{n≥0}, the Jacobsthal numbers (J_{n})_{n≥0}, the Tribonacci numbers (T_{n})_{n≥0}, and others are studied. Dresden and Wang close their article [5] with a short discussion of the two seemingly unrelated convolutions

∑_{j=0}^{n} J_{j}F_{n−j} = J_{n+1} − F_{n+1}  (1)

and

∑_{j=0}^{n} T_{j}F_{n−j} = T_{n+2} − F_{n+2}  (2)

(see [16] for (1) and [1, 6, 8] for (2), respectively). A third example of this nature is the following convolution, which can be found in [10, 19]:

∑_{j=0}^{n} P_{j}F_{n−j} = P_{n} − F_{n}.  (3)

A hidden link between (2) and (3) will be revealed later. At this point we can clearly see that identities (1)–(3) look suspiciously similar. Dresden and Wang [5] ask “... if there are other general convolution formulas waiting to be discovered?”. The answer to this question is “Definitely yes!”. Building on a generating function approach (also see [8, 13, 14, 15, 17]) for the Fibonacci m-step numbers we prove many new convolution identities, recovering known results as special cases, including the identities presented above.

We note that the generating function approach is not a novel discovery. However, the referenced articles show that this approach has received a lot of attention in the recent years. In this context, we mention the recent article by Gessel and Kar [9], which provides an extensive analysis of (binomial) convolutions of sequences with rational generating functions.

As for the Fibonacci m-step sequences, there seems to be a lack of a general approach to some of the convolution identities involving these sequences and other recurrence relations, mentioned at the beginning of the article and many more. Our response to this is a step forward towards a better understanding of the general inner structure of these convolutions. To keep things coherent and focused on a single topic, this article is devoted exclusively to the Fibonacci m-step numbers. Thus, identities related to the Lucas (m-step) sequences (see, for example, [3, 4]) are the subject of another study.

We start with a definition. The m-step Fibonacci numbers are defined for all m ≥ 1 by

F_{1}^{(m)} = 1, and F_{n}^{(m)} = 0 for all n = −(m − 2), …, 0

(F_{0}^{(1)} = 0) and for all n ≥ 2,

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

Their arithmetic structure was studied in a recent article by the second author [12]. The ordinary generating function for the m-step Fibonacci numbers is given by

F^{(m)}(x) = \frac{x}{1 − x − x^{2} − ⋯ − x^{m}} .

We introduce the following notation for a selection of particular Fibonacci m-step numbers. Let F_{n}^{(2)} = F_{n}, F_{n}^{(3)} = T_{n}, F_{n}^{(4)} = Q_{n}, and F_{n}^{(5)} = P_{n} denote the Fibonacci, Tribonacci, Tetranacci, and Pentanacci numbers, respectively. Therefore, the following can be stated.

F_{n} = F_{n−1} + F_{n−2},  F_{0} = 0, F_{1} = 1,
T_{n} = T_{n−1} + T_{n−2} + T_{n−3},  T_{0} = 0, T_{1} = T_{2} = 1,
Q_{n} = Q_{n−1} + Q_{n−2} + Q_{n−3} + Q_{n−4},  Q_{0} = 0, Q_{1} = Q_{2} = 1, Q_{3} = 2,
P_{n} = P_{n−1} + P_{n−2} + P_{n−3} + P_{n−4} + P_{n−5},  P_{0} = 0, P_{1} = P_{2} = 1, P_{3} = 2, P_{4} = 4.

Let F (x), T (x), Q(x), and P (x) denote the ordinary generating functions of these sequences, respectively. Hence, we have

F (x) = F^{(2)}(x), T (x) = F^{(3)}(x), Q(x) = F^{(4)}(x) and P (x) = F^{(5)}(x).

These special candidates will be used later to highlight particular cases of the results obtained in this paper.

1.1 Outline of the strategy of proofs

It is difficult to identify an universal approach for proving the identities which we present in the work. This is mainly due to the complexity of the problem, which is built up of at least three dimensions: the general nature of the m-step Fibonacci sequence comprising recurrences of arbitrary high order, the specific type of a convolution, and the number of sequences involved in such a convolution. The interplay between the three dimensions does not allow us to formulate one crucial observation from which all other results would follow. Nevertheless, some general ideas can be communicated which are valid for all the convolutions under consideration, both in the case of convolution of two sequences and in the case of convolution of more than two sequences.

The basis of our idea is the manipulation of generating functions to the extent that the relevant functional equations can be written down. In such equations, one component will contain the product of the generating functions of all the sequences under consideration, while the other components will contain the products of the smaller number of sequences under consideration. To give an explicit example, a convolution consisting of three sequences will be expressed as a combination of convolutions involving two of these sequences and “lower terms”. The foundation of our method is to indicate the appropriate elementary manipulations, which usually begin with a transformation of the relevant polynomial occurring in the denominator of the generating function of the sequence in question.

The next step is to use the functional equations and proceed to the power series, from which we will obtain identities expressed in the language of the sequences and their terms. Finally, we will make use of such identities by performing further manipulations (often using recursion of one of the sequences) to extract the final explicit formula. The explicit formula, in its best possible form, should contain on one side of the equality sign the convolution of the selected sequences, and on the other side an expression that is linearly dependent only on certain expressions of the sequences considered.

2 General convolution identities with the Fibonacci mstep numbers

This section contains general formulas for the Fibonacci m-step numbers. We consider several forms of formulas. First, we investigate convolutions of F_{n}^{(m)} with F_{n}^{(m′)} for m ≠ m′. Then we show a few somewhat curious identities with convolutions exhibiting what we call a “switch effect”. One such convolution is

∑_{j=0}^{n} F_{j}(T_{n−j} − Q_{n−j}) = ∑_{j=0}^{n−1} (F_{j} − T_{j})Q_{n−1−j},

where “switching” refers to “switch the parentheses”. Finally, we consider convolutions whose steps differ by 2.

2.1 Mixed convolution

Theorem 1. For all n ≥ m, we have

∑_{j=0}^{n−m} F_{j}^{(m)}F_{n−m−j}^{(m+1)} = F_{n}^{(m+1)} − F_{n}^{(m)}.  (4)

Proof. Notice that

1 − x − x^{2} − ⋯ − x^{m} = \frac{x}{F^{(m)}(x)}.

Subtracting x^{m+1} and rearranging we obtain

1 − x − x^{2} − ⋯ − x^{m} − x^{m+1} = \frac{x − x^{m+1}F^{(m)}(x)}{F^{(m)}(x)},

and thus

\frac{F^{(m)}(x)}{x − x^{m+1}F^{(m)}(x)} = \frac{F^{(m+1)}(x)}{x}.

This gives

F^{(m+1)}(x) − F^{(m)}(x) = x^{m}F^{(m)}(x)F^{(m+1)}(x)  (5)

or

∑_{n=0}^{∞}(F_{n}^{(m+1)} − F_{n}^{(m)})x^{n} = x^{m}( ∑_{n=0}^{∞} F_{n}^{(m)}x^{n})( ∑_{n=0}^{∞} F_{n}^{(m+1)}x^{n})

= ∑_{n=0}^{∞} ∑_{j=0}^{n} F_{j}^{(m)}F_{n−j}^{(m+1)}x^{n+m}

= ∑_{n=m}^{∞} ∑_{j=0}^{n−m} F_{j}^{(m)}F_{n−m−j}^{(m+1)}x^{n}.

This proves the theorem, since for all n < m we have

∑_{j=0}^{n−m} F_{j}^{m}F_{n−m−j}^{m+1} = 0 and F_{n}^{m+1} − F_{n}^{m} = 0.

As a corollary, we obtain Theorem 2.1 from [6] (identity (6) below) and many more. Corollary 2. Let n ≥ 0 be an integer. Then

∑_{j=0}^{n} F_{j}T_{n−j} = T_{n+2} − F_{n+2},  (6)
∑_{j=0}^{n} T_{j}Q_{n−j} = Q_{n+3} − T_{n+3},  (7)
∑_{j=0}^{n} Q_{j}P_{n−j} = P_{n+4} − Q_{n+4}.  (8)

Proof. Set m = 2, m = 3, and m = 4, in turn, in Theorem 1.

It is interesting that Theorem 1 can be generalized further. Theorem 3. Let p ≥ 0 be an integer. For all n ≥ m we have the identity

∑_{k=0}^{p−1} ∑_{j=0}^{n−m−k} F_{j}^{(m)}F_{n−m−k−j}^{(m+p)} = F_{n}^{(m+p)} − F_{n}^{(m)}.  (9)

Proof. This follows from the relation

\frac{x}{F^{(m+p)}(x)} = \frac{x − ( ∑_{k=1}^{p} x^{m+k})F^{(m)}(x)}{F^{(m)}(x)}

or equivalently

F^{(m+p)}(x) − F^{(m)}(x) = ( ∑_{k=1}^{p} x^{m+k−1})F^{(m)}(x)F^{(m+p)}(x).

The remaining part of the proof is similar to the proof of Theorem 1.

When p = 1 then we get Theorem 1. When p = 2 then we get the following. Corollary 4. For all n ≥ m we have the following identity

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

Corollary 4 allows one to obtain many different identities involving convolutions of two sequences. We give the following two examples.

Example 5. Set m = 1 in Corollary 4 to get

T_{n} − 1 = ∑_{j=0}^{n−2} T_{j} + ∑_{j=0}^{n−3} T_{j} = 2 ∑_{j=0}^{n−3} T_{j} + T_{n−2}.

This gives (after replacing n by n + 3)

∑_{j=0}^{n} T_{j} = \frac{1}{2}(T_{n+3} − T_{n+1} − 1) = \frac{1}{2}(T_{n+2} + T_{n} − 1),  (10)

which is a well-known partial sum formula (see, for example, [1, 7, 11]).

Example 6. For any n ≥ 0 we have

∑_{j=0}^{n} F_{j+2}Q_{n−j} = Q_{n+3} − F_{n+3}.  (11)

This follows from setting m = 2 in Corollary 4 and calculating

Q_{n} − F_{n} = ∑_{j=0}^{n−3} F_{j}(Q_{n−2−j} + Q_{n−3−j})

= ∑_{j=0}^{n−4} F_{j+1}Q_{n−3−j} + ∑_{j=0}^{n−3} F_{j}Q_{n−3−j}

= ∑_{j=0}^{n−3} F_{j+2}Q_{n−3−j}.

Finally, we point out that when m = 1 in Theorem 3 then we get the partial sum formula for the Fibonacci m-step numbers.

Corollary 7. For any n ≥ p,

F_{n}^{(p+1)} − 1 = ∑_{k=0}^{p−1} ∑_{j=0}^{n−2−k} F_{j}^{(p+1)}.  (12)

In fact, rewriting (12) in a slightly more convenient way we can get the following general identity.

Theorem 8 (Partial sum formula for the Fibonacci m-step numbers). For any m ≥ 2 we have

∑_{k=0}^{n} F_{k}^{(m)} = \frac{1}{m − 1} (F_{n+m}^{(m)} − ∑_{k=1}^{m−2} kF_{n+k}^{(m)} − 1) .  (13)

Proof. Substitute p + 1 → m in (12) to get

F_{n}^{(m)} − 1 = ∑_{k=0}^{m−2} ∑_{j=0}^{n−2−k} F_{j}^{(m)}

= ∑_{k=0}^{n−m} F_{k}^{(m)} + ∑_{k=n−m+1}^{n−2} F_{k}^{(m)}

+ ∑_{k=0}^{n−m} F_{k}^{(m)} + ∑_{k=n−m+1}^{n−3} F_{k}^{(m)}

⋮

+ ∑_{k=0}^{n−m} F_{k}^{(m)} + F_{n−m+1}^{(m)}

+ ∑_{k=0}^{n−m} F_{k}^{(m)}

= (m − 1) ∑_{k=0}^{n−m} F_{k}^{(m)} + ∑_{k=1}^{m−2} kF_{n−m+k}^{(m)}.

Substituting n → n + m and rearranging the terms leads to the desired formula.

We note that Theorem 8 is not new. For instance, in [18] the partial sum formula is proved using induction but the proof is two pages long. A shorter proof of an equivalent version of the partial sum formula is given by Dresden and Wang in [3]. The second author has recently shown a proof without words of this identity in [11]. Here, we obtained it as a corollary of a more general result.

We have seen from (11) that it is possible to derive a formula for the convolution of the Fibonacci and Tetranacci numbers. In the following, we gather all closed formulas for mixed convolutions of two Fibonacci m-step numbers with 2 ≤ m ≤ 5, that are not present in Corollary 2.

Corollary 9. Let n ≥ 0 be an integer. Then

∑_{j=0}^{n} F_{j}Q_{n−j} = Q_{n+1} + Q_{n−1} − F_{n+1},  (14)

∑_{j=0}^{n} F_{j}P_{n−j} = \frac{1}{2}(P_{n+2} + P_{n−1} − F_{n+2}),  (15)

∑_{j=0}^{n} P_{j}T_{n−j} = \frac{1}{2}(P_{n+3} + P_{n+1} + P_{n−1} − T_{n+3} − T_{n+1}).  (16)

Proof. Identity (14) follows from (11) after fixing the summation range. To show (15) we use Theorem 3 with m = 2 and p = 3, and perform some easy algebraic manipulations. To show (16) we use Theorem 3 with p = 2 and m = 3, and we get

P_{n} − T_{n} = ∑_{j=0}^{n−4} P_{j}(T_{n−3−j} + T_{n−4−j}).  (17)

Then, using (17) twice, second time with n + 2 in place of n, and adding up we get after rearranging the terms,

P_{n+2} + P_{n} − T_{n+2} − T_{n} = 2 ∑_{j=0}^{n−4} P_{j}T_{n−1−j} + 2P_{n−3} + P_{n−2}.

Finally, notice that

∑_{j=0}^{n−4} P_{j}T_{n−1−j} = ∑_{j=0}^{n−1} P_{j}T_{n−1−j} − P_{n−2} − P_{n−3},

which gives

∑_{j=0}^{n−1} P_{j}T_{n−1−j} = \frac{1}{2}(P_{n+2} + P_{n} + P_{n−2} − T_{n+2} − T_{n}).

This implies (16).

The method used to obtain identities (15) and (16) will be explored in the general case in Section 4.

2.2 Mixed convolutions with the “switch effect”

In the following theorem we show a convolution-type formula whereby switching the place of parentheses and the minus sign with minor adjustment of indices, we obtain the equality. It is also important to mention that the formula has an interesting connection to convolution sums of three sequences. The connection will be established in the next two sections.

Theorem 10. For all n ≥ 1 and m ≥ 3 we have

∑_{j=0}^{n} F_{j}^{(m−2)}(F_{n−j}^{(m)} − F_{n−j}^{(m−1)}) = ∑_{j=0}^{n−1} F_{j}^{(m)}(F_{n−1−j}^{(m−1)} − F_{n−1−j}^{(m−2)}).

Proof. Since

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

it follows that

\frac{1}{F^{(m)}(x)} = \frac{1}{F^{(m−1)}(x)} − \frac{x}{F^{(m−2)}(x)} + \frac{x}{F^{(m−1)}(x)}

or equivalently

F^{(m−2)}(x)(F^{(m)}(x) − F^{(m−1)}(x)) = xF^{(m)}(x)(F^{(m−1)}(x) − F^{(m−2)}(x)).

Passing to the power series and comparing coefficients of x^{n} we obtain the identity.

The next corollary is again a rediscovery of Theorem 2.1 in [6]. Corollary 11. For all n ≥ 1 we have

T_{n+1} − F_{n+1} = ∑_{j=0}^{n−1} T_{j}F_{n−1−j}.

Furthermore, for all n ≥ 1 we also have

∑_{j=0}^{n} F_{j}(T_{n−j} − Q_{n−j}) = ∑_{j=0}^{n−1} (F_{j} − T_{j})Q_{n−1−j}

and

∑_{j=0}^{n} T_{j}(Q_{n−j} − P_{n−j}) = ∑_{j=0}^{n−1} (T_{j} − Q_{j})P_{n−1−j}.  (18)

Proof. Set m = 3 in Theorem 10 and simplify using equation (10) and

∑_{j=0}^{n} F_{j} = F_{n+2} − 1.

This gives the first identity. To get the remaining two identities, set m = 4 and m = 5, in turn, in Theorem 10 and simplify.

It is also possible to obtain the “switch” effect in the following sense.

Theorem 12. For all m, n ≥ 2 we have

∑_{j=0}^{n} F_{j}^{(m−1)}F_{n−j}^{(m)} = ∑_{j=0}^{n−2} 2^{j}(F_{n−1−j}^{(m−1)} − F_{n−2−j}^{(m)}).

Proof. The relation

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

translates to

\frac{1}{F^{(m)}(x)} = \frac{1}{P_{2}(x)} + \frac{x}{F^{(m−1)}(x)}

with

P_{2}(x) = \frac{x}{1 − 2x} = x ∑_{n=0}^{∞} 2^{n}x^{n}.

This gives

P_{2}(x)F^{(m−1)}(x) = F^{(m)}(x)F^{(m−1)}(x) + xP_{2}(x)F^{(m)}(x).

Passing to the power series and comparing coefficients of x^{n} we obtain the identity.

Corollary 13. For all n ≥ 0,

∑_{j=0}^{n} 2^{j}F_{n−j} = 2^{n+1} − F_{n+3},  (19)

∑_{j=0}^{n} 2^{j}(F_{n+1−j} − T_{n−j}) = T_{n+4} − F_{n+4},  (20)

∑_{j=0}^{n} 2^{j}T_{n−j} = 2^{n+2} − T_{n+4},  (21)

∑_{j=0}^{n+2} T_{j}Q_{n−j} = ∑_{j=0}^{n} 2^{j}(T_{n+1−j} − Q_{n−j}).  (22)

Proof. Set m = 2 in Theorem 12, simplify, and replace n by n + 2. This shows (19). To get (20), set m = 3 in Theorem 12, use Corollary 11, and replace n by n + 2. The identity (21) follows from combining (19) with (20). Finally, set m = 4 in Theorem 12, and replace n by n + 2 to obtain (22).

Identities (19) and (21) can be generalized for Fibonacci m-step numbers as is seen in the next theorem.

Theorem 14. For all n ≥ 0 and m ≥ 1

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

Proof. We use induction on m. The statement is true for m = 1 and m = 2. Assume the identity is true for a fixed m − 1 > 2 (and all n). Replacing n by n + 2 in Theorem 12 yields

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

But from Theorem 1 upon making the replacement n ↦ n + 2 + m we get

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

and upon making the replacement m ↦ m − 1 we eventually get

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

From here using the inductive hypothesis we can calculate

∑_{j=0}^{n} 2^{j}F_{n−j}^{(m)} = ∑_{j=0}^{n} 2^{j}F_{n+1−j}^{(m−1)} − F_{n+1+m}^{(m)} + F_{n+1+m}^{(m−1)}

= ∑_{j=0}^{n+1} 2^{j}F_{n+1−j}^{(m−1)} − F_{n+1+m}^{(m)} + F_{n+1+m}^{(m−1)}

= 2^{n+1−1+(m−1)} − F_{n+1+1+(m−1)}^{(m−1)} − F_{n+1+m}^{(m)} + F_{n+1+m}^{(m−1)}

= 2^{n−1+m} − F_{n+1+m}^{(m)}.

2.3 Three other general identities

The next convolution identities involve an alternating sum. They all share the same structure; we convolve two sequences with indices m that differ by 2.

Theorem 15. For any n ≥ 2m − 1 we have

∑_{j=0}^{n−1}(−1)^{j}(F_{j}^{(2m)} − F_{j}^{(2m−2)}) = (−1)^{n+1} ∑_{j=0}^{n−2m+1} F_{j}^{(2m)}F_{n−2m+1−j}^{(2m−2)}.  (23)

Proof. As 1 + x − x^{2} + x^{3} ∓ ⋯ − x^{2(m−1)} + x^{2m−1} − x^{2m} = 1 + x − x^{2} + x^{3} ∓ ⋯ − x^{2(m−1)} + x^{2m−1}(1 − x), we obtain the functional equation

\frac{1}{F^{(2m)}(−x)} = \frac{1}{F^{(2m−2)}(−x)} − x^{2m−1} \frac{1}{F^{(1)}(x)}

or equivalently (F^{(2m)}(−x) − F^{(2m−2)}(−x))F^{(1)}(x) = x^{2m−1}F^{(2m)}(−x)F^{(2m−2)}(−x).

As a corollary, we can give a different proof of identity (14). Corollary 16. For any n ≥ 0 we have

∑_{j=0}^{n} F_{j}Q_{n−j} = Q_{n+1} + Q_{n−1} − F_{n+1}.  (24)

Proof. Set m = 2 in Theorem 15 and use

∑_{j=0}^{n}(−1)^{j}F_{j} = (−1)^{n}F_{n−1} − 1

as well as [20]

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

These results produce

∑_{j=0}^{n−3} F_{j}Q_{n−3−j} = Q_{n+2} − 2Q_{n+1} + Q_{n} − Q_{n−1} − F_{n−2},

and the statement follows upon replacing n by n + 3 and simplifying.

The companion result for Theorem 15 for the Fibonacci m-step numbers with odd m is stated next. Theorem 17. For any n ≥ 2m we have

∑_{j=0}^{n−1}(−1)^{j+1}(F_{j}^{(2m+1)} − F_{j}^{(2m−1)}) = (−1)^{n} ∑_{j=0}^{n−2m} F_{j}^{(2m+1)}F_{n−2m−j}^{(2m−1)}.  (25)

Proof. This result follows from the functional equation

\frac{1}{F^{(2m+1)}(−x)} = \frac{1}{F^{(2m−1)}(−x)} + x^{2m} \frac{1}{F^{(1)}(x)}.

We proceed with two corollaries. The first identity is known (see for instance Equation (18) in [7]), the second identity is a rediscovery of (16) with a slightly different (but equivalent) right-hand side.

Corollary 18. For any n ≥ 0 we have

∑_{j=0}^{n}(−1)^{j}T_{j} = \frac{1}{2}((−1)^{n}(T_{n+1} − T_{n−1}) − 1)

and

∑_{j=0}^{n} P_{j}T_{n−j} = \frac{1}{2}(−P_{n+7} + 2P_{n+6} − P_{n+5} + 2P_{n+4} + P_{n+3} − T_{n+4} + T_{n+2}).

Proof. Set m = 1 in Theorem 17 and simplify to get the first identity. For the second identity, set m = 2 in Theorem 17 and simplify while making use of (see [21])

∑_{j=0}^{n}(−1)^{j}P_{j} = \frac{1}{2}((−1)^{n}(−P_{n+4} + 2P_{n+3} − P_{n+2} + 2P_{n+1} + P_{n}) − 1).

We conclude this section with the remark that identities involving Fibonacci m-step numbers and other important number sequences can be obtained fairly easily using the generating function approach. We give an example involving Jacobsthal numbers, which is related to identity (1).

Theorem 19. Let J_{n} be the Jacobsthal numbers, i.e., J_{0} = 0, J_{1} = 1, and J_{n+2} = J_{n+1} +2J_{n}. Then, for m ≥ 3 and any n ≥ 2 we have

∑_{j=0}^{n} F_{j}^{(m)}F_{n−j}^{(m−2)} = J_{n−1} + ∑_{j=0}^{n−2} J_{j}(F_{n−j}^{(m−2)} − F_{n−2−j}^{(m)}).  (26)

Proof. We have

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

which implies

\frac{x}{F^{(m)}(x)} = \frac{x}{J(x)} + \frac{x^{3}}{F^{(m−2)}(x)},

where J(x) = \frac{x}{1−x−2x^{2}} is the ordinary generating function for Jacobsthal numbers.

Corollary 20. For any n ≥ 0 we have

∑_{j=0}^{n} J_{j}T_{n−j} = J_{n+1} + \frac{1}{2}(J_{n+2} − T_{n+3} − T_{n+1}).

Proof. Use the previous theorem with m = 3 in conjunction with (10) and

∑_{j=0}^{n} J_{j} = \frac{1}{2}(J_{n+2} − 1).

3 Convolutions of multiple sequences

The main goal of this section is to derive convolution identities of three and more Fibonacci m-step sequences. For convenience, we introduce the following notation:

K(ℓ, b) = {(k_{1}, …, k_{ℓ}) ∈ ℤ_{≥0}^{ℓ}: k_{1} + ⋯ + k_{ℓ} = b}.

Before providing an analysis of the m-step sequences, we present a result for the Pell sequence. Then we consider a general convolution of three Fibonacci m-step sequences and derive all mixed convolutions with 2 ≤ m ≤ 5. Finally, we delve into the convolution of four sequences.

3.1 A Pell-Fibonacci relation

Theorem 21. Let P_{n} be the Pell numbers, i.e., P_{0} = 0, P_{1} = 1, and P_{n+2} = 2P_{n+1} + P_{n}. Then, for all n ≥ 1 and m ≥ 2 we have the following Pell-Fibonacci-m-step-relation:

∑_{K(3,n−1)} P_{k_{1}}F_{k_{2}}^{(m−1)}F_{k_{3}}^{(m)} = ∑_{j=0}^{n} F_{j}^{(m−1)} (P_{n−j} − F_{n−j}^{(m)}) − ∑_{j=0}^{n−1} P_{j}F_{n−1−j}^{(m)}.

Proof. Let P(x) = \frac{x}{1−2x−x^{2}} denote the generating function for the Pell numbers. From

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

we get

\frac{1}{F^{(m)}(x)} = \frac{1}{P(x)} + x\frac{F^{(m−1)}(x) + 1}{F^{(m−1)}(x)},

or

xP(x)F^{(m−1)}(x)F^{(m)}(x) = F^{(m−1)}(x) (P(x) − F^{(m)}(x)) − xP(x)F^{(m)}(x).

The result follows upon passing to power series and comparing the coefficients of x^{n}.

As a first corollary, we rediscover identity (3). Corollary 22. For any n ≥ 0 we have

∑_{j=0}^{n} P_{j}F_{n−j} = P_{n} − F_{n}.

Proof. Set m = 2 in Theorem 21 and simplify. Corollary 23. For any n ≥ 0 we have

∑_{K(3,n)} P_{k_{1}}F_{k_{2}}T_{k_{3}} = P_{n+1} + F_{n+2} − T_{n+3} − ∑_{j=0}^{n} P_{j}T_{n−j}.

or

∑_{K(3,n)} P_{k_{1}}F_{k_{2}}T_{k_{3}} = \frac{1}{2} (P_{n+1} − T_{n+3} − T_{n+2}) + F_{n+2}.  (27)

Proof. Set m = 3 in Theorem 21, use (2) and (3), and simplify. To get (27), let R(x) = \frac{x}{1−x^{2}} and notice that

\frac{1}{T (x)} = \frac{1}{P(x)} + x · \frac{1}{R(x)},

which is equivalent to

xP(x)T (x) = R(x)(P(x) − T (x)).

Using

R(x) = \frac{x}{2} (\frac{1}{1 − x} + \frac{1}{1 + x})

and passing to power series, we get

∑_{j=0}^{n} P_{j}T_{n−j} = \frac{1}{2} ∑_{j=0}^{n} P_{j} + \frac{1}{2} ∑_{j=0}^{n}(−1)^{n−j}P_{j} − \frac{1}{2} ∑_{j=0}^{n} T_{j} − \frac{1}{2} ∑_{j=0}^{n}(−1)^{n−j}T_{j}.

Recall the well-known identities for Pell numbers (see for example [2]):

∑_{j=0}^{n} P_{j} = \frac{1}{2} (P_{n+1} + P_{n} − 1) and ∑_{j=0}^{n}(−1)^{j}P_{j} = \frac{1}{2} ((−1)^{n}(P_{n+1} − P_{n}) − 1) .

These relations show that

∑_{j=0}^{n} P_{j}T_{n−j} = \frac{1}{2} (P_{n+1} − T_{n+1} − T_{n})

and (27) follows.

From

P(x)F (x) = P(x) − F (x),

we get (by induction) for all r ≥ 1

P(x)F^{r}(x) = P(x) − ∑_{s=1}^{r} F^{s}(x),

or equivalently

∑_{K(r+1,n)} P_{k_{1}}F_{k_{2}}F_{k_{3}} ⋯ F_{k_{r+1}} = P_{n} − ∑_{s=1}^{r} ∑_{K(s,n)} F_{k_{1}} ⋯ F_{k_{s}}.

Special cases of this convolution include (see Zhang’s paper [22] for the Fibonacci convolutions)

∑_{K(3,n)} P_{k_{1}}F_{k_{2}}F_{k_{3}} = P_{n} − F_{n} − \frac{1}{5} ((n − 1)F_{n} + 2nF_{n−1}) (n ≥ 1)

as well as

∑_{K(4,n)} P_{k_{1}}F_{k_{2}}F_{k_{3}}F_{k_{4}} = P_{n} − F_{n} − \frac{1}{5} ((n − 1)F_{n} + 2nF_{n−1})

− \frac{1}{50} ((5n^{2} − 9n − 2)F_{n−1} + (5n^{2} − 3n − 2)F_{n−2}) (n ≥ 2). (28)

3.2 Convolution of three Fibonacci m-step sequences

The next theorem is the most important observation in this paper. We will use it to support some of the observations that follow.

Theorem 24. Let m, p, q ≥ 1 be integers. Then the following functional identity holds true:

x^{2m+p}(1 − x^{p})(1 − x^{q})F^{(m)}(x)F^{(m+p)}(x)F^{(m+p+q)}(x)
= x^{m}(1 − x)(1 − x^{p})F^{(m)}(x)F^{(m+p+q)}(x) − (1 − x)^{2}(F^{(m+p)}(x) − F^{(m)}(x)). (29)

In particular,

x^{2m+1}F^{(m)}(x)F^{(m+1)}(x)F^{(m+2)}(x) = x^{m}F^{(m)}(x)F^{(m+2)}(x) − F^{(m+1)}(x) + F^{(m)}(x). (30)

Proof. We utilize the proof of Theorem 3 and work with the identity:

F^{(a+b)}(x) − F^{(a)}(x) = (∑_{k=0}^{b−1} x^{a+k}) F^{(a)}(x)F^{(a+b)}(x).  (31)

Applying it in two different ways we get:

F^{(m+p)}(x) = \frac{F^{(m)}(x)}{1 − (∑_{k=0}^{p−1} x^{m+k}) F^{(m)}(x)},
F^{(m+p+q)}(x) − F^{(m+p)}(x) = (∑_{k=0}^{q−1} x^{m+p+k}) F^{(m+p)}(x)F^{(m+p+q)}(x).  (32)

Hence, we obtain

F^{(m+p+q)}(x) − \frac{F^{(m)}(x)}{1 − (∑_{k=0}^{p−1} x^{m+k}) F^{(m)}(x)} = (∑_{k=0}^{q−1} x^{m+p+k}) F^{(m+p)}(x)F^{(m+p+q)}(x),

or, after rearranging,

(∑_{k=0}^{p−1} x^{m+k}) (∑_{k=0}^{q−1} x^{m+p+k}) F^{(m)}(x)F^{(m+p)}(x)F^{(m+p+q)}(x)

= (∑_{k=0}^{q−1} x^{m+p+k}) F^{(m+p)}(x)F^{(m+p+q)}(x)

+ (∑_{k=0}^{p−1} x^{m+k}) F^{(m)}(x)F^{(m+p+q)}(x) − F^{(m+p+q)}(x) + F^{(m)}(x).

Simplifying using (32) yields

(∑_{k=0}^{p−1} x^{m+k}) (∑_{k=0}^{q−1} x^{m+p+k}) F^{(m)}(x)F^{(m+p)}(x)F^{(m+p+q)}(x)

= (∑_{k=0}^{p−1} x^{m+k}) F^{(m)}(x)F^{(m+p+q)}(x) − F^{(m+p)}(x) + F^{(m)}(x).

Finally, from the geometric series

(∑_{k=0}^{p−1} x^{m+k}) (∑_{k=0}^{q−1} x^{m+p+k}) = x^{2m+p} \frac{(1 − x^{p})(1 − x^{q})}{(1 − x)^{2}}, ∑_{k=0}^{p−1} x^{m+k} = x^{m} \frac{1 − x^{p}}{1 − x}

and the functional equation follows. The particular case belongs to p = q = 1.

The special case of Theorem 24 leads to yet another identity involving triple convolutions; namely the following result.

Theorem 25. For any p ≥ 1 and any m ≥ 1 we have

x^{m}F^{(m)}(x)F^{(m+1)}(x)F^{(p)}(x) = F^{(p)}(x)F^{(m+1)}(x) − F^{(p)}(x)F^{(m)}(x).

In particular,

∑_{K(3,n−m)} F_{k_{1}}^{(m)}F_{k_{2}}^{(m+1)}F_{k_{3}}^{(p)} = ∑_{j=0}^{n} F_{j}^{(p)}F_{n−j}^{(m+1)} − ∑_{j=0}^{n} F_{j}^{(p)}F_{n−j}^{(m)}.

Proof. Use identity (31).

We apply Theorem 24 with m = 2 and p = q = 1. This choice results in several different functional equations, one coming directly from the theorem.

x^{5}F (x)T (x)Q(x) = x^{2}F (x)x^{3}T (x)Q(x)
= x^{2}F (x)(Q(x) − T (x))
= x^{2}F (x)Q(x) − T (x) + F (x)
= x^{2}F (x)Q(x) + x^{3}T (x)Q(x) − Q(x) + F (x).

Theorem 26. We have for each n ≥ 0,

∑_{K(3,n)} F_{k_{1}}T_{k_{2}}Q_{k_{3}} = Q_{n+4} + Q_{n+2} − T_{n+5} + F_{n+3}.  (33)

Proof. Work with

x^{5}F (x)T (x)Q(x) = x^{2}F (x)Q(x) − T (x) + F (x).

When passing to the power series and comparing the coefficients of x^{n} use the identity (14) and simplify.

Working with m = 3 and p = q = 1 in Theorem 24 results in the functional equations, where again, one comes from the theorem.

x^{7}T (x)Q(x)P (x) = x^{3}T (x)x^{4}Q(x)P (x)
= x^{3}T (x)(P (x) − Q(x))
= x^{3}T (x)P (x) − Q(x) + T (x)
= x^{3}T (x)P (x) + x^{4}P (x)Q(x) − P (x) + T (x),

and this gives the next convolution.

Theorem 27. We have

∑_{K(3,n−7)} T_{k_{1}}Q_{k_{2}}P_{k_{3}} = \frac{1}{2}(P_{n} + P_{n−2} + P_{n−4} + T_{n} − T_{n−2}) − Q_{n}

valid for each n ≥ 7.

Proof. Using the identity

x^{7}T (x)Q(x)P (x) = x^{3}T (x)P (x) − Q(x) + T (x)

in conjunction with (16) we obtain, after minor simplification, the desired result.

In the following two results we find convolution sums of the remaining triples with 2 ≤ m ≤ 5 using Theorem 25.

Theorem 28. We have the following identity:

∑_{K(3,n−5)} F_{k_{1}}Q_{k_{2}}P_{k_{3}} = −Q_{n} − Q_{n−2} + \frac{1}{2}(P_{n+1} + P_{n−2} − F_{n+1}) + F_{n}.  (34)

Proof. Use Theorem 25 with m = 4 and p = 2, pass to power series, apply (14) and (15), and simplify.

Theorem 29. We have the following identity:

∑_{K(3,n−5)} F_{k_{1}}T_{k_{2}}P_{k_{3}} = \frac{1}{2}(P_{n} − P_{n−1} + P_{n−2} − T_{n} − T_{n−2} + F_{n−1}).

Proof. Use Theorem 25 with m = 2 and p = 5, pass to power series, apply (15) and (16), and simplify.

In the proofs of Theorem 28 and Theorem 29 we used a different approach. Instead of utilizing Theorem 24, we applied Theorem 25. This is necessary here, since, otherwise, the obtained formula would produce an identity with multiple triple convolution terms instead of one.

We finish this part of the article by showing that one can use a completely different approach to prove the results in this section. Namely, we can deduce the fundamental functional equations from other relations of the respective generating functions. Remark 30. Notice that one can prove Theorem 28 and Theorem 29 using other transformations of generating functions. For the first theorem, we can use the following identities:

P (x) − Q(x) = x^{4}P (x)Q(x) and Q(x) = \frac{F (x)}{1 + x^{2} − xF (x)},

where the formula for Q is substituted to the right-hand-side presence of Q in the first identity. For the second theorem, we start from the identity

\frac{x}{P (x)} = \frac{x}{F (x)} + \frac{x^{4}}{F (x)} − 2x^{3}

to obtain

P (x) − F (x) = 2x^{2}F (x)P (x) − x^{3}P (x).  (35)

Then we substitute F (x) = \frac{T (x)}{1+x^{2}T (x)} and obtain a functional equation.

3.3 Convolutions of four Fibonacci m-step sequences

The functional equations from Theorem 24 (as well as any other functional equations derived in this paper) can be multiplied by arbitrary F^{(r)}(x) or even by any product of the form

∏_{u=1}^{N} (F^{(r_{u})}(x))^{s_{u}} , s_{1}, …, s_{N}, r_{1}, …, r_{N} positive integers.

In particular cases these functional equations can be used for a different proof of Theorems 26–29. For example, using (30) we immediately get the following.

Theorem 31. For any m ≥ 1 we have

x^{2m+1}F^{(m)}(x)F^{(m+1)}(x)F^{(m+2)}(x)F^{(m+3)}(x)

= x^{m}F^{(m)}(x)F^{(m+2)}(x)F^{(m+3)}(x) − F^{(m+1)}(x)F^{(m+3)}(x) + F^{(m)}(x)F^{(m+3)}(x). (36)

This theorem implies a particular closed formula for the convolution of the Fibonacci, Tribonacci, Tetranacci, and Pentanacci numbers.

Theorem 32. We have

∑_{K(4,n−5)} F_{k_{1}}T_{k_{2}}Q_{k_{3}}P_{k_{4}} = \frac{1}{2}(P_{n+4} − P_{n+3} + P_{n+2} + T_{n+3} + T_{n+1} − F_{n}) − Q_{n+3} − Q_{n+1}.

Proof. Set m = 2 in Equation (36) to get

x^{5}F (x)T (x)Q(x)P (x) = x^{2}F (x)Q(x)P (x) − T (x)P (x) + F (x)P (x).

Pass to power series, use (34), (16) and (15), and simplify.

Remark 33. We note that identity (36) can be (after multiplication by x^{2}) further simplified using Theorem 25 so that the right-hand-side contains convolution sums of two sequences.

Other interesting identities involving the Fibonacci, Tribonacci, Tetranacci, and Pentanacci numbers can be derived. In particular, the following holds true:

x^{4}F (x)T (x)Q(x)P (x) = F (x)T (x)x^{4}Q(x)P (x)
= F (x)T (x)(P (x) − Q(x))
= F (x)T (x)P (x) − xF (x)T (x)Q(x),

or

x^{6}F (x)T (x)Q(x)P (x) = x^{2}F (x)T (x)x^{4}Q(x)P (x) = (T (x) − F (x))(P (x) − Q(x)). (37)

The last identity leads to the following surprising identity.

Theorem 34. For any m ≥ 1 we have

∑_{K(4,n−2m−2)} F_{k_{1}}^{(m)}F_{k_{2}}^{(m+1)}F_{k_{3}}^{(m+2)}F_{k_{3}}^{(m+3)} = ∑_{j=0}^{n} (F_{j}^{(m+3)} − F_{j}^{(m+2)})(F_{n−j}^{(m+1)} − F_{n−j}^{(m)}).

Proof. Following identity (37) and using (5) we have

x^{2m+2}F^{(m)}(x)F^{(m+1)}(x)F^{(m+2)}(x)F^{(m+3)}(x)
= (x^{m}F^{(m)}(x)F^{(m+1)}(x))(x^{m+2}F^{(m+2)}(x)F^{(m+3)}(x))
= (F^{(m+1)}(x) − F^{(m)}(x))(F^{(m+1)}(x) − F^{(m)}(x)),

and the identity follows after passing to power series.

4 Concluding results and comments

4.1 Higher order convolutions

We can derive identities for higher order convolutions by mimicking the argument made at the end of the previous section. For instance, Theorem 34 has the following generalization.

Theorem 35. Fix ℓ ≥ 1 and an integer m ≥ 1. Then

∑_{K(2ℓ,n−ℓ(m+ℓ−1))} ∏_{j=0}^{2ℓ−1} F_{k_{j+1}}^{(m+j)} = ∑_{K(ℓ,n)} ∏_{j=0}^{ℓ−1} (F_{k_{j}}^{(m+2j+1)} − F_{k_{j}}^{(m+2j)})  (38)

and

∑_{K(2ℓ+1,n−ℓ(m+ℓ−1))} ∏_{j=0}^{2ℓ} F_{k_{j}}^{(m+j)} = ∑_{K(ℓ+1,n)} F_{k_{ℓ+1}}^{(m+2ℓ)} (∏_{j=0}^{ℓ−1} (F_{k_{j}}^{(m+2j+1)} − F_{k_{j}}^{(m+2j)})) .  (39)

Proof. We sketch the proof of (38). Using (31), we can write the following functional equation.

x^{ℓ(m+ℓ−1)}F^{(m)}(x) ⋯ F^{(m+2ℓ−1)}(x)
= (x^{m}F^{(m)}(x)F^{(m+1)}(x)) ⋯ x^{m+2ℓ−2}(x^{m}F^{(m+2ℓ−2)}(x)F^{(m+2ℓ−1)}(x))
= (F^{(m+1)}(x) − F^{(m)}(x)) ⋯ (F^{(m+2ℓ−1)}(x) − F^{(m+2ℓ−2)}(x)).

Passing to power series we obtain the desired formula.

Theorem 35, in particular, allows us to effectively cut off half of the sequences from the initial convolution. For instance, it is sufficient to know the exact formula for the convolution of three among the Fibonacci to Hexanacci and Heptanacci numbers (so 2 ≤ m ≤ 7) in order to determine the expression for the convolution of all of the sequences.

In identity (39) of Theorem 35 the sequence F_{n}^{(m+2ℓ)} does not take a part in reducing the order of convolution. It is clear that another sequence can be distinguished in a similar way. The change results in different summation or product ranges, which are easily adjustable for a specific example. This implies, for instance, the following.

Corollary 36. We have

∑_{K(3,n−2)} F_{k_{1}}T_{k_{2}}Q_{k_{3}} = ∑_{j=0}^{n}(T_{j} − F_{j})Q_{n−j} = ∑_{j=0}^{n+1} F_{n+1−j}(Q_{j} − T_{j}).

The above observation also leads to yet another look at the “switch” effect described in Section 2. This effect turns out to be the two different versions of the simplified convolution sum of three sequences.

Finally, we also note that identities (38) and (39) can be stated in a more general setting; namely, the left-hand-side of either identity can be any finite product of the terms

F_{a}^{(m)}F_{b}^{(m+1)},

even with repetitions, and the general formula can be adjusted for that case as well. We leave the derivation of such a convoluted formula to the reader.

4.2 Some general cases of convolution of two sequences

In Section 2, we derived convolution identities that involve all pairs of sequences up to m = 5. However, following the proof of Corollary 9 we can do more. In fact, we can deliver the general algorithm for finding a simple and closed form of the convolution of F^{(m)} with F^{(m+p)} in the following cases.

Case 1: p | m.

Case 2: p | m + 1.

Case 3: p = 2m + 2.

We start with Case 1. So let m = ℓ · p for some integer ℓ ≥ 1. Applying Theorem 3 we get

F^{((ℓ+1)p)}(x) − F^{(ℓ·p)}(x) = (x^{ℓ·p} + ⋯ + x^{(ℓ+1)p−1}) F^{(ℓ·p)}(x)F^{((ℓ+1)p)}(x).  (40)

Multiplying (40) repeatedly by x^{p} we stack up a total of ℓ equalities:

x^{p}F^{((ℓ+1)p)}(x) − x^{p}F^{(ℓ·p)}(x) = (x^{(ℓ+1)p} + ⋯ + x^{(ℓ+2)p−1}) F^{(ℓ·p)}(x)F^{((ℓ+1)p)}(x),
⋮
x^{(ℓ−1)p}F^{((ℓ+1)p)}(x) − x^{(ℓ−1)p}F^{(ℓ·p)}(x) = (x^{(2ℓ−1)p} + ⋯ + x^{2ℓ·p−1}) F^{(ℓ·p)}(x)F^{((ℓ+1)p)}(x).

Adding everything up we get

∑_{j=0}^{ℓ−1} x^{j·p}(F^{((ℓ+1)p)}(x) − F^{(ℓ·p)}(x)) = (x^{ℓ·p} + ⋯ + x^{2ℓ·p−1}) F^{(ℓ·p)}(x)F^{((ℓ+1)p)}(x).  (41)

In the next part of our computation we use the following convention. Whenever we combine several sums into one with a fixed summation range, the remaining terms that are not included in the combined sum are called other terms and are referred as o.t. Depending in the exact case, these terms can be explicitly derived. We do not do that in the below computation as it makes the formula presented in the algorithm difficult to follow. Thus, only the important terms are explicit.

We go back to (41) and rewrite this in a power series to obtain

∑_{j=0}^{ℓ−1} (F_{n−j·p}^{((ℓ+1)p)} − F_{n−j·p}^{(ℓ·p)}) = ∑_{k=0}^{n−(2ℓ·p−1)} F_{k}^{((ℓ+1)p)} ( ∑_{j=0}^{ℓ·p−1} F_{n−(2ℓ·p−1)−k−j}^{(ℓ·p)}) + o.t.

= ∑_{k=0}^{n−(2ℓ·p−1)} F_{k}^{((ℓ+1)p)}F_{n−(2ℓ·p)−k}^{(ℓ·p)} + o.t.

From this we can derive the closed formula for the desired convolution.

Example 37. Set m = 4, p = 2, and denote s_{n} = F_{n}^{(6)}. It follows that

s_{n−2} − Q_{n−2} + s_{n} − Q_{n} = ∑_{j=0}^{n−7} s_{j}Q_{n−3−j} + o.t.  (42)

It is now easy to find that

o.t. = 2s_{n−6} + s_{n−5},

and this establishes the formula.

Setting m = p = 2 restores (11).

We now move to Case 2: p | m + 1. So, let m = ℓ · p − 1 for some positive integer ℓ. The further reasoning is similar to case p | m. Applying Theorem 3 we get

F^{((ℓ+1)p−1)}(x) − F^{(ℓ·p−1)}(x) = (x^{ℓ·p−1} + ⋯ + x^{(ℓ+1)p−2}) F^{(ℓ·p−1)}(x)F^{((ℓ+1)p−1)}(x). (43)

We multiply (43) again by x^{p} to get

x^{p}F^{((ℓ+1)p−1)}(x) − x^{p}F^{(ℓ·p−1)}(x) = (x^{(ℓ+1)p−1} + ⋯ + x^{(ℓ+2)p−2}) F^{(ℓ·p)}(x)F^{((ℓ+1)p)}(x),
⋮
x^{(ℓ−1)p}F^{((ℓ+1)p−1)}(x) − x^{(ℓ−1)p}F^{(ℓ·p−1)}(x) = (x^{(2ℓ−1)p−1} + ⋯ + x^{2ℓ·p−2}) F^{(ℓ·p−1)}(x)F^{((ℓ+1)p−1)}(x).

Adding everything up and passing to power series, we have

∑_{j=0}^{ℓ−1} (F_{n−j·p}^{((ℓ+1)p−1)} − F_{n−j·p}^{(ℓ·p)−1}) = ∑_{k=0}^{n−(2ℓ·p−2)} F_{k}^{((ℓ+1)p−1)} ( ∑_{j=0}^{ℓ·p−1} F_{n−(2ℓ·p−2)−k−j}^{(ℓ·p−1)}) + o.t.

= 2 ∑_{k=0}^{n−(2ℓ·p−2)} F_{k}^{((ℓ+1)p)−1}F_{n−(2ℓ·p−1)−k}^{(ℓ·p−1)} + o.t.

Example 38. Setting p = 3 and m = 2 we reproduce the proof of (15). Setting p = 2 and m = 3 we reproduce the identity (16).

Finally, consider Case 3 and p = 2m + 2. The key feature of this case is the following simple lemma.

Lemma 39. For any m ≥ 2 and any n ≥ 0 we have

∑_{k=0}^{2m+1} F_{n+k}^{(m)} = 4F_{n+2m}^{(m)}.  (44)

Proof. Write

4F_{n+2m}^{(m)} = (2F_{n+m}^{(m)} + ⋯ + 2F_{n+2m−1}^{(m)}) + 2F_{n+2m}^{(m)}
= 2F_{n+m}^{(m)} + (2F_{n+m+1}^{(m)} + ⋯ + 2F_{n+2m}^{(m)})
= F_{m}^{(m)} + ⋯ + F_{n+m−1}^{(m)} + F_{n+m}^{(m)}
+ F_{n+m+1}^{(m)} + ⋯ + F_{n+2m}^{(m)} + F_{n+2m+1}^{(m)}.

We now apply Theorem 3 to obtain

F^{3m+2}(x) − F^{(m)}(x) = (x^{m} + ⋯ + x^{3m+1})F^{(m)}(x)F^{(3m+2)}(x).

This implies, using (44), that

F_{n}^{(3m+2)} − F_{n}^{(m)} = ∑_{k=0}^{n−(3m+1)} F_{k}^{(3m+2)}(F_{n−(3m−1)−k}^{(m)} + ⋯ + F_{n−m−k}^{(m)}) + o.t.

= 4 ∑_{k=0}^{n−(3m+1)} F_{k}^{(3m+2)}F_{n−m−1−k}^{(m)} + o.t.

Example 40. Set m = 2 and let O = F^{(8)}. Then we have

O_{n} − F_{n} = 4 ∑_{j=0}^{n−7} O_{j}F_{n−3−j} + O_{n−3} + 2O_{n−4} + 4O_{n−5} + 7O_{n−6}

= 4 ∑_{j=0}^{n−3} O_{j}F_{n−3−j} + O_{n−3} − 2O_{n−4} − O_{n−6}.

It follows after some calculation that

∑_{j=0}^{n} O_{k}F_{n−j} = \frac{1}{4} (O_{n+3} − O_{n} + 2O_{n−1} + O_{n−3} − F_{n+3}) .  (45)

The methods provided so far allow us to find a closed form of the convolution of two different sequences out of the set of the Fibonacci, Tribonacci, Tetranacci, and Pentanacci numbers. If we include the Hexanacci numbers (i.e. s = F^{(6)}), then we can compute all convolutions but the convolution of the Fibonacci and Hexanacci numbers. This is at first glance surprising, but in fact the presented algorithm does not allow us to deal with that case, even though we can compute the explicit form of ∑_{j=0}^{n} F_{j}^{(20)}F_{n−j}^{(27)}.

We now show how to find the sum ∑_{j=0}^{n} s_{j}F_{n−j}. In order to deal with this problem, we have to use another approach.

Theorem 41. For n ≥ 3 we have

∑_{j=0}^{n} s_{j}F_{n−j} = \frac{1}{5} (s_{n+3} + s_{n+1} − s_{n} + 3s_{n−1} + s_{n−3} − F_{n+3} − F_{n+1}) .  (46)

Proof. Notice that by (31) or (9) we have

s_{n} − F_{n} = ∑_{j=0}^{n−2} s_{j}F_{n−j−2} + ∑_{j=0}^{n−3} s_{j}F_{n−j−3} + ∑_{j=0}^{n−4} s_{j}F_{n−j−4} + ∑_{j=0}^{n−5} s_{j}F_{n−j−5},

s_{n+2} − F_{n+2} = ∑_{j=0}^{n} s_{j}F_{n−j} + ∑_{j=0}^{n−1} s_{j}F_{n−j−1} + ∑_{j=0}^{n−2} s_{j}F_{n−j−2} + ∑_{j=0}^{n−3} s_{j}F_{n−j−3}.

Summing up and rearranging we get

s_{n+2} − F_{n+2} + s_{n} − F_{n} = ∑_{j=0}^{n−5} s_{j}(F_{n−j−5} + F_{n−j−4} + 2F_{n−j−3} + 2F_{n−j−2} + F_{n−j−1} + F_{n−j})
+ s_{n−1} + 2s_{n−2} + 5s_{n−3} + 9s_{n−4}.

To proceed further, we apply the identity

F_{n} + F_{n+1} + 2F_{n+2} + 2F_{n+3} + F_{n+4} + F_{n+5} = 5F_{n+4}  (47)

valid for any n ≥ 0 and we substitute n → n + 1 to obtain

s_{n+3} − F_{n+3} + s_{n+1} − F_{n+1} = ∑_{j=0}^{n−5} 5s_{j}F_{n−j−1} + s_{n−1} + 2s_{n−2} + 5s_{n−3} + 9s_{n−4}

= 5 ∑_{j=0}^{n} s_{j}F_{n−j} + s_{n} − 3s_{n−1} − s_{n−3}.

Thus, after minor adjustments, we have (46).

We note that there are more cases where an identity similar to (47) leads to a closed sum formula. Namely, if we consider p + m ≤ 8 and let S = F^{(7)} (the Heptanacci numbers), then the only missing cases, not following from the rules described by the three cases, are

∑_{j=0}^{n} S_{j}F_{n−j},  ∑_{j=0}^{n} S_{j}Q_{n−j},  and  ∑_{j=0}^{n} O_{j}T_{n−j}.

These sums can be derived using an approach similar to (46), but this time with the aid of the following identities:

2F_{n} + 2F_{n+1} + 3F_{n+2} + 3F_{n+3} + 3F_{n+4} + F_{n+5} + F_{n+6} = 11F_{n+4}, (48)
Q_{n} + Q_{n+1} + Q_{n+2} + Q_{n+3} + Q_{n+4} + 2Q_{n+5} + 2Q_{n+6} + 2Q_{n+7} + Q_{n+8} = 3Q_{n+8}, (49)
2T_{n} + 2T_{n+1} + 3T_{n+2} + 5T_{n+3} + 5T_{n+4} + 3T_{n+5} + 3T_{n+6} + 2T_{n+7} = 11T_{n+6}. (50)

To clarify how to use them, we write, for example,

Q_{n} + Q_{n+1} + Q_{n+2} + Q_{n+3} + Q_{n+4} + 2Q_{n+5} + 2Q_{n+6} + 2Q_{n+7} + Q_{n+8}
= (Q_{n} + Q_{n+1} + Q_{n+2}) + (Q_{n+3} + Q_{n+4} + Q_{n+5})
+ (Q_{n+5} + Q_{n+6} + Q_{n+7}) + (Q_{n+6} + Q_{n+7} + Q_{n+8})

and it is clear that each bracket can be generated from the identity

S(x) − Q(x) = (x^{4} + x^{5} + x^{6})Q(x)S(x).

4.3 Open problems

In the previous section we presented the algorithm for computation of the convolution sum of two sequences under (major) restrictions. We dealt with the missing case m = 2 and p = 4 separately so that all convolution sums with m + p ≤ 8 for m ≥ 2 and p ≥ 1 have their closed forms calculated. The first case that is not covered by our methods (that is, the case with the smallest possible m + p and the smallest possible p) is the following convolution sum (also see Table 1):

∑_{j=0}^{n} P_{j}F_{n−j}^{(9)}.

The trick that was used above could also work here but this does not replace a general approach to these sums (identities (47)–(50) seem to only work in the presented form, we do not know if/how they generalize, as they were found by trial and error). In our opinion, a good starting point is to search for an identity of the form

∑_{k∈K} ∑_{j=0}^{p−1} F_{n+j+k}^{(m)} = N · F_{n+ℓ}^{(m)}  (51)

valid for any n, m ≥ 2, with N and ℓ being unknown, K being a finite set, ℓ related to n and p. Identity (47) is the case m = 2 and follows that pattern with K = {0, 2}, p = 4, N = 5 and ℓ = 4. The identity (44) is the simplest example of that form, with K = {0}. Any identity of the form (51) would give us yet another convolution sum. We believe that finding any other solution (or even an infinite family of solutions) to that equation is a good motivation for further research in the topic.

\begin{matrix}m \ p & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & (14) & (15) & (46) & (48) & (45) & ? & ? & ? \\ 3 & (16) & p | m & p | m + 1 & (50) & ? & ? & p = 2m + 2 & ? \\ 4 & (42) & (49) & p | m & p | m + 1 & ? & ? & ? & ? \\ 5 & p | m + 1 & p | m + 1 & ? & p | m & p | m + 1 & ? & ? & ? \\ 6 & p | m & p | m & ? & ? & p | m & p | m + 1 & ? & ? \\ 7 & p | m + 1 & ? & p | m + 1 & ? & ? & p | m & p | m + 1 & ? \\ 8 & p | m & p | m + 1 & p | m & ? & ? & ? & p | m & p | m + 1 \\ 9 & p | m + 1 & p | m & ? & p | m + 1 & ? & ? & ? & p | m \end{matrix}

Table 1: Convolution sums ∑ F_{j}^{(m)}F_{n−j}^{(m+p)} with 2 ≤ m, p ≤ 9 covered directly or indirectly in this article. The cases m = 1 and p = 1 are covered by (13) and (4), respectively. Question marks indicate unsolved cases.

5 Conclusion

This article was devoted to study convolutions involving the Fibonacci m-step numbers. We have applied the prominent generating function approach to prove several appealing results that strengthen the understanding of these numbers. Many known identities for the Fibonacci, Tribonacci, Tetranacci, and Pentanacci numbers now follow from our results as special cases. In addition, we have stated mixed convolutions involving the Fibonacci mstep numbers, the Jacobsthal numbers, and the Pell numbers. To keep things coherent and streamlined, we focused exclusively on the Fibonacci m-step numbers. There is still much work to be done. Identities for the Lucas m-step numbers, the Pell m-step numbers, and others, and also mixed convolutions of these sequences can be studied in the future.

6 Acknowledgments

The authors would like to thank the anonymous referee for carefully reading the paper and for the detailed feedback, which substantially improved the manuscript.

References

[1] A. T. Benjamin and J. J. Quinn, Proofs that Really Count, Mathematical Association of America, 2003.

[2] B. Bradie, Extensions and refinements of some properties of sums involving Pell numbers, Missouri J. Math. Sci. 22 (2010), 37–43.

[3] G. Dresden and Y. Wang, Sums and convolutions of k-bonacci and k-Lucas numbers, Integers 21 (2021), Paper No. A56.

[4] G. Dresden and M. Tulskikh, Convolutions of sequences with similar linear recurrence formulas, J. Integer Sequences 25 (2022), Article 22.3.3.

[5] G. Dresden and Y. Wang, A general convolution identity, Math. Magazine 97 (2024), 98–109.

[6] R. Frontczak, Some Fibonacci-Lucas-Tribonacci-Lucas identities, Fibonacci Quart. 56 (2018), 263–274.

[7] R. Frontczak, Sums of Tribonacci and Tribonacci-Lucas numbers, Int. J. Math. Analysis 12 (2018), 19–24.

[8] R. Frontczak, Relations for generalized Fibonacci and Tribonacci sequences, Notes Number Theory Discrete Math. 25 (2019), 178–192.

[9] I. M. Gessel and I. Kar, Binomial convolutions for rational power series, J. Integer Sequences 27 (2024), Article 24.1.3.

[10] G. C. Greubel and R. Frontczak, Solution to Problem B-756, Fibonacci Quart. 58 (2020), 82–84.

[11] K. Gryszka, Proof without words: sum of Fibonacci numbers and beyond, Math. Intelligencer 44 (2022), 371–372.

[12] K. Gryszka, A note on the Fibonacci m-step sequences modulo q, Math. Commun. 27 (2022), 215–223.

[13] T. Komatsu, Convolution identities for Tribonacci numbers, Ars Combin. 136 (2018), 199–210.

[14] T. Komatsu, Convolution identities for Tribonacci-type numbers with arbitrary initial values, Palestine J. Math. 8 (2019), 413–417.

[15] T. Komatsu and R. Li, Convolution identities for Tetranacci numbers, Notes Number Theory Discrete Math. 25 (2019), 142–169.

[16] T. Koshy and M. Griffiths, Some gibonacci convolutions with dividends, Fibonacci Quart. 56 (2018), 237–245.

[17] H. Prodinger and S. J. Selkirk, Sums of squares of Tetranacci numbers: A generating function approach, arxiv preprint, arXiv:1906.08336 [math.NT], 2019. Available at

    https://arxiv.org/abs/1906.08336v1

[18] R. Schumacher, How to sum the squares of the Tetranacci numbers and the Fibonacci m-step numbers, Fibonacci Quart. 57 (2019), 168–176.

[19] H.-J. Seiffert, Problem B-759, Fibonacci Quart. 32 (1994), 86.

[20] Y. Soykan, Sum formulas for generalized Tetranacci numbers: Closed forms of the sum formulas ∑_{k=0}^{n} x^{k}W_{k} and ∑_{k=0}^{n} x^{k}W_{−k}, J. Progressive Research Math. 18 (1) (2021), 24–47.

[21] Y. Soykan, A study on sum formulas of generalized Pentanacci sequence: Closed forms of the sum formulas ∑_{k=0}^{n} x^{k}W_{k} and ∑_{k=0}^{n} x^{k}W_{−k}, J. Progressive Research Math. 18 (2) (2021), 20–38.

[22] W. Zhang, Some identities involving the Fibonacci numbers, Fibonacci Quart. 35 (1997), 225–229.

2020 Mathematics Subject Classification: Primary 11B39, Secondary 11B37, 05A15. Keywords: convolution, Fibonacci m-step number, generating function.

(Concerned with sequences \underline{A000045}, \underline{A000073}, \underline{A000078}, \underline{A001591}, \underline{A001592}, \underline{A066178}, \underline{A079262}, \underline{A094687}, and \underline{A106515}.)

Received April 5 2024; revised version received April 13 2024; April 14 2024; December 2 2024; December 3 2024. Published in Journal of Integer Sequences, January 2 2025.

Return to Journal of Integer Sequences home page.