Convolutions of Sequences with Similar Linear Recurrence Formulas

Greg Dresden Washington & Lee University Lexington, VA 24450 USA

                       dresdeng@wlu.edu

Michael Tulskikh Columbia University New York, NY 10027 USA

                   tulskikhmichael@gmail.com

Abstract We show that a collection of convolution formulas involving the Fibonacci, Tribonacci, Pell, Jacobsthal, Narayana, and other number sequences can all be derived from a single elegant formula so long as the sequences follow certain mild requirements. We give many examples, both old and new.

1 Introduction

Let us dive right into some interesting convolution formulas. From Szakács [?, Corollary 2.4] and two years later in Koshy and Griffiths [?, equation (2.2)] we have this lovely convolution formula that connects the Fibonacci numbers F_{n} (\underline{A000045} in the On-Line Encyclopedia of Integer Sequences [?]) with the seemingly-unrelated Jacobsthal numbers J_{n} (\underline{A001045}),

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

This formula can also be found at \underline{A094687}.

From Frontczak [?, Theorem 2.1] we have another lovely formula, this one with the Fibonacci numbers and the Tribonacci numbers T_{n} (\underline{A000073}) except that our Tribonacci numbers start with T_{0} = 0, T_{1} = 1, T_{2} = 1,

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

The terms T_{n+2} − F_{n+2} appear at sequence \underline{A000100}.

Dresden and Wang [?] noted the similarity between formulas 1 and 2, and asked if there were other convolution formulas of this type. A bit of investigation reveals quite a few more, such as this next little gem that involves just the Fibonacci numbers,

∑_{i=0}^{n} F_{3i}F_{n−i} = \frac{1}{3} (F_{3n} − 2F_{n}) .  (3)

The above formula can be found at \underline{A049674}.

Here is an adorable equation that connects the Narayana numbers N_{n} (\underline{A000930}) and the triangular numbers t_{n} (\underline{A000217}),

∑_{i=1}^{n} N_{3i−1}t_{n−i} = N_{3n−1} − t_{n}.  (4)

We believe this formula is new; we added it to the OEIS at \underline{A350498}.

This next one gives us another surprising connection (first proved by Szakács [?, Corollary 2.7]), this time between the Jacobsthal numbers and Pell numbers (\underline{A000129}),

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

Here are some formulas with Fibonacci numbers and with powers that all seem rather similar:

∑_{i=0}^{n} F_{i} 1^{n−i} = F_{n+2} − 1 · 1^{n+1}  (6)

∑_{i=0}^{n} F_{2i} 3^{n−i} = 1 · 3^{n+1} − F_{2(n+2)}  (7)

∑_{i=0}^{n} F_{3i} 4^{n−i} = F_{3(n+2)} − 2 · 4^{n+1}.  (8)

The general rule is

∑_{i=0}^{n} F_{ki} (L_{k})^{n−i} = (−1)^{k} (F_{k} · (L_{k})^{n+1} − F_{k(n+2)}) .  (9)

It should not come as a surprise that we can play a similar game with the Pell numbers:

∑_{i=0}^{n} P_{i} 2^{n−i} = P_{n+2} − 1 · 2^{n+1}  (10)

∑_{i=0}^{n} P_{2i} 6^{n−i} = 2 · 6^{n+1} − P_{2(n+2)}  (11)

∑_{i=0}^{n} P_{3i} 14^{n−i} = P_{3(n+2)} − 5 · 14^{n+1}.  (12)

The general rule for these is

∑_{i=0}^{n} P_{ki} (Q_{k})^{n−i} = (−1)^{k} (P_{k} · (Q_{k})^{n+1} − P_{k(n+2)}) ,  (13)

where the Q_{n}’s are the Pell-Lucas numbers A002203. For k odd, these Fibonacci and Pell formulas can also be derived from a combinatorial formula by Benjamin and Quinn [?, Identity 99].

At this point, it is probably not surprising that we can also find convolution formulas for Fibonacci numbers and Pell numbers together, such as the well-known formula

∑_{i=0}^{n} F_{i}P_{n−i} = P_{n} − F_{n}  (14)

and the less familiar formula

∑_{i=0}^{n} F_{3i}P_{n−i} = F_{3n}/2 − P_{n}.  (15)

With not much effort, we can prove a general formula for the Fibonacci and Pell numbers involving the Lucas numbers L_{n} (\underline{A000032}) and the Pell-Lucas numbers Q_{n},

∑_{i=0}^{n} F_{ki}P_{m(n−i)} = \frac{1}{L_{k} − Q_{m}} (F_{kn}P_{m} − F_{k}P_{mn}) ,  for k, m same parity.  (16)

(It takes a bit more effort to show that L_{k} = Q_{m} only for k = 0 and m = 0, 1; this follows from a procedure of Alekseyev [?, eq. (10)] which gives us the Diophantine system x^{2} − 5y^{2} = ±4 and x^{2} − 8z^{2} = ±4 which by a bit of algebra and the method of infinite descent gives only (x, y, z) = (2, 0, 0) as the single non-negative solution and hence L_{k} = Q_{m} only when both equal 2.)

Along the lines of equation (16), we have another general convolution formula, this one just involving the Fibonacci numbers which is a nice generalization of equation (3) from earlier:

∑_{i=0}^{n} F_{ki}F_{m(n−i)} = \frac{1}{L_{k} − L_{m}} (F_{kn}F_{m} − F_{k}F_{mn}) ,  for k ≠ m but of same parity. (17)

It should not come as a surprise to learn that we have a version of equation (17) but for the Pell numbers in place of the Fibonacci numbers,

∑_{i=0}^{n} P_{ki}P_{m(n−i)} = \frac{1}{Q_{k} − Q_{m}} (P_{kn}P_{m} − P_{k}P_{mn}) ,  for k ≠ m but of same parity. (18)

We note that for k, m both odd, then equations (16), (17), and (18) can all be derived from a theorem of Bramham and Griffiths [?, Theorem 3.1], but we believe the extension to when k, m are both even is original to this paper.

Finally, here is a rather complicated formula that does not seem related to the others (but as we will reveal later it is indeed in the same family),

∑_{i=0}^{2n}(−1)^{i}F_{i}F_{i+1}F_{2n−i−1} = \frac{2}{3} ∑_{i=0}^{n} F_{2i−1}F_{4(n−i)} = \frac{1}{2} (F_{4n+1} − F_{2n−1}) .  (19)

This formula is completely new, and it illustrates how our approach can produce novel results.

The right-hand sides of all these equations (1) through (19) exhibit a striking pattern. Is there a single theorem that will allow us to derive all these formulas? Of course there is, and we give two proofs of this theorem, one using generating functions and the other using a tiling argument. Our work follows closely the tiling techniques studied by Benjamin and Quinn [?] and elaborated by Bramham and Griffiths [?], and also the generating function techniques illustrated by Wilf [?].

We should note that in general, most convolution formulas are not as elegant as the ones seen above. For example, the convolution of F_{n} with itself is the rather unpleasant ((n−1)F_{n}+2nF_{n−1})/5, and for the convolution of (F_{n})^{2} with F_{3n} we have the quite unsavory equation

∑_{i=0}^{n}(F_{i})^{2}F_{3(n−i)} = \frac{1}{11}(F_{3n} + L_{3n+1} − 5(F_{n})^{2} − (F_{n+1})^{2} − 3F_{n}F_{n+1}).

By comparison, our convolution formulas (1) through (19) are delightfully simple and graceful, with all but equation (5) involving just two terms. Furthermore, they all derive from a single theorem, as we now explain.

2 Definitions and the main theorem

To begin, we suppose that (a_{n})_{n≥0} is a linear recurrence sequence with initial values a_{n} = 0 for n ≤ 0 and a_{1} = 1, and with recurrence formula

a_{n} = c_{1}a_{n−1} + c_{2}a_{n−2} + ⋯ + c_{L}a_{n−L}  (20)

for n > 1, with not all c_{i} equal to zero. We say that this sequence has signature {c_{1}, c_{2}, …, c_{L}} and has order L. It is not hard to show that this sequence (a_{n}) has generating function A(x), where

A(x) = ∑_{n=0}^{∞} a_{n}x^{n} = \frac{x}{1 − c_{1}x − c_{2}x^{2} − ⋯ − c_{L}x^{L}} .  (21)

As an example, the Fibonacci sequence (F_{n})_{n≥0} has signature {1, 1}, order 2, and generating function x/(1 − x − x^{2}).

Next, we suppose that (b_{n}) is another linear recurrence sequence with the same initial values as (a_{n}) and whose signature is {c_{1}, c_{2}, …, (c_{j}+d_{j}), …, c_{L}}, differing from the signature for (a_{n}) only in position j by a non-zero amount d_{j}. It is convenient but not necessary to assume that d_{j} > 0. The sequence (b_{n}) has generating function B(x), where

B(x) = ∑_{n=0}^{∞} b_{n}x^{n} = \frac{x}{1 − c_{1}x − c_{2}x^{2} − ⋯ − (c_{j} + d_{j})x^{j} − ⋯ − c_{L}x^{L}} .  (22)

With all this in mind, we have the following theorem.

Theorem 1. For any two sequences (a_{n}) and (b_{n}) as defined above with initial values of 0 for n ≤ 0 and 1 for n = 1 and whose recurrence signatures differ in only the j^{th} term by an amount d_{j}, we have the convolution formula

∑_{i=0}^{n} a_{i}b_{n−i} = ∑_{i=0}^{n} b_{i}a_{n−i} = \frac{1}{d_{j}} (b_{n+j−1} − a_{n+j−1}).  (23)

We note that Szakács [?, Theorem 2.1] covers our Theorem 1 but only for second-order linear recurrences. In the next two sections, we present two separate proofs of our theorem.

3 Proving the convolution theorem using generating functions

Recall that we have

A(x) = ∑_{n=0}^{∞} a_{n}x^{n} = \frac{x}{1 − c_{1}x − c_{2}x^{2} − ⋯ − c_{L}x^{L}} ,

B(x) = ∑_{n=0}^{∞} b_{n}x^{n} = \frac{x}{1 − c_{1}x − c_{2}x^{2} − ⋯ − (c_{j} + d_{j})x^{j} − ⋯ − c_{L}x^{L}} .

A bit of algebra (and a common denominator) reveals that

B(x) − A(x) = d_{j}x^{j−1}A(x)B(x),

which we simplify to

A(x)B(x) = \frac{1}{d_{j}} (\frac{B(x)}{x^{j−1}} − \frac{A(x)}{x^{j−1}}) .  (24)

Here we make two crucial observations. First, we note that A(x)B(x) is the generating function for the convolution sequence (∑_{i=0}^{n} a_{i}b_{n−i})_{n≥0} which if we replace i with n − i gives us the identical expression (∑_{i=0}^{n} b_{i}a_{n−i})_{n≥0}, and second, we note that dividing a generating function by a power of x shifts the index in the positive direction by that same power. In other words,

\frac{A(x)}{x^{j−1}} = ∑_{n=−(j−1)}^{∞} a_{n+(j−1)}x^{n},

with a similar statement for B(x)/x^{j−1}. Hence, equation (24) can be rewritten in terms of coefficients as

∑_{i=0}^{n} a_{i}b_{n−i} = \frac{1}{d_{j}} (b_{n+j−1} − a_{n+j−1}) for all n ≥ 0.

Therefore, we have proved Theorem 1.

4 Proving the convolution theorem using tilings

Note that tiling proofs for convolution formulas are quite common. Equation (6) is the very first identity in Benjamin and Quinn’s book [?]. Versions of Theorem 1 for degree-two recurrence sequences can be found in that same book [?, Identities 99, 100] and also in an article by Bramham and Griffiths [?, Theorems 3.1, 3.2], and a limited version for degree three also appears in Benjamin and Quinn [?, p. 47, Ex. 4].

To begin our tiling proof, we turn once more to Benjamin and Quinn [?, Section 3.1], where we find the following theorem:

Theorem 2 (Benjamin, Quinn). Let c_{1}, c_{2}, … c_{L} be nonnegative integers, and let a_{0}, a_{1}, … be the sequence of numbers defined by the recurrence

a_{n} = c_{1}a_{n−1} + c_{2}a_{n−2} + ⋯ + c_{L}a_{n−L}

with “ideal” initial conditions a_{1} = 1 and a_{n} = 0 for n ≤ 0. Then for all n ≥ 1, a_{n} counts the colored tilings of a board of length n − 1, using tiles of length at most L, where for 1 ≤ i ≤ L each tile of length i is assigned one of c_{i} colors.