A Discrete Convolution on the Generalized Hosoya Triangle

Éva Czabarka Department of Mathematics University of South Carolina

Columbia, SC 29208

USA

czabarka@math.sc.edu

Rigoberto Flórez

Department of Mathematics and Computer Science

The Citadel Charleston, SC 29409

USA

rigo.florez@citadel.edu

Leandro Junes

Department of Mathematics, Computer Science and Information Systems

California University of Pennsylvania

California, PA 15419

USA

junes@calu.edu

Abstract

The generalized Hosoya triangle is an arrangement of numbers where each entry is a product of two generalized Fibonacci numbers. We define a discrete convolution C based on the entries of the generalized Hosoya triangle. We use C and generating functions to prove that the sum of every k-th entry in the n-th row or diagonal of generalized Hosoya triangle, beginning on the left with the first entry, is a linear combination of rational functions on Fibonacci numbers and Lucas numbers. A simple formula is given for a particular case of this convolution. We also show that C summarizes several sequences in the OEIS. As an application, we use our convolution to enumerate many statistics in combinatorics.

1 Introduction

The Hosoya triangle [3, 4, 5, 7, 9] consists of a triangular array of numbers where each entry is a product of two Fibonacci numbers (see Figure 3). If we use generalized Fibonacci numbers instead of Fibonacci numbers, then we obtain the generalized Hosoya triangle. Several authors have been interested in finite sums of products of Fibonacci numbers (see for example, [6, 9, 10]). The generalized Hosoya triangle is a good visualizing tool for the study of sums of products of generalized Fibonacci numbers, and in particular, for the study of finite sums of products of Fibonacci numbers and Lucas numbers.

We define a discrete convolution C as a finite sum of products of generalized Fibonacci numbers, and prove, using generating functions, that it is a linear combination of five rational functions on Fibonacci and Lucas numbers. The convolution depends on three variables m, l, and k, each of them having a geometric interpretation in terms of the generalized Hosoya triangle. Moreover, particular cases for the variables m, l, and k give known results found by several authors [6, 9, 10]. That is, our convolution generalizes the study of finite sums of products of Fibonacci and Lucas numbers. We also provide several examples where C enumerates statistics on Fibonacci words and non-decreasing Dyck paths. In addition, our convolution summarizes 15 distinct numeric sequences from The On-Line Encyclopedia of Integer Sequences.

The known results that are generalized by our convolution are as follows: in 2011 Griffiths [6, Thm. 3.1], using generating functions, gave a closed formula for the sum of all elements in the n-th diagonal of the Hosoya triangle. His result can be deduced from our first main result, Theorem 5, by taking m = n, l = 2, and k = 0. Similarly, Moree [10, Thm. 4] proves that

F_{n}F_{1} + F_{n−1}F_{2} + ⋯ + F_{2}F_{n−1} + F_{1}F_{n} = (nL_{n+1} + 2F_{n})/5.

This identity is a particular case of our second main result, Theorem 6, by taking m = n, l = 1, and k = 0.

Theorem 6 also relates the convolution C to several counting results. In particular, C can be used to count the number of elements in all subsets of {1, 2, …, n} with no consecutive integers, the number of binary sequences of length n with exactly one pair of consecutive 1’s, the total number of zeros in odd/even position for all Fibonacci binary words of length n and the total pyramid weight for all non-decreasing Dyck paths of length n, (see Section 5).

In addition to these enumerative applications, the convolution C “compactifies” a wide variety of numeric sequences into a single definition. The advantage of this “compactification” is that it provides a single closed formula (see Theorems 5 and 6) that might help in the study of several sequences. The authors suspect (based on numerical computations) that C summarizes more than the 15 sequences depicted in Table 1.

2 Preliminaries and examples

In this section we introduce notation and give some examples. We also give some definitions that will be used throughout the paper, some of which are well known, but we prefer to restate them here to avoid ambiguities.

2.1 The generalized Hosoya triangle

We let {G_{n}(a, b)}_{n∈ℕ} denote the generalized Fibonacci sequence with integers a and b. That is,

G_{1}(a, b) = a, G_{2}(a, b) = b, and G_{n}(a, b) = G_{n−1}(a, b) + G_{n−2}(a, b) for all n ∈ ℕ \ {1, 2}. (1)

If there is no ambiguity with a and b, then we let G_{n} denote the n-th term of the generalized Fibonacci sequence, instead of G_{n}(a, b). It is easy to see that G_{n}(1, 1) = F_{n}. The first eight terms of the generalized Fibonacci sequence with integers a and b are

a, b, a + b, a + 2b, 2a + 3b, 3a + 5b, 5a + 8b, and 8a + 13b.

Notice that every element in this sequence is a linear combination of the integers a and b with Fibonacci coefficients. In general, we have that G_{n} = a F_{n−2} + b F_{n−1} for all n ∈ ℕ. (See for example, [9, Thm. 7.1, p. 109].)

The generalized Hosoya sequence {H_{a,b}(r, k)}_{r≥k≥1} is defined by the double recursion

H_{a,b}(r, k) = H_{a,b}(r − 1, k) + H_{a,b}(r − 2, k)

and

H_{a,b}(r, k) = H_{a,b}(r − 1, k − 1) + H_{a,b}(r − 2, k − 2)

where r > 2 and 1 ≤ k ≤ r with initial conditions

H_{a,b}(1, 1) = a^{2}; H_{a,b}(2, 1) = ab; H_{a,b}(2, 2) = ab; H_{a,b}(3, 2) = b^{2}.

It is easy to see that if we let a = b = 1 in the generalized Hosoya sequence, then we obtain the regular Hosoya sequence {H(r, k)}_{r≥k≥1} as Koshy defined it [9, p. 187–188]. It is known that

H(r, k) = F_{k} F_{r−k+1}

for all natural numbers r, k such that k ≤ r; see [9, Ch. 15]. This and Proposition 1 show that the definition of {H_{a,b}(r, k)}_{r≥k≥1} is the right generalization for {H(r, k)}_{r≥k≥1}.

Proposition 1 ([4]). If r and k are natural numbers such that k ≤ r, then

H_{a,b}(r, k) = G_{k} G_{r−k+1},

for all integers a, b ∈ ℤ.

The generalized Hosoya sequence gives rise to the generalized Hosoya triangle that is defined as a vertex-weighted grid graph in the first quadrant of ℝ^{2} as follows: consider the grid formed by all points in the first quadrant of the xy-plane with natural numbers as coordinates. Every point/vertex (x, y) ∈ ℕ × ℕ has weight H_{a,b}(x + y − 1, y). Figure 1 depicts a finite portion of the generalized Hosoya triangle where the view of perspective is rotated 135^{∘} clockwise.

Figure 1: Generalized Hosoya triangle for weights H_{a,b}(r, k) with 1 ≤ k ≤ r ≤ 6.

We define the r-th row of the generalized Hosoya triangle as the collection of all the weights

{H_{a,b}(r, 1), H_{a,b}(r, 2), …, H_{a,b}(r, r − 1), H_{a,b}(r, r)}

with their corresponding vertices.

Proposition 1 shows that every weight of the generalized Hosoya triangle is the product of two generalized Fibonacci numbers. In particular, if we use Proposition 1 for all entries of Figure 1, we obtain Figure 2.

Thorough the rest of the paper we ignore the axes in any generalized Hosoya triangle figure.

Figure 2: The first six rows of the generalized Hosoya triangle.

We now give some examples of generalized Hosoya triangles. We can construct different triangles by fixing values for the integers a and b. Fixing a = b = 1 in (1) we obtain the Fibonacci sequence

G_{1} = 1, G_{2} = 1, G_{3} = 2, G_{4} = 3, G_{5} = 5, G_{6} = 8, …

Substituting these values in Figure 2, we obtain the regular Hosoya triangle. (See [3, 4, 5, 7, 9] and Figure 3.)

Fixing a = 7 and b = 2 in (1) we obtain the sequence

G_{1} = 7, G_{2} = 2, G_{3} = 9, G_{4} = 11, G_{5} = 20, G_{6} = 31, …

Substituting these values in Figure 2, we obtain a Hosoya triangle with a = 7 and b = 2. (See Figure 4 part (a).) Similarly, fixing a = 5 and b = 8 in (1) we obtain another numerical sequence

G_{1} = 5, G_{2} = 8, G_{3} = 13, G_{4} = 21, G_{5} = 34, G_{6} = 55, …

The Hosoya triangle generated by this new sequence is depicted in Figure 4 part (b).

2.2 Discrete convolution on the generalized Hosoya triangle

We let ⌈x⌉ denote the ceiling or least integer function of the real number x. We now define an operator C that will be called convolution, that acts on the weights of the generalized Figure 3: The first six rows of the regular Hosoya triangle.

Figure 4: Two generalized Hosoya triangles.

Hosoya triangle as follows: if l, m > 0 and k ≥ 0 are integers, then

C_{a,b}(m, l, k) = ∑_{i=0}^{⌈\frac{m}{l(k+1)}⌉−1} G_{(k+1)i+1}(a, b) · G_{m−l(k+1)i}(a, b).  (2)

If there is no ambiguity with the integers a and b, instead of (2), we write

C (m, l, k) = ∑_{i=0}^{⌈\frac{m}{l(k+1)}⌉−1} G_{(k+1)i+1} · G_{m−l(k+1)i}.

The convolution C_{a,b}(m, l, k) summarizes several sums of products of Fibonacci numbers, Lucas numbers, and has a geometric interpretation in terms of the vertices of the generalized Hosoya triangle.

We begin the study of the convolution C by discussing some examples. We first notice that {C_{1,1}(m, 1, 0)}_{m∈ℕ} is the sequence of Fibonacci numbers convolved with themselves. (See Sloane \underline{A001629} and [10].) Indeed,

C_{1,1}(m, 1, 0) = ∑_{i=0}^{m−1} F_{i+1} · F_{m−i} = F_{1} F_{m} + F_{2} F_{m−1} + ⋯ + F_{m} F_{1}.

Similarly, {C_{1,3}(m, 1, 0)}_{m∈ℕ} is the sequence of Lucas numbers convolved with themselves; see Sloane \underline{A004799}. In general, \{C_{a,b}(m, 1, 0)\}_{m∈ℕ} is the sequence of generalized Fibonacci numbers convolved with themselves. That is, C_{a,b}(m, 1, 0) is the sum of all entries in the m-th row of the generalized Hosoya triangle. For instance, in (3) these are the entries of the m-th row of the generalized Hosoya triangle.

G_{1} G_{m} G_{2} G_{m−1} G_{3} G_{m−2} ⋯ G_{m−2} G_{3} G_{m−1} G_{2} G_{m} G_{1}  (3)

We consider examples of C_{a,b}(m, 1, 0) for some values of a, b, and m. If we fix a = b = 1 and m = 6, then C_{1,1}(6, 1, 0) is the sum of all the weights of the 6-th row of Figure 3. That is,

C_{1,1}(6, 1, 0) = ∑_{i=0}^{5} F_{i+1} · F_{6−i} = 8 + 5 + 6 + 6 + 5 + 8 = 38.

If we fix a = 7, b = 2, and m = 5, then C_{7,2}(5, 1, 0) is the sum of all the weights of the 5-th row of Figure 4 part (a). Therefore,

C_{7,2}(5, 1, 0) = ∑_{i=0}^{4} G_{i+1}(7, 2) · G_{5−i}(7, 2) = 140 + 22 + 81 + 22 + 140 = 405.

We now give an interpretation to the convolution C_{a,b}(m, 1, k) for k ≥ 1 and fixed numbers a, b, and m. We first notice that

C_{a,b}(m, 1, 1) = ∑_{i=0}^{⌈\frac{m}{2}⌉−1} G_{2i+1} · G_{m−2i}.

That is, C_{a,b}(m, 1, 1) is the sum of all the weights in the m-th row of the generalized Hosoya triangle starting at G_{1} G_{m} and “jumping” one vertex. (See (3) for the m-th row of the generalized Hosoya triangle.) Similarly, it is easy to see that

C_{a,b}(m, 1, 2) = ∑_{i=0}^{⌈\frac{m}{3}⌉−1} G_{3i+1} · G_{m−3i}.

That is, C_{a,b}(m, 1, 2) is the sum of all the weights in the m-th row of the generalized Hosoya triangle starting at G_{1} G_{m} and “jumping” two vertices. In general, the convolution C_{a,b}(m, 1, k) for k ≥ 1, is the sum of all the weights in the m-th row of the generalized Hosoya triangle starting at G_{1} G_{m} and “jumping” k vertices. For instance, C_{1,1}(6, 1, 1) is the sum of the weights in the 6-th row in Figure 3 starting at F_{1} F_{6} = 8 and jumping one vertex. That is, the convolution C_{1,1}(6, 1, 1) is the sum of 8, 6, and 5. So,

C_{1,1}(6, 1, 1) = ∑_{i=0}^{2} F_{2i+1} · F_{6−2i} = 8 + 6 + 5 = 19.

Similarly, C_{5,8}(6, 1, 2) is the sum of the weights in the 6-th row in Figure 4 part (b) starting at G_{1} G_{6} = 275 and jumping two entries. Therefore,

C_{5,8}(6, 1, 2) = ∑_{i=0}^{1} G_{3i+1} · G_{6−3i} = 275 + 273 = 548.

Several sequences in Sloane [11] are summarized by the convolution C_{a,b}(m, 1, k). In particular, the sequences

{C_{1,1}(2n, 1, 1)}_{n∈ℕ}, {C_{1,3}(2n, 1, 1)}_{n∈ℕ}, {C_{2,1}(2n, 1, 1)}_{n∈ℕ}, and {C_{1,1}(2n − 1, 1, 1)}_{n∈ℕ}

correspond to \underline{A001870}, \underline{A061171}, \underline{A203574}, and \underline{A030267}, respectively.

We now give an interpretation to the convolution C_{a,b}(m, l, 0) for l ≥ 1 and fixed numbers a, b, and m. The convolution C_{a,b}(m, 1, 0) was already mentioned in page 7 and it is the sum of all the weights in the m-th row of the generalized Hosoya triangle. We consider the convolution C_{a,b}(m, 2, 0). It is easy to see that

C_{a,b}(m, 2, 0) = ∑_{i=0}^{⌈\frac{m}{2}⌉−1} G_{i+1} · G_{m−2i}.  (4)

We consider some particular values of m to visualize (4) in the generalized Hosoya triangle. If we set m = 3, m = 7, and m = 10 in (4), then

C_{a,b}(3, 2, 0) = ∑_{i=0}^{1} G_{i+1} · G_{3−2i} = G_{1} G_{3} + G_{2} G_{1},  (5)

C_{a,b}(7, 2, 0) = ∑_{i=0}^{3} G_{i+1} · G_{7−2i} = G_{1} G_{7} + G_{2} G_{5} + G_{3} G_{3} + G_{4} G_{1},  (6)

C_{a,b}(10, 2, 0) = ∑_{i=0}^{4} G_{i+1} · G_{10−2i} = G_{1} G_{10} + G_{2} G_{8} + G_{3} G_{6} + G_{4} G_{4} + G_{5} G_{2}. (7)

The convolutions (5), (6), and (7) are depicted in Figure 5.

Notice that C_{a,b}(3, 2, 0), C_{a,b}(7, 2, 0), and C_{a,b}(10, 2, 0) are the sums of all the weights over the main diagonals of the generalized Hosoya triangle that begin at G_{1} G_{3}, G_{1} G_{7}, and

Figure 5: The convolutions C_{a,b}(3, 2, 0), C_{a,b}(7, 2, 0), and C_{a,b}(10, 2, 0).

G_{1} G_{10}, respectively. In general, the convolution C_{a,b}(m, 2, 0) for m ≥ 3 is the sum of all the weights over the line of the generalized Hosoya triangle that passes through the vertices with coordinates (m, 1) and (m − 2, 2). If m ∈ {1, 2}, then C_{a,b}(m, 2, 0) = G_{1} G_{m}.

Some sequences in Sloane [11] are summarized by the convolution C_{a,b}(m, 2, 0). In particular, the sequences \{C_{1,1}(2n, 2, 0)\}_{n∈ℕ} and \{C_{1,1}(2n − 1, 2, 0)\}_{n∈ℕ} correspond to \underline{A056014} and \underline{A094292}, respectively. Griffiths [6] studied a particular case of C_{a,b}(m, 2, 0). Indeed, [6, Thm. 3.1] provides a closed formula for C_{1,1}(m, 2, 0). That is,

C_{1,1}(m, 2, 0) = \frac{1}{2} (F_{m+3} − F_{2⌊ \frac{m}{2} ⌋−⌊ \frac{m−5}{2} ⌋}) .

We prove a more general result in this article. We give a closed formula for C_{a,b}(m, l, k) for all integers a, b, m, l, k with l, m > 0 and k ≥ 0 (see Theorems 5 and 6).

We now consider the convolution C_{a,b}(m, 3, 0) for fixed numbers a, b, and m. It is easy to see that

C_{a,b}(m, 3, 0) = ∑_{i=0}^{⌈\frac{m}{3}⌉−1} G_{i+1} · G_{m−3i}.  (8)

We fix some particular values of m to visualize (8) in the generalized Hosoya triangle. If we set m = 3, m = 7, and m = 10 in (8), then

C_{a,b}(3, 3, 0) = ∑_{i=0}^{0} G_{i+1} · G_{3−3i} = G_{1} G_{3},  (9)

C_{a,b}(7, 3, 0) = ∑_{i=0}^{2} G_{i+1} · G_{7−3i} = G_{1} G_{7} + G_{2} G_{4} + G_{3} G_{1},  (10)

C_{a,b}(10, 3, 0) = ∑_{i=0}^{3} G_{i+1} · G_{10−3i} = G_{1} G_{10} + G_{2} G_{7} + G_{3} G_{4} + G_{4} G_{1}.  (11)

The convolutions (9), (10), and (11) are depicted in Figure 6.

Figure 6: The convolutions C_{a,b}(3, 3, 0), C_{a,b}(7, 3, 0), and C_{a,b}(10, 3, 0).

The convolutions C_{a,b}(7, 3, 0) and C_{a,b}(10, 3, 0) are the sums of all the weights over the line of the generalized Hosoya triangle that is determined by the pair of points ((7, 1), (4, 2)) and ((10, 1), (7, 2)), respectively. In general, the convolution C_{a,b}(m, 3, 0) for m ≥ 4 is the sum of all the weights over the line of the generalized Hosoya triangle that passes through the points (m, 1) and (m − 3, 2). If m ∈ {1, 2, 3}, then C_{a,b}(m, 3, 0) = G_{1} G_{m}.

We recall that in this paper the generalized Hosoya triangle as a grid is viewed in perspective and it is rotated 135^{∘} clockwise (see page 4). Notice that all lines in Figure 5, when l = 2, have slope −1/2 and all lines in Figure 5, when l = 3, have slope −1/3. Figure 7 depicts C_{a,b}(10, l, 0) for l ∈ {1, …, 4}.

We can now interpret C_{a,b}(m, l, 0) in terms of the generalized Hosoya triangle for every l ≥ 1. The convolution C_{a,b}(m, l, 0) for m ≥ l + 1 is the sum of all the weights over the line that passes through the points (m, 1) and (m − l, 2) in the generalized Hosoya triangle.

Figure 7: The convolutions C_{a,b}(10, l, 0) for l ∈ {1, …, 4}.

If m ∈ {1, …, l}, then C_{a,b}(m, l, 0) = G_{1} G_{m}. In general, if L′ is the line passing through the point (m, 1) with slope −1/l, then C_{a,b}(m, l, 0) = ∑_{(x,y)∈L′∩(ℕ×ℕ)} G_{x} · G_{y}, (see Figure 7). Notice that L′ ∩ (ℕ × ℕ) is a non-empty finite set of points (the point (m, 1) is always an element of L′ ∩ (ℕ × ℕ)) and the points are pairs of natural numbers.

Since we already have a geometric interpretation of C_{a,b}(m, l, 0) for l ≥ 1, the geometric interpretation of C_{a,b}(m, l, k) for k ≥ 1 follows easily. Indeed, C_{a,b}(m, l, k) = ∑_{(x,y)∈L′_{k}} G_{x}·G_{y} where L′_{k} ⊆ L′ ∩ (ℕ × ℕ), (m, 1) ∈ L′_{k}, and L′_{k} is obtained from L′ ∩ (ℕ × ℕ) by jumping k vertices starting at (m, 1). For instance, C_{a,b}(10, 2, 1) = ∑_{(x,y)∈L′_{1}} G_{x} · G_{y} where L′_{1} = {(10, 1), (6, 3), (2, 5)} (see Figure 7). Thus,

C_{a,b}(10, 2, 1) = G_{1} G_{10} + G_{3} G_{6} + G_{5} G_{2}.

Similarly, C_{a,b}(10, 1, 3) = ∑_{(x,y)∈L′_{3}} G_{x} · G_{y} where L′_{3} = {(10, 1), (6, 5), (2, 9)} (see Figure 7). Therefore,

C_{a,b}(10, 1, 3) = G_{1} G_{10} + G_{5} G_{6} + G_{9} G_{2}.

3 A closed formula for C (m, l, k)

In this section, we give a closed formula to calculate the convolution C (m, l, k) for l > 1. We recall that L_{n} represents the sequence of Lucas numbers. That is, L_{0} = 2, L_{1} = 1, and L_{n} = L_{n−1} + L_{n−2}, with n > 1. Some authors have found some useful results to determine the sums of products of Fibonacci numbers. For example, Griffiths [6] prove that the sum of the consecutive elements lying on the n-th main diagonal of the Hosoya triangle is a combination of Lucas and Fibonacci numbers (see Figure 5). In fact, his result can be calculated by C_{1,1}(m, 2, 0). Using ordinary generating functions, he proved that

C_{1,1}(m, 2, 0) = ∑_{i=0}^{⌈ \frac{m}{2} ⌉−1} F_{i+1}F_{m−2i} = \frac{1}{2} (F_{m+3} − F_{2⌊m/2⌋−⌊(m−5)/2⌋}) .  (12)

Moree [10] gives another example. He proved that the sum of the consecutive elements lying on the n-th row of the Hosoya triangle is a combination of Lucas and Fibonacci numbers. Thus,

C_{1,1}(m, 1, 0) = ∑_{i=0}^{m−1} F_{i+1}F_{m−i} = \frac{mL_{m+1} + 2F_{m}}{5} .  (13)

Notice that equations (12) and (13) use regular Fibonacci numbers, and their deduction follows from algebraic manipulations of basic generating functions. In contrast, the deduction of the closed formula for C_{a,b}(m, l, k) requires extensive calculations using generalized Fibonacci numbers. We use generating functions to prove that the convolution is an average of five terms. Each of those terms is a rational function on Lucas numbers.

We remind the reader of the following notation: let α and β be the positive and negative roots, respectively, of the quadratic equation x^{2} − x − 1 = 0. That is, α = (1 + \sqrt{5})/2, and β = (1 − \sqrt{5})/2. Note that αβ = −1. It is well known that F_{n} = (α^{n} − β^{n})/\sqrt{5} and L_{n} = α^{n} + β^{n} for all n ∈ ℤ. (See for example, [9, Thms. 5.6 and 5.8].)

Theorem 2 ([9]). If c = a + (a − b)β, d = a + (a − b)α, and n ∈ ℤ, then

G_{n} = \frac{cα^{n} − dβ^{n}}{\sqrt{5}} .

Proposition 3. If k, r, and n are non-negative integers and c = a+(a−b)β, d = a+(a−b)α, then

(i) c^{2}α^{n} + d^{2}β^{n} = a^{2}L_{n−4} + 2ab L_{n−3} + b^{2}L_{n−2},

(ii) ∑_{n=0}^{∞} G_{kn+r} x^{n} = \frac{1}{\sqrt{5}} [\frac{cα^{r}}{1 − α^{k} x} − \frac{dβ^{r}}{1 − β^{k} x}],

(iii) ∑_{n=0}^{∞} G_{kn+r} x^{n} = \frac{G_{r} + (−1)^{k+1}G_{r−k} x}{1 − L_{k} x + (−1)^{k} x^{2}},

(iv) If k > 0, then ∑_{n=0}^{∞} \frac{F_{k(n+1)}}{F_{k}} x^{n} = \frac{1}{1 − L_{k} x + (−1)^{k} x^{2}} .

Proof. We prove part (i) by induction on n. Let S(n) be the statement

a^{2}L_{n−4} + 2ab L_{n−3} + b^{2}L_{n−2} = c^{2}α^{n} + d^{2}β^{n}

for a non-negative integer n. It is easy to see that S(0) and S(1) are true. We suppose that S(n − 1) and S(n) are true for a fixed integer n ≥ 2 and prove that S(n + 1) is true. It is easy to see that using the recursive definition of Lucas numbers, S(n − 1), and S(n) we obtain

a^{2}L_{n−3} + 2ab L_{n−2} + b^{2}L_{n−1} = (c^{2}α^{n} + d^{2}β^{n}) + (c^{2}α^{n−1} + d^{2}β^{n−1})
= c^{2}α^{n−1}(α + 1) + d^{2}β^{n−1}(β + 1)
= c^{2}α^{n+1} + d^{2}β^{n+1}.

Thus, S(n + 1) is true.

We now prove part (ii). Using Theorem 2, we can see that

∑_{n=0}^{∞} G_{kn+r} x^{n} = ∑_{n=0}^{∞} \frac{cα^{kn+r} − dβ^{kn+r}}{\sqrt{5}} x^{n} = \frac{1}{\sqrt{5}} [cα^{r} ∑_{n=0}^{∞}(α^{k}x)^{n} − dβ^{r} ∑_{n=0}^{∞}(β^{k}x)^{n}] .

The proof now follows by noticing that ∑_{n=0}^{∞} y^{n} = \frac{1}{1 − y}.

We prove part (iii). Using part (ii), we can write

∑_{n=0}^{∞} G_{kn+r} x^{n} = \frac{1}{\sqrt{5}} [\frac{cα^{r}}{1 − α^{k}x} − \frac{dβ^{r}}{1 − β^{k}x}] = \frac{1}{\sqrt{5}} [\frac{cα^{r} − dβ^{r} + (dβ^{r}α^{k} − cα^{r}β^{k}) x}{1 − (α^{k} + β^{k})x + (αβ)^{k} x^{2}}] .

Since L_{k} = α^{k} + β^{k} and αβ = −1, we obtain that

∑_{n=0}^{∞} G_{kn+r} x^{n} = \frac{1}{\sqrt{5}} [\frac{cα^{r} − dβ^{r} + (dβ^{r}α^{k} − cα^{r}β^{k}) x}{1 − L_{k}x + (−1)^{k} x^{2}}]

= \frac{1}{\sqrt{5}} [\frac{cα^{r} − dβ^{r} − (αβ)^{k}(cα^{r−k} − dβ^{r−k}) x}{1 − L_{k}x + (−1)^{k} x^{2}}] .

The proof now follows by Theorem 2.

We now prove part (iv). Using part (iii) with a = b = 1 and r = 0 we can easily see that

∑_{n=0}^{∞} F_{kn} x^{n} = \frac{F_{0} + (−1)^{k+1}F_{−k} x}{1 − L_{k} x + (−1)^{k} x^{2}} = \frac{F_{k} x}{1 − L_{k} x + (−1)^{k} x^{2}} .

Dividing on both sides of this equality by F_{k} x, part (iv) follows.

Lemma 4. If k ≥ 0 and l > 0 are integers, then every natural number m can be written in the form m = l(k + 1)n + r where n ∈ ℤ_{≥0} and 0 < r ≤ l(k + 1). Moreover,

n = ⌈\frac{m}{l(k + 1)} − 1⌉ and r = m − ⌈\frac{m}{l(k + 1)} − 1⌉ l(k + 1).

Proof. Using the division algorithm with m and l(k + 1), there are n′ ∈ ℕ and r′ ∈ ℤ_{≥0} such that m = l(k + 1)n′ + r′ where 0 ≤ r′ < l(k + 1). If r′ > 0, then we can take n = n′ and r = r′. Thus, it is clear that m = l(k + 1)n + r and 0 < r < l(k + 1).

If r′ = 0, then m = l(k + 1)n′ = l(k + 1)(n′ − 1) + l(k + 1). Taking n = n′ − 1 and r = l(k + 1) we obtain that m = l(k + 1)n + r with 0 < r ≤ l(k + 1).

For the moreover part, we assume that m = l(k + 1)n + r where n ∈ ℤ_{≥0} and 0 < r ≤ l(k + 1). Therefore,

r = m − l(k + 1)n.  (14)

Thus, 0 < m−l(k +1)n ≤ l(k +1). This shows that \frac{m}{l(k + 1)} −1 ≤ n < \frac{m}{l(k + 1)}. Therefore,

n = ⌈\frac{m}{l(k+1)} − 1⌉. This and (14) prove the Lemma.

We now introduce some notation and definitions needed for Theorem 5. Suppose that m > 0, k ≥ 0, and l > 1 are integers. If

\begin{matrix}n = ⌈\frac{m}{l(k + 1)} − 1⌉; & r = m − l(k + 1)n; \\ w_{1} = (k + 1)(n − l + 1) + (r + 1); & w_{2} = m + 1; \\ w_{3} = (k + 1)n + (r + 1); & w_{4} = m + l(k + 1) − k; \\ w_{5} = (k + 1)(n + 1) − (k + r); & w_{6} = m + l(k + 1) + k; \\ w_{7} = (k + 1)(n + l + 1) − (r − 1); & w_{8} = m − 1, \end{matrix}

then we define

\begin{aligned}S_{1} & = cd [\frac{(−1)^{k+r}L_{w_{5}} − L_{w_{6}} + (−1)^{r}L_{w_{7}} + (−1)^{l(k+1)}L_{w_{8}}}{(−1)^{k+1} + (−1)^{l(k+1)} − L_{(l+1)(k+1)}} ] , \\ S_{2} & = \frac{a^{2}L_{w_{3}−4} + 2abL_{w_{3}−3} + b^{2}L_{w_{3}−2}}{(−1)^{(l+1)(k+1)} − L_{(l−1)(k+1)} + 1} , \\ S_{3} & = \frac{a^{2}L_{w_{1}−4} + 2abL_{w_{1}−3} + b^{2}L_{w_{1}−2}}{−1 + (−1)^{(l+1)(k+1)} (L_{(l−1)(k+1)} − 1)}, \end{aligned}

\begin{aligned}S_{4} & = \frac{a^{2}L_{w_{4}−4} + 2abL_{w_{4}−3} + b^{2}L_{w_{4}−2}}{(−1)^{l(k+1)+k} + L_{(l−1)(k+1)} − 1} , \\ S_{5} & = \frac{a^{2}L_{w_{2}−4} + 2abL_{w_{2}−3} + b^{2}L_{w_{2}−2}}{(−1)^{(l+1)(k+1)} + (−1)^{l(k+1)+k}L_{(l−1)(k+1)} + 1}. \end{aligned}

Theorem 5. If S_{1}, S_{2}, S_{3}, S_{4}, and S_{5} are as above, then

C (m, l, k) = \frac{S_{1} + S_{2} + S_{3} + S_{4} + S_{5}}{5} .

Proof. We prove the theorem by finding the generating function of the sequence C (m, l, k) with fixed positive integers k and l. We use Lemma 4 to simplify computations. That is, we let m = l(k + 1)n + r where n ∈ ℤ_{≥0} and 0 < r ≤ l(k + 1).

We consider the generating function of the sequence {C (l(k + 1)n + r, l, k)}_{n=0}^{∞} for fixed numbers r, l, and k. Using the definition of C (m, l, k) one can see that

C (l(k + 1)n + r, l, k) = ∑_{i=0}^{n} G_{(k+1)i+1} · G_{l(k+1)(n−i)+r}.

Therefore,

∑_{n=0}^{∞} C (l(k + 1)n + r, l, k) x^{n} = (∑_{n=0}^{∞} G_{(k+1)n+1} x^{n}) · (∑_{n=0}^{∞} G_{l(k+1)n+r} x^{n}) .

This and Proposition 3 part (ii) imply that the formal power series

∑_{n=0}^{∞} C (l(k + 1)n + r, l, k) x^{n}

is equal to

(15)

\frac{1}{5} [\frac{c^{2}α^{r+1}}{(1 − α^{k+1}x) (1 − α^{l(k+1)}x)} + \frac{d^{2}β^{r+1}}{(1 − β^{k+1}x) (1 − β^{l(k+1)}x)}

+ cd (\frac{β^{r−1}}{(1 − α^{k+1}x) (1 − β^{l(k+1)}x)} + \frac{α^{r−1}}{(1 − β^{k+1}x) (1 − α^{l(k+1)}x)})] .

We consider the term \frac{β^{r−1}}{(1 − α^{k+1}x)(1 − β^{l(k+1)}x)} of (15). Using partial fractions and ∑_{n=0}^{∞} x^{n} =

1/(1 − x), one can easily see that

\frac{β^{r−1}}{(1 − α^{k+1}x) (1 − β^{l(k+1)}x)} = \frac{β^{r−1}}{α^{k+1} − β^{l(k+1)}} [\frac{α^{k+1}}{1 − α^{k+1}x} − \frac{β^{l(k+1)}}{1 − β^{l(k+1)}x}]

= \frac{β^{r−1}}{α^{k+1} − β^{l(k+1)}} [α^{k+1} ∑_{n=0}^{∞} α^{n(k+1)}x^{n} − β^{l(k+1)} ∑_{n=0}^{∞} β^{l(k+1)n}x^{n}]

= ∑_{n=0}^{∞} β^{r−1} (\frac{α^{(k+1)(n+1)} − β^{l(k+1)(n+1)}}{α^{k+1} − β^{l(k+1)}} ) x^{n}.

That is,

\frac{β^{r−1}}{(1 − α^{k+1}x) (1 − β^{l(k+1)}x)} = ∑_{n=0}^{∞} β^{r−1} (\frac{α^{(k+1)(n+1)} − β^{l(k+1)(n+1)}}{α^{k+1} − β^{l(k+1)}} ) x^{n}.  (16)

Similarly, we get that

\frac{α^{r−1}}{(1 − β^{k+1}x) (1 − α^{l(k+1)}x)} = ∑_{n=0}^{∞} α^{r−1} (\frac{β^{(k+1)(n+1)} − α^{l(k+1)(n+1)}}{β^{k+1} − α^{l(k+1)}} ) x^{n}.  (17)

To simplify notation, we use u = k + 1, t = n + 1, v = k + r, s = t + l, and z = r − 1. Now, from (16) and (17) we have that

\frac{β^{r−1}}{(1 − α^{u}x) (1 − β^{lu}x)} + \frac{α^{r−1}}{(1 − β^{u}x) (1 − α^{lu}x)}

is equal to

∑_{n=0}^{∞} [β^{z} (\frac{α^{ut} − β^{lut}}{α^{u} − β^{lu}} ) + α^{z} (\frac{β^{ut} − α^{lut}}{β^{u} − α^{lu}} )] x^{n}

= ∑_{n=0}^{∞} [\frac{β^{z} (α^{ut} − β^{lut}) (β^{u} − α^{lu}) + α^{z} (β^{ut} − α^{lut}) (α^{u} − β^{lu})}{(α^{u} − β^{lu}) (β^{u} − α^{lu})}] x^{n}

= ∑_{n=0}^{∞} \frac{(β^{v}α^{ut} + α^{v}β^{ut}) − (β^{lut+v} + α^{lut+v}) − (β^{z}α^{us} + α^{z}β^{us}) + (β^{lut+z}α^{lu} + α^{lut+z}β^{lu})}{(−1)^{u} − (α^{(l+1)u} + β^{(l+1)u}) + (−1)^{lu}}x^{n}

= ∑_{n=0}^{∞} \frac{(αβ)^{v} (α^{ut−v} + β^{ut−v}) − L_{lut+v} − (αβ)^{z} (α^{us−z} + β^{us−z}) + (αβ)^{lu} (α^{lun+z} + β^{lun+z})}{(−1)^{u} + (−1)^{lu} − L_{(l+1)u}}x^{n}

= ∑_{n=0}^{∞} \frac{(−1)^{v}L_{ut−v} − L_{lut+v} − (−1)^{z}L_{us−z} + (−1)^{lu}L_{lun+z}}{(−1)^{u} + (−1)^{lu} − L_{(l+1)u}} x^{n}

= ∑_{n=0}^{∞} \frac{S_{1}}{cd} x^{n}.

Thus,

∑_{n=0}^{∞} \frac{S_{1}}{cd} x^{n} = \frac{β^{r−1}}{(1 − α^{k+1}x) (1 − β^{l(k+1)}x)} + \frac{α^{r−1}}{(1 − β^{k+1}x) (1 − α^{l(k+1)}x)}.  (18)

We now consider the terms

\frac{c^{2}α^{r+1}}{(1 − α^{k+1}x)(1 − α^{l(k+1)}x)} and \frac{d^{2}β^{r+1}}{(1 − β^{k+1}x) (1 − β^{l(k+1)}x)}

of (15). Using partial fractions and ∑_{n=0}^{∞} x^{n} = 1/(1 − x), one can easily write

\frac{c^{2}α^{r+1}}{(1 − α^{k+1}x) (1 − α^{l(k+1)}x)} = ∑_{n=0}^{∞} c^{2} \frac{α^{ut+r+1} − α^{lut+r+1}}{α^{u} − α^{lu}} x^{n} and  (19)
\frac{d^{2}β^{r+1}}{(1 − β^{k+1}x)(1 − β^{l(k+1)}x)} = ∑_{n=0}^{∞} d^{2} \frac{β^{ut+r+1} − β^{lut+r+1}}{β^{u} − β^{lu}} x^{n}.  (20)

To simplify notation, we use y = r + 1. From (19) and (20) we have that

\frac{c^{2}α^{r+1}}{(1 − α^{k+1}x)(1 − α^{l(k+1)}x)} + \frac{d^{2}β^{r+1}}{(1 − β^{k+1}x)(1 − β^{l(k+1)}x)}

is equal to

∑_{n=0}^{∞} \frac{c^{2} (α^{ut+y} − α^{lut+y}) (β^{u} − β^{lu}) + d^{2} (β^{ut+y} − β^{lut+y}) (α^{u} − α^{lu})}{(α^{u} − α^{lu}) (β^{u} − β^{lu})} x^{n}

= ∑_{n=0}^{∞} [\frac{(c^{2}α^{ut+y}β^{u} + d^{2}β^{ut+y}α^{u}) − (c^{2}α^{lut+y}β^{u} + d^{2}β^{lut+y}α^{u})}{(αβ)^{u} + (αβ)^{lu} − (α^{u}β^{lu} + α^{lu}β^{u})} +

\frac{− (c^{2}α^{ut+y}β^{lu} + d^{2}β^{ut+y}α^{lu}) + (c^{2}α^{lut+y}β^{lu} + d^{2}β^{lut+y}α^{lu})}{(αβ)^{u} + (αβ)^{lu} − (α^{u}β^{lu} + α^{lu}β^{u})} ] x^{n}

= ∑_{n=0}^{∞} [\frac{(αβ)^{u} (c^{2}α^{u(t−1)+y} + d^{2}β^{u(t−1)+y}) − (αβ)^{u} (c^{2}α^{u(lt−1)+y} + d^{2}β^{u(lt−1)+y})}{(αβ)^{u} + (αβ)^{lu} − (αβ)^{u} (β^{(l−1)u} + α^{(l−1)u})} +

\frac{− (αβ)^{lu} (c^{2}α^{u(t−l)+y} + d^{2}β^{u(t−l)+y}) + (αβ)^{lu} (c^{2}α^{lu(t−1)+y} + d^{2}β^{lu(t−1)+y})}{(αβ)^{u} + (αβ)^{lu} − (αβ)^{u} (β^{(l−1)u} + α^{(l−1)u})} ] x^{n}

= ∑_{n=0}^{∞} [\frac{(−1)^{u} (c^{2}α^{u(t−1)+y} + d^{2}β^{u(t−1)+y}) − (−1)^{u} (c^{2}α^{u(lt−1)+y} + d^{2}β^{u(lt−1)+y})}{(−1)^{u} + (−1)^{lu} − (−1)^{u} (β^{(l−1)u} + α^{(l−1)u})} +

\frac{− (−1)^{lu} (c^{2}α^{u(t−l)+y} + d^{2}β^{u(t−l)+y}) + (−1)^{lu} (c^{2}α^{lu(t−1)+y} + d^{2}β^{lu(t−1)+y})}{(−1)^{u} + (−1)^{lu} − (−1)^{u} (β^{(l−1)u} + α^{(l−1)u})} ] x^{n}.

This and Proposition (3) part (i) imply that

\frac{c^{2}α^{r+1}}{(1 − α^{k+1}x)(1 − α^{l(k+1)}x)} + \frac{d^{2}β^{r+1}}{(1 − β^{k+1}x)(1 − β^{l(k+1)}x)} = ∑_{n=0}^{∞} (S_{2} + S_{3} + S_{4} + S_{5}) x^{n}. (21)

Thus, (15), (18), and (21) imply that

∑_{n=0}^{∞} C (l(k + 1)n + r, l, k) x^{n} = ∑_{n=0}^{∞} (\frac{S_{1} + S_{2} + S_{3} + S_{4} + S_{5}}{5} ) x^{n}.

This proves the theorem.

Notice that the conclusion of Theorem 5 does not work when l = 1. The denominators of S_{2}, S_{3}, S_{4}, and S_{5}, are always zero when l = 1.

4 The special case C_{a,b}(m, 1, k)

In the previous section we gave a closed formula for C_{a,b}(m, l, k) where l > 1 is an integer. However, the formula cannot be applied when l = 1. The purpose of this section is to obtain a simple formula for the special case C_{a,b}(m, 1, k).

The convolution C_{1,1}(m, 1, k) can be use to enumerate several combinatorial objects. In particular, this convolution counts some types of Fibonacci words and pyramid weights of all non-decreasing Dyck paths of a given length; see [1, 2]. Section 5 gives detailed examples on how to apply the convolution in counting problems.

To simplify notation, we use C_{a,b}(m, k) to mean C_{a,b}(m, 1, k) or we use C (m, k) instead of C_{a,b}(m, 1, k), if there is no ambiguity with a and b.

Theorem 6 generalizes Moree’s result [10, Thm. 4] from the regular Hosoya triangle to the generalized Hosoya triangle. Moreover, our generalization also considers the sum (13) in the generalized Hosoya triangle “jumping” k vertices, for any k ≥ 0.

Theorem 6. Let k ≥ 0 and m > 0 be integers and let q = ⌈\frac{m}{k + 1}⌉. If r = m−(q−1)(k+1),

then

C (m, k) = \frac{q}{5} (a^{2}L_{m−3} + 2ab L_{m−2} + b^{2}L_{m−1}) + cd\frac{F_{q(k+1)}}{5F_{(k+1)}} L_{r−1} .

Proof. We prove this theorem using the same technique as in Theorem 5. That is, we find the generating function of the sequence C (m, k) with k fixed and use Lemma 4 to simplify computations.

Let m = (k + 1)n + r where n ∈ ℤ_{≥0} and 0 < r ≤ k + 1. We consider the generating function of the sequence {C ((k + 1)n + r, k)}_{n=0}^{∞} for fixed numbers r and k. Using the definition of C (m, k), one can see that

C ((k + 1)n + r, k) = ∑_{i=0}^{n} G_{(k+1)i+1} · G_{(k+1)(n−i)+r} .

Therefore,

∑_{n=0}^{∞} C ((k + 1)n + r, k) x^{n} = (∑_{n=0}^{∞} G_{(k+1)n+1} x^{n}) · (∑_{n=0}^{∞} G_{(k+1)n+r} x^{n}) .

This last equality and Proposition 3 part (ii) imply that

∑_{n=0}^{∞} C ((k + 1)n + r, k) x^{n} =\frac{1}{\sqrt{5}} [\frac{cα}{1 − α^{k+1}x} − \frac{dβ}{1 − β^{k+1}x}] \frac{1}{\sqrt{5}} [\frac{cα^{r}}{1 − α^{k+1}x} − \frac{dβ^{r}}{1 − β^{k+1}x}]

=\frac{1}{5} [\frac{c^{2}α^{r+1}}{(1 − α^{k+1}x)^{2}} + \frac{d^{2}β^{r+1}}{(1 − β^{k+1}x)^{2}} − \frac{cdαβ(α^{r−1} + β^{r−1})}{1 − L_{k+1}x + (−1)^{k+1}x^{2}} ] .

Since αβ = −1 and L_{r−1} = α^{r−1} + β^{r−1}, we obtain

∑_{n=0}^{∞} C ((k + 1)n + r, k) x^{n} = \frac{1}{5} [\frac{c^{2}α^{r+1}}{(1 − α^{k+1}x)^{2}} + \frac{d^{2}β^{r+1}}{(1 − β^{k+1}x)^{2}} + \frac{cdL_{r−1}}{1 − L_{k+1}x + (−1)^{k+1}x^{2}} ] .

This last equality, the Taylor series \frac{1}{(1 − ax)^{2}} = ∑_{n=0}^{∞}(n + 1)a^{n}x^{n}, and Proposition 3 part

(iv) imply that 5 ∑_{n=0}^{∞} C ((k + 1)n + r, k) x^{n} is equal to

c^{2}α^{r+1} ∑_{n=0}^{∞}(n + 1)α^{(k+1)n}x^{n} + d^{2}β^{r+1} ∑_{n=0}^{∞}(n + 1)β^{(k+1)n}x^{n} + cdL_{r−1} ∑_{n=0}^{∞} \frac{F_{(k+1)(n+1)}}{F_{k+1}} x^{n}

= ∑_{n=0}^{∞} [(n + 1)c^{2}α^{(k+1)n+r+1} + (n + 1)d^{2}β^{(k+1)n+r+1} + cdL_{r−1} \frac{F_{(k+1)(n+1)}}{F_{(k+1)}} ] x^{n}.

Thus,

5C ((k + 1)n + r, k) = (n + 1) (c^{2}α^{(k+1)n+r+1} + d^{2}β^{(k+1)n+r+1}) + cdL_{r−1} \frac{F_{(k+1)(n+1)}}{F_{(k+1)}} .

This and Proposition 3 part (i) imply that 5C ((k + 1)n + r, k) is equal to

(n + 1) (a^{2}L_{(k+1)n+r−3} + 2ab L_{(k+1)n+r−2} + b^{2}L_{(k+1)n+r−1}) + cdL_{r−1} \frac{F_{(k+1)(n+1)}}{F_{(k+1)}} .

Since m = (k + 1)n + r, Lemma 4 implies that

C (m, k) = \frac{q}{5} (a^{2}L_{m−3} + 2ab L_{m−2} + b^{2}L_{m−1}) + cd\frac{F_{q(k+1)}}{5F_{(k+1)}} L_{r−1} .

This proves the theorem.

5 Enumerative applications of C_{a,b}(m, l, k)

The convolution C_{a,b}(m, l, k) summarizes several sequences in [11], see for example, Table 1. Moreover, particular cases of our convolution can be use to enumerate many statistics in combinatorics. For instance, C_{1,1}(n, 0) is the number of elements in all subsets of {1, 2, …, n} with no consecutive integers. If we take n = 5, then we can easily see that all the subsets of {1, 2, 3, 4, 5} that have no consecutive elements are:

{}, {1}, {2}, {3}, {4}, {5}, {1, 3}, {1, 4}, {1, 5}, {2, 4}, {2, 5}, {3, 5}, {1, 3, 5},

and the total number of elements in all these subsets (counting repetitions) is 20 = C(5, 0).

The convolution C_{1,1}(n − 1, 0) counts also binary words. Indeed, if n ≥ 2 is a natural number, then C_{1,1}(n − 1, 0) is the number of binary sequences of length n with exactly one pair of consecutive 1’s. For instance, if n = 5, then all the binary sequences of length 5 with exactly one pair of consecutive 1’s are

\begin{matrix}11010; & 11001; & 11000; & 10110; & 10011; \\ 01101; & 01100; & 01011; & 00110; & 00011. \end{matrix}

The number of these binary sequences is 10 = C_{1,1}(4, 0). For more enumerative applications of C_{1,1}(n, 0) see Sloane \underline{A001629}.

Another familiar presentation of C_{1,1}(n, 0) is given in [9, p. 222] by

C_{1,1}(n, 0) = ∑_{2j≤n} j\binom{n − j}{j}.

Whoever is familiar with non-decreasing Dyck paths, should be interested in the following enumerative application of C_{1,1}(n, 1); see Proposition 7. For a reference and notation, see [1]. Proposition 7 can be proved easily using Theorem 6 and [1, Thm. 4.2].

Proposition 7. If n ∈ ℕ, then the sum of the weights of all pyramids in all non-decreasing Dyck paths of length 2n is C_{1,1}(2n − 1, 1) = (2nF_{2n+1} + (2 − n)F_{2n})/5.

We now discuss some enumerative applications of C_{1,1}(n, 1). A Fibonacci binary word consists of a strings of zeros and ones having no two zeros sub-words [8, 11]. In the example below, we can see that the total number of zeros in odd position for all Fibonacci binary words of length 4 is 5 = C_{1,1}(4, 1).

0110, 1101, 0111, 0101, 1111, 1110, 1011, 1010.

In general, the total number of zeros in odd position for all Fibonacci binary words of length n is C_{1,1}(n, 1); see Sloane \underline{A129720}. Similarly, the total number of zeros in even position for all Fibonacci binary words of length 4 is 5 = C_{1,1}(4, 1):

0110, 1101, 0111, 0101, 1111, 1110, 1011, 1010.

In general, the total number of zeros in even position for all Fibonacci binary words of length 2n is C_{1,1}(2n, 1); see Sloane \underline{A129722}.

The Fibonacci cube is a graph that has Fibonacci binary words as vertices, two vertices being adjacent whenever they differ in exactly one coordinate. Klavžar and Peterin [8] use C_{1,1}(n − 1, 0) to count the number of edges of the Fibonacci cube.

6 Acknowledgements

The second author was partially supported by The Citadel Foundation. The third author was supported by the FPDC travel grant at California University of Pennsylvania.

Convolution Sloane  Convolution  Sloane
C_{1,1}(n, 0)  \underline{A001629} C_{1,1}(2n − 1, 1) \underline{A030267}
C_{1,1}(2n, 1) \underline{A001870} C_{1,1}(2n + 1, 0) \underline{A054444}
C_{1,2}(n, 0)  \underline{A004798} C_{2,1}(2n − 1, 0) \underline{A203573}
C_{2,1}(n, 0)  \underline{A099924} C_{1,3}(2n − 1, 0) \underline{A060934}
C_{1,3}(n, 0)  \underline{A004799} C_{1,1}(2n, 2, 0)  \underline{A056014}
C_{1,3}(2n, 1) \underline{A061171} C_{1,1}(2n − 1, 2, 0) \underline{A094292}
C_{2,1}(2n, 1) \underline{A203574} C_{1,1}(2n, 1)  \underline{A129722}
C_{1,1}(n, 1)  \underline{A129720}

Table 1: Some sequences in [11] summarized by the convolution C_{a,b}(m, l, k).

References

[1] É. Czabarka, R. Flórez, and L. Junes, Some enumerations on non-decreasing Dyck paths, to appear.

[2] A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math. 137 (1995), 155–176.

[3] R. Flórez, R. Higuita, and A. Mukherjee, Alternating sums in the Hosoya polynomial triangle, J. Integer Seq., 17 (2014), Article 14.9.5.

[4] R. Flórez, R. Higuita, and L. Junes, GCD property of the generalized star of David in generalized Hosoya triangle, J. Integer Seq., 17 (2014), Article 14.3.6.

[5] R. Flórez and L. Junes, GCD properties in Hosoya’s triangle, Fibonacci Quart. 50 (2012), 163–174.

[6] M. Griffiths, Fibonacci diagonals, Fibonacci Quart. 10 (2011), 51–56.

[7] H. Hosoya, Fibonacci triangle, Fibonacci Quart. 14 (1976), 173–178.

[8] S. Klavžar and I. Peterin, Edge-counting vectors, Fibonacci cubes, and Fibonacci triangle. Publ. Math. Debrecen, 71 (2007), 267–278.

[9] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, 2001.

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

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

2010 Mathematics Subject Classification: Primary 11B39; Secondary 05A15. Keywords: Hosoya triangle, generalized Fibonacci number, convolution, non-decreasing Dyck path, Fibonacci binary word.

(Concerned with sequences \underline{A001629}, \underline{A001870}, \underline{A004798}, \underline{A004799}, \underline{A030267}, \underline{A054444}, \underline{A056014}, \underline{A060934}, \underline{A061171}, \underline{A094292}, \underline{A099924}, \underline{A129720}, \underline{A129722}, \underline{A203573}, and \underline{A203574}.)

Received August 24 2014; revised versions received September 16 2014; December 6 2014. Published in Journal of Integer Sequences, January 8 2015.

Return to Journal of Integer Sequences home page.