Walks in Tiled Rectangles and Self-Convolutions of Higher-Order

Fibonacci Numbers

Jan Sedlák and Antonín Slavík Faculty of Mathematics and Physics Charles University Sokolovská 83 186 75 Prague Czech Republic

                 deg.sedlak@gmail.com
               slavik@karlin.mff.cuni.cz

Abstract

We derive new formulas for self-convolutions of Fibonacci numbers of arbitrary order using a combinatorial approach based on counting walks in tiled rectangles. This approach leads to a difference equation whose solution can be expressed in terms of weighted sums involving higher-order Fibonacci numbers, and we evaluate these sums via summation by parts. In addition, we provide combinatorial proofs of further convolution identities for Fibonacci numbers.

1 Introduction

Self-convolutions of the Fibonacci numbers appear in various combinatorial problems, some of which are listed in the On-Line Encyclopedia of Integer Sequences (OEIS) [15] (see \underline{A001629} there), for instance:

• Consider sequences of n tosses of a fair coin. It is well known that the number of sequences with no pair of successive heads is F_{n+2}, where (F_{n})_{n∈ℤ} is the Fibonacci sequence satisfying F_{n} = F_{n−1} + F_{n−2} for all n ∈ ℤ, F_{0} = 0, and F_{1} = 1. What about sequences of tosses with exactly one pair of successive heads? Suppose the unique pair HH is located at positions i, i + 1. It must be preceded by a sequence of length i − 2 with no two successive heads, followed by a tail; the number of such prefixes is F_{i}. Also, the pair HH must be followed by a tail and a sequence of length n − i − 2 with no two successive heads; the number of such suffixes is F_{n−i}. Hence, the total number of sequences with a unique pair of heads is ∑_{i=0}^{n} F_{i}F_{n−i}.

• Consider all subsets of {1, …, n − 1} with no two consecutive integers. Clearly, the number of such subsets is F_{n+1}, since each subset S can be represented by a sequence of heads and tails, where T’s corresponds to elements of S, and H’s correspond to elements of {1, …, n − 1} \ S.

But what is the total number of elements in such subsets? Let us fix an integer i ∈ {1, …, n − 1}, and calculate how many subsets S contain i. Note that S must avoid both i − 1 and i + 1. Hence, S = S_{1} ∪ {i} ∪ S_{2}, where S_{1} ⊂ {1, …, i − 2}, S_{2} ⊂ {i + 2, …, n − 1}, and S_{1}, S_{2} never contain consecutive integers. Since S_{1} can be chosen in F_{i} ways and S_{2} can be chosen in F_{n−i} ways, the total number of subsets containing i is F_{i}F_{n−i}. Hence, the total number of elements in all subsets of {1, …, n − 1} with no two successive integers is ∑_{i=0}^{n} F_{i}F_{n−i}.

• Consider tilings of a 1×n rectangle with monominoes and dominoes, where exactly one of the dominoes is colored. The number of such tilings is again ∑_{i=0}^{n} F_{i}F_{n−i}. Indeed, if the colored domino is located at positions i and i + 1, there are F_{i} ways of tiling the left 1 × (i − 1) rectangle, and F_{n−i} ways of tiling the right 1 × (n − i − 1) rectangle.

One of the earliest papers [10] dealing with Fibonacci self-convolutions contains the explicit formula

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

More general results were obtained by Moree [12], who derived explicit formulas for higherorder convolutions Fibonacci numbers expressed in terms of the Fibonacci and Lucas numbers, as well as by Czabarka et al. [2], who dealt with generalized Fibonacci (also known as Gibonacci) numbers G_{n} with arbitrary initial values G_{1} = a, G_{2} = b, and studies convolutions of the form ∑_{i} G_{(k+1)i+1}G_{m−l(k+1)i} for arbitrary parameters k, l, m.

Another possibility is to replace Fibonacci numbers by their higher-order analogues (F_{n}^{(m)})_{n∈ℤ}, which satisfy

F_{n}^{(m)} = F_{n−1}^{(m)} + F_{n−2}^{(m)} + ⋯ + F_{n−m}^{(m)}, n ∈ ℤ,

and

F_{0}^{(m)} = F_{1}^{(m)} = ⋯ = F_{m−2}^{(m)} = 0, F_{m−1}^{(m)} = 1.

These include the Fibonacci numbers (m = 2), Tribonacci numbers (m = 3), Tetranacci numbers (m = 4), Pentanacci numbers (m = 5), etc.

Generalizing the above-mentioned counting problems leads to convolutions of higherorder Fibonacci numbers. For example, it is not difficult to observe that the number of sequences of n coin tosses with no m consecutive heads is F_{n+m}^{(m)}. Consequently, the convolution

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

counts the number of sequences of length n−m+2 with exactly one occurrence of m successive heads: If the m heads occur on positions i − m + 2, …, i + 1, there are F_{i}^{(m)} ways to choose a prefix consisting of a sequence of length i − m followed by a tail, and F_{n−i}^{(m)} ways to choose a suffix beginning with a tail followed by a sequence of length n − i − m.

As far as we are aware, there are no explicit formulas for the self-convolutions of Fibonacci numbers of order m ≥ 4, and the goal of the present paper is to fill this gap. For our purposes, it will be more convenient to replace n by n + 2m − 2. Thus, recalling that F_{0}^{(m)} = F_{1}^{(m)} = ⋯ = F_{m−2}^{(m)} = 0, we will focus on sums of the form

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

A neat combinatorial interpretation of these numbers, which correspond to shifted selfconvolutions of higher-order Fibonacci numbers, was provided by Khadir et al. [11]: w_{n}^{(m)} is the number of tilings of a 1 × n board with linear polyominoes of length at most m having two different colors, where the first tile must have color 1. (Note that their result is more general, dealing with k-fold convolutions and k colors.)

Our goal is to find an explicit formula for w_{n}^{(m)}, and this will also lead to an explicit formula for ∑_{i=0}^{n} F_{i}^{(m)}F_{n−i}^{(m)}.

Figure 1: A tiling of a 1 × 9 board and an admissible walk.

We begin with an alternative combinatorial interpretation of w_{n}^{(m)}, which generalizes a tiling problem studied by Németh [14]. It is well known (and easy to verify by the standard last-tile argument) that the number of tilings of a 1 × n board by linear polyominoes of lengths 1, 2, …, m equals F_{n+m−1}^{(m)}. We claim that w_{n}^{(m)} is the number of shortest walks along the edges of such tilings starting in the lower left corner and terminating in the upper right corner. Hence, each walk consists of n unit steps to the right, exactly one unit step upwards, and the upward step must occur at a vertical grid line that is a boundary between tiles (cf. Figure 1). If the upward step occurs after j right-steps, then the tiles to the left of that step form a tiling of length j, and the tiles to the right form a tiling of length n − j. Hence there are F_{j+m−1}^{(m)} F_{n−j+m−1}^{(m)} such walks, and summing over j yields

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

Németh [14] deals with the case m = 2 (i.e., tilings with monominoes and dominoes) and does not mention the convolution formula. Instead, the author derives and solves a recurrence relation for w_{n}^{(2)}. The final formula agrees with the right-hand side of (1) in which n is replaced by n + 2m − 2 = n + 2, i.e.,

w_{n}^{(2)} = \frac{1}{5}((n + 1)F_{n+2} + (2n + 4)F_{n+1}) = \frac{1}{5}((n + 1)F_{n+3} + (n + 3)F_{n+1}).  (3)

Our plan is as follows: In Section 2, we extend Németh’s method [14] and derive a first-order linear nonhomogeneous recurrence relation for w_{n}^{(m)} (with m being fixed). In order to solve this recurrence, we will need to evaluate weighted Fibonacci sums of the form ∑_{k=0}^{n} q^{k}F_{k+l}^{(m)} and ∑_{k=0}^{n} kq^{k}F_{k+l}^{(m)}; we will achieve this goal using summation by parts in Section 3. In Section 4, we solve the earlier recurrence and obtain an explicit formula for w_{n}^{(m)}. In Section 5, we return to convolutions of the form ∑_{i=0}^{n} F_{i}^{(m)}F_{n−i}^{(m)}, write down the explicit formulas for small values on m, and identify the corresponding sequences in the OEIS. In Section 6, we return to counting walks in tiled boards. By distinguishing whether the upward step occurs at an even or odd position, we obtain new combinatorial proofs of additional convolution identities. Several open problems are discussed in the final Section 7.

There is an extensive literature dealing with other convolution-type identities involving the Fibonacci, Lucas, Tribonacci, Jacobsthal, Pell and similar numbers [3, 4, 5, 7, 8, 13].

2 A recurrence relation for the number of walks

Let m ∈ ℕ be fixed. In the present section, we derive a recurrence relation for w_{n}^{(m)}, the number of walks in the 1 × n rectangle tiled with linear polyominoes whose length does not exceed m. As in Figure 1, each walk partitions the board into two regions, a white region and a gray region. The walk is determined by the unique step upward.

We now express w_{n}^{(m)} in two different ways. For clarity, we begin with the case m = 2, and later extend the argument to a general m. To simplify notation, denote v_{n} = w_{n}^{(2)}.

One approach of counting the walks, described by Németh [14], is to condition on the last tile. If the last tile is a monomino, then there are v_{n−1} walks that reach the red point in the upper-right diagram in Figure 2, and a further F_{n} walks that reach the blue point and then continue with one step to the right and one step up. The case where the last tile is a domino can be analyzed in a similar manner, and we get the recurrence formula

v_{n} = v_{n−2} + F_{n−1} + v_{n−1} + F_{n} = v_{n−1} + v_{n−2} + F_{n+1}.  (4)

\begin{matrix}v_{n−2} \\ v_{n−1} \\ F_{n−1} \\ F_{n} \end{matrix}

Figure 2: Tiling and walks on a (1 × n)-board (reproduced from Németh [14]).

Here is a second way of calculating v_{n}. There are F_{n+1} possible tilings of the 1 × n rectangle. Given such a tiling, we may choose any of the n + 1 vertical grid lines as the position of the upward step of the walk. If the chosen position lies on a boundary between tiles, the upward step is feasible and we obtain a valid walk on the 1 × n board, contributing to v_{n}. Otherwise, the chosen position cuts through the interior of a domino, so the upward step is not allowed. In that case we remove this domino and place the upward step at its right endpoint; this produces a walk on a 1 × (n − 2) rectangle, and all such walks arise in this way. This reasoning yields the recurrence

v_{n} + v_{n−2} = (n + 1)F_{n+1}  (5)

By adding (4) and (5), we get a first-order linear nonhomogeneous recurrence for v_{n}:

2v_{n} − v_{n−1} = (n + 2)F_{n+1}.  (6)

Extending the preceding argument for a general m ∈ ℕ leads to the following recurrence relation.

Theorem 1. If w_{n}^{(m)} is the number of shortest walks in a 1 × n rectangle tiled with linear polyominoes whose size does not exceed m, then

(m + 1)w_{n+1}^{(m)} − 2m w_{n}^{(m)} = (n + m + 2)F_{n+m}^{(m)} − (n + m)F_{n+m−1}^{(m)}, n ∈ ℕ_{0}.  (7)

Proof. Again, we express w_{n}^{(m)} in two different ways.

First, distinguish the walk according to the length of the last tile. If the last tile has length k ∈ {1, 2, …, m}, then either the upward step occurs somewhere in the first n − k positions (giving a walk counted by w_{n−k}^{(m)}), or the walk is the unique “lower-boundary” walk determined by a tiling of length n − k (giving F_{n−k+m−1}^{(m)} possibilities). Summing over k gives

w_{n}^{(m)} = ∑_{k=1}^{m}(w_{n−k}^{(m)} + F_{n−k+m−1}^{(m)}) = ∑_{k=1}^{m} w_{n−k}^{(m)} + F_{n+m−1}^{(m)}.  (8)

Second, fix a tiling of the 1 × n board, and choose one of the n + 1 vertical grid lines as the position of the upward step. If the chosen line lies on a boundary between tiles, the upward step is feasible and we obtain a walk counted by w_{n}^{(m)}. Otherwise, if the line lies inside a tile of length l, then there are l − 1 interior vertical lines, and removing that tile and moving the step to its right endpoint produces a walk on a 1 × (n − l) board, counted by w_{n−l}^{(m)}. Therefore

w_{n}^{(m)} + ∑_{l=2}^{m}(l − 1) w_{n−l}^{(m)} = (n + 1) F_{n+m−1}^{(m)}.  (9)

The final task is to manipulate (8) and (9) to get a first-order recurrence relation for w_{n}^{(m)}. Subtracting (8) from its shifted version (with n replaced by n + 1), we get

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

Similarly, subtracting (9) from its shifted version (with n replaced by n + 1), we obtain

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

Using (8) to rewrite

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

and substituting into (11), we obtain

\begin{aligned}(n + 2)F_{n+m}^{(m)} − (n + 1)F_{n+m−1}^{(m)} & = w_{n+1}^{(m)} − w_{n}^{(m)} + w_{n}^{(m)} − F_{n+m−1}^{(m)} − m w_{n−m}^{(m)} \\ & = w_{n+1}^{(m)} − F_{n+m−1}^{(m)} − m w_{n−m}^{(m)}. \end{aligned}  (12)

Equivalently,

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

Multiplying (10) by m and adding (13) yields the recurrence (7).

3 Weighted sums with higher-order Fibonacci numbers

In order to solve the recurrence (7) and obtain an explicit formula for w_{n}^{(m)}, we will need to evaluate sums of the form

S(m, n, l, q) := ∑_{k=0}^{n} q^{k}F_{k+l}^{(m)},

where m ∈ ℕ, n ∈ ℕ_{0}, l ∈ ℤ, q ∈ ℝ. As shown by Slavík [17], weighted Fibonacci sums can be evaluated using summation by parts.

The following result might be of independent interest. The calculations in the present section do not depend on the choice of the initial values F_{0}^{(m)}, …, F_{m−1}^{(m)}; we only assume that the sequence (F_{n}^{(m)})_{n∈ℤ} satisfies

F_{n}^{(m)} = F_{n−1}^{(m)} + ⋯ + F_{n−m}^{(m)}, n ∈ ℤ.

Theorem 2. If q^{m+1} − 2q + 1 ≠ 0, then

S(m, n, l, q) = \frac{(q − 1) (q^{n+1}F_{n+l+1}^{(m)} − F_{l}^{(m)} + ∑_{i=1}^{m−1} (∑_{j=1}^{i} q^{i+1−j} (q^{n+1}F_{n+l−j+1}^{(m)} − F_{l−j}^{(m)})))}{q^{m+1} − 2q + 1}.

Proof. Recalling that the antidifference to q^{k} is q^{k}/(q − 1), summation by parts gives

S(m, n, l, q) = ∑_{k=0}^{n} q^{k}F_{k+l}^{(m)} = [\frac{q^{k}}{q − 1}F_{k+l}^{(m)}]_{k=0}^{n+1} − ∑_{k=0}^{n} \frac{q^{k+1}}{q − 1} (F_{k+l+1}^{(m)} − F_{k+l}^{(m)})

= \frac{1}{q − 1} (q^{n+1}F_{n+l+1}^{(m)} − F_{l}^{(m)} − ∑_{k=0}^{n} q^{k+1} ∑_{i=1}^{m−1} F_{k+l−i}^{(m)})

= \frac{1}{q − 1} (q^{n+1}F_{n+l+1}^{(m)} − F_{l}^{(m)} − ∑_{i=1}^{m−1} q^{i+1} ∑_{k=0}^{n} q^{k−i}F_{k+l−i}^{(m)})

= \frac{1}{q − 1} (q^{n+1}F_{n+l+1}^{(m)} − F_{l}^{(m)} − ∑_{i=1}^{m−1} q^{i+1} ∑_{k=−i}^{n−i} q^{k}F_{k+l}^{(m)})

= \frac{q^{n+1}F_{n+l+1}^{(m)} − F_{l}^{(m)} − ∑_{i=1}^{m−1} q^{i+1} (S(m, n, l, q) − ∑_{j=0}^{i−1} q^{n−j}F_{n+l−j}^{(m)} + ∑_{j=1}^{i} q^{−j}F_{l−j}^{(m)})}{q − 1}

= \frac{q^{n+1}F_{n+l+1}^{(m)} − F_{l}^{(m)} − S(m, n, l, q) ∑_{i=1}^{m−1} q^{i+1} + ∑_{i=1}^{m−1} (∑_{j=1}^{i} q^{i+1−j} (q^{n+1}F_{n+l−j+1}^{(m)} − F_{l−j}^{(m)}))}{q − 1}.

Solving this for S(m, n, l, q) yields

S(m, n, l, q) = \frac{q^{n+1}F_{n+l+1}^{(m)} − F_{l}^{(m)} + ∑_{i=1}^{m−1} (∑_{j=1}^{i} q^{i+1−j} (q^{n+1}F_{n+l−j+1}^{(m)} − F_{l−j}^{(m)}))}{(q − 1) (1 + ^{\frac{∑_{i=1}^{m−1} q^{i+1}}{q−1}} )},

and the proof is finished by a simple algebraic manipulation.

We will also need to evaluate sums of the form

S_{2}(m, n, l, q) = ∑_{k=0}^{n} kq^{k}F_{k+l}^{(m)},

where m ∈ ℕ, n ∈ ℕ_{0}, q ∈ ℝ, l ∈ ℤ. This is easily achieved by differentiating S(m, n, l, q) with respect to q; since

\frac{∂}{∂q} S(m, n, l, q) = ∑_{k=1}^{n} kq^{k−1}F_{k+l}^{(m)} = ∑_{k=0}^{n} kq^{k−1}F_{k+l}^{(m)},

we have

S_{2}(m, n, l, q) = q \frac{∂}{∂q} S(m, n, l, q).

Although it is not difficult to calculate the derivative on the right-hand side, the result is not particularly enlightening, so we prefer to keep the formula in the present simple form.

4 Explicit formula for the number of walks

After a brief digression, we return to the recurrence (7) for the number of paths in tiled boards, i.e.,

(m + 1)w_{n+1}^{(m)} − 2mw_{n}^{(m)} = (n + m + 2)F_{n+m}^{(m)} − (n + m)F_{n+m−1}^{(m)}, n ∈ ℕ_{0}, w_{0}^{(m)} = 1. (14)

We will express the solution in terms of the sums S and S_{2} introduced in the previous section.

Theorem 3. For each m ∈ ℕ, the solution of the recurrence (14) is given by

w_{n}^{(m)} = (\frac{2m}{m + 1})^{n} + \frac{(2m)^{n−1}}{(m + 1)^{n}} ((m + 2)S (m, n − 1, m, \frac{m + 1}{2m})

+ S_{2} (m, n − 1, m, \frac{m + 1}{2m}) − mS (m, n − 1, m − 1, \frac{m + 1}{2m})

− S_{2} (m, n − 1, m − 1, \frac{m + 1}{2m})), n ∈ ℕ_{0}.

Proof. The solution of the general first-order recurrence relation

a_{n+1} − αa_{n} = β_{n}, n ∈ ℕ_{0}, a_{0} = 1,  (15)

is given by

a_{n} = α^{n} + ∑_{k=0}^{n−1} α^{n−k−1}β_{k}

[6, formula (1.2.6)]. Our recurrence (14) is a special case of (15) with

α = \frac{2m}{m + 1}, β_{n} = \frac{n + m + 2}{m + 1}F_{n+m}^{(m)} − \frac{n + m}{m + 1}F_{n+m−1}^{(m)}.

Hence, the solution is

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

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

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

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

and the proof is finished by recalling the definitions of S and S_{2}.

5 Self-convolution identities

In the present section, we return to the standard m-the order Fibonacci sequence having the initial terms

F_{0}^{(m)} = ⋯ = F_{m−2}^{(m)} = 0, F_{m−1}^{(m)} = 1,

and study its self-convolutions. According to (2), we have

∑_{i=0}^{n} F_{i+m−1}^{(m)}F_{n−i+m−1}^{(m)} = w_{n}^{(m)},

where (w_{n}^{(m)})_{n=0}^{∞} satisfies the recurrence (14). Using the formula for w_{n}^{(m)} from the previous section, we get

∑_{i=0}^{n} F_{i+m−1}^{(m)}F_{n−i+m−1}^{(m)} = (\frac{2m}{m + 1})^{n} + \frac{(2m)^{n−1}}{(m + 1)^{n}} ((m + 2)S (m, n − 1, m, \frac{m + 1}{2m})

+ S_{2} (m, n − 1, m, \frac{m + 1}{2m}) − mS (m, n − 1, m − 1, \frac{m + 1}{2m})

− S_{2} (m, n − 1, m − 1, \frac{m + 1}{2m})).

It is perhaps more natural to replace n by n − 2m + 2, which yields the n-the term of the self-convolution of (F_{n}^{(m)})_{n=0}^{∞}, namely

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

= F_{0}^{(m)}F_{n}^{(m)} + ⋯ + F_{n}^{(m)}F_{0}^{(m)} = ∑_{i=0}^{n} F_{i}^{(m)}F_{n−i}^{(m)},

where we used the fact that F_{0}^{(m)} = ⋯ = F_{m−2}^{(m)} = 0. This leads to the following main result.

Theorem 4. For all m ∈ ℕ and n ∈ ℕ_{0}, we have

∑_{i=0}^{n} F_{i}^{(m)}F_{n−i}^{(m)} = w_{n−2m+2}^{(m)}

= (\frac{2m}{m + 1})^{n−2m+2} + \frac{(2m)^{n−2m+1}}{(m + 1)^{n−2m+2}} ((m + 2)S (m, n − 2m + 1, m, \frac{m + 1}{2m})

+ S_{2} (m, n − 2m + 1, m, \frac{m + 1}{2m}) − mS (m, n − 2m + 1, m − 1, \frac{m + 1}{2m})

− S_{2} (m, n − 2m + 1, m − 1, \frac{m + 1}{2m})).

Using the formulas for S and S_{2}, we can write down special cases of the previous identity for an arbitrary choice of m. We use Wolfram Mathematica to evaluate S and S_{2}, and to transform the resulting expression using the recurrence F_{j}^{(m)} = F_{j−1}^{(m)} + ⋯ + F_{j−m}^{(m)} so that it contains only those terms F_{j}^{(m)} with j ∈ {n − m + 1, …, n}.

For m = 2, we get the Fibonacci identity

F_{0}^{(2)}F_{n}^{(2)} + ⋯ + F_{n}^{(2)}F_{0}^{(2)} = \frac{1}{5}(2nF_{n−1}^{(2)} + (n − 1)F_{n}^{(2)}),

which is in agreement with (1), and whose sides correspond to the sequence \underline{A001629}. For m = 3, we get the Tribonacci identity

F_{0}^{(3)}F_{n}^{(3)} + ⋯ + F_{n}^{(3)}F_{0}^{(3)} = \frac{1}{22}((5n − 5)F_{n−2}^{(3)} + (n − 5)F_{n−1}^{(3)} + (2n − 4)F_{n}^{(3)}),

whose sides correspond to the sequence \underline{A073778}; the explicit formula (written in a slightly different form) was derived by Gryszka [9] using generating functions.

For m = 4, we get the Tetranacci identity

F_{0}^{(4)}F_{n}^{(4)} + ⋯ + F_{n}^{(4)}F_{0}^{(4)} = \frac{1}{563}((86n − 172)F_{n−3}^{(4)} + (−n − 85)F_{n−2}^{(4)} + (15n − 85)F_{n−1}^{(4)}
+ (25n − 75)F_{n}^{(4)}),

whose sides correspond to a shifted version of the sequence \underline{A118898}. The interpretation in terms of convolution and the explicit formula are new.

For m = 5, we get the new Pentanacci identity

F_{0}^{(5)}F_{n}^{(5)} + ⋯ + F_{n}^{(5)}F_{0}^{(5)} = \frac{1}{1198}((136n − 408)F_{n−4}^{(5)} + (−22n − 92)F_{n−3}^{(5)}
+ (3n − 117)F_{n−2}^{(5)} + (18n − 117)F_{n−1}^{(5)} + (27n − 108)F_{n}^{(5)}).

6 More bijections

As in Section 2, let v_{n} denote the number of shortest walks on a tiled 1 × n board with a single upward step allowed at an arbitrary position (along a vertical tile boundary). Then

v_{n} = e_{n} + o_{n},  (16)

where e_{n} is the number of walks with the upward step at an even position, and o_{n} is the number of walks with the upward step at an odd position. In the next lemma, we use bijections to establish relations between e_{n} and o_{n}.

Lemma 5. For every k ∈ ℕ, we have

e_{2k−1} = o_{2k−1},  (17)
e_{2k} = o_{2k} + F_{2k+2}.  (18)

Proof. For 1 × (2k − 1) rectangles, the horizontal flip is a bijection between tilings with an upward step at an even position and those with an upward step at an odd position. Hence,

(17) holds.

To prove (18), we rewrite it as

e_{2k} = o_{2k} + F_{2k} + F_{2k+1}.  (19)

We make the following observations concerning the terms on the right-hand side:

• F_{2k+1} counts all tilings of a 1 × 2k rectangle. This coincides with the number of walks in a tiled 1 × 2k rectangle whose upward step occurs at position 2k.

• F_{2k} counts all tilings of a 1 × (2k − 1) rectangle. For each tiling, let the last monomino (there is at least one) determine a walk by placing the upward step along its left border and replacing the monomino with a domino. This yields a walk in a 1 × 2k rectangle with an upward step at an even position less than 2k, followed only by dominoes. This defines a bijection, with the following inverse map: given a walk with the upward step at an even position less than 2k followed only by dominoes, replace the domino immediately after the upward step with a monomino and remove the walk.

• By definition, o_{2k} counts walks in a 1×2k rectangle whose upward step occurs at an odd position. For each walk, swap the upward step with the first monomino preceding it (there is at least one). This produces a walk with the upward step at an even position, followed by at least one monomino (cf. Figures 3 and 4). Again, this is a bijection, with the following inverse: for a walk with an upward step at an even position followed by at least one monomino, swap the upward step with the first monomino after it.

Hence, o_{2k} + F_{2k} + F_{2k+1} counts all walks in a 1 × 2k rectangle whose upward step occurs at an even position.

Figure 3: Upward step at odd position j and first preceding monomino between positions i and i + 1, where i is even.

Figure 4: After swap, the upward step is at even position i, and the monomino is between positions j − 1 and j.

We can now derive explicit formulas for e_{n} and o_{n}, keeping in mind that we have already established an explicit formula for v_{n}.

Theorem 6. For every k ∈ ℕ, we have

e_{2k−1} = o_{2k−1} = \frac{v_{2k−1}}{2} ,  (20)
e_{2k} = \frac{v_{2k} + F_{2k+2}}{2} , o_{2k} = \frac{v_{2k} − F_{2k+2}}{2} , .  (21)

Proof. The relations (20) follow from e_{2k−1} = o_{2k−1} and e_{2k−1} + o_{2k−1} = v_{2k−1}. Similarly, the relations (21) follow from e_{2k} − o_{2k} = F_{2k+2} and e_{2k} + o_{2k} = v_{2k}.

Note that e_{n} and o_{n} can also be counted in another way: once the position of the upward step in a walk is fixed, the left and right parts of the rectangle can be tiled arbitrarily. This gives the formulas

e_{2k} = ∑_{i=0}^{k} F_{2i+1}F_{2k−2i+1} = F_{1}F_{2k+1} + F_{3}F_{2k−1} + ⋯ + F_{2k+1}F_{1},

o_{2k} = ∑_{i=0}^{k−1} F_{2i+2}F_{2k−2i} = F_{2}F_{2k} + F_{4}F_{2k−2} + ⋯ + F_{2k}F_{2},

e_{2k−1} = ∑_{i=0}^{k−1} F_{2i+1}F_{2k−2i} = F_{1}F_{2k} + F_{3}F_{2k−2} + ⋯ + F_{2k}F_{1}.

Using the explicit formulas for e_{n} and o_{n} from Theorem 6, we can evaluate the convolutions on the right-hand sides. For example, recalling that v_{n} = w_{n}^{(2)} and using formula (3), we get

e_{2k} = \frac{v_{2k} + F_{2k+2}}{2} = \frac{\frac{1}{5} ((2k + 1)F_{2k+2} + (4k + 4)F_{2k+1}) + F_{2k+2}}{2}

= \frac{(2k + 2)F_{2k+1} + (k + 3)F_{2k+2}}{5} .

This result was obtained in our recent paper as a special case of an identity involving Chebyshev polynomials [16, Lemma A.2 and Corollary A.3]. We posed it as an open problem to prove this identity combinatorially, and here we accomplish this task.

All convolutions in the present section are special cases of the sums

∑_{i} G_{(k+1)i+1}G_{m−l(k+1)i},

which were evaluated by Czabarka et al. [2] using extensive computations with generating functions. Therefore, we believe that our combinatorial proofs, based on the bijections developed in Lemma 5, may be of independent interest.

7 Conclusion

Finally, we offer a list of possible projects for the interested reader:

• Find explicit formulas for k-fold convolutions of Fibonacci numbers of order m. Note that these convolutions have a natural combinatorial interpretation; see, for instance, the colored tiling model described by Khadir et al. [11].

• Investigate whether the methods of the present article extend to bracelet (annular) tilings. Do they yield explicit formulas for convolutions of higher-order Lucas numbers?

• Following Section 6, count the number of walks whose upward step occurs in an even or odd position, respectively. Assume that the rectangle is tiled not only by monominoes and dominoes, but also by trominoes or possibly longer polyominoes. This may lead to new identities involving Tribonacci or higher-order Fibonacci numbers. For instance, a numerical analysis of walks in the monomino-domino-tromino case appears to yield an analogue of Lemma 5, in which the difference between the numbers of even and odd walks is given by the sum of even-indexed Tribonacci numbers.

• It appears that the self-convolution formulas in Section 5 are related to the sequence whose initial terms are 1, 5, 44, 563, 9584, 205937, . . .. Up to sign, this is sequence \underline{A106273} from the OEIS, which gives the discriminants of the polynomials x^{m} −x^{m−1} − ⋯ − x − 1, that is, the characteristic polynomials of the recurrence defining Fibonacci numbers of order m. If the right-hand sides of the self-convolution identities are multiplied by these numbers, one obtains linear combinations of Fibonacci numbers of order m with integer coefficients. What explains this phenomenon?

References

[1] A. Bramham and M. Griffiths, Combinatorial interpretations of some convolution identities, Fibonacci Quart. 54 (2016), 335–339.

[2] É. Czabarka, R. Flórez, and L. Junes, A discrete convolution on the generalized Hosoya triangle, J. Integer Sequences 18 (2015), Article 15.1.6.

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

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

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

[6] S. Elaydi, An Introduction to Difference Equations. Third Edition, Springer, 2005.

[7] R. Frontczak and K. Gryszka, General convolution sums involving Fibonacci m-step numbers, J. Integer Sequences 27 (2024), Article 24.8.8.

[8] M. Griffiths, Fibonacci diagonals, Fibonacci Quart. 49 (2011), 51–56.

[9] K. Gryszka, A note on the self-convolution of the Tribonacci sequence, Notes Number Theory Discrete Math. 32 (2026), 133–136.

[10] V. E. Hoggatt and M. Bicknell-Johnson, Fibonacci convolution sequences, Fibonacci Quart. 15 (1977), 117–122.

[11] O. Khadir, L. Németh, and L. Szalay, Tiling of dominoes with ranked colors, Results Math. 79 (2024), Article 253.

[12] P. Moree, Convoluted convolved Fibonacci numbers, J. Integer Sequences 7 (2004), Article 04.2.2.

[13] D. Nacin, Fibonacci convolutions, Math. Mag. 96 (2023), 356–358.

[14] L. Németh, Walks on tiled boards, Math. Slovaca 74 (2024), 1369–1382.

[15] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2026. Available

    at https://oeis.org.

[16] J. Sedlák and A. Slavík, Resistance distances and Kirchhoff indices in graph joins, J. Phys. A 58 (2025), Article 505203.

[17] A. Slavík, Discrete calculus and weighted Fibonacci and Tribonacci sums, Amer. Math. Monthly 132 (2025), 622–633.

2020 Mathematics Subject Classification: Primary 11B39; Secondary 05A19, 11B37, 05B45, 52C20. Keywords: Fibonacci number, Tribonacci number, convolution, tiling.

(Concerned with sequences \underline{A001629}, \underline{A073778}, \underline{A106273}, \underline{A118898}.)

Received April 15 2026; revised versions received April 16 2026; May 29 2026; May 30 2026. Published in Journal of Integer Sequences, June 1 2026.

Return to Journal of Integer Sequences home page.