Linear Recurrence Sequences and Their Convolutions via Bell Polynomials

Daniel Birmajer Department of Mathematics Nazareth College Rochester, NY 14618 USA

                   abirmaj6@naz.edu

Juan B. Gil and Michael D. Weiner Department of Mathematics and Statistics Penn State Altoona Altoona, PA 16601 USA

                     jgil@psu.edu
                     mdw8@psu.edu

Abstract

We recast homogeneous linear recurrence sequences with fixed coefficients in terms of partial Bell polynomials, and use their properties to obtain various combinatorial identities and multifold convolution formulas. Our approach relies on a basis of sequences that can be obtained as the INVERT transform of the coefficients of the given recurrence relation. For such a basis sequence with generating function Y (t), and for any positive integer r, we give a formula for the convolved sequence generated by Y (t)^{r} and prove that it satisfies an elegant recurrence relation.

1 Introduction

A linear recurrence sequence (a_{n}) of elements in a commutative ring R is a sequence given by a homogeneous linear recurrence relation

a_{n} = c_{1}a_{n−1} + c_{2}a_{n−2} + ⋯ + c_{d}a_{n−d} for n ≥ d,  (1)

with fixed coefficients c_{1}, …, c_{d} ∈ R, together with initial values a_{0}, a_{1}, …, a_{d−1} ∈ R. The generating function of such a sequence is a rational function of the form f(t) = \frac{p(t)}{q(t)} with

q(t) = 1 − c_{1}t − c_{2}t^{2} − ⋯ − c_{d}t^{d},

and a polynomial p(t) of degree at most d − 1 that depends on the initial values. In other words, the function f(t) is a linear combination of the rational functions

\frac{1}{q(t)}, \frac{t}{q(t)}, \frac{t^{2}}{q(t)}, …, \frac{t^{d−1}}{q(t)} ,

and their respective associated sequences form a basis for the space of linear recurrence sequences with coefficients c_{1}, …, c_{d}.

On the other hand, if (c_{n}) is a sequence and Q(t) is the formal power series

Q(t) = 1 − ∑_{n=1}^{∞} c_{n}t^{n},

then its reciprocal Y (t) = \frac{1}{Q(t)} can be written as Y (t) = 1 + ∑_{n=1}^{∞} y_{n}t^{n} with

y_{n} = ∑_{k=0}^{n} \frac{k!}{n!}B_{n,k}(1!c_{1}, 2!c_{2}, 3!c_{3}, …),  (2)

where B_{n,k} = B_{n,k}(x_{1}, x_{2}, …) denotes the (n, k)-th partial Bell polynomial in the variables x_{1}, x_{2}, …, x_{n−k+1}. This is a direct consequence of Faà di Bruno’s formula (cf. Theorem B in [7, Section 3.5]), and the sequence (y_{n}) is precisely the INVERT^{1} transform of (c_{n}).

Observe that if c_{n} = 0 for all n > d, then 1/q(t) = 1/Q(t). Consequently, any linear recurrence sequence with fixed coefficients can be expressed in terms of partial Bell polynomials in the coefficients of the recurrence. An explicit formula is given in Section 2, see formula (3), together with a few illustrating examples. As a particular application, we provide an alternative derivation of the Girard-Waring formulas for the power sum symmetric functions.

The benefit of the representation (3) is that the partial Bell polynomials absorb the coefficients of the recurrence and facilitate the derivation of universal identities. This is particularly convenient when working with multifold self-convolutions. In Section 3, we recall a convolution formula given by the authors in [4] and discuss it in the context of multifold convolutions of linear recurrence sequences. For this type of convolved sequences we give a universal recurrence formula (of the same depth as the original sequence), which is obtained by using properties of the partial Bell polynomials. We conclude the paper with a few examples that illustrate some applications of our main result.

1Introduced by Bernstein and Sloane [2]. This is also the operator A discussed by Cameron [5].

2 Linear Recurrence Sequences

The representation of linear recurrence sequences in terms of partial Bell polynomials, as discussed in the introduction, can be summarized as follows:

Proposition 1. Let (a_{n}) be a linear recurrence sequence satisfying

a_{n} = c_{1}a_{n−1} + c_{2}a_{n−2} + ⋯ + c_{d}a_{n−d} for n ≥ d ≥ 1,

with initial values a_{0}, a_{1}, …, a_{d−1}. Let (y_{n}) be defined as in (2), and let

λ_{0} = a_{0}, λ_{n} = a_{n} − ∑_{j=1}^{n} c_{j}a_{n−j} for n = 1, …, d − 1.

Then a_{n} = λ_{0}y_{n} + λ_{1}y_{n−1} + ⋯ + λ_{d−1}y_{n−d+1}, so

a_{n} = ∑_{k=0}^{d−1} λ_{k} ∑_{j=0}^{n−k} \frac{j!}{(n − k)!}B_{n−k,j}(1!c_{1}, 2!c_{2}, …) for n ≥ 1.  (3)

Proof. If S denotes the right-shift operator S(a_{1}, a_{2}, …) = (0, a_{1}, a_{2}, …), then the sequences (y_{n}), S(y_{n}), S^{2}(y_{n}), …, S^{d−1}(y_{n}), clearly form a basis for the space of all linear recurrence sequences with coefficients c_{1}, …, c_{d}. Thus there are constants λ_{0}, λ_{1}, …, λ_{d−1} such that a_{n} = λ_{0}y_{n} + λ_{1}y_{n−1} + ⋯ + λ_{d−1}y_{n−d+1}, with the convention that y_{k} = 0 if k < 0. To find the λ_{k}’s, we just need to look at the initial values and solve the equation

(\begin{matrix}1 & 0 & ⋯ & ⋯ & ⋯ & 0 \\ y_{1} & 1 & 0 & ⋯ & ⋯ & 0 \\ y_{2} & y_{1} & 1 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & & ... & & ⋮ \\ ⋮ & ⋮ & & & ... & ⋮ \\ y_{d−1} & y_{d−2} & ⋯ & ⋯ & y_{1} & 1 \end{matrix}) ( λ_{0} ; λ_{1} ; λ_{2} ; ⋮ ; ⋮ ; λ_{d−1}) = ( a_{0} ; a_{1} ; a_{2} ; ⋮ ; ⋮ ; a_{d−1}) .

By definition, (y_{n}) satisfies the same recurrence as (a_{n}), so y_{n} = ∑_{j=1}^{n} c_{j}y_{n−j}. Thus the inverse of the above d × d matrix is

(\begin{matrix}1 & 0 & ⋯ & ⋯ & 0 \\ −c_{1} & 1 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & & ⋮ \\ ⋮ & ⋮ & & ... & ⋮ \\ −c_{d−1} & −c_{d−2} & ⋯ & −c_{1} & 1 \end{matrix}) ,

and the claimed formula follows by applying this matrix to the vector (a_{0}, …, a_{d−1}).

Remark 2. It is worth mentioning, that the representation (3) provides a unifying approach to linear recurrence sequences in which the coefficients of the recurrence are separated and organized inside the partial Bell polynomials. In many cases, this gives known and new combinatorial identities for the sequence at hand (regardless of the order of recursion) as well as for their repeated convolutions, see Section 3.

For illustration purposes, let us consider a few basic examples.

Example 3. (Generalized Fibonacci) For arbitrary α and coefficients c_{1} and c_{2}, let (f_{n}) be the sequence defined by

f_{0} = 0, f_{1} = α,
f_{n} = c_{1}f_{n−1} + c_{2}f_{n−2} for n ≥ 2.

In the terminology of Proposition 1, we then have λ_{0} = 0, λ_{1} = α, and for n ≥ 1 we get

f_{n} = αy_{n−1} = α ∑_{k=0}^{n−1} \frac{k!}{(n − 1)!}B_{n−1,k}(1!c_{1}, 2!c_{2}, 0, …),

and since B_{n−1,k}(c_{1}, 2c_{2}, 0, …) = \frac{(n−1)!}{k!} \binom{k}{n−1−k}c_{1}^{2k−n+1}c_{2}^{n−1−k}, we arrive at

f_{n} = α ∑_{k=0}^{n−1} \binom{k}{n − 1 − k}c_{1}^{2k−n+1}c_{2}^{n−1−k} = α ∑_{j=0}^{n−1} \binom{n − 1 − j}{j}c_{1}^{n−1−2j}c_{2}^{j}.  (4)

Example 4. (Padovan, \underline{A000931} in [9]) Consider the sequence defined by

P_{0} = 1, P_{1} = P_{2} = 0,
P_{n} = P_{n−2} + P_{n−3} for n ≥ 3.

Using Proposition 1 with c_{1} = 0 and c_{2} = c_{3} = 1, we get λ_{0} = 1, λ_{1} = 0, λ_{2} = −1, and for n ≥ 3,

P_{n} = y_{n} − y_{n−2} = y_{n−3} = ∑_{k=0}^{n−3} \frac{k!}{(n − 3)!}B_{n−3,k}(0, 2!, 3!, 0, …).

Now, since \frac{k!}{(n−3)!}B_{n−3,k}(0, 2!, 3!, 0, …) = \binom{k}{n−3−2k}, we conclude

P_{n} = ∑_{k=0}^{n−3} \binom{k}{n − 3 − 2k} for n ≥ 3.  (5)

Example 5. (Tribonacci, \underline{A000073} in [9]) Let (t_{n}) be the sequence defined by

t_{0} = t_{1} = 0, t_{2} = 1,
t_{n} = t_{n−1} + t_{n−2} + t_{n−3} for n ≥ 3.

By Proposition 1, we have t_{n} = y_{n−2}, so

t_{n} = ∑_{k=0}^{n−2} \frac{k!}{(n − 2)!}B_{n−2,k}(1!, 2!, 3!, 0, …),

and since B_{n,k}(1!, 2!, 3!, 0, …) = \frac{n!}{k!} ∑_{ℓ=0}^{k} \binom{k}{k−ℓ}\binom{k−ℓ}{n+ℓ−2k}, we get

t_{n} = ∑_{k=0}^{n−2} ∑_{ℓ=0}^{k} \binom{k}{k − ℓ}\binom{k − ℓ}{n − 2 + ℓ − 2k} = ∑_{k=0}^{n−2} ∑_{ℓ=0}^{k} \binom{k}{ℓ}\binom{ℓ}{n − 2 − k − ℓ}.

With the change of variable ℓ = j − k, and changing the order of summation, we arrive at

t_{n} = ∑_{j=0}^{n−2} ∑_{k=0}^{j} \binom{k}{j − k}\binom{j − k}{n − 2 − j} for n ≥ 2.  (6)

Example 6. (Chebyshev) We now consider the Chebyshev polynomials defined by

T_{0}(x) = 1, T_{1}(x) = x,
T_{n}(x) = 2xT_{n−1}(x) − T_{n−2}(x) for n ≥ 2.

Here c_{1} = 2x, c_{2} = −1, so λ_{0} = 1, λ_{1} = −x, and for n ≥ 1 we get

T_{n}(x) = y_{n} − xy_{n−1}

= ∑_{j=0}^{n} \frac{j!}{n!}B_{n,j}(2x, −2, 0, …) − x ∑_{j=0}^{n−1} \frac{j!}{(n − 1)!}B_{n−1,j}(2x, −2, 0, …)

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

= ∑_{j=0}^{n} \binom{j}{n − j}(2x)^{2j−n}(−1)^{n−j} − \frac{1}{2} ∑_{j=1}^{n} \binom{j − 1}{n − j}(2x)^{2j−n}(−1)^{n−j},

which can be written as

T_{n}(x) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋}(−1)^{k} \frac{n}{2(n − k)}\binom{n − k}{k}(2x)^{n−2k} for n ≥ 1.  (7)

Similarly, for the Chebyshev polynomials of second kind U_{n}(x), defined by the same recurrence relation as for T_{n}(x), but with initial values U_{0}(x) = 1 and U_{1}(x) = 2x, we get

U_{n}(x) = y_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋}(−1)^{k}\binom{n − k}{k}(2x)^{n−2k} for n ≥ 1.  (8)

2.1 Power Sums

We finish this section by considering the power sum symmetric functions

s_{n} = x_{1}^{n} + ⋯ + x_{d}^{n}

with d variables. The sequence (s_{n}) satisfies the relations (Newton’s identities):

s_{0} = d
s_{1} = e_{1}
s_{2} = e_{1}s_{1} − 2e_{2}
s_{3} = e_{1}s_{2} − e_{2}s_{1} + 3e_{3}
⋮
s_{n} = e_{1}s_{n−1} − e_{2}s_{n−2} + ⋯ + (−1)^{d−1}e_{d}s_{n−d} for n ≥ d,

where e_{1}, …, e_{d} are the elementary symmetric functions in x_{1}, …, x_{d}. In other words, (s_{n}) is a linear recurrence sequence of length d with initial values s_{0}, s_{1}, …, s_{d−1}. Thus, as a consequence of Proposition 1, each power sum s_{n} can be expressed in terms of partial Bell polynomials in e_{1}, …, e_{d}. This representation is an efficient way to organize and prove the Girard-Waring formulas (see, e.g., Gould [8]).

Proposition 7. Let s_{n} = x_{1}^{n} + ⋯ + x_{d}^{n} and let e_{1}, …, e_{d} be the elementary symmetric functions in the variables x_{1}, …, x_{d}. Then, for n ≥ 1, we have

s_{n} = ∑_{k=1}^{n}(−1)^{n+k} \frac{(k − 1)!}{(n − 1)!}B_{n,k}(1!e_{1}, 2!e_{2}, …, d!e_{d}, 0, …).

Our proof relies on the following basic recursive formula.

Lemma 8. For any sequence x = (x_{1}, x_{2}, …), we have

nB_{n,k}(x) = ∑_{j=1}^{n−k+1} j\binom{n}{j}x_{j}B_{n−j,k−1}(x).

Proof. This is a consequence of the known identity

B_{n,k} = ∑_{j=0}^{n−k} \binom{n − 1}{j}x_{j+1}B_{n−1−j,k−1} = ∑_{j=1}^{n−k+1} \binom{n − 1}{j − 1}x_{j}B_{n−j,k−1},

see [6, Eq. (11.11) p. 415].

nB_{n,k} = ∑_{j=1}^{n−k+1} n\binom{n − 1}{j − 1}x_{j}B_{n−j,k−1} = ∑_{j=1}^{n−k+1} j\binom{n}{j}x_{j}B_{n−j,k−1}

as claimed.

Proof of Proposition 7. Let s_{n} = x_{1}^{n} + ⋯ + x_{d}^{n}. As mentioned before, (s_{n}) is a linear recurrence sequence with coefficients

c_{j} = (−1)^{j−1}e_{j} for j = 1, …, d,

and initial values

s_{0} = d, s_{k} = ∑_{j=1}^{k−1} c_{j}s_{k−j} + kc_{k} for k = 1, …, d − 1.

By Proposition 1, we can write s_{n} = ∑_{j=0}^{d−1} λ_{j}y_{n−j} with (y_{n}) defined as in (2), and the λ_{j}’s given by λ_{0} = s_{0} = d and

λ_{j} = s_{j} − ∑_{i=1}^{j} c_{i}s_{j−i} = ( ∑_{i=1}^{j−1} c_{i}s_{j−i} + jc_{j}) − ∑_{i=1}^{j} c_{i}s_{j−i} = (j − d)c_{j}

for j = 1, …, d − 1. Also, recall that (y_{n}) is designed to satisfy the same recurrence relation as (s_{n}) for n ≥ d. Therefore, y_{n} = ∑_{j=1}^{d} c_{j}y_{n−j}, and we can rewrite s_{n} as follows:

s_{n} = ∑_{j=0}^{d−1} λ_{j}y_{n−j} = λ_{0}y_{n} + ∑_{j=1}^{d−1} λ_{j}y_{n−j}

= d( ∑_{j=1}^{d} c_{j}y_{n−j}) + ∑_{j=1}^{d−1}(j − d)c_{j}y_{n−j}

= dc_{d}y_{n−d} + ∑_{j=1}^{d−1} jc_{j}y_{n−j} = ∑_{j=1}^{d} jc_{j}y_{n−j}

= ∑_{j=1}^{d} ∑_{k=0}^{n−j} jc_{j} \frac{k!}{(n − j)!}B_{n−j,k}(1!c_{1}, 2!c_{2}, …, d!c_{d}, 0, …).

Since c_{j} = 0 for j > d, we can write the sum over j up to n to facilitate a change of summation. Then

s_{n} = ∑_{j=1}^{n} ∑_{k=0}^{n−j} jc_{j} \frac{k!}{(n − j)!}B_{n−j,k}(1!c_{1}, 2!c_{2}, …)

= ∑_{k=0}^{n−1} ∑_{j=1}^{n−k} jc_{j} \frac{k!}{(n − j)!}B_{n−j,k}(1!c_{1}, 2!c_{2}, …)

= ∑_{k=0}^{n−1} \frac{k!}{n!}( ∑_{j=1}^{n−k} j\binom{n}{j}(j!c_{j})B_{n−j,k}(1!c_{1}, 2!c_{2}, …))

which by Lemma 8 yields

s_{n} = ∑_{k=0}^{n−1} \frac{k!}{n!} nB_{n,k+1}(1!c_{1}, 2!c_{2}, …) = ∑_{k=1}^{n} \frac{(k − 1)!}{(n − 1)!}B_{n,k}(1!c_{1}, 2!c_{2}, …).

The claimed identity for the power sum s_{n} follows by replacing back c_{j} = (−1)^{j−1}e_{j} and using the homogeneity properties of the polynomial B_{n,k}.

3 Convolutions

We now turn our attention to convolutions of sequences of the form

y_{n} = ∑_{k=0}^{n} \frac{k!}{n!}B_{n,k}(1!c_{1}, 2!c_{2}, 3!c_{3}, …).  (9)

In [4], we considered a more general family of sequences and proved the following result.

Theorem 9 ([4, Theorem 2.1]). Let a and b be arbitrary numbers. Let y_{0} = 1 and

y_{n} = ∑_{k=1}^{n} \binom{an + bk}{k − 1}\frac{(k − 1)!}{n!}B_{n,k}(1!c_{1}, 2!c_{2}, …) for n ≥ 1.

For r ∈ ℕ, we have

∑_{m_{1}+···+m_{r}=n}y_{m_{1}} ⋯ y_{m_{r}} = r ∑_{k=1}^{n} \binom{an + bk + r − 1}{k − 1}\frac{(k − 1)!}{n!}B_{n,k}(1!c_{1}, 2!c_{2}, …).

The proof of this theorem relies on a convolution formula for partial Bell polynomials given by the authors in [3]. In particular, the special case when a = 0 and b = 1 can be formulated as follows:

Corollary 10. For (y_{n}) defined by (9) and r ∈ ℕ, we have

y_{n}^{(r)} = ∑_{m_{1}+···+m_{r}=n}y_{m_{1}} ⋯ y_{m_{r}} = r ∑_{k=1}^{n} \binom{k + r − 1}{k − 1}\frac{(k − 1)!}{n!}B_{n,k}(1!c_{1}, 2!c_{2}, …) (10)

= ∑_{k=1}^{n} \binom{k + r − 1}{k}\frac{k!}{n!}B_{n,k}(1!c_{1}, 2!c_{2}, …).

Remark 11. More generally, if δ ≥ 0 is an integer, and if we let y_{−1} = ⋯ = y_{−δ} = 0, then

∑_{m_{1}+···+m_{r}=n}y_{m_{1}−δ} ⋯ y_{m_{r}−δ} = ∑_{k=0}^{n−δr} \binom{k + r − 1}{k}\frac{k!}{(n − δr)!}B_{n−δr,k}(1!c_{1}, 2!c_{2}, …).

Let us now revisit some of the basic examples considered in the previous section. Example 12. (Generalized Fibonacci) For α, c_{1}, c_{2} ∈ ℝ, consider (f_{n}) defined by

f_{0} = 0, f_{1} = α, f_{n} = c_{1}f_{n−1} + c_{2}f_{n−2} for n ≥ 2.

Then, as described in Example 3, we have f_{n} = αy_{n−1}, and therefore

∑_{m_{1}+···+m_{r}=n}f_{m_{1}} ⋯ f_{m_{r}} = α^{r} ∑_{m_{1}+···+m_{r}=n}y_{m_{1}−1} ⋯ y_{m_{r}−1}

= α^{r} ∑_{k=0}^{n−r} \binom{k + r − 1}{k}\frac{k!}{(n − r)!}B_{n−r,k}(1!c_{1}, 2!c_{2}, 0, …)

= α^{r} ∑_{k=0}^{n−r} \binom{k + r − 1}{k}\binom{k}{n − r − k}c_{1}^{2k−n+r}c_{2}^{n−r−k}.

Example 13. (Padovan) Let (P_{n}) be defined by

P_{0} = 1, P_{1} = P_{2} = 0, P_{n} = P_{n−2} + P_{n−3} for n ≥ 3.

As mentioned in Example 4, we have P_{n} = y_{n−3} and so

∑_{m_{1}+···+m_{r}=n}P_{m_{1}+1} ⋯ P_{m_{r}+1} = ∑_{m_{1}+···+m_{r}=n}y_{m_{1}−2} ⋯ y_{m_{r}−2}

= ∑_{k=0}^{n−2r} \binom{k + r − 1}{k}\frac{k!}{(n − 2r)!}B_{n−2r,k}(0, 2!, 3!, 0, …)

= ∑_{k=0}^{n−2r} \binom{k + r − 1}{k}\binom{k}{n − 2r − 2k}.

And, with a little more work, we also get

∑_{m_{1}+···+m_{r}=n}P_{m_{1}} ⋯ P_{m_{r}} = ∑_{ℓ=1}^{r} \binom{r}{ℓ} ∑_{k=0}^{n−3ℓ} \binom{k + ℓ − 1}{k}\binom{k}{n − 3ℓ − 2k}.

Example 14. (Tribonacci) Let (t_{n}) be defined by

t_{0} = t_{1} = 0, t_{2} = 1, t_{n} = t_{n−1} + t_{n−2} + t_{n−3} for n ≥ 3.

As discussed in the previous section, we have t_{n} = y_{n−2}, so

∑_{m_{1}+···+m_{r}=n}t_{m_{1}} ⋯ t_{m_{r}} = ∑_{m_{1}+···+m_{r}=n}y_{m_{1}−2} ⋯ y_{m_{r}−2}

= ∑_{k=0}^{n−2r} \binom{k + r − 1}{k}\frac{k!}{(n − 2r)!}B_{n−2r,k}(1!, 2!, 3!, 0, …)

= ∑_{k=0}^{n−2r} ∑_{ℓ=0}^{k} \binom{k + r − 1}{k}\binom{k}{ℓ}\binom{ℓ}{n − 2r − k − ℓ}.

We now present a recurrence relation for convolved sequences of the form (10). Theorem 15. For any sequence of the form y_{n} = ∑_{k=0}^{n} \frac{k!}{n!}B_{n,k}(1!c_{1}, 2!c_{2}, …), and for r ∈ ℕ, consider the convolved sequence

y_{n}^{(r)} = ∑_{m_{1}+···+m_{r}=n}y_{m_{1}} ⋯ y_{m_{r}} for n ≥ 0.

Then, for n ≥ 1, we have the recurrence relation

n y_{n}^{(r)} = ∑_{m=1}^{n} (n + m(r − 1))c_{m} y_{n−m}^{(r)}.  (11)

Proof. By definition, we have y_{0}^{(r)} = 1 and y_{1}^{(r)} = rc_{1}, so (11) is true for n = 1. For n > 1, write

∑_{m=1}^{n} (n + m(r − 1))c_{m} y_{n−m}^{(r)} = nrc_{n} + ∑_{m=1}^{n−1} (n + m(r − 1))c_{m} y_{n−m}^{(r)}.

Now, by means of the identity (10), we have

\frac{1}{r} ∑_{m=1}^{n−1} (n + m(r − 1))c_{m}y_{n−m}^{(r)}

= \frac{1}{r} ∑_{m=1}^{n−1} (n + m(r − 1))c_{m} ∑_{k=1}^{n−m} r\binom{k+r−1}{k−1} \frac{(k−1)!}{(n−m)!}B_{n−m,k}(1!c_{1}, 2!c_{2}, …)

= ∑_{k=1}^{n−1} \binom{k+r−1}{k−1}(k − 1)! ∑_{m=1}^{n−k} \frac{n+m(r−1)}{(n−m)!}c_{m}B_{n−m,k}(1!c_{1}, 2!c_{2}, …)

= ∑_{k=2}^{n} \binom{k+r−2}{k−2}(k − 2)! ∑_{m=k−1}^{n−1} \frac{n+(n−m)(r−1)}{m!}c_{n−m}B_{m,k−1}(1!c_{1}, 2!c_{2}, …).

We split the last equation into two terms and get

= ∑_{k=2}^{n} \binom{k+r−2}{k−2}(k − 2)! ( ∑_{m=k−1}^{n−1} \frac{n}{m!}c_{n−m}B_{m,k−1} + ∑_{m=k−1}^{n−1} \frac{(n−m)(r−1)}{m!}c_{n−m}B_{m,k−1}).

On the one hand,

∑_{k=2}^{n} \binom{k+r−2}{k−2}(k − 2)! ∑_{m=k−1}^{n−1} \frac{n}{m!}c_{n−m}B_{m,k−1}(1!c_{1}, 2!c_{2}, …)

= ∑_{k=2}^{n} \binom{k+r−2}{k−2} \frac{(k−2)! k}{(n−1)!} (\frac{1}{k} ∑_{m=k−1}^{n−1} \binom{n}{m}(n − m)! c_{n−m}B_{m,k−1}(1!c_{1}, 2!c_{2}, …))

= ∑_{k=2}^{n} \binom{k+r−2}{k−2} \frac{(k−2)! k}{(n−1)!}B_{n,k}(1!c_{1}, 2!c_{2}, …).

On the other hand,

∑_{k=2}^{n} \binom{k+r−2}{k−2}(k − 2)! ∑_{m=k−1}^{n−1} \frac{(n−m)(r−1)}{m!}c_{n−m}B_{m,k−1}

= ∑_{k=2}^{n} \binom{k+r−2}{k−2} \frac{(k−2)!(r−1)}{(n−1)!} ( ∑_{m=k−1}^{n−1} \binom{n−1}{m}(n − m)!c_{n−m}B_{m,k−1}(1!c_{1}, 2!c_{2}, …))

= ∑_{k=2}^{n} \binom{k+r−2}{k−2} \frac{(k−2)!(r−1)}{(n−1)!}B_{n,k}(1!c_{1}, 2!c_{2}, …).

Therefore,

\frac{1}{r} ∑_{m=1}^{n−1} (n + m(r − 1))c_{m}y_{n−m}^{(r)} = ∑_{k=2}^{n} \binom{k+r−2}{k−2} \frac{(k−2)!}{(n−1)!}(k + r − 1)B_{n,k}(1!c_{1}, 2!c_{2}, …)

= ∑_{k=2}^{n} \binom{k+r−1}{k−1} \frac{(k−1)!}{(n−1)!}B_{n,k}(1!c_{1}, 2!c_{2}, …),

and so

∑_{m=1}^{n−1} (n + m(r − 1))c_{m}y_{n−m}^{(r)} = r ∑_{k=2}^{n} \binom{k+r−1}{k−1} \frac{(k−1)!}{(n−1)!}B_{n,k}(1!c_{1}, 2!c_{2}, …)

= n ∑_{k=2}^{n} \binom{k+r−1}{k} \frac{k!}{n!}B_{n,k}(1!c_{1}, 2!c_{2}, …) = n(y_{n}^{(r)} − rc_{n}).

Finally, adding the term nrc_{n} to both sides of this equation, we arrive at (11). To illustrate our result, we now consider a few basic examples.

Example 16. Let (a_{n}) be the sequence defined by a_{0} = 1, a_{1} = 1, a_{n} = a_{n−1} + a_{n−2} for n ≥ 2.

This is a shift of the Fibonacci sequence (a_{n} = F_{n+1}), and a_{n} = ∑_{k=0}^{n} \frac{k!}{n!}B_{n,k}(1, 2, 0, …). By means of Corollary 10, we have

a_{n}^{(r)} = ∑_{m_{1}+···+m_{r}=n}a_{m_{1}} ⋯ a_{m_{r}} = ∑_{k=1}^{n} \binom{k + r − 1}{k}\binom{k}{n − k},

and according to Theorem 15, this sequence satisfies

na_{n}^{(r)} = (n + r − 1)a_{n−1}^{(r)} + (n + 2(r − 1))a_{n−2}^{(r)}.

For r = 2, 3, 4, this gives the recurrence relations (cf. [9]):

na_{n}^{(2)} = (n + 1)a_{n−1}^{(2)} + (n + 2)a_{n−2}^{(2)}, (\underline{A001629})
na_{n}^{(3)} = (n + 2)a_{n−1}^{(3)} + (n + 4)a_{n−2}^{(3)}, (\underline{A001628})
na_{n}^{(4)} = (n + 3)a_{n−1}^{(4)} + (n + 6)a_{n−2}^{(4)}. (\underline{A001872})

Example 17. Let (a_{n}) be the sequence defined by a_{0} = 1, a_{1} = 0, a_{2} = 1, and

a_{n} = a_{n−2} + a_{n−3} for n ≥ 3.

This is a shifted version of the Padovan sequence, and a_{n} = ∑_{k=0}^{n} \frac{k!}{n!}B_{n,k}(0, 2!, 3!, 0, …).

By Theorem 15, the corresponding convolved sequence (cf. Example 13)

a_{n}^{(r)} = ∑_{k=1}^{n} \binom{k + r − 1}{k}\binom{k}{n − 2k}

satisfies the recurrence relation

na_{n}^{(r)} = (n + 2(r − 1))a_{n−2}^{(r)} + (n + 3(r − 1))a_{n−3}^{(r)}.

For r = 2, we get a shift of the sequence \underline{A228577} in [9] (number of gaps of length 1 in all possible covers of a line of length n by segments of length 2). In this case, we obtain

na_{n}^{(2)} = (n + 2)a_{n−2}^{(2)} + (n + 3)a_{n−3}^{(2)}.

Example 18. Let (a_{n}) be the sequence defined by

a_{0} = 1, a_{1} = 1, a_{2} = 2, and
a_{n} = a_{n−1} + a_{n−2} + a_{n−3} for n ≥ 3.

This is a shift of the Tribonacci sequence discussed in Examples 5 and 14. More precisely,

a_{n} = t_{n+2} = ∑_{k=0}^{n} \frac{k!}{n!}B_{n,k}(1!, 2!, 3!, 0, …), and the convolved sequence (a_{n}^{(r)})_{n≥1} takes the form

a_{n}^{(r)} = ∑_{k=1}^{n} \binom{k + r − 1}{k} ∑_{ℓ=0}^{k} \binom{k}{k − ℓ}\binom{k − ℓ}{n + ℓ − 2k},

which satisfies

na_{n}^{(r)} = (n + r − 1)a_{n−1}^{(r)} + (n + 2(r − 1))a_{n−2}^{(r)} + (n + 3(r − 1))a_{n−3}^{(r)}.

For r = 2, we obtain a recurrence relation for \underline{A073778} in [9]:

na_{n}^{(2)} = (n + 1)a_{n−1}^{(2)} + (n + 2)a_{n−2}^{(2)} + (n + 3)a_{n−3}^{(2)}.

References

[1] E. T. Bell, Exponential polynomials, Ann. of Math. 35 (1934), 258–277.

[2] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra Appl. 226/228 (1995), 57–72.

[3] D. Birmajer, J. Gil, and M. Weiner, Some convolution identities and an inverse relation involving partial Bell polynomials, Electron. J. Combin. 19 (2012), no. 4, Paper 34.

[4] D. Birmajer, J. Gil, and M. Weiner, Convolutions of Tribonacci, Fuss–Catalan, and Motzkin sequences, preprint, 2014.

[5] P. J. Cameron, Some sequences of integers, Discrete Math. 75 (1989), 89–102.

[6] C. A. Charalambides, Enumerative Combinatorics, Chapman and Hall/CRC, Boca Raton, 2002.

[7] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, D. Reidel Publishing Co., Dordrecht, 1974.

[8] H. Gould, The Girard-Waring power sum formulas for symmetric functions and Fibonacci sequences, Fibonacci Quart. 37 (1999), 135–140.

[9] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 11B83, 11B39. Keywords: linear recurrence sequence, Bell polynomial, power sum, convolved sequence.

(Concerned with sequences \underline{A000073}, \underline{A000931}, \underline{A001628} \underline{A001629}, \underline{A001872}, \underline{A073778}, and \underline{A228577}.)

Received May 29 2014; revised version received November 28 2014; November 29 2014. Published in Journal of Integer Sequences, December 14 2014.

Return to Journal of Integer Sequences home page.