The 2-Pascal Triangle and a Related Riordan Array

Yassine Otmani Faculty of Mathematics USTHB, RECITS Laboratory P.O. Box 32 El Alia, 16111 Bab Ezzouar Algiers Algeria

     yotmani@usthb.dz and otmaniyassine93@gmail.com

Abstract

In this paper, we determine the structure of the 2-Pascal triangle and prove that it consists of even rows within a specific proper Riordan array. We provide the generating functions for two identities involving the coefficients of the triangle. As a consequence, we derive some combinatorial identities, including the generating functions for the sums of diagonal elements along a finite ray through the 2-Pascal triangle. Finally, we determine the inverse transform of the trinomial transform.

1 Introduction

Let F := ℝ[t] denote the set of formal power series over ℝ in the indeterminate t. We let F_{0} denote the set of all formal power series f(t) ∈ F in which f(0) ≠ 0, and by F_{1} = tF_{0} the set of formal power series f(t) ∈ F with f(0) = 0 and f′(0) ≠ 0. A Riordan array D := (d_{n,k})_{n,k≥0} is an infinite lower triangular matrix in which every entry is given by

d_{n,k} := [t^{n}]d(t)h(t)^{k},  (1)

where d(t) ∈ F and h(t) ∈ tF (see, for instance, [22, 27]). The notation [t^{k}]f(t) indicates the extraction coefficient of t^{k} in f(t) for every integer k. The operator [t^{k}] has many properties that are illustrated in [26, Section 1.2] and [20]; some of them are given below. Let f(t) := ∑_{k≥0} f_{k}t^{k} and g(t) := ∑_{k≥0} g_{k}t^{k}, where f and g are formal power series. The following statements hold.

(R1) Linearity [t^{n}](αf(t) + βg(t)) = α[t^{n}]f(t) + β[t^{n}]g(t);
(R2) Shifting  [t^{n}]t^{m}f(t) = [t^{n−m}]f(t);
(R3) Convolution  [t^{n}]f(t)g(t) = ∑_{k=0}^{n} f_{k}g_{n−k};

where m is an integer. According to (R2), for k > n, we have d_{n,k} = 0.

In addition, we use the notation D := R(d(t), h(t)). A good example of a Riordan array is the Pascal triangle P = (\binom{n}{k})_{n,k≥0} (\underline{A008277}), in which

\binom{n}{k} = [t^{n}]\frac{1}{1 − t} (\frac{t}{1 − t})^{k} ,  (2)

with the convention \binom{n}{k} = 0, for k < 0 and n > 0. It follows from (1) that d(t)h(t)^{k} is the generating function of k-column of the Riordan array D. It can also be characterized by the following bivariate generating function [27],

d(t, z) = ∑_{k≥0} d(t)h(t)^{k}z^{k} = \frac{d(t)}{1 − zh(t)}.

If d(t) ∈ F_{0} and h(t) ∈ F_{1} the Riordan array D is called proper. In the literature, there are numerous articles dealing with the theory of Riordan arrays. Let D_{1} = R(d_{1}(t), h_{1}(t)) and D_{2} = R(d_{2}(t), h_{2}(t)) be two Riordan arrays. We let D_{1} ∗ D_{2} denote the row-by-column product of two Riordan arrays. Then we have

D_{1} ∗ D_{2} = R(d_{1}(t)d_{2} (h_{1}(t)) , h_{2} (h_{1}(t))).

Let 𝔸 denote the set of proper Riordan arrays. The valuable algebraic property of proper Riordan arrays is the fact that the set 𝔸 with the usual matrix row-by-column product form a group called the Riordan group [24], where the identity element of the group is R(1, t), and for all R(d(t), h(t)) ∈ 𝔸 the inverse element is given as R^{−1}(d (1/h̄(t)) , h̄(t)), in which h̄(t) is the compositional inverse of h(t).

Rogers [22] discovered a fundamental characterization of Riordan arrays; he showed that for every proper Riordan array (d_{n,k})_{n,k≥0} there exists a sequence A = (a_{n})_{n≥0} (where a_{0} ≠ 0) such that for every n, k ∈ ℕ ∪ {0}, we have

d_{n+1,k+1} = ∑_{j=0}^{∞} a_{j}d_{n,k+j}.

This is called the A-sequence of the Riordan array. Let A(t) be the generating function of the sequence A. It follows that

h(t) = tA(h(t)),

as shown in [27, Theorem 1.3] and [19].

An important property pointed out by Sprugnoli [27, Theorem 1.1] is that the sums involving the product of rows of a Riordan array R(d(t), h(t)) by a sequence (f_{n})_{n≥0} can describe the coefficient of a formal power series relative to d(t), h(t) and f(t) (where f(t) is the generating function of the sequence (f_{n})_{n≥0}). This property can be stated as follows:

Theorem 1 (Sprugnoli [27]). Let d(t) and h(t) be formal power series with h ∈ tF. Let R(d(t), h(t)) = (d_{n,k})_{n,k≥0} be a Riordan array, and f(t) := ∑_{k≥0} f_{k}t^{k}. We have

∑_{k=0}^{n} d_{n,k}f_{k} = [t^{n}]d(t)f(h(t)).  (3)

A common example of this result is the Euler transformation

∑_{k=0}^{n} \binom{n}{k}f_{k} = [t^{n}]\frac{1}{1 − t}f (\frac{t}{1 − t}) .

Sprugnoli [27, Section 3] illustrated many applications of the Riordan array transformation (3), proving almost all identities in Gould’s book [15]. In particular, he proved the following generalizations that allow the treatment of many combinatorial formulas.

Theorem 2. Let n, m be nonnegative integers and x, a, b are integers and y is a complex number. If b − a ∈ ℕ, then

∑_{k} \binom{n + ak}{x + bk}f_{k} = [t^{n}]\frac{t^{x}}{(1 − t)^{x+1}} f (\frac{t^{b−a}}{(1 − t)^{b}} ) .  (4)

If b < 0, then

∑_{k} \binom{y + ak}{m + bk}f_{k} = [t^{m}](1 + t)^{y}f (t^{−b}(1 + t)^{a}) .  (5)

Let n be a nonnegative integer with s ∈ ℕ. The bi^{s}nomial coefficient \binom{n}{k}_{s} is defined by

\binom{n}{k}_{s} := \begin{cases}[t^{k}](1 + t + ⋯ + t^{s})^{n}, & if k ∈ \{0, 1, …, sn\}; \\ 0, & otherwise; \end{cases}  (6)

see Belbachir et al. [5] and Comtet [11, Page 77]. The bi^{s}nomial coefficient is a natural extension of the binomial coefficient. It appears that there are several representations and denominations of the bi^{s}nomial coefficients in the literature [7, Table 1]. Moreover, many combinatorial interpretations for the bi^{s}nomial coefficients are known. Freund [12] showed that the term \binom{n}{k}_{s} counts the number of different ways of distributing k objects among n cells where each cell contains at most s objects. In addition, one can see [2, 8].

We list below some of the important properties related to the bi^{s}nomial coefficient.

• The symmetric relation:

\binom{n}{k}_{s} = \binom{n}{sn − k}_{s}.

• The longitudinal recurrence relation:

\binom{n}{k}_{s} = \binom{n − 1}{k}_{s} + \binom{n − 1}{k − 1}_{s} + ⋯ + \binom{n − 1}{k − s}_{s}.

• The explicit form of bi^{s}nomial coefficient in the term of binomial coefficients:

\binom{n}{k}_{s} = ∑_{j_{1}+j_{2}+···+j_{s}=k} \binom{n}{j_{1}}\binom{j_{1}}{j_{2}} ⋯ \binom{j_{s−1}}{j_{s}}.  (7)

For more properties we refer to [6]. For s = 2 in (6), we obtain the bi^{2}nomial coefficients. Let z be a complex number, Comtet [11, Page 77] (see also [4, Section 4]) extends the bi^{s}nomial coefficient as

\binom{z}{k}_{s} = [t^{k}](1 + t + ⋯ + t^{s})^{z}.  (8)

Explicitly, we have

\binom{z}{k}_{s} = ∑_{\begin{matrix}j_{1}+j_{2}+···+j_{s}=k \\ j_{1}≥j_{2}≥···≥j_{s} \end{matrix}} \frac{z(z − 1) ⋯ (z − j_{1} + 1)}{(j_{1} − j_{2})!(j_{2} − j_{3})! ⋯ (j_{s−1} − j_{s})!j_{s}!}.  (9)

Relation (8) suggests the convention \binom{z}{k}_{s} = 0, for k ∉ ℕ ∪ \{0\}. The s-Pascal triangle (that is, the bi^{s}nomial coefficients arranged in triangle form) is an extension of Pascal’s triangle which, by the longitudinal recurrence relation 1, is constructed by the sum of s adjacent values in the preceding row with the constant term 1 in the first row (for s = 2 see Table 1). For s = 3, 4, 5 see \underline{A008287}, \underline{A035343}, \underline{A063260}, respectively.

n\k 0 1 2 3 4 5 6 7 8 9 10 11 12
0 1
1 1 1 1
2 1 2 3 2 1
3 1 3 6 7 6 3 1
4 1 4 10 16 19 16 10 4 1
5 1 5 15 30 45 51 45 30 15 5 1
6 1 6 21 50 90 126 141 126 90 50 21 6 1

Table 1: The 2-Pascal triangle (\underline{A027907}), also called the trinomial triangle.

The aim of the present paper is to study the structure of the 2-Pascal triangle. In particular, we provide the column generating functions of the 2-Pascal triangle, and furthermore, we give formulas similar to Eqs. (4) and (5) involving the bi^{2}nomial coefficients. Several other results are established.

The paper is organized as follows: in Section 2, we examine the bi^{2}nomial coefficient and determine a relationship between the 2-Pascal triangle and a proper Riordan array. In Section 3, we demonstrate two formulas similar to Eqs. (4) and (5) for the bi^{2}nomial coefficients. In Section 4, we investigate the formulas from Section 3 to derive several combinatorial identities. Sections 5 and 6 are devoted to studying particular cases of the formulas mentioned in Section 3. Finally, in Section 7, we provide the inverse transform of the trinomial transform [21].

2 The characterization of 2-Pascal triangle

In this section, we primarily derive a new generating function for the bi^{2}nomial coefficients. Furthermore, by investigating this generating function, we apply the Lagrange inversion formula to establish a connection between the 2-Pascal triangle and a proper Riordan array.

Theorem 3. Let n be a nonnegative integer and k be an integer. Then

\binom{n}{k}_{2} = [t^{2n}](1 − t + t^{2})^{n} \frac{1}{1 − t} (\frac{t}{1 − t})^{k} .  (10)

Proof. Let n be a nonnegative integer and k be an integer. Setting

a(n, k) = [t^{2n}](1 − t + t^{2})^{n} \frac{1}{1 − t} (\frac{t}{1 − t})^{k} .

Note that a(0, 0) = a(n, 2n) = 1. Additionally, for k > 2n or k < 0, we have a(n, k) = 0. Setting n ≥ 1 with k ≤ 2n, we obtain

a(n − 1, k) + a(n − 1, k − 1) + a(n − 1, k − 2)

= [t^{2(n−1)}](1 − t + t^{2})^{n−1} \frac{1}{1 − t} (\frac{t}{1 − t})^{k} + [t^{2(n−1)}](1 − t + t^{2})^{n−1} \frac{1}{1 − t} (\frac{t}{1 − t})^{k−1}

+ [t^{2(n−1)}](1 − t + t^{2})^{n−1} \frac{1}{1 − t} (\frac{t}{1 − t})^{k−2}

= [t^{2(n−1)}](1 − t + t^{2})^{n−1} \frac{1}{1 − t} (\frac{t}{1 − t})^{k−2} ((\frac{t}{1 − t})^{2} + \frac{t}{1 − t} + 1)

= [t^{2n}](1 − t + t^{2})^{n} \frac{1}{1 − t} (\frac{t}{1 − t})^{k}

= a(n, k).

One can observe that a(n, k) verified the same recurrence relation of bi^{2}nomial coefficient over ℤ. Hence, the proof is done.

Remark 4. Note that

a(n, k) = [t^{0}] (1 + \frac{1 − t}{t^{2}})^{n} \frac{1}{1 − t} (\frac{t}{1 − t})^{k}

= ∑_{j=0}^{n} \binom{n}{j}[t^{j}]\frac{t^{k−j}}{(1 − t)^{k−j+1}} .

Now from Eq. (2), it follows that

a(n, k) = ∑_{j=0}^{min(n,k)} \binom{n}{j}\binom{j}{k − j}.

In view of Eq. (7), for s = 2, we conclude

a(n, k) = \binom{n}{k}_{2}.

The Lagrange inversion formula [16, Thm. 1.2.4] is a remarkable tool for solving certain functional equations arise in combinatorial enumeration. The theorem stated as follows:

Theorem 5 (Lagrange inversion formula). Let F (t) be a formal power series and ϕ(t) ∈ F_{0}. We have

[t^{n}]F (t)ϕ(t)^{n} = [t^{n}] [\frac{F (w)}{1 − tϕ′(w)}| w = tϕ(w)] .  (11)

The notation [f(y)| y = g(t)] denotes the composition f(g(t)).

Let α(t) ∈ F_{0} and β(t) ∈ F_{1} defined as follows:

α(t) := −\frac{2 (2\sqrt{−t\sqrt{4 − 3t^{2}} − t^{2} + 2} + t^{2}\sqrt{8 − 6t^{2}} − t\sqrt{2})}{\sqrt{−t\sqrt{4 − 3t^{2}} − t^{2} + 2} (3t^{4} + 2t\sqrt{4 − 3t^{2}} − t^{2} − 4)},

β(t) := −\frac{t(t + \sqrt{4 − 3t^{2}})}{2t^{2} − 2}.

Theorem 6. Let n and k be nonnegative integers. Then

\binom{n}{k}_{2} = [t^{2n}]α(t) (β(t))^{k} .  (12)

Proof. From Theorem 3, the formula (10) can be rewritten as follows:

\binom{n}{k}_{2} = [t^{2n}] (\sqrt{1 − t + t^{2}})^{2n} \frac{1}{1 − t} (\frac{t}{1 − t})^{k} .

Setting ϕ(t) = \sqrt{1 − t + t^{2}} and F (t) = \frac{1}{1−t} (\frac{t}{1−t})^{k}. Solving the function equation w = tϕ(w), we obtain

w(t) = −\frac{t(−t + \sqrt{4 − 3t^{2}})}{2t^{2} − 2}.

Applying Eq. (11), and after simplifications, we deduce Eq. (12).

Obviously, the 2-Pascal triangle is a collection of even rows of the proper Riordan array R(α(t), β(t)) (see Table 2).

n\k 0  1  2  3 4 5 6 7 8
0  1
1  \frac{1}{2}  1
2  1  1  1
3  \frac{11}{16}  \frac{15}{8}  \frac{3}{2}  1
4  1  2  3  2 1
5 \frac{203}{256}  \frac{355}{128}  \frac{65}{16}  \frac{35}{8}  \frac{5}{2} 1
6  1  3  6  7 6 3 1
7 \frac{1759}{2048} \frac{3787}{1024} \frac{1953}{256} \frac{1435}{128} \frac{175}{16} \frac{63}{8}  \frac{7}{2} 1
8  1  4 10 16 19 16 10 4 1

Table 2: The Riordan array R(α(t), β(t)).

3 Combinatorial bi^{2}nomial identities

We demonstrated in the previous section how the generating function in Eq. (10) plays an important role in determining the relationship between the 2-Pascal triangle and the proper Riordan array R(α(t), β(t)). In this section, we further examine the generating function in Eq. (10), through which we establish formulas for bi^{2}nomial coefficients, as shown in Theorem 2. Additionally, we derive several new combinatorial identities.

Let n, m and k be nonnegative integers. Define

d_{n,k} := \binom{n + ak}{x + bk}_{2}and z_{m,k} := \binom{y + ak}{m + bk}_{2},

where a, b, x are integers and y is a complex number. For b−2a ∈ ℕ, the triangle (d_{n,k})_{n,k≥0} is an extension of 2-Pascal triangle. In addition, for b < 0, the triangle (z_{m,k})_{m,k≥0} is a Riordan array, in both cases we can apply the Riordan array transformation Eq. (3), in which we establish the following formulas.

Theorem 7. Let f(t) be the generating function of the sequence (f_{n})_{n≥0}.

• If b − 2a ∈ ℕ, then

∑_{k} \binom{n + ak}{x + bk}_{2}z^{2n−x+(2a−b)k}f_{k}

= [t^{2n}](1 − zt + (zt)^{2})^{n} \frac{t^{x}}{(1 − zt)^{x+1}} f (\frac{t^{b−2a}(1 − zt + (zt)^{2})^{a}}{(1 − zt)^{b}} ) .  (13)

• If b < 0, then

∑_{k} \binom{y + ak}{m + bk}_{2}z^{m+bk}f_{k} = [t^{m}](1 + zt + (zt)^{2})^{y}f (t^{−b}(1 + zt + (zt)^{2})^{a}) .  (14)

Proof. Recall that for all formal power series g(t) (see [26, (0TR), Page 7]), we have

[t^{n}]g(zt) = z^{n}[t^{n}]g(t).

From the formula (10), we obtain

\binom{n + ak}{x + bk}_{2}z^{2n−x+(2a−b)k} = z^{2n−x+(2a−b)k}[t^{2(n+ak)}](1 − t + t^{2})^{n+ak} \frac{1}{1 − t} (\frac{t}{1 − t})^{x+bk}

= [t^{2n}](1 − zt + (zt)^{2})^{n} \frac{t^{x}}{(1 − zt)^{x+1}} (\frac{t^{b−2a}}{(1 − zt + (zt)^{2})^{−a}(1 − zt)^{b}} )^{k} .

Assume that b − 2a ∈ ℕ. Then the n-th row of the triangle formed by bi^{2}nomial coefficients \binom{n+ak}{x+bk}_{2} is the 2n-th row of the Riordan array R (\frac{(1−zt+(zt)^{2})^{n}}{1−zt} (\frac{t}{1−zt})^{x} , \frac{t^{b−2a}}{(1−zt+(zt)^{2})^{−a}(1−zt)^{b}} ). Therefore, applying Theorem 1, we deduce the formula (13).

Now, suppose that b < 0. Hence

\binom{y + ak}{m + bk}_{2}z^{m+bk} = [t^{m+bk}](1 + zt + (zt)^{2})^{y+ak}
= [t^{m}](1 + zt + (zt)^{2})^{y} (t^{−b}(1 + zt + (zt)^{2})^{a})^{k} .

Thus, the triangle formed by the bi^{2}nomial coefficients \binom{y+ak}{m+bk}_{2} is exactly the Riordan array R ((1 + zt + (zt)^{2})^{y}, t^{−b}(1 + zt + (zt)^{2})^{a}). Again, using Theorem 1, we deduce the formula (14).

Example 8. Taking b = 3, x = 0 and f_{k} = 1 in (13), we get

∑_{k=0}^{⌊2n/3⌋} \binom{n}{3k}_{2} = [t^{2n}](1 − t + t^{2})^{n} [\frac{1}{1 − y} | y = \frac{t^{3}}{(1 − t)^{3}} ]

= [t^{2n}](1 − t + t^{2})^{n} \frac{(1 − t)^{2}}{(1 − 2t)(1 − t + t^{2})}

= [t^{2n−2}](1 − t + t^{2})^{n−1} \frac{1}{1 − 2t}

= ∑_{k=0}^{2(n−1)} \binom{n − 1}{k}_{2}(−1)^{k}2^{2(n−1)−k}

= 3^{n−1}.

It follows that

∑_{k=0}^{⌊2n/3⌋} \binom{n}{3k}_{2} = 3^{n−1}.

Similarly, we deduce that

∑_{k=0}^{⌊(2n−1)/3⌋} \binom{n}{3k + 1}_{2} = ∑_{k=0}^{⌊(2n−2)/3⌋} \binom{n}{3k + 2}_{2} = 3^{n−1}.

More generally, we establish the following result. Theorem 9. Let x ∈ ℤ^{+}, b ∈ ℕ and z be a complex number. If 0 ≤ x < b, then

∑_{k=0}^{⌊(2n−x)/b⌋} \binom{n}{x + bk}_{2}z^{x+bk} = z^{n} \frac{1}{b} ∑_{j=1}^{b} w_{b}^{j(n−x)} (1 + zw_{b}^{j} + (zw_{b}^{j})^{−1})^{n} ,  (15)

where w_{b} = exp (2iπ/b) with i^{2} = −1. Proof. Applying (13), for a = 0 and 0 ≤ x < b, substituting z with 1, and taking f_{k} = z^{x+bk}, we obtain

∑_{k≥0} \binom{n}{x + bk}_{2}z^{x+bk} = [t^{2n}](1 − t + t^{2})^{n} \frac{t^{x}}{(1 − t)^{x+1}} [\frac{z^{x}}{1 − z^{b}y} | y = \frac{t^{b}}{(1 − t)^{b}} ]

= [t^{2n}](1 − t + t^{2})^{n} \frac{(zt)^{x}(1 − t)^{b−x−1}}{(1 − t)^{b} − (zt)^{b}} .

Recall that the formal power series g(t) = \frac{(zt)^{x}(1−t)^{b−x−1}}{(1−t)^{b}−(zt)^{b}} is the generating function of lacunary sums of binomial coefficients (see [15, (1.53)] and [9, Section 4]). This implies that

∑_{k≥0} \binom{n}{x + bk}_{2}z^{x+bk} = \frac{1}{b} ∑_{k=0}^{2n} \binom{n}{k}_{2}(−1)^{k} ∑_{j=1}^{b}(w_{b}^{j})^{−x}(1 + zw_{b}^{j})^{2n−k}.

Thus,

∑_{k≥0} \binom{n}{x + bk}_{2}z^{x+bk} = \frac{1}{b} ∑_{j=1}^{b} w_{b}^{−jx} (1 − (1 + zw_{b}^{j}) + (1 + zw_{b}^{j})^{2})^{n}

= \frac{1}{b} ∑_{j=1}^{b} w_{b}^{−jx} (1 + zw_{b}^{j} + (zw_{b}^{j})^{2})^{n} .

This concludes the proof of the theorem.

Substituting z = 1 into (15) and using the fact 2 cos θ = (e^{iθ} + e^{−iθ}), we conclude that

∑_{k≥0} \binom{n}{x + bk}_{2} = \frac{1}{b} ∑_{j=1}^{b} (1 + 2 cos (\frac{2jπ}{b} ))^{n} cos (\frac{2j (n − x) π}{b} ) .  (16)

The lacunary sums of bi^{2}nomial coefficients (16) have been studied in various papers. Hoggatt et al. [14] examined the case b = 5. In addition, Hoggatt et al. [14] derived the lacunary sums for all bi^{s}nomial coefficients. Andrews [3, Eq. (2.18)] determined the case b = 10 for x = 0, 1, …, 5. Ni et al. [13, Thm. 1.1] obtained a new explicit form of (16) where they treated the case b = 12. To our knowledge, no one has dealt with the alternative case of lacunary sums of bi^{2}nomial coefficients. Let us examine some cases.

Corollary 10. Let n be a nonnegative integer. Then

3 ∑_{k≥0} \binom{n}{3k + x}_{2}(−1)^{k+x} = \begin{cases}(−1)^{n}2^{n+1} + 1, & if n ≡ x (mod 3); \\ (−1)^{n+1}2^{n} + 1, & if n ≡ x ± 1 (mod 3), \end{cases}  (17)

and

5 ∑_{k≥0} \binom{n}{5k + x}_{2}(−1)^{k+x} = \begin{cases}2(−1)^{n}L_{2n} + 1, & if n ≡ x (mod 5); \\ (−1)^{n+1}L_{2n+1} + 1, & if n ≡ x ± 1 (mod 5); \\ (−1)^{n}L_{2n−1} + 1, & if n ≡ x ± 2 (mod 5), \end{cases}  (18)

where (L_{n})_{n≥0} is the Lucas sequence (\underline{A000032}).

Proof. We prove only (18), since the same steps can be followed to prove the identity in (17). Taking b = 5 and z = −1 in (15), we obtain

∑_{k} \binom{n}{5k + x}_{2}(−1)^{k+x} = \frac{1}{5} ∑_{j=1}^{5} (2 cos (\frac{2jπ}{5} ) − 1)^{n} cos (\frac{2j(n − x)π}{5} ) .

Note that cos(2π/5) = cos(8π/5) = (\sqrt{5} − 1)/4 and cos(4π/5) = cos(6π/5) = −(\sqrt{5} + 1)/4. Now, if n − x ≡ 0 (mod 5), we get

∑_{k} \binom{n}{5k + x}_{2}(−1)^{k+x} = \frac{2}{5} (\frac{\sqrt{5} − 1}{2} − 1)^{n} + (−\frac{\sqrt{5} + 1}{2} − 1)^{n} + \frac{1}{5}

= \frac{1}{5}(2(−1)^{n}L_{2n} + 1).

Following the same steps we can easily prove the other cases modulo 5.

Let us now examine the case when b is an even number and z = −1 in (15).

Corollary 11. Let b be an even number. Then

∑_{k≥0} \binom{n}{x + bk}_{2}(−1)^{k} = \frac{1}{b} ∑_{j=1}^{b} cos (\frac{π(n − x)(1 + 2j)}{b}) (1 + 2 cos (\frac{π(2j + 1)}{b}))^{n} . (19)

Proof. Setting z = exp (iπ/b), where b is an even nonnegative integer. It follows that

∑_{k≥0} \binom{n}{x + bk}_{2}(−1)^{k} = z^{−x} ∑_{k≥0} \binom{n}{x + bk}_{2}z^{bk+x}.

In view of (15), we obtain

∑_{k≥0} \binom{n}{x + bk}_{2}(−1)^{k} = \frac{z^{n−x}}{b} ∑_{j=1}^{b} w_{b}^{j(n−x)}(1 + zw_{b}^{j} + (zw_{b}^{j})^{−1})^{n},

= \frac{z^{n−x}}{b} ∑_{j=1}^{b} w_{b}^{j(n−x)} (1 + 2 cos (\frac{π(2j + 1)}{b}))^{n} .

By simplifying the last line of the above equation, the proof is completed.

Example 12. The following identity holds:

∑_{k≥0} \binom{n}{4k + x}_{2}(−1)^{k} = \begin{cases}(−1)^{(n−x)/4}Q_{n}/2, & if n ≡ x (mod 4); \\ (−1)^{(n−x±1)/4}P_{n}, & if n ≡ x ∓ 1 (mod 4); \\ 0, & if n ≡ x + 2 (mod 4), \end{cases}  (20)

where (Q_{n})_{n≥0} is the Pell-Lucas sequence (\underline{A001333}), and (P_{n})_{n≥0} is the Pell sequence (\underline{A000129}).

Moreover, we find

∑_{k≥0} \binom{n}{6k + x}_{2}(−1)^{k} = \begin{cases}(−1)^{(n−x)/6}a_{n}, & if n ≡ x (mod 6); \\ (−1)^{(n−x∓1)/6}b_{n}, & if n ≡ x ± 1 (mod 6); \\ (−1)^{(n−x∓2)/6}c_{n−2}, & if n ≡ x ± 2 (mod 6); \\ 0, & if n ≡ x + 3 (mod 6), \end{cases}  (21)

where the sequences (a_{n})_{n≥0}, (b_{n})_{n≥0}, and (c_{n})_{n≥0} correspond exactly to \underline{A052948}, \underline{A002605}, and \underline{A077846}, respectively.

One can see that some amazing cases can be obtained from (19). Let us now examine the case when b = 2, x = a = 0 as in (13), as follows:

Corollary 13. Let z be an indeterminate and n be a nonnegative integer. Then

∑_{k≥0} \binom{n}{2k}_{2}z^{k} = \frac{(1 + \sqrt{z} + z)^{n} + (1 − \sqrt{z} + z)^{n}}{2} .  (22)

Proof. With the help of (13), we get

∑_{k≥0} \binom{n}{2k}_{2}z^{k} = [t^{2n}](1 − t + t^{2})^{n} \frac{1 − t}{1 − 2t + (1 + z)t}

= \frac{1}{2}[t^{2n}](1 − t + t^{2})^{n} (\frac{1}{1 − (1 − \sqrt{z})t} + \frac{1}{1 − (1 + \sqrt{z})t})

= \frac{(1 − (1 + \sqrt{z}) + (1 + \sqrt{z})^{2})^{n} + (1 − (1 − \sqrt{z}) + (1 − \sqrt{z})^{2})^{n}}{2} .

Simplifying the last line in the above equation completes the proof.

We let p_{n}(z) denote the left-hand side of identity (22). The polynomial p_{n}(z) verifies the following recurrence relation

p_{n}(z) = 2(z + 1)p_{n−1}(z) − (z^{2} + z + 1)p_{n−2}(z),  (23)

where p_{0}(z) = 1 and p_{1}(z) = z + 1. For z = 2, 3, 4, 5 we get \underline{A083878}, \underline{A083882}, \underline{A081336}, \underline{A152107}, respectively. The proof of (23) can be obtained easily by applying the right-hand side of (22).

Remark 14. Note that for all complex numbers λ and w, we have

[t^{2n}](1 − wt + (wt)^{2})^{n} \frac{1}{1 − λt} = (w^{2} − λw + λ^{2})^{n}.

By applying the same steps, we derive the following result.

Corollary 15. Let z be an indeterminate and n be a nonnegative integer. Then

q_{n}(z) := ∑_{k≥0} \binom{n}{2k + 1}_{2}z^{k} = \frac{(1 + \sqrt{z} + z)^{n} − (1 − \sqrt{z} + z)^{n}}{2\sqrt{z}} .

The polynomial q_{n}(x) satisfies the same recurrence (23) where the initial values are q_{0}(z) = 0 and q_{1}(z) = 1. The value z = 2 gives \underline{A081179}.

4 Some combinatorial identities

In this section, we focus on a distinct category of identities. We examine a number of cases where f_{k} relates to the binomial coefficients. Our first identify is as follows: Theorem 16. Let n and m be nonnegative integers. Then

∑_{k=m}^{2n} \binom{n}{k}_{2}\binom{k}{m}(−1)^{k} = \binom{n}{m}_{2}.

Proof. Applying (13), for a = x = 0, b = z = 1, and taking f_{k} = \binom{k}{m}(−1)^{k}, we find

∑_{k=m}^{2n} \binom{n}{k}_{2}\binom{k}{m}(−1)^{k} = [t^{2n}](1 − t + t^{2})^{n} \frac{1}{1 − t} [\frac{(−y)^{m}}{(1 + y)^{m+1}} | y = \frac{t}{1 − t}]
= (−1)^{m}[t^{2n−m}](1 − t + t^{2})^{n}.

This concludes the proof of the theorem. Theorem 17. Let n and m be nonnegative integers. Then

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

Proof. Applying (13), for a = x = 0, b = z = 1, and taking f_{k} = \binom{m}{k}, we get

∑_{k=0}^{m} \binom{n}{k}_{2}\binom{m}{k} = [t^{2n}](1 − t + t^{2})^{n} \frac{1}{1 − t} [(1 + y)^{m}| y = \frac{t}{1 − t}]

= [t^{2n}](1 − t + t^{2})^{n} \frac{1}{(1 − t)^{m+1}} .

Finally, by convolution product the proof is done. Theorem 18. Let n and m be nonnegative integers. If n ≤ m, then

∑_{k=0}^{n} \binom{n − k}{m}_{2}\binom{n}{k}(−1)^{k} = \binom{n}{m − n}.

Proof. In view of (13), for a = −z = 1, b = 0, and substituting x with m, let f_{k} = \binom{n}{k}, we obtain

∑_{k=0}^{n} \binom{n − k}{m}_{2}\binom{n}{k}(−1)^{k} = [t^{2n}](1 − t + t^{2})^{n} \frac{t^{m}}{(1 − t)^{m+1}} [(1 − y)^{n}| y = \frac{t^{2}}{1 − t + t^{2}} ]

= [t^{2n}]\frac{t^{m}}{(1 − t)^{m−n+1}} .

Finally, applying (R2) (see Page 2) and using the formula (2), we complete the proof.

Theorem 19. Let n be a nonnegative integer. Then

∑_{k=0}^{n} \binom{2n − 2k}{n}_{2}\binom{n}{k}(−1)^{k} = 2^{n}.

Proof. In view of (13), for a = −2, z = 1, b = 0, and substituting x with n, let f_{k} = \binom{n}{k}(−1)^{k}, we find

∑_{k=0}^{n} \binom{2n − 2k}{n}_{2}\binom{n}{k}(−1)^{k} = [t^{4n}](1 − t + t^{2})^{2n} \frac{t^{n}}{(1 − t)^{n+1}} [(1 − y)^{n}| y = \frac{t^{4}}{(1 − t + t^{2})^{2}} ]

= [t^{3n}]\frac{((1 − t)^{n}(1 − t + 2t^{2}))^{n}}{(1 − t)^{n+1}}

= [t^{3n}]\frac{(1 − t + 2t^{2})^{n}}{1 − t} .

By convolution product, we obtain

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

= ∑_{j=0}^{n} \binom{n}{j} ∑_{k=j}^{3n} \binom{j}{k − j}2^{k−j}(−1)^{k}.

Observe that for j = 0, 1, …, n, we have 3n > 2j. Hence

∑_{k=j}^{3n} \binom{j}{k − j}2^{k−j}(−1)^{k} = ∑_{k=j}^{2j} \binom{j}{k − j}2^{k−j}(−1)^{k}

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

Now, in view of binomial theorem, we conclude

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

The proof is done.

In what follows, we present a theorem similar to Vandermonde’s convolution identity [15, (3.20)].

Theorem 20. Let n and m be nonnegative integers and l be an integer. Then

∑_{k=0}^{2m} \binom{n}{l + k}_{2}\binom{m}{k}_{2} = \binom{n + m}{2m + l}_{2}.  (24)

Proof. Applying (13), for a = 0, b = z = 1, substituting x with l, and taking f_{k} = \binom{m}{k}_{2}, we find

∑_{k=0}^{2m} \binom{n}{l + k}_{2}\binom{m}{k}_{2} = [t^{2n}](1 − t + t^{2})^{n} \frac{t^{l}}{(1 − t)^{l+1}} [(1 + y + y^{2})^{m}| y = \frac{t}{1 − t}]

= [t^{2n}](1 − t + t^{2})^{n+m} \frac{t^{l}}{(1 − t)^{2m+l+1}} .

Finally, multiplying and dividing by t^{2m}, and then using (10), we conclude (24).

Let us now examine some cases of the formula (14). We obtain the results below.

Theorem 21. Let x and y be two complex numbers and n be a nonnegative integer. Then the following identities hold:

∑_{k=0}^{n} \binom{2x}{n − k}_{2}\binom{y − 2x}{k}(−1)^{n−k} = ∑_{k=0}^{⌊n/3⌋} \binom{x}{k}\binom{y − 3x}{n − 3k} = ∑_{k=0}^{n} \binom{x}{k}\binom{y − 2k}{n − k}(−3)^{k}, (25)

∑_{k=0}^{⌊n/3⌋} \binom{−x}{n − 3k}_{2}\binom{x}{k}(−1)^{k} = (−1)^{n}\binom{x}{n}.  (26)

Proof. In view of (14), for a = 0, b = z = −1, substituting y with 2x and m with n, and taking f_{k} = \binom{y−2x}{k}, we obtain

∑_{k=0}^{n} \binom{2x}{n − k}_{2}\binom{y − 2x}{k}(−1)^{n−k} = [t^{n}](1 − t + t^{2})^{2x} [(1 + w)^{y−2x}| w = t]
= [t^{n}](1 − t + t^{2})^{2x}(1 + t)^{y−2x}.

For the right-hand side of (25), we use the formula (5), which gives the same generating function as the one in the above identity.

Similarly, using (14), for a = 0, b = −3, z = 1, substituting y with −x and m with n, and taking f_{k} = \binom{x}{k}(−1)^{k}, we find

∑_{k=0}^{⌊n/3⌋} \binom{−x}{n − 3k}_{2}\binom{x}{k}(−1)^{k} = [t^{n}](1 + t + t^{2})^{−x} [(1 − y)^{x}| y = t^{3}]
= [t^{n}](1 − t)^{x}.

Hence, the proof of (26) is finished.

Remark 22. The right-hand side of (25) is the identity [15, (3.51)].

The next identity represents the extended form of the identity [15, (3.42)] to the bi^{2}nomial coefficients.

Theorem 23. Let x be a complex number and n be a nonnegative integer. Then

∑_{k=0}^{n} \binom{2n − x}{n − k}_{2}\binom{x}{k}_{2}(−1)^{k} = ∑_{k=0}^{⌊n/2⌋} \binom{2n − 2x}{n − 2k}_{2}\binom{x}{k}_{2}.

Proof. Applying (14), for a = 0, b = −z = −1, substituting y with 2n − x and m with n, and taking f_{k} = \binom{x}{k}_{2}(−1)^{k}, we obtain

∑_{k=0}^{n} \binom{2n − x}{n − k}_{2}\binom{x}{k}_{2}(−1)^{k} = [t^{n}](1 + t + t^{2})^{2n−x} [(1 − y + y^{2})^{x}| y = t]
= [t^{n}](1 + t + t^{2})^{2n−x}(1 − t + t^{2})^{x}.

Alternatively, we find

∑_{k=0}^{⌊n/2⌋} \binom{2n − 2x}{n − 2k}_{2}\binom{x}{k}_{2} = [t^{n}](1 + t + t^{2})^{2n−2x} [(1 + y + y^{2})^{x}| y = t^{2}]
= [t^{n}](1 + t + t^{2})^{2n−2x}(1 + t^{2} + t^{4})^{x}
= [t^{n}](1 + t + t^{2})^{2n−2x}(1 + t + t^{2})^{x}(1 − t + t^{2})^{x}
= [t^{n}](1 + t + t^{2})^{2n−x}(1 − t + t^{2})^{x}.

This concludes the proof of the theorem.

Theorem 24. Let n be a nonnegative integer. Then

∑_{k=0}^{2n} \binom{n}{k}_{2}^{2}(−1)^{k} = \binom{n}{n}_{2}.  (27)

Proof. Using (14), for a = 0, b = −z = −1, substituting y with n and m with 2n, and taking f_{k} = \binom{n}{k}_{2}(−1)^{k}, we find

∑_{k=0}^{2n} \binom{n}{k}_{2}^{2}(−1)^{k} = ∑_{k=0}^{2n} \binom{n}{2n − k}_{2}\binom{n}{k}_{2}(−1)^{k}
= [t^{2n}](1 + t + t^{2})^{n} [(1 − y + y^{2})^{n}| y = t]
= [t^{2n}](1 + t^{2} + t^{4})^{n}.

Then the proof is done.

Remark 25. The identity (27) may be shown as an extended form of the identity (3.81) in Gould’s book [15].

Finally, we extend the Identities (3.70) and (3.72) in Gould’s book [15] to bi^{2}nomial coefficients as next.

Theorem 26. If n be a nonnegative integer, then the following identities hold:

∑_{k=0}^{n} \binom{n}{2k}_{2}^{2} = \frac{1}{2}\binom{2n}{2n}_{2} + \frac{1}{2}\binom{n}{n}_{2},  (28)

∑_{k=0}^{⌊n/2⌋} \binom{n}{n − 2k}_{2}\binom{n}{2k}_{2} = \frac{1}{2}\binom{2n}{n}_{2} + \frac{1}{2}\binom{n}{n/2}_{2}.  (29)

Proof. One can observe that

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

Using the generating function (22) and the formula (14), for a = 0, b = −2, z = 1, substituting y with n and m with 2n, and taking f_{k} = \binom{n}{2k}_{2}, we obtain

∑_{k=0}^{n} \binom{n}{2k}_{2}^{2} = [t^{2n}](1 + t + t^{2})^{n} [\frac{(1 + \sqrt{y} + y)^{n} + (1 − \sqrt{y} + y)^{n}}{2} | y = t^{2}]

= \frac{1}{2}[t^{2n}](1 + t + t^{2})^{2n} + \frac{1}{2}[t^{2n}](1 + t^{2} + t^{4})^{n}.

Hence, the proof of (28) is done. The identity (29) follows by the same steps.

5 On the combinatorial sums involving the diagonal elements of the 2-Pascal triangle

The purpose of this section is to study some combinatorial identities involving the diagonal elements of the 2-Pascal triangle by investigating the formula (13).

Let (y_{n})_{n≥0} be a sequence (\underline{A077943}) defined by

y_{n} = 2y_{n−1} − 2y_{n−2} + 2y_{n−3}, where y_{0} = y_{1} = 0 and y_{2} = 1.

The characteristic polynomial p of the sequence (y_{n})_{n≥0} gives p (t) = t^{3} − 2t^{2} + 2t − 2. Let α, β, \overline{β} be the zeros of p, where \overline{β} is the complex conjugate of β. By applying Cardan’s formulas to p, we obtain

α = \frac{1}{3} (2 + (17 − 3\sqrt{33})^{1/3} − (−17 + 3\sqrt{33})^{1/3}) ,
β = \frac{1}{6} (4 + (1 + i\sqrt{3})(−17 + 3\sqrt{33})^{1/3} − (1 − i\sqrt{3})(17 + 3\sqrt{33})^{1/3}) .

Therefore

y_{n} = \frac{α^{n}}{(α − β)(α − \overline{β})} + \frac{β^{n}}{(β − α)(β − \overline{β})} + \frac{\overline{β}^{n}}{(\overline{β} − α)(\overline{β} − β)}.  (30)

The formula (30) is called the Binet formula of the sequence (y_{n})_{n≥0}.

It is well-known that the Tribonacci sequence (T_{n})_{n≥0} (\underline{A000073}) defined by

T_{n} = T_{n−1} + T_{n−2} + T_{n−3}, where T_{0} = T_{1} = 0 and T_{2} = 1.

Furthermore, the Tribonacci numbers appear as the sums of the diagonals of the 2-Pascal triangle. In the formula (13), the Tribonacci numbers follow the direction b = −a = 1 for f_{k} = 1, yielding the following identity.

Theorem 27. Let n be a nonnegative integer. Then

T_{n+2} = \frac{1}{2^{n+1}} y_{3(n+1)}.

Proof. From (13), setting x = 0, b = −a = 1, and taking f_{k} = 1, it follows that

T_{n+2} = ∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2}

= [t^{2n}](1 − t + t^{2})^{n} \frac{1}{1 − t} [\frac{1}{1 − y} | y = \frac{t^{3}}{(1 − t)(1 − t + t^{2})}]

= [t^{2n}](1 − t + t^{2})^{n+1} \frac{1}{(1 − t)(1 − t + t^{2}) − t^{3}}

= [t^{2(n+1)}](1 − t + t^{2})^{n+1} \frac{t^{2}}{1 − 2t + 2t^{2} − 2t^{3}} .

One can observe that the formal power series \frac{t^{2}}{1−2t+2t^{2}−2t^{3}} is the generating function of the sequence (y_{n})_{n≥0}. Thus, by (R3) we get

T_{n+2} = ∑_{k=0}^{2n} \binom{n}{k}_{2}(−1)^{2n−k}y_{k}.

Now, using (30), we find

T_{n+2} = \frac{(1 − α + α^{2})^{n+1}}{(α − β)(α − \overline{β})} + \frac{(1 − β + β^{2})^{n+1}}{(β − α)(β − \overline{β})} + \frac{(1 − \overline{β} + \overline{β}^{2})^{n+1}}{(\overline{β} − α)(\overline{β} − β)} .

In addition, we have α^{3} = 2(α^{2} − α + 1) (where also β and \overline{β} verify the same equality). This concludes the proof of the theorem.

More generally, consider the case when f_{k} = z^{k}, b = −a = 1, and let w be a complex number. Define the sequence (Y_{n})_{n≥0} as

Y_{n} = 2wY_{n−1} − 2w^{2}Y_{n−2} + (z + w^{3})Y_{n−3}, where Y_{0} = Y_{1} = 0 and Y_{2} = 1.

Let α_{z,w}, β_{z,w} and \overline{β}_{z,w} be the zeros of the polynomial p_{z,w}(t) = t^{3} − 2wt^{2} + 2w^{2}t − (z + w^{3}), in which

α_{z,w} = \frac{1}{6}u(z, w) − \frac{4w^{2}}{3u(z, w)} + \frac{2w}{3}
β_{z,w} = −\frac{1}{12}u(z, w) + \frac{2w^{2}}{3u(z, w)} + \frac{2w}{3} + \frac{i\sqrt{3}}{2} (\frac{1}{6}u(z, w) + \frac{4w^{2}}{3u(z, w)}) ,

where

u(z, w) = (28w^{3} + 108z + 12\sqrt{81z^{2} + 42zw^{3} + 9w^{6}})^{1/3}

and \overline{β}_{z,w} is the complex conjugate of β_{z,w}. Applying the same steps as in the previous proof, we deduce the following result.

Theorem 28. Let n be a nonnegative integer. Then

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2}w^{2n−3k}z^{k} = \frac{(w^{2} − wα_{z,w} + α_{z,w}^{2})^{n+1}}{(α_{z,w} − β_{z,w})(α_{z,w} − \overline{β}_{z,w})} + \frac{(w^{2} − wβ_{z,w} + β_{z,w}^{2})^{n+1}}{(β_{z,w} − α_{z,w})(β_{z,w} − \overline{β}_{z,w})}+

\frac{(w^{2} − w\overline{β}_{z,w} + \overline{β}_{z,w}^{2})^{n+1}}{(\overline{β}_{z,w} − α_{z,w})(\overline{β}_{z,w} − β_{z,w})}.  (31)

Example 29. Substituting z = 3 and w = 1 (resp., z = −1 and w = 1) into (31), we obtain

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2}3^{k} = \frac{3^{n}}{2} + \frac{(−1)^{n}}{4} ((1 + i\sqrt{2})^{n} − (1 − i\sqrt{2})^{n})

and

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2}(−1)^{k} = \begin{cases}1, & if n ≡ 0, 1 (mod 4); \\ 0, & if n ≡ 2, 3 (mod 4). \end{cases}

Remark 30. Putting w = 1, the cases z = −1, z = 2, and z = 3 are recorded in OEIS [25] as \underline{A133872}, \underline{A102001}, and \underline{A103770}, respectively. Setting z = w, the cases z = \sqrt{2}, z = \sqrt{3}, and z = 2 are recorded in OEIS [25] as \underline{A077835}, \underline{A077828}, and \underline{A103771}, respectively.

Lemma 31. Let n and k be nonnegative integers with n > 0. Then

\frac{k}{n}\binom{n}{k}_{2} = \binom{n − 1}{k − 1}_{2} + 2\binom{n − 1}{k − 2}_{2}.

Proof. The proof follows directly from [7, Thm. 2.2].

Now, we turn our attention to another identity, which we establish as follows: Theorem 32. Let n > 0 be an integer, f(t) be the generating function of the sequence (f_{n})_{n≥0}. Then

∑_{k=0}^{⌊2n/3⌋}\binom{n − k}{k}_{2} \frac{n}{n − k} f_{k} = [t^{2n}]\frac{(1 − t + t^{2})^{n−1}(3 − 4t + 2t^{2})}{1 − t}f (\frac{t^{3}}{(1 − t + t^{2})(1 − t)}) . (32)

Proof. Note that

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} f_{k} = ∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{((n − k) + k)}{n − k}f_{k}

= ∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2}f_{k} + ∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{k}{n − k} f_{k}.

In view of Lemma 31, we get

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} f_{k} = ∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2}f_{k} + ∑_{k=0}^{⌊2n/3⌋} \binom{n − 1 − k}{k − 1}_{2}f_{k}+

2 ∑_{k=0}^{⌊2n/3⌋} \binom{n − 1 − k}{k − 2}_{2}f_{k}.

Applying (13), we find

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} f_{k} = [t^{2n}](1 − t + t^{2})^{n} \frac{1}{1 − t}f (\frac{t^{3}}{(1 − t + t^{2})(1 − t)})

+ [t^{2(n−1)}](1 − t + t^{2})^{n−1}t^{−1}f (\frac{t^{3}}{(1 − t + t^{2})(1 − t)})

+ 2[t^{2(n−1)}](1 − t + t^{2})^{n−1} \frac{t^{−2}}{(1 − t)^{−1}} f (\frac{t^{3}}{(1 − t + t^{2})(1 − t)}) .

Therefore

∑_{k=0}^{⌊2n/3⌋}\binom{n − k}{k}_{2} \frac{n}{n − k} f_{k} =

[t^{2n}](1 − t + t^{2})^{n−1}f (\frac{t^{3}}{(1 − t + t^{2})(1 − t)}) (\frac{1 − t + t^{2}}{1 − t} + t + 2(1 − t)) .

By simplifying the last expression, the proof is done.

Let us examine some cases of the identity (32). Let (λ_{n})_{n≥0} be a sequence (\underline{A075115}) defined as follows:

λ_{n} = 2λ_{n−1} − 2λ_{n−2} + 2λ_{n−3}, λ_{0} = 3, λ_{1} = 2, λ_{2} = 0.

It is clear that

λ_{n} = α^{n} + β^{n} + \overline{β}^{n}.  (33)

Corollary 33. Let n > 0 be an integer. Then

K_{n} := ∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} = \frac{1}{2^{n}} λ_{3n}.

Proof. From (32), putting f_{k} = 1, we obtain

K_{n} = [t^{2n}]\frac{(1 − t + t^{2})^{n−1}(3 − 4t + 2t^{2})}{1 − t} [\frac{1}{1 − y} | y = \frac{t^{3}}{(1 − t)(1 − t + t^{2})}]

= [t^{2n}](1 − t + t^{2})^{n} \frac{3 − 4t + 2t^{2}}{1 − 2t + 2t^{2} − 2t^{3}} .

Observe that the formal power series \frac{3−4t+2t^{2}}{1−2t+2t^{2}−2t^{3}} is the generating function of the sequence (λ_{n})_{n≥0}. Using the Binet formula (33), we conclude

K_{n} = (1 − α + α^{2})^{n} + (1 − β + β^{2})^{n} + (1 − \overline{β} + \overline{β}^{2})^{n}.

Finally, we have α^{3} = 2(α^{2} − α + 1) (where also β and \overline{β} verify the same equality). Thus, the proof is done.

Remark 34. The sequence (K_{n})_{n≥0} is known as the Tribonacci-Lucas numbers (\underline{A001644}). Recall that the sequence (\underline{A146559}) is defined by

a_{n} := [t^{n}]\frac{1 − t}{1 − 2t + 2t^{2}} ,

in which a_{n} has the following explicit form

a_{n} = \frac{1}{2}(1 + i)^{n} + \frac{1}{2}(1 − i)^{n},

where i^{2} = −1.

Corollary 35. Let n > 0 be an integer. Then

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} (−1)^{k} = \begin{cases}1, & if n ≡ ±1 (mod 4); \\ −1, & if n ≡ 2 (mod 4); \\ 3, & if n ≡ 0 (mod 4). \end{cases}

Proof. Applying (32), for f_{k} = −1, we obtain

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} (−1)^{k} = [t^{2n}](1 − t + t^{2})^{n} \frac{3 − 4t + 2t^{2}}{1 − 2t + 2t^{2}}

= 1 + 2[t^{2n}](1 − t + t^{2})^{n} \frac{1 − t}{1 − 2t + 2t^{2}} .

This implies that

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} (−1)^{k} = [t^{2n}](1 − t + t^{2})^{n} \frac{3 − 4t + 2t^{2}}{1 − 2t + 2t^{2}}
= 1 + (1 − (1 − i) + (1 − i)^{2})^{n} + (1 − (1 + i) + (1 + i)^{2})^{n} .

Therefore

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} (−1)^{k} = 1 + i^{n} ((−1)^{n} + 1) .

Finally, we examine the cases of n modulo 4.

More generally, we establish the following identity.

Corollary 36. Let n > 0 be an integer, w and z be complex numbers. Then

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} w^{2n−3k}z^{k} = (w^{2} − wα_{z,w} + α_{z,w}^{2})^{n} + (w^{2} − wβ_{z,w} + β_{z,w}^{2})^{n}+
(w^{2} − w\overline{β}_{z,w} + \overline{β}_{z,w}^{2})^{n}.  (34)

Example 37. Taking z = 3 and w = 1 in (34), we get

∑_{k=0}^{⌊2n/3⌋} \binom{n − k}{k}_{2} \frac{n}{n − k} 3^{k} = 3^{n} + (−1)^{n} ((1 + i\sqrt{2})^{n} + (1 − i\sqrt{2})^{n}) .  (35)

6 On the bi^{2}nomial coefficient of the form \binom{n+ak}{n+bk}_{2}

If x depends on n, or y depends on m, the formulas (13) and (14) are only applicable in limited cases. In this section, we examine the bi^{2}nomial coefficients of the form \binom{n+ak}{n+bk}_{2}. We

evaluate the cases of a and b in order to find out the nature of the arrays (\binom{n+ak}{n+bk}_{2})_{n,k≥0}. We

also derive some combinatorial identities involving these kinds of bi^{2}nomial coefficients.

To establish the generating function of some cases of the bi^{2}nomial coefficients \binom{n+ak}{n+bk}_{2}, we use the Lagrange inversion formula (Theorem 5). Then we obtain the result below.

Theorem 38. Let n be a nonnegative integer and a, b are integers. If b − 2a ≥ 0, then

\binom{n + ak}{n + bk}_{2} = [t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}} (\frac{(1 − t − \sqrt{1 − 2t − 3t^{2}})^{b−a}}{2^{b−a}t^{b}} )^{k} .  (36)

Proof. Let b − 2a ≥ 0. In view of (10), we get

\binom{n + ak}{n + bk}_{2} = [t^{2n}](1 − t + t^{2})^{n} \frac{t^{n}}{(1 − t)^{n}} \frac{1}{1 − t} (\frac{t^{b−2a}(1 − t + t^{2})^{a}}{(1 − t)^{b}} )^{k}

= [t^{n}](1 − t + t^{2})^{n} \frac{1}{(1 − t)^{n}} \frac{1}{1 − t} (\frac{t^{b−2a}(1 − t + t^{2})^{a}}{(1 − t)^{b}} )^{k} .

Setting ϕ(t) = (1 + t + t^{2})/(1 − t). We obtain

w(t) = \frac{t − \sqrt{1 − 2t − 3t^{2}} + 1}{2(t + 1)}.

With the help of (11) and, after some simplifications, we arrive at (36).

Let D := (\binom{n+ak}{n+bk}_{2})_{n,k≥0}. Setting a ≥ 0 and b ≥ 0, we distinguish the following cases.

• If 0 ≤ b ≤ 2a, then D is not a triangular array;

• If b = 2a + 1, then D is a proper Riordan array;

• If b > 1 + 2a, then D is an improper Riordan array.

Now, suppose that b < 0. According to symmetric relation, we have \binom{n+ak}{n+bk}_{2} = \binom{n+ak}{n+(2a−b)k}_{2}. Take c = 2a − b. Note that c ≥ 2a, then this letter reduces to the cases above.

Now, consider a < 0. If b ≥ 0, one can observe that for all values of k we have n+bk ≥ 0. Hence, according to (9) D is not a triangular array. If b < 0, according to the convention on page 4, we have \binom{n+ak}{n+bk} = 0 for k > ⌊n/b⌋. Here we get

\binom{n + ak}{n − ck}_{2} = [t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}} (\frac{(1 − t − \sqrt{1 − 2t − 3t^{2}})^{c+a}}{2^{c+a}t^{c+2a}} )^{k} ,

where b = −c. Hence • If c = 1, then D is a proper Riordan array;

• If c > 1, then D is an improper Riordan array. Remark 39. Substituting a = 0 and b = 1 into (36), we get R (\frac{1}{\sqrt{1−2t−3t^{2}}} , \frac{1−t−\sqrt{1−2t−3t^{2}}}{2t} ), which is called the Motzkin triangle (\underline{A094531}). It was studied in [17].

Let us now derive some identities. Corollary 40. Let n be a nonnegative integer and w be a complex number. Then

∑_{k=0}^{n} \binom{n}{n − k}_{2}w^{n+k} = \frac{(1 + w + w^{2})^{n}}{2} + \frac{1}{2}\binom{n}{n}_{2}w^{n} + \frac{(w^{2} − 1)}{2} ∑_{k=0}^{n−1} \binom{k}{k}_{2}(1 + w + w^{2})^{n−1−k}w^{k}. (37)

Proof. Substituting a = 0 and b = −1 into (36), then applying (3) for f_{k} = w^{k}, we find

∑_{k=0}^{n} \binom{n}{n − k}_{2}w^{k} = [t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}} [\frac{1}{1 − wy} | y = \frac{1 − t − \sqrt{1 − 2t − 3t^{2}}}{2t} ]

= [t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}} \frac{2t}{(2 + w)t − w + w\sqrt{1 − 2t − 3t^{2}}}

= [t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}} \frac{2t (w\sqrt{1 − 2t − 3t^{2}} − (2 + w)t + w)}{(−4w^{2}t^{2} − 4t^{2} − 4wt^{2} + 4wt)}.

Simplifying the last expression, we get

∑_{k=0}^{n} \binom{n}{n − k}_{2}w^{k} = \frac{1}{2}[t^{n}]\frac{w}{w − (w^{2} + w + 1)t} + \frac{1}{2}[t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}}

+ \frac{1}{2}[t^{n−1}]\frac{w^{2} − 1}{\sqrt{1 − 2t − 3t^{2}}(w − (w^{2} + w + 1)t)}.

Therefore, the proof is done. Remark 41. Setting w = 1 in (37) yields \underline{A027914}, and setting w = −1 in (37) yields \underline{A246437}. Corollary 42. Let n be a nonnegative integer. Then

∑_{k} \binom{n + k}{n − k}_{2} = \frac{1}{2}T_{2(n+1)} + \frac{1}{2}\binom{n}{n}_{2} + \frac{1}{2} ∑_{k=0}^{n−1} \binom{k}{k}_{2}(T_{2(n−k)} + T_{2(n−1−k)}),  (38)

where T_{2n} is the bisection of Tribonacci numbers (\underline{A099463}). Proof. Substituting a = 1 and b = −1 into (36), then applying (3), for f_{k} = 1, we obtain

∑_{k=0}^{n} \binom{n + k}{n − k}_{2} = [t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}} [\frac{1}{1 − y} | y = \frac{(1 − t − \sqrt{1 − 2t − 3t^{2}})^{2}}{4t^{3}} ]

= [t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}} \frac{4t^{3}}{4t^{3} − (1 − t − \sqrt{1 − 2t − 3t^{2}})^{2}}

= [t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}} \frac{4t^{3}}{(4t^{3} + 2t^{2} + 4t − 2 − 2\sqrt{−3t^{2} − 2t + 1}(t − 1))}.

Simplifying the last expression, we get

∑_{k=0}^{n} \binom{n + k}{n − k}_{2} = \frac{1}{2}[t^{n}]\frac{(t − 1)}{t^{3} + t^{2} + 3t − 1} + \frac{1}{2}[t^{n}]\frac{1}{\sqrt{1 − 2t − 3t^{2}}}

+ \frac{1}{2}[t^{n−1}]\frac{t^{2} − 1}{\sqrt{1 − 2t − 3t^{2}}(t^{3} + t^{2} + 3t − 1)}.

Then the proof is done.

Following the same steps of precedent proof, we get the alternating sign version of (38);

Corollary 43. Let n be a nonnegative integer. Then

∑_{k} \binom{n + k}{n − k}_{2}(−1)^{k} = \frac{1 + (−1)^{n}}{4} + \binom{n}{n}_{2} − \frac{w_{n}}{2} ,

where (w_{n})_{n≥0} is \underline{A097893}.

7 Trinomial transform and its inverse relation

In this final section, we introduce the trinomial transform concept and we determine its inverse relation.

Definition 44. Let γ be a real number. Recall that the Gegenbauer polynomial C_{n}^{(γ)}(x) (cf. [1, Chapter 22]) is defined by

C_{n}^{(γ)}(x) = [t^{n}]\frac{1}{(1 − 2xt + t^{2})^{γ}} .

Beside to important application of the Riordan array transformation (3), to solve combinatorial identities, we can also use the algebraic property of proper Riordan arrays to find the sums inversion, i.e., for all proper Riordan array D = (d_{n,k})_{n,k≥0} and its inverse D^{−1} = (d̄_{n,k})_{n,k≥0}, we have

∑_{k=0}^{n} d_{n,k}f_{k} = g_{n} ⟺ f_{n} = ∑_{k=0}^{n} d̄_{n,k}g_{k},  (39)

where (f_{n})_{n≥0} and (g_{n})_{n≥0} are two sequences [18]. In particular, we have

∑_{k=0}^{n} \binom{n}{k}f_{k} = g_{n} ⟺ f_{n} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}g_{k}.  (40)

The right-hand side of the formula (40) is known as the binomial transform [23].

Németh [21] gave a new transform called the trinomial transform of a sequence. His definition inspired from the well-known binomial transform, replacing binomial coefficients with bi^{2}nomial coefficients.

Examining Theorem 6 we get the following result.

Theorem 45. Let (f_{n})_{n≥0} and (g_{n})_{n≥0} be sequences. Then

∑_{k=0}^{2n} \binom{n}{k}_{2}f_{k} = g_{2n} ⟺ ∑_{k=0}^{2n} ā_{2n,k}g_{k} = f_{2n},  (41)

where a_{0,0} = a_{n,n} = 1, and for n ≥ 1, we have

ā_{n,k} = C_{n−k}^{(k/2+1)}(−1/2) + \frac{1}{2}C_{n−k−1}^{(k/2+1)}(−1/2).

Proof. Let R(α(t), β(t)) = (a_{n,k})_{n,k≥0}. One can show that

R^{−1}(α(t), β(t)) = R (\frac{2 + t}{2 + 2t + 2t^{2}} , \frac{t}{\sqrt{1 + t + t^{2}}} ) ,

see Page 2. Define B = (ā_{n,k})_{n,k≥0}, where

ā_{n,k} = [t^{n}] \frac{2 + t}{2 + 2t + 2t^{2}} (\frac{t}{\sqrt{1 + t + t^{2}}} )^{k} .

This gives

ā_{n,k} = C_{n−k}^{(k/2+1)}(−1/2) + \frac{1}{2}C_{n−k−1}^{(k/2+1)}(−1/2).

In view of (39), we have

∑_{k=0}^{n} a_{n,k}f_{k} = g_{n} ⟺ f_{n} = ∑_{k=0}^{n} ā_{n,k}g_{k}.

By changing n to 2n and applying Theorem 6, the proof is completed.

Remark 46. Obviously, the inverse transform of the trinomial transform gives only the evenindex terms of the sequence (f_{n})_{n≥0}, because it is mainly related to the position of bi^{2}nomial rows over the Riordan array R(α(t), β(t)).

Using the Lagrange inversion formula, Merlini et al. [18, Thm. 6] established that.

Theorem 47. Let us suppose that the sum a_{n} = ∑_{k=0}^{n} d_{n,k}b_{k} corresponds to the implicit Riordan array D = (f(t)ψ(t)^{n}, h(t)), that is, to the relation a_{n} = [t^{n}]f(t)ψ(t)^{n}b(h(t)), with ψ(0) ≠ 0, h(0) = 0 and h′(0) ≠ 0. Then the inverse sum is

b_{n} = ∑_{k=0}^{n} ([t^{n−k}]\frac{(ψ(t) − tψ′(t)) h′(t)}{f(t)ψ(t)^{k+1}} \frac{t^{n+1}}{h(t)^{n+1}} ) a_{k}.

Remark 48. The concept of implicit Riordan arrays is given in [18, Page 2].

According to (10) the bi^{2}nomial transform can be written as

g_{2n} = [t^{2n}](1 − t + t^{2})^{n} \frac{1}{1 − t}f (\frac{t}{1 − t}) ,

where f(t) is the generating function of the sequence (f_{n})_{n≥0}. Let g(t) = α(t)f(β(t)). Then we obtain.

Corollary 49. Let n be a nonnegative integer. Then

f_{2n} = [t^{2n}]\frac{(2 − t)(1 − t)^{2n}}{2(1 − t + t^{2})} g (\frac{t}{\sqrt{1 − t + t^{2}}} ) .

8 Acknowledgment

Our sincere thanks to the reviewers for their valuable feedback and constructive suggestions, which have significantly strengthened this paper. This paper is partially supported by DGRSDT grant n^{∘} C0656701.

References

[1] M. Abramowitz and I. A. Stegun, (Eds.), Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (Vol. 55), US Government printing office, 1948.

[2] D. André, Mémoire sur les combinaisons régulières et leurs applications, Ann. Sci. Éc. Norm. Supér. 5 (1876), 155–198.

[3] G. Andrews, Euler’s ‘exemplum memorabile inductionis fallacis’ and q-trinomial coefficients, J. Amer. Math. Soc. 3 (1990), 653–669.

[4] H. Belbachir, Determining the mode for convolution powers for discrete uniform distribution, Probab. Engrg. Inform. Sci. 25 (2011), 469–475.

[5] H. Belbachir and A. Benmezai, A q-analogue for bi^{s}nomial coefficients and generalized Fibonacci sequences, C. R. Math. Acad. Sci. Paris 352 (2014), 167–171.

[6] H. Belbachir, S. Bouroubi, and A. Khelladi, Connection between ordinary multinomials, Fibonacci numbers, Bell polynomials and discrete uniform distribution, Ann. Math. Inform. 35 (2008), 21–30.

[7] H. Belbachir and O. Igueroufa, Congruence properties for bi^{s}nomial coefficients and like extended Ram and Kummer theorems under suitable hypothesis, Mediterr. J. Math. 17 (2020), 1–14.

[8] H. Belbachir and O. Igueroufa, Combinatorial interpretation of bi^{s}nomial coefficients and generalized Catalan numbers, Proceedings of the 1st International Conference on Algebras, Graphs and Ordered Sets (ALGOS 2020), 47–54.

[9] H. Belbachir, T. Komatsu, and L. Szalay, Linear recurrences associated to rays in Pascal’s triangle and combinatorial identities, Math. Slovaca 64 (2014), 287–300.

[10] G. S. Cheon and S. T. Jin, The group of multidimensional Riordan arrays, Linear Algebra Appl. 524 (2017), 263–277.

[11] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel, 1974.

[12] J. E. Freund, Restricted occupancy theory—a generalization of Pascal’s triangle, Amer. Math. Monthly 63 (1956), 20–27.

[13] H. X. Ni and H. Pan, On the lacunary sum of trinomial coefficients, Appl. Math. Comput. 339 (2018), 286–293.

[14] V. E. Hoggatt Jr and G. L. Alexanderson, Sum of partition sets in generalized Pascal triangles, Fibonacci Quart. 14 (1976), 117–125.

[15] H. W. Gould, Combinatorial Identities, Morgantown, W. Va., 1972.

[16] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, 1983.

[17] A. Luzón, D. Merlini, M. A. Morón, and R. Sprugnoli, Complementary Riordan arrays, Discrete Appl. Math. 172 (2014), 75–87.

[18] D. Merlini, R. Sprugnoli, and M. Verri, Combinatorial sums and implicit Riordan arrays, Discrete Math. 309 (2009), 475–486.

[19] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math. 49 (1997), 301–320.

[20] D. Merlini, R. Sprugnoli, and M. C. Verri, The method of coefficients, Amer. Math. Monthly 114 (2007), 40–57.

[21] L. Németh, The trinomial transform triangle, J. Integer Seq. 21 (2018), Article 18.7.3.

[22] D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (1978), 301–310.

[23] J. Riordan, Combinatorial Identities, John Wiley and Sons, 1968.

[24] L. V. Shapiro, S. Getu, W.-J. Woan, and L. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

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

[26] R. Sprugnoli, Riordan Array Proofs of Identities in Gould’s Book, University of Florence, Italy, 2006.

[27] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

2020 Mathematics Subject Classification: Primary 11B65; Secondary 05A10, 05A15, 05A19. Keywords: Riordan array, 2-Pascal triangle, generating function, bi^{2}nomial coefficient, combinatorial identity.

(Concerned with sequences \underline{A000032}, \underline{A000073}, \underline{A000129}, \underline{A001333}, \underline{A001644}, \underline{A002605}, \underline{A008277}, \underline{A008287}, \underline{A027907}, \underline{A027914}, \underline{A035343}, \underline{A052948}, \underline{A063260}, \underline{A075115}, \underline{A077828}, \underline{A077835}, \underline{A077843}, \underline{A077846}, \underline{A077943}, \underline{A081179}, \underline{A081336}, \underline{A083878}, \underline{A083882}, \underline{A094531}, \underline{A097893}, \underline{A099463}, \underline{A102001}, \underline{A103770}, \underline{A103771}, \underline{A133872}, \underline{A146559}, \underline{A152107}, and \underline{A246437}.)

Received September 17 2023; revised versions received November 9 2024; November 16 2024; December 3 2024. Published in Journal of Integer Sequences, April 19 2025.

Return to Journal of Integer Sequences home page.