The Trinomial Transform Triangle

László Németh Institute of Mathematics University of Sopron Bajcsy Zs. u. 4 Sopron H9400 Hungary

              nemeth.laszlo@uni-sopron.hu

Abstract

The trinomial transform of a sequence is a generalization of the well-known binomial transform, replacing binomial coefficients with trinomial coefficients. We examine Pascal-like triangles under the trinomial transform, focusing on ternary linear recurrent sequences. We determine the sums and alternating sums of the elements in columns, and we give some examples of the trinomial transform triangle.

1 Introduction

The binomial transform of a sequence (a_{i})_{i=0}^{∞} is a sequence (b_{n})_{n=0}^{∞} defined by b_{n} = ∑_{i=0}^{n} \binom{n}{i}a_{i}. This transformation is invertible with formula a_{n} = ∑_{i=0}^{n} \binom{n}{i}(−1)^{n−i}b_{i}. Several studies [4, 6, 7, 10] examine the properties and the generalizations of the binomial transform. One generation is the trinomial transform. Let it be given by

b_{n} = ∑_{i=0}^{2n} \binom{n}{i}_{2}a_{i},

where for 0 ≤ i ≤ 2n

\binom{n}{i}_{2} = ∑_{j=0}^{i} \binom{n}{j}\binom{j}{i − j}

holds with the classical binomial coefficients. It is known that the trinomial triangle (Figure 2) determines the trinomial coefficients \binom{n}{i}_{2} that arise in the expansion of (1 + x + x^{2})^{n}. (For example, Belbachir et al. [5] discussed some details of the trinomial coefficients, the trinomial tringle and their generalizations.)

To the best of our knowledge, this transformation has not been previously studied or even mentioned in journals, although there are eleven sequences in the OEIS [8], which are trinomial transforms of certain sequences, that do not appear in the literature We will refer to some of them in the last section.

In this article, we define an arithmetic structure similar to an infinite triangle, where the terms are arranged in rows and columns. Let the trinomial transform triangle T be defined the following way. Row 0 consists of the terms of a given sequence (a_{k})_{k=0}^{∞}, and any term in an other row is the sum of the three terms directly above it according to Figure 1. The exact definition is

a_{0}^{k} = a_{k},
a_{n}^{k} = a_{n−1}^{k−1} + a_{n−1}^{k} + a_{n−1}^{k+1}, (1 ≤ n ≤ k).  (1)

Let the ℓ^{th} (ℓ ≥ 0) diagonal sequence of T be the sequence (a_{n}^{n+l})_{n=0}^{∞}. We shall give some properties of triangle T and show that the 0^{th} or main diagonal sequence of T is the trinomial transform sequence of (a_{k}). In particular, we show that the trinomial transform of a ternary linear recurrent sequence is also a ternary linear recurrent sequence. Moreover, we give some properties of T , for example, sums and partial sums in the columns. The author [6] dealt with a generalized binomial transform triangle.

In the last section, we present some special examples for the trinomial transform triangles.

a_{0}^{0} ⋯ a_{0}^{1} ⋯ a_{0}^{2} ⋯ a_{0}^{3} ⋯ a_{0}^{4} ⋯ a_{0}^{5} ⋯ a_{0}^{6} ⋯ a_{1}^{1} ⋯ a_{1}^{2} ⋯ a_{1}^{3} ⋯ a_{1}^{4} ⋯ a_{1}^{5} ⋯ a_{1}^{6} ⋯ a_{2}^{2} ⋯ a_{2}^{3} ⋯ a_{2}^{4} ⋯ a_{2}^{5} ⋯ a_{2}^{6} ⋯ a_{3}^{3} ⋯ a_{3}^{4} ⋯ a_{3}^{5} ⋯ a_{3}^{6} ⋯ ⋮⋮⋮...

Figure 1: Construction of the trinomial transform triangle T

2 Trinomial triangle and its partial sum triangle

Most of our proofs are based on the elements of the trinomial triangle (or Feinberg’s triangle named by Anatriello and Vincenzi [2]) and its partial sum triangle, therefore first of all we define them and give some known basic properties [1, 5].

Let the trinomial coefficient \binom{n}{k}_{2} be the k^{th} term of the n^{th} row in the trinomial triangle, where 0 ≤ n and 0 ≤ k ≤ 2n (see Figure 2 and \underline{A027907} in the OEIS [8]). The terms of the triangle satisfy the relations

\binom{n}{0}_{2} = \binom{n}{2n}_{2} = 1 (0 ≤ n),

\binom{n}{k}_{2} = \binom{n − 1}{k − 2}_{2} + \binom{n − 1}{k − 1}_{2} + \binom{n − 1}{k}_{2} (1 ≤ n).

We use the convention \binom{n}{k}_{2} = 0 for k ∉ \{0, 1, …, 2n\}. (For more details and some generalization of binomial and trinomial coefficients see [5].) Now, we take the partial sums of terms in columns of the trinomial triangle. Let \begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} denote the partial sum of values of \binom{n}{k}_{2} and all the terms above it in its column, so that

\begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = ∑_{j=0}^{n} \binom{n − j}{k − j}_{2}.

Without zero elements, we also have

\begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = ∑_{i=|n−k|}^{n} \binom{i}{i − (n − k)}_{2} = ∑_{i=|n−k|}^{n} ∑_{j=0}^{i−n+k} \binom{i}{j}\binom{j}{i − n + k − j}.

1

1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
Figure 2: Trinomial triangle (\underline{A027907})

By arranging them into an infinite triangle, we gain the partial sum triangle of trinomial triangle (or partial sum trinomial triangle — see Figure 3). It is not in the OEIS yet, but the partial sum sequences of the central trinomial coefficients and of the two neighbouring column sequences do — see \underline{A097893}, \underline{A097861}, and \underline{A097894}.

1 2 1
1 3 5 3 1
1 4 9 12 9 4 1
1 5 14 25 31 25 14 5 1
1 6 20 44 70 82 70 44 20 6 1
1 7 27 70 134 196 223 196 134 70 27 7 1

Figure 3: Partial sum triangle of trinomial triangle

Our major aim in this paper is not to examine the partial sum trinomial triangle, but we give some of its properties that we use in the following sections.

From the vertical symmetry of the trinomial triangle, \binom{n}{k}_{2} = \binom{n}{2n−k}_{2}, the partial sum trinomial triangle also has a symmetry axis and

\begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = \begin{aligned}[ \\ ( & {n \atop 2n − k} & ) \\ & ] \end{aligned}_{2}.

Moreover, if n ≥ k, then

\begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = ∑_{i=0}^{k} \binom{n − i}{k − i}_{2} = ∑_{i=0}^{k} ∑_{j=0}^{n−i} \binom{n − i}{j}\binom{j}{k − i − j}.

Furthermore, this triangle evidently satisfies the recursive relations below.

\begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = \begin{cases}1, & if k = 0 or k = 2n; \\ \begin{matrix}[ \\ ( & {n−1 \atop k−1} & ) \\ ] \end{matrix}_{2} + \binom{n}{k}_{2}, & otherwise. \end{cases}  (2)

\begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = \begin{cases}1, & if k = 0 or k = 2n; \\ n + 1, & if k = 1 or k = 2n − 1; \\ \begin{matrix}[ \\ ( & {n−1 \atop n−2} & ) \\ ] \end{matrix}_{2} + \begin{matrix}[ \\ ( & {n−1 \atop n−1} & ) \\ ] \end{matrix}_{2} + \begin{matrix}[ \\ ( & {n−1 \atop n} & ) \\ ] \end{matrix}_{2} + 1, & if 2 ≤ n = k; \\ \begin{matrix}[ \\ ( & {n−1 \atop k−2} & ) \\ ] \end{matrix}_{2} + \begin{matrix}[ \\ ( & {n−1 \atop k−1} & ) \\ ] \end{matrix}_{2} + \begin{matrix}[ \\ ( & {n−1 \atop k} & ) \\ ] \end{matrix}_{2} , & otherwise. \end{cases}  (3)

Theorem 1 provides summation identities for the partial sum trinomial triangle, as a corollary of the last section.

Theorem 1. The partial sum trinomial triangle satisfies the following summation expressions

∑_{k=0}^{2n} \begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = \frac{3^{n+1} − 1}{2},  ∑_{k=0}^{2n}(−1)^{k}\begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = \begin{cases}0, & if n is odd; \\ 1, & otherwise, \end{cases}

∑_{k=0}^{2n} k\begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = n\frac{3^{n+1} − 1}{2},  ∑_{k=0}^{2n}(−1)^{k}k\begin{matrix}[ \\ ( & {n \atop k} & ) \\ ] \end{matrix}_{2} = \begin{cases}0, & if n is odd or n = 0; \\ n, & otherwise. \end{cases}

3 Trinomial transform triangle

Any term of T can be determined by the terms of sequence (a_{k}) with trinomial coefficients. Recall a_{0}^{k} = a_{k}.

Theorem 2. For any 0 ≤ n ≤ k, we have

a_{n}^{k} = ∑_{i=k−n}^{k+n} \binom{n}{i − k + n}_{2}a_{0}^{i}.  (4)

Proof. The proof is by induction on n. For n = 0 the statement is trivial. For clarity in case n = 1, we have

a_{1}^{k} = a_{0}^{k−1} + a_{0}^{k} + a_{0}^{k+1} = \binom{1}{0}_{2}a_{0}^{k−1} + \binom{1}{1}_{2}a_{0}^{k} + \binom{1}{2}_{2}a_{0}^{k+1} = ∑_{i=k−1}^{k+1} \binom{1}{i − k + 1}_{2}a_{0}^{i}.

Let us suppose that the result is true for n − 1, so, for example,

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

Using (3), we have

a_{n}^{k} = a_{n−1}^{k−1} + a_{n−1}^{k} + a_{n−1}^{k+1}
= ∑_{i=k−n}^{k+n−2} \binom{n − 1}{i − k + n}_{2}a_{0}^{i} + ∑_{i=k−n+1}^{k+n−1} \binom{n − 1}{i − k + n − 1}_{2}a_{0}^{i} + ∑_{i=k−n+2}^{k+n} \binom{n − 1}{i − k + n − 2}_{2}a_{0}^{i}

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

+ (\binom{n − 1}{2}_{2} + \binom{n − 1}{1}_{2} + \binom{n − 1}{0}_{2}) a_{0}^{k−n+2} + ⋯

+ (\binom{n − 1}{i − k + n − 2}_{2} + \binom{n − 1}{i − k + n − 1}_{2} + \binom{n − 1}{i − k + n}_{2}) a_{0}^{i} + ⋯

+ (\binom{n − 1}{2n − 3}_{2} + \binom{n − 1}{2n − 2}_{2}) a_{0}^{k+n−1} + \binom{n − 1}{2n − 2}_{2}a_{0}^{k+n}

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

We let (b_{n}) denote the 0^{th} diagonal sequence (a_{n}^{n}) in T . If k = n, then we obtain the next corollary from Theorem 2.

Corollary 3. The diagonal sequence (b_{n}) of the trinomial transform triangle is the trinomial transform sequence of (a_{k}).

Let (s_{n})_{n=0}^{∞} be the sum sequence of the values of columns in T , so that

s_{n} = ∑_{i=0}^{n} a_{i}^{n}.  (5)

Theorem 4.

s_{n} = ∑_{i=0}^{n} ∑_{j=n−i}^{n+i} \binom{i}{j − n + i}_{2}a_{0}^{j} = ∑_{i=0}^{n} ∑_{k=0}^{2i} \binom{i}{k}_{2}a_{0}^{n+k−i}.

Proof. Substitute (4) into (5) and put k = i + j − n.

Let us express the term s_{n} by the help of the terms of the partial sum trinomial triangle and for it, first, we have to prove the theorem below.

Theorem 5. If n ≤ k, then

∑_{i=0}^{n} a_{i}^{k} = ∑_{ℓ=k−n}^{k+n} \begin{matrix}[ \\ ( & {n \atop ℓ − k + n} & ) \\ ] \end{matrix}_{2}a_{0}^{ℓ}.  (6)

Proof. We prove again by induction. The case n = 0 is clear, and for clarity in case n = 1, we have ∑_{i=0}^{1} a_{i}^{k} = a_{0}^{k} + a_{1}^{k} = a_{0}^{k−1} + 2a_{0}^{k} + a_{0}^{k+1}. The hypothesis of induction for n − 1 is

∑_{i=0}^{n−1} a_{i}^{k} = ∑_{ℓ=k−n+1}^{k+n−1} \begin{matrix}[ \\ ( & {n − 1 \atop ℓ − k + n + 1} & ) \\ ] \end{matrix}_{2}a_{0}^{ℓ}.

Now, using (2), we obtain

∑_{i=0}^{n} a_{i}^{k} = ∑_{i=0}^{n−1} a_{i}^{k} + a_{n}^{k}
= ∑_{ℓ=k−n+1}^{k+n−1} \begin{matrix}[ \\ ( & {n − 1 \atop ℓ − k + n + 1} & ) \\ ] \end{matrix}_{2}a_{0}^{ℓ} + ∑_{i=k−n}^{k+n} \binom{n}{i − k + n}_{2}a_{0}^{i}
= ∑_{ℓ=k−n+1}^{k+n−1} \begin{matrix}[ \\ ( & {n − 1 \atop ℓ − k + n + 1} & ) \\ ] \end{matrix}_{2}a_{0}^{ℓ} + \binom{n}{0}_{2}a_{0}^{k−n} + \binom{n}{2n}_{2}a_{0}^{k+n} + ∑_{ℓ=k−n+1}^{k+n−1} \binom{n}{ℓ − k + n}_{2}a_{0}^{ℓ}
= \binom{n}{0}_{2}a_{0}^{k−n} + ∑_{ℓ=k−n+1}^{k+n−1} (\begin{matrix}[ \\ ( & {n − 1 \atop ℓ − k + n + 1} & ) \\ ] \end{matrix}_{2} + \binom{n}{ℓ − k + n}_{2}) a_{0}^{ℓ} + \binom{n}{2n}_{2}a_{0}^{k+n}
= ∑_{ℓ=k−n}^{k+n} \begin{matrix}[ \\ ( & {n \atop ℓ − k + n} & ) \\ ] \end{matrix}_{2}a_{0}^{ℓ}.

The same induction method yields the following theorem. Theorem 6. If 0 ≤ j ≤ n, then we have

∑_{i=0}^{k} a_{i}^{k} = ∑_{ℓ=k−n+j}^{k+n−j} \begin{aligned}[ \\ ( & {n − j \atop ℓ − k + n − j} & ) \\ & ] \end{aligned}_{2}a_{j}^{ℓ}.

Applying Theorem 5 for the case k = n, we obtain the main theorem of this section. Theorem 7. The column sum sequence can be given with the expression

s_{n} = ∑_{ℓ=0}^{2n} \begin{matrix}[ \\ ( & {n \atop ℓ} & ) \\ ] \end{matrix}_{2}a_{0}^{ℓ}.

4 Trinomial transform triangles generated by ternary

homogeneous linear recurrent sequences

From this point on we examine the case a_{0}^{k} = a_{k}, where (a_{k})_{k=0}^{∞} is a ternary linear recursive sequence with initial values a_{0}, a_{1}, a_{2} ∈ ℤ (|a_{0}| + |a_{1}| + |a_{2}| ≠ 0). And it is defined for 3 ≤ k by

a_{k} = αa_{k−1} + βa_{k−2} + γa_{k−3},  (7)

where α, β, γ ∈ ℤ, γ ≠ 0. (In general, the results of this section hold for an integral domain.) From now on, we will use three important variables

A = α^{2} + α + 2β + 3,
B = −2α^{2} + αβ + 2αγ − β^{2} − 2α − 3β + 3γ − 3,
C = α^{2} − αβ − αγ + β^{2} − βγ + γ^{2} + α + β − 2γ + 1.

Theorem 8. The terms in the rows satisfy the same ternary relation,

a_{n}^{k} = αa_{n}^{k−1} + βa_{n}^{k−2} + γa_{n}^{k−3}  (0 ≤ n ≤ k − 3).  (8)

Proof. We prove by induction on n. If n = 0, then (8) is the definition of a_{k}. We suppose that it holds for up to row n − 1. Then

a_{n}^{k} = a_{n−1}^{k−1} + a_{n−1}^{k} + a_{n−1}^{k+1}
= αa_{n−1}^{k−2} + βa_{n−1}^{k−3} + γa_{n−1}^{k−4} + αa_{n−1}^{k−1} + βa_{n−1}^{k−2} + γa_{n−1}^{k−3} + αa_{n−1}^{k} + βa_{n−1}^{k−1} + γa_{n−1}^{k−2}
= α(a_{n−1}^{k} + a_{n−1}^{k−1} + a_{n−1}^{k−2}) + β(a_{n−1}^{k−1} + a_{n−1}^{k−2} + a_{n−1}^{k−3}) + γ(a_{n−1}^{k−2} + a_{n−1}^{k−3} + a_{n−1}^{k−4})
= αa_{n}^{k−1} + βa_{n}^{k−2} + γa_{n}^{k−3}.

Remark 9. Let us extend the sequence (a_{k}) for negative indices, so that let a_{k} = 0, if k < 0. From definition (1), the initial values of sequences of rows are a_{n}^{−n} = a_{0}, a_{n}^{−n+1} = na_{0} + a_{1}, and a_{n}^{−n+2} = \binom{n+1}{2}a_{0} + na_{1} + a_{2} with extension for negative indices. It can be easily proved by induction.

Theorem 10. The terms in the diagonals can be described by the same ternary recurrence relation,

a_{n}^{n+ℓ} = Aa_{n−1}^{n+ℓ−1} + Ba_{n−2}^{n+ℓ−2} + Ca_{n−3}^{n+ℓ−3}  (3 ≤ n, 0 ≤ ℓ).  (9)

Proof. We prove it by induction first on ℓ and second on n.

First, let n = 3. In case ℓ = 0, 1, 3, we can check the recurrence (9) by computer. (For example the expression of a_{3}^{3} contains more than hundred characters. Figure 4 shows a small part of the triangle based on initial elements x, y and z.) Now, we suppose that (9) holds for up to ℓ − 1. We obtain

a_{3}^{6+ℓ} = αa_{3}^{5+ℓ} + βa_{3}^{4+ℓ} + γa_{3}^{3+ℓ}
= α (Aa_{2}^{4+ℓ} + Ba_{1}^{3+ℓ} + Ca_{0}^{2+ℓ}) + β (Aa_{2}^{3+ℓ} + Ba_{1}^{2+ℓ} + Ca_{0}^{1+ℓ})
+ γ (Aa_{2}^{2+ℓ} + Ba_{1}^{1+ℓ} + Ca_{0}^{ℓ})
= A (αa_{2}^{4+ℓ} + βa_{2}^{3+ℓ} + γa_{2}^{2+ℓ}) + B (αa_{1}^{3+ℓ} + βa_{1}^{2+ℓ} + γa_{1}^{1+ℓ})
+ C (αa_{0}^{2+ℓ} + βa_{0}^{1+ℓ} + γa_{0}^{ℓ})
= Aa_{2}^{5+ℓ} + Ba_{1}^{4+ℓ} + Ca_{0}^{3+ℓ}.

Second, we suppose in case any ℓ that (9) holds for up to 4 ≤ n − 1, and thus we have

a_{n}^{n+ℓ} = a_{n−1}^{n+ℓ−1} + a_{n−1}^{n+ℓ} + a_{n−1}^{n+ℓ+1}
= Aa_{n−2}^{n+ℓ−2} + Ba_{n−3}^{n+ℓ−3} + Ca_{n−4}^{n+ℓ−4} + Aa_{n−2}^{n+ℓ−1} + Ba_{n−3}^{n+ℓ−2} + Ca_{n−4}^{n+ℓ−3}

+ Aa_{n−2}^{n+ℓ} + Ba_{n−3}^{n+ℓ−1} + Ca_{n−4}^{n+ℓ−2}

= A (a_{n−2}^{n+ℓ−2} + a_{n−2}^{n+ℓ−1} + a_{n−2}^{n+ℓ}) + B (a_{n−3}^{n+ℓ−3} + a_{n−3}^{n+ℓ−2} + a_{n−3}^{n+ℓ−1})

+ C (a_{n−4}^{n+ℓ−4} + a_{n−4}^{n+ℓ−3} + a_{n−4}^{n+ℓ−2})

= Aa_{n−1}^{n+ℓ−1} + Ba_{n−2}^{n+ℓ−2} + Ca_{n−3}^{n+ℓ−3}.

x yzγx + βy + αz \begin{matrix}αγx+ \\ (αβ + γ)y+ \end{matrix} ; (α^{2} + β)z x + y + z \begin{matrix}γx + (β + 1)y \\ +(α + 1)z \end{matrix} \begin{matrix}(αγ + γ)x+ \\ (αβ + β + γ)y+ \end{matrix} ; (α^{2} + α + β + 1)z \begin{matrix}(αγ + 2γ + 1)x+ \\ (αβ + 2β + γ + 2)y+ \end{matrix} ; (α^{2} + 2α + β + 3)z

Figure 4: A part of the growing of T

Theorem 10 for case ℓ = 0 and Figure 4 provide the main statement of this section.

Corollary 11 (Main corollary). The trinomial transform sequence of a given ternary linear recurrent sequence (a_{k}) defined by (7) is the ternary linear recurrent sequence (b_{k}) defined by

b_{n} = Ab_{n−1} + Bb_{n−2} + Cb_{n−3} (3 ≤ n, 0 ≤ ℓ),

with initial values b_{0} = a_{0}, b_{1} = a_{0} + a_{1} + a_{2} and b_{2} = (αγ + 2γ + 1)a_{0} + (αβ + 2β + γ + 2)a_{1} + (α^{2} + 2α + β + 3)a_{2}.

Moreover, we can give a general statement for the linear homogenous recurrence sequences according to Barbero et al. [3].

Theorem 12. Let (a_{k}) be a linear recurrent sequence of degree r with characteristic polynomial given by p(t), and zeros ω_{1}, ω_{2}, …, ω_{r} are all different. Then its trinomial transform sequence (b_{k}) is a linear recurrent sequence of degree r, and zeros of the characteristic polynomial of (b_{k}) are ω_{1}^{2} + ω_{1} + 1, ω_{2}^{2} + ω_{2} + 1, …, ω_{r}^{2} + ω_{r} + 1.

Proof. Our proof is similar to the proof of Barbero et al. [3, Thm. 10]. If p(t) has distinct complex zeros ω_{1}, …, ω_{r}, then by Binet formula

a_{n} = ∑_{j=1}^{r} A_{j}ω_{j}^{n},

for some complex A_{i} derived from initial conditions [9, Thm. C.1. p. 33]. For all terms of (b_{k}), we have

b_{n} = ∑_{i=0}^{2n} \binom{n}{i}_{2}a_{i} = ∑_{i=0}^{2n} \binom{n}{i}_{2} ∑_{j=1}^{r} A_{j}ω_{j}^{i} = ∑_{j=1}^{r} A_{j}(ω_{j}^{2} + ω_{j} + 1)^{n} .

It is surprising that a ternary recurrence relation with rational coefficients holds for the finite column sequences (a_{i}^{k})_{i=0}^{k}. The following theorem formulates it precisely.

Theorem 13. The terms in the column k can be described by the ternary recurrence relation

a_{n}^{k} = \frac{P}{γ} a_{n−1}^{k} + \frac{Q}{γ}a_{n−2}^{k} + \frac{C}{γ} a_{n−3}^{k} (3 ≤ n ≤ k),

where P = αγ − β + 3γ and Q = αβ − 2αγ + βγ − α + 2β.

Proof. The proof is very similar to that of Theorem 10. We use the induction method. First, let n = 3. For cases k = 3, 4, 5 we can check the equation

γa_{3}^{k} = Pa_{2}^{k} + Qa_{1}^{k} + Ca_{0}^{k}.  (10)

Now, we suppose that the equation (10) holds up to k − 1. So the condition of induction yields the equations

α(γa_{3}^{k−1}) = α(Pa_{2}^{k−1} + Qa_{1}^{k−1} + Ca_{0}^{k−1}),
β(γa_{3}^{k−2}) = β(Pa_{2}^{k−2} + Qa_{1}^{k−2} + Ca_{0}^{k−2}),
γ(γa_{3}^{k−3}) = γ(Pa_{2}^{k−3} + Qa_{1}^{k−3} + Ca_{0}^{k−3}).

Summing the equations and applying Theorem 8 we obtain that (10) holds for any k. Second, if we suppose that

γa_{n−1}^{k} = Pa_{n−2}^{k} + Qa_{n−3}^{k} + Ca_{n−4}^{k}  (11)

holds for any 4 ≤ n ≤ k, then we have

γa_{n−1}^{k−1} = Pa_{n−2}^{k−1} + Qa_{n−3}^{k−1} + Ca_{n−4}^{k−1},
γa_{n−1}^{k} = Pa_{n−2}^{k} + Qa_{n−3}^{k} + Ca_{n−4}^{k},
γa_{n−1}^{k+1} = Pa_{n+1}^{k−3} + Qa_{n+1}^{k−3} + Ca_{n−4}^{k+1}.

Using (1) for the sum of the equations we obtain

γa_{n}^{k} = Pa_{n−1}^{k} + Qa_{n−2}^{k} + Ca_{n−3}^{k}.

4.1 Sums and alternating sums of columns

We give (s_{n}) as a linear recurrent sequence with coefficients given by the coefficients of sequences (a_{n}) and (b_{n}). Recall (s_{n}) was defined in (5).

Theorem 14. If n ≥ 6, then the sequence (s_{n}) can be described by the sixth order homogeneous linear recurrence relation

s_{n} = (α + A)s_{n−1} + (B − αA + β)s_{n−2} − (αB + βA − C − γ)s_{n−3} − (αC + βB + γA)s_{n−4} − (βC + γB)s_{n−5} − γCs_{n−6}. (12)

Proof. First, we prove that the recurrence relations of sequences (a_{n}^{k}), (a_{n}^{n+ℓ}) (ℓ ≥ 0) are the same as relation (12). Extend relation (8) to sixth order homogeneous linear recurrence relation by sum of a_{n}^{k}, Aa_{n}^{k−1}, Ba_{n}^{k−2} and Ca_{n}^{k−3}, moreover extend (9) also by sum of a_{n}^{n+ℓ}, αa_{n−1}^{n+ℓ−1}, βa_{n−2}^{n+ℓ−2} and γa_{n−3}^{n+ℓ−3}. Then we obtain the same coefficients as in (12).

Second, we give the connection between s_{n} and s_{n−2}. It is from

s_{n−1} − a_{0}^{n−1} = ∑_{i=1}^{n−1} a_{i}^{n−1} = ∑_{i=1}^{n−1} (a_{i−1}^{n−2} + a_{i−1}^{n−1} + a_{i−1}^{n}) = ∑_{i=0}^{n−2} a_{i}^{n−2} + ∑_{i=0}^{n−2} a_{i}^{n−1} + ∑_{i=0}^{n−2} a_{i}^{n}
= s_{n−2} + s_{n−1} − a_{n−1}^{n−1} + s_{n} − a_{n−1}^{n} − a_{n}^{n}.

Reordering the equation, we have

s_{n} = −s_{n−2} + a_{n−1}^{n−1} + a_{n−1}^{n} + a_{n}^{n} − a_{0}^{n−1}.

Third, we have finished the preparations to prove the theorem by induction on n. Because of the complexity in case n = 6, we can check the recurrence (12) by computer. Then we suppose that (12) holds for cases up to n − 1. We obtain

s_{n} = −s_{n−2} + a_{n−1}^{n−1} + a_{n−1}^{n} + a_{n}^{n} − a_{0}^{n−1}
= −((α + A)s_{n−3} − (B − αA + β)s_{n−4} − (αB + βA − C − γ)s_{n−5}
−(αC + βB + γA)s_{n−6} − (βC + γB)s_{n−7} − γCs_{n−8})
+(α + A)a_{n−2}^{n−2} + (B − αA + β)a_{n−3}^{n−3} + (αB + βA − C − γ)a_{n−4}^{n−4}
+(αC + βB + γA)a_{n−5}^{n−5} + (βC + γB)a_{n−6}^{n−6} + γCa_{n−7}^{n−7}
+ ⋯
−(α + A)a_{0}^{n−2} − (B − αA + β)a_{0}^{n−3} − (αB + βA − C − γ)a_{0}^{n−4}
−(αC + βB + γA)a_{0}^{n−5} − (βC + γB)a_{0}^{n−6} − γCa_{0}^{n−7}
= (α + A)(−s_{n−3} + a_{n−2}^{n−2} + a_{n−2}^{n−1} + a_{n−1}^{n−1} − a_{0}^{n−2})
+ (B − αA + β)(−s_{n−4} + a_{n−3}^{n−3} + a_{n−3}^{n−2} + a_{n−2}^{n−2} − a_{0}^{n−3})
− (αB + βA − C − γ)(−s_{n−5} + a_{n−4}^{n−4} + a_{n−4}^{n−3} + a_{n−3}^{n−3} − a_{0}^{n−4})
− (αC + βB + γA)(−s_{n−6} + a_{n−5}^{n−5} + a_{n−5}^{n−4} + a_{n−4}^{n−4} − a_{0}^{n−5})
− (βC + γB)(−s_{n−7} + a_{n−6}^{n−6} + a_{n−6}^{n−5} + a_{n−5}^{n−5} − a_{0}^{n−6})
− γC(−s_{n−8} + a_{n−7}^{n−7} + a_{n−7}^{n−6} + a_{n−6}^{n−6} − a_{0}^{n−7})
= (α + A)s_{n−1} + (B − αA + β)s_{n−2} − (αB + βA − C − γ)s_{n−3}
−(αC + βB + γA)s_{n−4} − (βC + γB)s_{n−5} − γCs_{n−6}.

Let (s̄_{n}) be the alternating sum of the values of columns n, so that

s̄_{n} = ∑_{i=0}^{n}(−1)^{i}a_{i}^{n} = ∑_{i=0}^{n} ∑_{k=0}^{2i}(−1)^{i}\binom{i}{k}_{2}a_{0}^{n+k−i}.

Theorem 15. If n ≥ 6, then the alternating sum sequences (s̄_{n}) can be described by the sixth order homogeneous linear recurrence relation

s̄_{n} = (α − A)s̄_{n−1} + (B + αA + β)s̄_{n−2} − (αB − βA + C − γ)s̄_{n−3} + (αC − βB + γA)s̄_{n−4} + (βC − γB)s̄_{n−5} + γCs̄_{n−6}.

Proof. Row by row the signs of the terms in the alternating sums change in directions parallel to the diagonal, hence we have to change the sign of A and C in the summation relation (12). They have influence on the signs of every next and third terms, respectively. In a row the signs of the terms do not change.

5 Examples

In this section, we give some examples for the trinomial transform triangles generated by ternary linear recurrent sequences.

5.1 Fibonacci sequence

Let the base sequence be the Fibonacci sequence (F_{k})_{k=0}^{∞} defined by F_{0} = 0, F_{1} = 1 and F_{k} = F_{k−1} + F_{k−2}, k ≥ 2 (\underline{A000045}). If we extend it to a ternary recurrence (with sum of F_{k} and F_{k−1}), then we obtain that F_{k} = 2F_{k−1} − F_{k−3}, k ≥ 3. So let a_{0}^{k} = F_{k} for any k, moreover α = 2, β = 0 and γ = −1.

When we substitute the initial values into T , then we have the Fibonacci trinomial transform triangle, see Table 1.

0 1 2 3 4  5  6  7  8  9
0 0 1 1 2 3  5  8  13  21  34
1  2 4 6 10 16  26  42  68  110
2  12 20 32 52  84  136  220  356
3  64 104 168 272  440  712  1152
4  336 544 880 1424 2304  3728
5  1760 2848 4608 7456  12064
6  9216 14912 24128 39040
7  48256 78080 126336
8  252672 408832
9  1323008
s_{n} 0 3 17 92 485 2545 13334 69831 365661 1914660
s̄_{n} 0 −1 9 −48 257 −1343 7042 −36861 193029 −1010680

Table 1: Fibonacci trinomial transform triangle

Having observed the rows of Table 1, we have found that they are the well-known i-Fibonacci sequences, defined by F_{0}^{[i]} = 0, F_{1}^{[i]} = i and F_{j}^{[i]} = F_{j−1}^{[i]} +F_{j−2}^{[i]}, j ≥ 2. This result is expressed in the following theorem.

Theorem 16. The terms of the rows in Table 1 are the terms of the 2^{n}-Fibonacci sequences, so that

a_{n}^{k} = F_{k+n}^{[2^{n}]}.

Proof. Obviously, for case n = 1 the theorem is true. Let us suppose that the result is also true for n−1. As the relation between the Fibonacci and i-Fibonacci sequences is i·F_{k} = F_{k}^{[i]}, we gain

a_{n}^{k} = a_{n−1}^{k−1} + a_{n−1}^{k} + a_{n−1}^{k+1} = F_{k−1+n−1}^{[2^{n−1}]} + F_{k+n−1}^{[2^{n−1}]} + F_{k+1+n−1)}^{[2^{n−1}]}
= 2F_{k−n}^{[2^{n−1}]} = F_{k−n}^{[2^{n}]}.

For all the directions parallel to the diagonal of Table 1 and for the trinomial transform sequence, we obtain from (9) and Theorem 11 the following corollaries.

Corollary 17. If 2 ≤ n ≤ k, then

a_{n}^{k} = 6a_{n−1}^{k−1} − 4a_{n−2}^{k−2}.

Corollary 18. The trinomial transform sequence (b_{n}) of the Fibonacci sequence is the binary sequence b_{n} = 6b_{n−1} − 4b_{n−2} with initial elements b_{0} = 0, b_{1} = 2. (The main diagonal of Table 1.)

In OEIS the trinomial transform of the Fibonacci numbers is the sequence \underline{A082761} (1, 4, 20, 104, …), which can be seen in Table 1 as the second diagonal.

We obtain the following corollaries from the theorems of the previous section.

Corollary 19. If 2 ≤ n ≤ k, then

F_{k+n}^{[2^{n}]} = 2F_{k+n−1}^{[2^{n−1}]} + 4F_{k+n−2}^{[2^{n−2}]},
F_{k+n}^{[2^{n}]} = 6F_{k+n−2}^{[2^{n−1}]} − 4F_{k+n−4}^{[2^{n−2}]}.

Corollary 20. For the sum and alternating sum of columns, we have

s_{n} = ∑_{i=0}^{n} F_{i+n}^{[2^{n}]} = ∑_{i=0}^{2n} \begin{matrix}[ \\ ( & {n \atop i} & ) \\ ] \end{matrix}_{2}F_{i} = ∑_{i=0}^{n} ∑_{k=0}^{2i} \binom{i}{k}_{2}F_{n+k−i},

s̄_{n} = ∑_{i=0}^{n}(−1)^{i}F_{i+n}^{[2^{n}]} = ∑_{i=0}^{n}(−1)^{i} ∑_{k=0}^{2i} \binom{i}{k}_{2}F_{n+k−i}.

Moreover, if n ≥ 4, then

s_{k} = 7s_{k−1} − 9s_{k−2} − 2s_{k−3} + 4s_{k−4},
s̄_{k} = −5s̄_{k−1} + 3s̄_{k−2} + 10s̄_{k−3} + 4s̄_{k−4}.

with initial values s_{0} = 0, s_{1} = 3, s_{2} = 17, s_{3} = 92, and s̄_{0} = 0, s̄_{1} = −1, s̄_{2} = 9, s̄_{3} = −48.

5.2 Tribonacci sequence

Let the base sequence a_{0}^{k} be the Tribonacci sequence (\underline{A000073}), defined by t_{k} = t_{k−1} +t_{k−2} + t_{k−3}, k ≥ 3 with initial values t_{0} = 0, t_{1} = 0, t_{2} = 1. So let a_{0}^{k} = t_{k} and α = β = γ = 1. The Tribonacci trinomial transform triangle is depicted in Table 2.

Easy to see that a_{n}^{k} = a_{n−1}^{k+2} = ⋯ = a_{0}^{k+2n} = t_{k+2n}, and from it with the statements in the previous section, we have the following corollaries.

Corollary 21. In the case 3 ≤ n ≤ k, we obtain

a_{n}^{k} = 7a_{n−1}^{k−1} − 5a_{n−2}^{k−2} + a_{n−3}^{k−3},
a_{n}^{k} = 3a_{n−1}^{k} + a_{n−2}^{k} + a_{n−3}^{k}

Moreover, the terms of sequence (a_{n}^{k})_{n=0}^{k} are every second terms of the Tribonacci numbers, so that a_{n}^{n} = t_{3n}.

0 1 2 3 4  5  6  7  8  9
0 0 0 1 1 2  4  7  13  24  44
1  1 2 4 7 13  24  44  81  149
2  7 13 24 44  81  149  274  504
3  44 81 149 274  504  927  1705
4  274 504 927 1705 3136  5768
5  1705 3136 5768 10609 19513
6  10609 19513 35890 66012
7  66012 121415 223317
8  410744 755476
9  2555757
s_{k} 0 1 10 62 388 2419 15058 93708 583100 3628245
s̄_{k} 0 −1 6 −34 212 −1315 8190 −50948 317036 −1972637

Table 2: Tribonacci trinomial transform triangle

Corollary 22. The trinomial transform sequence (b_{n}) of the Tribonacci sequence is the ternary sequence b_{n} = 6b_{n−1} − 4b_{n−2} + b_{n−3} with initial terms b_{0} = 0, b_{1} = 1, b_{2} = 7. (The main diagonal of Table 2.)

In OEIS the trinomial transform of the Tribonacci numbers is the sequence \underline{A192806} (1, 1, 4, 24, 149, 927, …), which is the third diagonal in Table 1 with an additional first term.

Corollary 23. For the sum and alternating sum of columns, we have

s_{n} = ∑_{i=0}^{n} t_{n+2i} = ∑_{i=0}^{2n} \begin{matrix}[ \\ ( & {n \atop i} & ) \\ ] \end{matrix}_{2}t_{i} = ∑_{i=0}^{n} ∑_{k=0}^{2i} \binom{i}{k}_{2}t_{n+k−i},

s̄_{n} = ∑_{i=0}^{n}(−1)^{i}t_{n+2i} = ∑_{i=0}^{n}(−1)^{i} ∑_{k=0}^{2i} \binom{i}{k}_{2}t_{n+k−i}.

In addition,

s_{n} = 8s_{n−1} − 11s_{n−2} − 3s_{n−4} + 4s_{n−5} − s_{n−6}  (n ≥ 6),
s̄_{n} = −6s̄_{n−1} + 3s̄_{n−2} + 12s̄_{n−2} + 13s̄_{n−4} + 6s̄_{n−5} + s̄_{n−6}  (n ≥ 6),

with initial values s_{0} = 0, s_{1} = 1, s_{2} = 10, s_{3} = 62, s_{4} = 388, s_{5} = 2419, and s̄_{0} = 0, s̄_{1} = −1, s̄_{2} = 6, s̄_{3} = −34, s̄_{4} = 212, s̄_{5} = −1315.

5.3 The constant sequence 1

In this subsection, we give Table 3 generated by the constant sequence 1 (\underline{A000012}) and the expressions that prove Theorem 1.

0 1 2 3 4 5  6  7  8  9
0 1 1 1 1 1 1  1  1  1  1
1  3 3 3 3 3  3  3  3  3
2  9 9 9 9  9  9  9  9
3  27 27 27 27  27  27  27
4  81 81 81  81  81  81
5  243 243 243 243 243
6  729 729 729 729
7  2187 2187 2187
8  6561 6561
9  19683
s_{k} 1 4 13 40 121 364 1093 3280 9841 29524
s̄_{k} 1 −2 7 −20 61 −182 547 −1640 4921 −14762

Table 3: Trinomial transform triangle generated by the constant sequence 1

One can easily see that a_{n}^{k} = 3^{n} (\underline{A000244}). It implies that the trinomial transform sequence of the constant sequence 1 is the sequence 3^{n}. Moreover, the columns also form geometric sequences with common ratio 3. Thus

s_{n} = ∑_{i=0}^{2n} \begin{matrix}[ \\ ( & {n \atop i} & ) \\ ] \end{matrix}_{2} = ∑_{i=0}^{n} ∑_{k=0}^{2i} \binom{i}{k}_{2} = ∑_{i=0}^{n} 3^{i} = \frac{3^{n+1} − 1}{2} (\underline{A003462}),

s̄_{n} = ∑_{i=0}^{n} ∑_{k=0}^{2i} \binom{i}{k}_{2}(−1)^{i} = ∑_{i=0}^{n}(−3)^{i} = \frac{3(−3)^{n} + 1}{4} (\underline{A014983}),

5.4 Natural numbers

Let a_{0}^{k} = k, the non-negative integers (\underline{A001477}). We obtain that a_{n}^{k} = k3^{n}, and the trinomial transform of the natural sequence is the sequence n3^{n} (\underline{A036290}).

In this case, the columns also form geometric sequences with common ratio 3 (see Table 4). Thus

s_{n} = ∑_{i=0}^{2n} i\begin{matrix}[ \\ ( & {n \atop i} & ) \\ ] \end{matrix}_{2} = ∑_{i=0}^{n} ∑_{k=0}^{2i} n\binom{i}{k}_{2} = ∑_{i=0}^{n} n3^{i} = n\frac{3^{n+1} − 1}{2},

s̄_{n} = ∑_{i=0}^{n} ∑_{k=0}^{2i} \binom{i}{k}_{2}(−1)^{i}n = ∑_{i=0}^{n} n(−3)^{i} = n\frac{3(−3)^{n} + 1}{4}.

0 1 2 3 4 5  6  7  8  9
0 0 1 2 3 4 5  6  7  8  9
1  3 6 9 12 15 18  21  24  27
2  18 27 36 45 54  63  72  81
3  81 108 135 162 189  216  243
4  324 405 486 567  648  729
5  1215 1458 1701 1944 2187
6  4374 5103 5832 6561
7  15309 17496 19683
8  52488 59049
9  177147
s_{k} 0 4 26 120 484 1820 6558 22960 78728 265716
s̄_{k} 0 −2 14 −60 244 −910 3282 −11480 39368 −132858

Table 4: Trinomial transform triangle generated by natural numbers

5.5 Two other sequences

In this subsection, we give two cases without tables, whose trinomial transform sequences are the all 1’s sequence and the natural numbers mentioned in the previous subsections. We gain the results with very easy calculations.

First, let a_{0}^{k} = (−1)^{k} (\underline{A033999}). Then a_{n}^{k} = (−1)^{n+k} and b_{n} = 1.

s_{n} = ∑_{i=0}^{2n}(−1)^{i}\begin{matrix}[ \\ ( & {n \atop i} & ) \\ ] \end{matrix}_{2} = ∑_{i=0}^{n} ∑_{k=0}^{2i}(−1)^{n+k−i}\binom{i}{k}_{2} = ∑_{i=0}^{n}(−1)^{n+i} = \begin{cases}0, & if n is odd; \\ 1, & if n is even. \end{cases}

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

Second, let a_{0}^{k} = (−1)^{k}k (\underline{A038608}). Then a_{n}^{k} = (−1)^{n+k}k and b_{n} = n.

s_{n} = ∑_{i=0}^{2n}(−1)^{i}i\begin{matrix}[ \\ ( & {n \atop i} & ) \\ ] \end{matrix}_{2} = ∑_{i=0}^{n} ∑_{k=0}^{2i}(−1)^{n+k−i}n\binom{i}{k}_{2} = ∑_{i=0}^{n}(−1)^{n+i}n

= \begin{cases}0, & if n is odd or n = 0; \\ n, & otherwise. \end{cases}

s̄_{n} = n ∑_{i=0}^{n} ∑_{k=0}^{2i} \binom{i}{k}_{2}(−1)^{i} = ∑_{i=0}^{n} n = n^{2} + n (\underline{A002378}).

References

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

[2] G. Anatriello and G. Vincenzi, Tribonacci-like sequences and generalized Pascal’s pyramids, Internat. J. Math. Ed. Sci. Tech. 45 (2014), 1220–1232.

[3] S. Barbero, U. Cerruti, and N. Murru, Transforming recurrent sequences by using Binomial and Invert operators, J. Integer Sequences 13 (2010), Article 10.7.7.

[4] S. Barbero, U. Cerruti, and N. Murru, A generalization of the binomial interpolated operator and its action on linear recurrent sequences, J. Integer Sequences 13 (2010), Article 10.9.7.

[5] 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.

[6] L. Németh, On the binomial interpolated triangles, J. Integer Sequences 20 (2017), Article 17.7.8.

[7] J. Pan, Some properties of the multiple binomial transform and the Hankel transform of shifted sequences, J. Integer Sequences 14 (2011), Article 11.3.4.

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

[9] T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations, Cambridge University Press, 1986.

[10] M. Z. Spivey and L. L. Steil, The k-binomial transforms and the Hankel transform, J. Integer Sequences 9 (2006), Article 06.1.1.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11B39, 11B65, 11B75. Keywords: binomial transform, trinomial transform, trinomial coefficient, recurrent sequence, Fibonacci sequence, Tribonacci sequence.

(Concerned with sequences \underline{A000012}, \underline{A000045}, \underline{A000073}, \underline{A000244}, \underline{A001477}, \underline{A002378}, \underline{A003462}, \underline{A014983}, \underline{A027907}, \underline{A033999}, \underline{A036290}, \underline{A038608}, \underline{A082761}, \underline{A097861}, \underline{A097893}, \underline{A097894}, and \underline{A192806}.)

Received January 9 2018; revised version received May 7 2018; May 23 2018; July 16 2018. Published in Journal of Integer Sequences, August 23 2018.

Return to Journal of Integer Sequences home page.