On the Binomial Interpolated Triangles

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

                  nemeth.laszlo@uni-sopron.hu

Abstract

The binomial interpolated transform of a sequence is a generalization of the wellknown binomial transform. We examine a Pascal-like triangle, on which a binomial interpolated transform works between the left and right diagonals, focusing on binary recurrences. We give the sums of the elements in rows and in rising diagonals, and we define two special classes of these arithmetical triangles.

1 Introduction

Let us define the sequence b = {b_{n}}_{n=0}^{∞} ∈ ℝ^{∞} as the binomial transform of the given sequence a = \{a_{n}\}_{n=0}^{∞} ∈ ℝ^{∞} 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 researchers [1, 2, 3, 5, 7] examined the properties and the generalizations of the binomial transformation. One of its generalizations is the so-called binomial interpolated transform [1] given by

b_{n} = ∑_{i=0}^{n} \binom{n}{i}u^{i}v^{n−i}a_{i}  (1)

for any non-zero u, v ∈ ℝ. Bhadouria at al. [2] and Falcon and Plaza [3] showed for some (falling and rising) k-binomial transform cases, when u = 1, v = k; u = k, v = 1 or u = v = k, that there are special infinite (Pascal-like) triangles, whose left diagonal (left leg) contains the terms of a and the right one (right leg) the terms of b.

In our paper, we examine the inner part of this type of triangle in a generalized form focusing exclusively on the binary recurrence sequences a. We determine the sums and alternating sums of rows, rising diagonals and central term sequence and give explicit forms for entries of the triangle. Finally, we define and examine two special classes of our arithmetical triangles.

2 Binomial interpolated triangle

Let an arithmetical triangle (called “derangement triangle” [2]) be defined by terms a_{n,k} (k-th entry in row n — see Figure 1) from the sequence {a_{n,0}}_{n=0}^{∞}, where

a_{n,k} = ua_{n,k−1} + va_{n−1,k−1} (1 ≤ k ≤ n),  (2)

u, v ∈ ℝ and uv ≠ 0.

We shall show that the right diagonal sequence is a binomial interpolated transform of the left diagonal sequence with parameters u and v. Moreover, we shall prove that the converse

also holds, with the parameters −v/u and 1/u. a_{0,0} a_{1,0} a_{1,1} a_{2,0} a_{2,1} a_{2,2} a_{3,0} a_{3,1} a_{3,2} a_{3,3} a_{4,0} a_{4,1} a_{4,2} a_{4,3} a_{4,4}... ⋮⋮⋮⋮... a_{n−1,k−1} a_{n,k−1} a_{n,k} vu a_{n−1,k−1} a_{n,k} a_{n,k−1} −\frac{v}{u} \frac{1}{u}

Figure 1: Binomial interpolated triangle

Theorem 1. For all integer r, k such that k_{0} ≤ k ≤ n, where k_{0} ≥ 0 is a fixed integer, we have

a_{n,k} = ∑_{i=0}^{k−k_{0}} \binom{k − k_{0}}{i}u^{i}v^{k−k_{0}−i}a_{n−k+k_{0}+i,k_{0}}.  (3)

Proof. We prove it by induction on n and k. If k = k_{0}, then the formula (3) trivially holds for any n. We suppose that (3) is true up to k_{0} ≤ k − 1. Let 1 ≤ \overline{k} = k − k_{0}. Then

a_{n,k} = ua_{n,k−1} + va_{n−1,k−1}
= u ∑_{i=0}^{\overline{k}−1} \binom{\overline{k} − 1}{i}u^{i}v^{\overline{k}−i−1}a_{n−\overline{k}+i+1,k_{0}} + v ∑_{i=0}^{\overline{k}−1} \binom{\overline{k} − 1}{i}u^{i}v^{\overline{k}−i−1}a_{n−\overline{k}+i,k_{0}}

= ∑_{i=0}^{\overline{k}−1} \binom{\overline{k} − 1}{i}u^{i+1}v^{\overline{k}−i−1}a_{n−\overline{k}+i+1,k_{0}} + ∑_{i=0}^{\overline{k}−1} \binom{\overline{k} − 1}{i}u^{i}v^{\overline{k}−i}a_{n−\overline{k}+i,k_{0}}

= ∑_{i=1}^{\overline{k}} \binom{\overline{k} − 1}{i − 1}u^{i}v^{\overline{k}−i}a_{n−\overline{k}+i,k_{0}} + ∑_{i=0}^{\overline{k}−1} \binom{\overline{k} − 1}{i}u^{i}v^{\overline{k}−i}a_{n−\overline{k}+i,k_{0}}

= u\overline{k}a_{n,k_{0}} + ∑_{i=1}^{\overline{k}−1} \binom{\overline{k} − 1}{i − 1}u^{i}v^{\overline{k}−i}a_{n−\overline{k}+i,k_{0}} + v\overline{k}a_{n−\overline{k},k_{0}} + ∑_{i=1}^{\overline{k}−1} \binom{\overline{k} − 1}{i}u^{i}v^{\overline{k}−i}a_{n−\overline{k}+i,k_{0}}

= v\overline{k}a_{n−\overline{k},k_{0}} + ∑_{i=1}^{\overline{k}−1} (\binom{\overline{k} − 1}{i − 1} + \binom{\overline{k} − 1}{i}) u^{i}v^{\overline{k}−i}a_{n−\overline{k}+i,k_{0}} + u\overline{k}a_{n,k_{0}}

= ∑_{i=0}^{\overline{k}} \binom{\overline{k}}{i}u^{i}v^{\overline{k}−i}a_{n−\overline{k}+i,k_{0}}.

Considering the substitutions k_{0} = 0 and k = n, or considering a fixed term a_{n_{0},k_{0}} leads us to the following corollary.

Corollary 2. The right diagonal sequence is the binomial interpolated transform of the left diagonal sequence, so

b_{n} = a_{n,n} = ∑_{i=0}^{n} \binom{n}{i}u^{i}v^{n−i}a_{i,0}.  (4)

Furthermore, let us fix k_{0} and n_{0}, so that 0 ≤ k_{0} ≤ n_{0}. Then the terms \overline{a}_{i,j} = a_{n,k} form a binomial interpolated sub-triangle (see Figure 2), where i = n − n_{0}, j = k − k_{0} n_{0} ≤ n, k_{0} ≤ k ≤ n−(n_{0}−k_{0}). The sub-triangle’s right diagonal sequence is the binomial interpolated transform of its left diagonal sequence.

We now express the terms a_{n,k} by the right diagonal sequence {a_{n,n}}_{n=0}^{∞}.

Theorem 3. For any 0 ≤ k ≤ n

a_{n}^{k} = ∑_{i=0}^{n−k} \binom{n − k}{i} (\frac{1}{u})^{i} (−\frac{v}{u})^{n−k−i} a_{k+i}^{k+i}.  (5)

a_{0,0} a_{1,0} a_{1,1} ............n_{0} k_{0} \overline{a}_{0,0} \overline{a}_{1,0} \overline{a}_{1,1}... ... ... ...

Figure 2: Sub-triangle of the binomial interpolated triangle

Proof. We suppose that the sequence {b_{n} = a_{n,n}} with {b_{n}}_{n=0}^{∞} = {a_{n,n}}_{n=0}^{∞} is given. Let U = 1/u and V = −v/u, then the right equality is a_{n,k−1} = Ua_{n,k} + V a_{n−1,k−1}, according to (2). Based on this connection, we can write the entries of the binomial interpolated triangle (from right to left) by b_{n,r}, where b_{n,0} = b_{n}, b_{n,r} = Ub_{n,r−1} + V b_{n−1,r−1} (1 ≤ r ≤ n). Using relation (3), proved in Theorem 1, we obtain

b_{n,r} = ∑_{i=0}^{r} \binom{r}{i}U^{i}V^{r−i}b_{n−r+i,0}.

Since b_{n,r} = a_{n,n−r}, considering the substitution k = n − r, the thesis follows.

If k = 0, as a direct consequence of Theorem 3, the inverse transformation of the binomial interpolated transform (1) is

a_{n,0} = ∑_{i=0}^{n} \binom{n}{i} (\frac{1}{u})^{i} (−\frac{v}{u})^{n−i} a_{i,i}.  (6)

3 Binary binomial interpolated triangle

Let a_{n,0} = a_{n}, where {a_{n}}_{n=0}^{∞} is a binary recursive sequence defined by

a_{n} = αa_{n−1} + βa_{n−2} (2 ≤ n, α, β ∈ ℝ, αβ ≠ 0),  (7)

with initial values a_{0}, a_{1} ∈ ℝ (|a_{0}|+|a_{1}| ≠ 0). Then we call the binomial interpolated triangle binary binomial interpolated triangle and we let BIT (a_{0}, a_{1}, α, β; u, v) (in short BIT ) denote it.

Bhadouria et al. [2] gave three special examples, where the triangles are generated by the 4-Lucas sequence. They are BIT (2, 4, 4, 1; 1, 1), BIT (2, 4, 4, 1; 4, 1) and BIT (2, 4, 4, 1; 4, 4).

From now on, we will use two important variables

A = uα + 2v and B = u^{2}β − uvα − v^{2}.

First of all, we give some recursive formulas for terms a_{n,k}. The results of the next technical lemma will be useful during the proofs of the further theorems.

Lemma 4. The following recurrence relations hold

a_{n,k} = αa_{n−1,k} + βa_{n−2,k}  (2 ≤ k + 2 ≤ n),  (8)
a_{n}^{k} = \frac{uβ}{v} a_{n−1,k} − \frac{B}{v} a_{n−1,k−1}  (2 ≤ k + 1 ≤ n),  (9)
a_{n,k} = \frac{uα + v}{u} a_{n−1,k} + \frac{B}{u} a_{n−2,k−1}  (2 ≤ k + 1 ≤ n),  (10)

a_{n,k} = (uα + v)a_{n−1,k−1} + uβa_{n−2,k−1}  (2 ≤ k + 1 ≤ n),  (11)
a_{n,k} = \frac{u^{2}β + v^{2}}{v} a_{n−1,k−1} − \frac{uB}{v} a_{n−1,k−2}  (2 ≤ k ≤ n),  (12)
a_{n,k} = A a_{n−1,k−1} + B a_{n−2,k−2}  (2 ≤ k ≤ n),  (13)

a_{n,k} = \frac{2uβ − vα}{β}a_{n,k−1} − \frac{B}{β} a_{n,k−2}  (2 ≤ k ≤ n).  (14)

Proof. First we prove relation (8) by induction. For k = 0 it corresponds to definition (7). Let us suppose that this formula is true up to k − 1. So, if x = a_{n−3,k−1} and y = a_{n−2,k−1}, then a_{n−1,k−1} = βx + αy and a_{n,k−1} = αβx + (β + α^{2})y hold. Figure 3, which is a suitable part of Figure 1, depicts it. Now a_{n−2,k} = vx + uy, a_{n−1,k} = uβx + (uα + v)y and a_{n,k} = (uαβ +vβ)x+(uα^{2} +vα +uβ)y, which gives (8). Moreover, we proved with it, that Figure 3 could be any part of Figure 1.

In order to prove the further equations we can also use the relevant part of Figure 3. For example, in the case (11) a_{n,k} = (uα + v) y + uβ x = uβx + (uα + v)y.

The relation (13) gives that the right diagonal sequence b (and the i-th diagonals parallel to it) satisfies the binary recurrence relation

∀n ≥ 2 b_{n} = Ab_{n−1} + Bb_{n−2}  (15)

with initial values b_{0} = a_{0}, b_{1} = ua_{1} + va_{0} (generally, b_{0} = a_{i,0}, b_{1} = a_{i+1,1}, i ≥ 0). Moreover, the system of equations A = 0, B = 0 gives v = −uα/2 and u^{2}(α^{2} + 4β) = 0. Thus, as the condition uv ≠ 0 holds, if v ≠ −uα/2 or α^{2} + 4β ≠ 0, then |A| + |B| ≠ 0, otherwise A = B = 0.

x yβx + αy αβx + (α^{2} + β)y vx + uy uβx + (uα + v)y \begin{matrix}(uαβ + vβ)x + \\ (uα^{2} + vα + uβ)y \end{matrix} \begin{matrix}(u^{2}β + v^{2})x + \\ (u^{2}α + 2uv)y \end{matrix} \begin{matrix}(u^{2}αβ + 2uvβ)x + \\ (u^{2}α^{2} + u^{2}β + 2uvα + v^{2})y \end{matrix}

Figure 3: A part of the growing

3.1 Sums and alternating sums of rows

Let s = {s_{n}}_{n=0}^{∞} be the sequence whose elements are the sums of the values belonging to the n-th row of a binomial interpolated triangle. We have

s_{n} = ∑_{k=0}^{n} a_{n,k} = ∑_{k=0}^{n} ∑_{i=0}^{k} \binom{k}{i}u^{i}v^{k−i}a_{n−k+i,0}.  (16)

We obtain a linear recurrence for s, whose coefficients depend only on α, β, A and B, i.e., the coefficients of the binary recurrences related to sequences a and b.

Theorem 5. The sequence s satisfies the following fourth order linear homogeneous recurrence

∀n ≥ 4 s_{n} = (α + A)s_{n−1} + (β − αA + B)s_{n−2} − (αB + βA)s_{n−3} − βBs_{n−4}.  (17)

Proof. The sum of row n can be given by the previous two ones in form

s_{n} = α(s_{n−1} − a_{n−1,n−1}) + βs_{n−2} + a_{n,n−1} + a_{n,n}.  (18)

Since ua_{n,n−1} = a_{n,n} − va_{n−1,n−1} then from (18) we obtain

u s_{n} = uα s_{n−1} + uβ s_{n−2} + (u + 1)a_{n,n} − (αu + v)a_{n−1,n−1}.  (19)

Applying (13) and as A − αu − v = v we have

u s_{n} = uα s_{n−1} + uβ s_{n−2} + (Au + v)a_{n−1,n−1} + B(u + 1)a_{n−2,n−2}.  (20)

Now we transform (19) into

u s_{n−1} = uα s_{n−2} + uβ s_{n−3} + (u + 1)a_{n−1,n−1} − (αu + v)a_{n−2,n−2}.  (21)

Transforming again (19) into form u s_{n−2} = uα s_{n−3} + … and using (13) we gain

uB s_{n−2} = uB(α s_{n−3} + β s_{n−4}) − (αu + v)a_{n−1,n−1} + (B(u + 1) + (αu + v)A) a_{n−2,n−2}. (22)

Finally, let us express a_{n−1,n−1} and a_{n−2,n−2} from (20) and (21), respectively. We substitute them into (22) and obtain (17).

Remark 6. It should be noticed that the recurrence (18) is the minimal order recurrence of s when

B(u + 1)^{2} + (αu + v)(Au + v) ≠ 0.

Indeed, in this case the determinant of coefficients of the system (from (20) and (21))

\begin{cases}(Au + v)a_{n−1,n−1} + B(u + 1)a_{n−2,n−2} = u s_{n} − uα s_{n−1} − uβ s_{n−2} \\ (u + 1)a_{n−1,n−1} − (αu + v)a_{n−2,n−2} = u s_{n−1} − uα s_{n−2} − uβ s_{n−3} \end{cases}

is different from 0, so the system has a unique solution, otherwise when

B(u + 1)^{2} + (αu + v)(Au + v) = 0

or, equivalently, with a little bit of calculations, when B(u + 1)^{2} + (α − u)(v + uα) = 0 the minimal order of the linear recurrence of s should be less then four. For example, the solution u = −1 and v = α implies that A = α and B = β. Then the relation (20) becomes

∀n ≥ 2 s_{n} = α s_{n−1} + β s_{n−2}.  (23)

Obviously, summing relations s_{n} = αs_{n−1} + βs_{n−2}, −αs_{n−1} = −α^{2}s_{n−2} − αβs_{n−3} and −βs_{n−2} = −αβs_{n−3} − β^{2}s_{n−4} we find that the recurrence (17) also holds for sequence s, but it is not the minimal order one.

Let the sequence s̄ = {s̄_{n}}_{n=0}^{∞} be the alternating sum sequence, where the terms are the values of rows of a binomial interpolated triangle, so that

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

Theorem 7. The sequence s̄ satisfies the following fourth order linear homogeneous recurrence

∀n ≥ 4 s̄_{n} = (α − A)s̄_{n−1} + (β + αA + B)s̄_{n−2} − (αB − βA)s̄_{n−3} − βBs̄_{n−4}.  (24)

Proof. Row by row the signs of the entries in the alternating sums do not change in directions parallel to the left diagonal (sign((−1)^{k}a_{n,k}) = sign((−1)^{k}a_{n−1,k})), but parallel to the right diagonal they change (sign((−1)^{k}a_{n,k}) ≠ sign((−1)^{k−1}a_{n−1,k−1})). Hence we only have to change the sign of A in the summation relation (17).

Remark 8. If u = −1 and v = α, then the relation (24) becomes more simple,

∀n ≥ 3 s̄_{n} = (α^{2} + 2β)s̄_{n−2} − β^{2}s̄_{n−4}.  (25)

3.2 Rising diagonal sum sequence

The sequence d = {d_{n}}_{n=0}^{∞} of sums of elements in rising diagonals has the following definition

∀n ≥ 0 d_{n} = ∑_{k=⌈ \frac{n}{2} ⌉}^{n} a_{k,n−k} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} a_{n−k,k}.  (26)

When we consider the Pascal arithmetical triangle it is well-known that these sums provide the Fibonacci sequence. We give the recurrence relation for the sequence of sums of elements belonging to rising diagonal (i.e.,“shallow diagonal” as they are defined in Wolfram Math World [8]) of our binomial interpolated triangles.

Theorem 9. The rising diagonals sums sequence d of a BIT satisfies the sixth order linear recurrence relation

∀n ≥ 6 D_{n} = AD_{n−2} + BD_{n−4},  (27)

where D_{n} = −d_{n} + αd_{n−1} + βd_{n−2}. Moreover, for even n (n = 2k, n ≥ 2), D_{n} = −b_{k} also holds.

We point out that with the equation (27) is a concise expression for the following sixth order recurrence relation

d_{n} = αd_{n−1} + (β + A)d_{n−2} − αAd_{n−3} + (−βA + B)d_{n−4} − αBd_{n−5} − βBd_{n−6}.  (28)

Proof. Without loss of generality, let n = 2k. The values of d_{n+2} and d_{n+3} can be given by the previous two ones in forms

d_{n+2} = αd_{n+1} + βd_{n} + a_{k+1,k+1},
d_{n+3} = α (d_{n+2} − a_{k+1,k+1}) + βd_{n+1} + a_{k+2,k+1},

generally for even and odd indexes we have

d_{n+2i} = αd_{n+2i−1} + βd_{n+2i−2} + a_{k+i,k+i},
d_{n+2i+1} = α (d_{n+2i} − a_{k+i,k+i}) + βd_{n+2i−1} + a_{k+i+1,k+i}.

When we consider D_{n}, with n even, we obtain

∀i ≥ 1 a_{k+i,k+i} = d_{n+2i} − αd_{n+2i−1} − βd_{n+2i−2} = −D_{n+2i},

and according to (13)

D_{n+6} − AD_{n+4} − BD_{n+2} = −a_{k+3,k+3} + Aa_{k+2,k+2} + Ba_{k+1,k+1} = 0.

If we deal with the case D_{n}, with n odd, then, using relations (10) and (2), we find

d_{n+3} = αd_{n+2} + βd_{n+1} + \frac{v}{u}a_{k+1,k+1} + \frac{B}{u} a_{k,k},
d_{n+5} = αd_{n+4} + βd_{n+3} + \frac{vA + B}{u} a_{k+1,k+1} + \frac{vB}{u} a_{k,k},
d_{n+7} = αd_{n+6} + βd_{n+5} + \frac{vA^{2} + vB + AB}{u} a_{k+1,k+1} + \frac{vAB + B^{2}}{u} a_{k,k}.

Thus

u(D_{n+7} − AD_{n+5} − BD_{n+3}) =

(−(vA^{2} + vB + AB) + A(vA + B) + vB)a_{k+1,k+1}

+ (−(vAB + B^{2}) + vAB + B^{2})a_{k,k} = 0.

3.3 Central elements

The central elements of the binomial triangles are the terms a_{2k,k} with k ≥ 0. In this subsection we give the relation between them, moreover it turns out that the before mentioned recurrence relation holds for all the columns (which are parallel to the vertical axis of the triangle). These sequences are defined by {a_{2k+ℓ,k}}_{k=k_{0}}^{∞} with ℓ ∈ ℤ and

k_{0} = \begin{cases}0, & if ℓ ≥ 0; \\ |ℓ|, & if ℓ < 0. \end{cases}  (29)

Moreover, if ℓ = 0, then it is the sequence of the central elements.

Theorem 10. All the sequences {a_{2k+ℓ,k}}_{k=k_{0}}^{∞} of the binomial interpolated triangle with ℓ ∈ ℤ and k_{0} defined by (29) satisfy the same binary homogeneous recurrence relation

c_{k+2} = (α^{2}u + αv + 2βu)c_{k+1} − βBc_{k},  (30)

where c_{k} = a_{2k+ℓ,k}.

Proof. We have to prove that

a_{2(k+2)+ℓ,k+2} = (α^{2}u + αv + 2βu)a_{2(k+1)+ℓ,k+1} − β(u^{2}β − uvα − v^{2})a_{2k+ℓ,k}.  (31)

First, supposing that uα + v ≠ 0 and recalling (11) and (8) we obtain

a_{2k+3+ℓ,k+1} = (uα + v)a_{2k+2+ℓ,k} + uβa_{2k+1+ℓ,k}
= (uα + v) (αa_{2k+1+ℓ,k} + βa_{2k+ℓ,k}) + uβa_{2k+1+ℓ,k}
= (uα^{2} + vα + uβ)\frac{a_{2k+2+ℓ,k+1} − uβa_{2k+ℓ,k}}{uα + v} + (uα + v)βa_{2k+ℓ,k},

furthermore

a_{2k+4+ℓ,k+2} = (uα + v)a_{2k+3+ℓ,k+1} + uβa_{2k+2+ℓ,k+1}
= (uα^{2} + vα + uβ) (a_{2k+2+ℓ,k+1} − uβa_{2k+ℓ,k}) + (uα + v)^{2}βa_{2k+ℓ,k}
+uβa_{2k+2+ℓ,k+1}
= (uα^{2} + vα + 2uβ)a_{2k+2+ℓ,k+1} + β(−u^{2}β + uvα + v^{2})a_{2k+ℓ,k}.

Second, when v = −uα the equality (30) becomes

c_{k+2} = 2uβc_{k+1} − u^{2}β^{2}c_{k},

or explicitly

a_{2(k+2)+ℓ,k+2} = 2uβa_{2(k+1)+ℓ,k+1} − u^{2}β^{2}ca_{2k+ℓ,k}.  (32)

Thus, since the sequence is a geometric progression we have

a_{2(k+2)+ℓ,k+2} = uβa_{2(k+1)+ℓ,k+1} = u^{2}β^{2}a_{2k+ℓ,k},

and clearly (32) holds because it corresponds to the identity uβa_{2(k+1)+ℓ,k+1} = 2uβa_{2(k+1)+ℓ,k+1} − uβa_{2(k+1)+ℓ,k+1}.

3.4 Explicit formula

Theorem 11. Let D = \sqrt{α^{2} + 4β}. If D ≠ 0, then the explicit formula of a_{n,k} is

a_{n,k} = \frac{(vD + αv − 2βu)a_{n,0} + 2βa_{n,1}}{2vD} (\frac{βu − vx_{2}}{β} )^{k} +

\frac{(vD − αv + 2βu)a_{n,0} − 2βa_{n,1}}{2vD} (\frac{βu − vx_{1}}{β} )^{k} , (33)

where x_{1} = (α + D)/2, x_{2} = (α − D)/2 and

a_{n,0} = \frac{(D − α)a_{0,0} + 2a_{1,0}}{2D} x_{1}^{n} + \frac{(D + α)a_{0,0} − 2a_{1,0}}{2D} x_{2}^{n},  (34)
a_{n,1} = \frac{(D − α)a_{0,0} + 2a_{1,0}}{2D} x_{1}^{n−1}(ux_{1} + v) + \frac{(D + α)a_{0,0} − 2a_{1,0}}{2D} x_{2}^{n−1}(ux_{2} + v). (35)

If D = 0 and A ≠ 0, then the explicit formula is

a_{n,k} = (a_{n,0} + k (\frac{αa_{n,1}}{A} − a_{n,0})) (\frac{A}{α})^{k},

where

a_{n,0} = (a_{0,0} + n\frac{2a_{1,0} − αa_{0,0}}{α} ) (\frac{α}{2})^{n}  (36)
a_{n,1} = ua_{n,0} + v (a_{0,0} + (n − 1)\frac{2a_{1,0} − αa_{0,0}}{α} ) (\frac{α}{2})^{n−1} .  (37)

If D = 0 and A = 0, then

a_{n,0} = (a_{0,0} + n\frac{2a_{1,0} − αa_{0,0}}{α} ) (\frac{α}{2})^{n}  (38)
a_{n,1} = u\frac{2a_{1,0} − αa_{0,0}}{α} (\frac{α}{2})^{n} .  (39)

and a_{n,k} = 0, if k ≥ 2.

Proof. We suppose that α^{2} + 4β ≠ 0. Firstly, we give the explicit form of the elements in case of the main path (k = 0). As the recursion is binary with coefficient α and β, then the characteristic equation of (7) is x^{2} − αx − β = 0 with roots x_{1} ≠ x_{2}. Consequently, for all n ≥ 0 the term a_{n,0} is a linear combination of the powers x_{1}^{n}, x_{2}^{n}. In order to determine the coefficients of this linear combination, we need to solve the system of equations px_{1}^{i} + qx_{2}^{i} = a_{i,0}, i = 0, 1. From this system we find p = \frac{a_{1,0}−a_{0,0}x_{2}}{x_{1}−x_{2}} and q = \frac{a_{1,0}x_{1}−a_{1,0}}{x_{1}−x_{2}} . Thus observing that

x_{1} = \frac{a + D}{2}, x_{2} = \frac{a − D}{2}, x_{1} − x_{2} = D,

where D = \sqrt{α^{2} + 4β}, we easily find equality (34). Moreover a_{n,1} = ua_{n,0} + va_{n−1,0} yields (35).

Secondly, we give similarly the explicit formula of the sequence {a_{n,k}}_{k=0}^{n} with initial conditions a_{n,0} and a_{n,1}. Because of (14), its characteristic equation is

y^{2} − \frac{2βu − αv}{β} y − \frac{αuv − βu^{2} + v^{2}}{β} = 0

and the roots are

y_{1} = \frac{2βu − αv + vD}{2β} = u + \frac{v(D − α)}{2β} = \frac{βu − vx_{2}}{β} and y_{2} = \frac{βu − vx_{1}}{β} .

When we consider the case D^{2} = α^{2} + 4β = 0 and A ≠ 0 (or, equivalently, β = −α^{2}/4 and v = −uα/2) we use the same method adopted before. Taking in account that the characteristic equation x^{2} − αx − β = 0 has the unique root x_{0} = α/2, we have to solve the system (p + qi)x_{0}^{i} = a_{i,0}, i = 0, 1, which provides the coefficients p, q for a_{n,0} = (p + qn)x_{0}^{n} in equality (36). In this case the characteristic equation of sequence {a_{n}^{k}}_{k=0}^{n} also has just one root y_{0} = A/α ≠ 0 and the equations (p̄+ q̄i)y_{0}^{i} = a_{n}^{i}, i = 0, 1 and k yield the final formula.

Finally, we examine the case D^{2} = α^{2}+4β = 0 and A = 0. Now the equivalent conditions β = −α^{2}/4 and v = −uα/2 imply that B = 0 and the equality (37) is simplified into (39). Moreover if k ≥ 2, then the relation (14) becomes a_{n,k} = 0 a_{n,k−1} + 0 a_{n,k−2} = 0.

4 Special types of binary binomial interpolated triangles

The classical Pascal triangle has vertical symmetry and its inner elements satisfy the wellknown rule of addition, namely every elements is the sum of the two terms directly above it. In this section we give the classes of our triangles which have the same properties, and we answer the question, “Is Pascal’s triangle a binomial interpolated triangle?”

A binomial interpolated triangle is (vertically) symmetrical if

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

Theorem 12. Let a_{0,0} ≠ 0 and a_{1,0} be given. A binary binomial interpolated triangle is symmetrical if and only if

u = −1, v = α = \frac{2a_{1,0}}{a_{0,0}}

or

α = \frac{2a_{1,0}}{a_{0,0}} , β = −\frac{α^{2}}{4} , v = −\frac{α(u − 1)}{2},

where u ≠ 1 or

u = −1, v = α = \frac{2a_{1,0}}{a_{0,0}} , β = −\frac{α^{2}}{4} .

(See [1] for the binomial transform in a special case).

Proof. Indeed clearly the condition a_{n,k} = a_{n,n−k} implies the following system of equations

\begin{cases}α = A = uα + 2v \\ β = B = u^{2}β − uvα − v^{2} \\ b_{1} = a_{1,0} = ua_{1,0} + va_{0,0} \end{cases} .

From the first equation we find v = −α(u − 1)/2 and substituting in the second equation we obtain, with some calculations,

(α^{2} + 4β)(u + 1)(u − 1) = 0.

Now, we have the three possibilities α^{2} + 4β = 0, u = −1, u = 1. Obviously the case u = 1 implies v = 0, a contradiction. The case u = −1 gives v = α and α = 2a_{1,0}/a_{0,0}. Considering the case α^{2} +4β = 0 we obtain the second part of the statement of the theorem. Finally, the equalities α^{2} + 4β = 0 and u = −1 yield the third last case.

Corollary 13. Let λ = a_{1,0}/a_{0,0} and a_{0,0} ≠ 0, u ≠ 1. Then the form of a symmetrical binomial interpolated triangle can be written by

BIT (a_{0}, λa_{0}, 2λ, β; −1, 2λ),  (40)

BIT (a_{0}, λa_{0}, 2λ, −λ^{2}; u, λ(1 − u)),  (41)

or

BIT (a_{0}, λa_{0}, 2λ, −λ^{2}; −1, 2λ).  (42)

Figure 4 shows a symmetrical binomial interpolated triangle, namely BIT (2, 1, 1, 1; −1, 1) generated by Lucas numbers (\underline{A000032} in [6]).

\begin{matrix}2 \\ 1 \\ 1 \\ 3 \\ −2 \\ 3 \\ 4 \\ −1 \\ −1 \\ 4 \\ 7 \\ −3 \\ 2 \\ −3 \\ 7 \\ 11 \\ −4 \\ 1 \\ 1 \\ −4 \\ 11 \\ 18 \\ −7 \\ 3 \\ −2 \\ 3 \\ −7 \\ 18 \end{matrix}

Figure 4: Symmetrical binomial interpolated triangle BIT (2, 1, 1, 1; −1, 1)

Remark 14. According to (23) the recursion of s in the symmetrical binomial interpolated triangles case is s_{n} = 2λs_{n−1} + βs_{n−2} or s_{n} = 2λs_{n−1} − λ^{2}s_{n−2}. Moreover, when we consider the triangle (42) for the sequence d we obtain d_{n} = λd_{n−1} + λd_{n−2} − λ^{2}d_{n−3}.

Theorem 15. Pascal’s triangle is not a binomial interpolated triangle.

Proof. The “sum of above terms” condition and relation (9) should imply aβ/v = −B/v = 1 and the vertical symmetry implies β = B. Thus we find u = −1 and v = −β. Now the first set of solutions coming from Theorem 12 gives v = β = α = 2, since in Pascal’s triangle we have a_{0,0} = a_{1,0} = 1. The recurrence (7) becomes a_{n,0} = 2a_{n−1,0} −2a_{n−2,0} which is clearly not satisfied in Pascal’s triangle by the first elements (all equal to 1) of any row. From the second set of solutions we find α = 2, β = −1, v = 1 − u, but, since u = −1, from these solutions we must have v = 2 and on the other hand since v = −β = −1 we find a contradiction.

Now we give the conditions of u and v, so that an inner entry of BIT could be the sum of values not only left but also directly above it by coefficients u and v. Using (9), we can gain it in two different ways (see Figure 5). Our cases are

case 1:  u = \frac{uβ}{v} ,  v = −\frac{B}{v} ,
case 2:  v = \frac{uβ}{v} ,  u = −\frac{B}{v} .

\begin{matrix}a_{n−1,k−1} \\ a_{n−1,k} \\ a_{n,k} \\ v \\ u \\ a_{n−1,k−1} \\ a_{n−1,k} \\ a_{n,k} \\ u \\ v \end{matrix}

Figure 5: Coefficients of summing downwards

\begin{matrix}a_{0} & a_{1} & βa_{0} + αa_{1} & βa_{0} + αa_{1} & \begin{matrix}αβa_{0}+ \\ (α^{2} + β)a_{1} \end{matrix} & \begin{matrix}(α^{2}β + β^{2})a_{0}+ \\ (α^{3} + 2αβ)a_{1} \end{matrix} & \begin{matrix}αβa_{0}+ \\ (α^{2} + β)a_{1} \end{matrix} & \begin{matrix}(α^{2}β + β^{2})a_{0}+ \\ (α^{3} + 2αβ)a_{1} \end{matrix} & \begin{matrix}(α^{3}β + 2αβ^{2})a_{0} + \\ (α^{4} + 3α^{2}β + β^{2})a_{1} \end{matrix} & \begin{matrix}(α^{4}β + 3α^{2}β^{2} + β^{3})a_{0} + \\ (α^{5} + 4α^{3}β + 3αβ^{2})a_{1} \end{matrix} \\ Figure 6: BIT (a_{0}, a_{1}, α, β; α, β) \end{matrix}

4.1 Case 1

Solving the system

\begin{cases}u = \frac{uβ}{v} \\ v = −\frac{B}{v} \end{cases} ,

we can easily obtain that u = α and v = β, thus the triangle is

BIT (a_{0}, a_{1}, α, β; α, β).  (43)

We derive some interesting properties of this triangle. From Figure 6, which shows the first four rows of triangle BIT (a_{0}, a_{1}, α, β; α, β) (see also Figure 7), we notice that the rows and the left diagonal satisfy the same recurrence. Indeed, using the equalities u = α, v = β, the recurrence relation (14) becomes a_{n,k} = αa_{n,k−1} + βa_{n,k−2}. Moreover, the terms along the rising diagonals are the same. The next theorem and corollary will provide it precisely.

\begin{matrix}a_{n−1,k−1} \\ a_{n−1,k} \\ a_{n,k−1} \\ a_{n+1,k−1} \\ a_{n,k} \\ a_{n,k+1} \\ α \\ β \\ α \\ β \\ α \\ α \\ β \end{matrix}

Figure 7: Coefficients of summing in case 1 Theorem 16. The entries in triangle BIT (a_{0}, a_{1}, α, β; α, β) can be written (n ≥ 1) by

a_{n,k} = a_{0} ∑_{i=0}^{⌊ \frac{n+k−2}{2} ⌋} \binom{n + k − i − 2}{i}α^{n+k−2i−2}β^{i+1} + a_{1} ∑_{i=0}^{⌊ \frac{n+k−1}{2} ⌋} \binom{n + k − i − 1}{i}α^{n+k−2i−1}β^{i}.

Proof. We consider the results of Theorem 11. Indeed, using the equalities u = α, v = β and x_{1} + x_{2} = α, αx_{1} + β = x_{1}^{2}, αx_{2} + β = x_{2}^{2}, D + α = 2x_{1}, D − α = −2x_{2} the equations (33)–(35) become

a_{n,k} = \frac{−a_{n,0}x_{2} + a_{n,1}}{D} x_{1}^{k} + \frac{a_{n,0}x_{1} − a_{n,1}}{D} x_{2}^{k},

where D = \sqrt{α^{2} + 4β} = x_{1} − x_{2} ≠ 0 and

a_{n,0} = \frac{−a_{0}x_{2} + a_{1}}{D} x_{1}^{n} + \frac{a_{0}x_{1} − a_{1}}{D} x_{2}^{n},
a_{n,1} = \frac{−a_{0}x_{2} + a_{1}}{D} x_{1}^{n+1} + \frac{a_{0}x_{1} − a_{1}}{D} x_{2}^{n+1}.

A little calculation shows that

a_{n,k} = a_{0}β (\frac{x_{1}^{n+k−1} − x_{2}^{n+k−1}}{x_{1} − x_{2}} ) + a_{1} (\frac{x_{1}^{n+k} − x_{2}^{n+k}}{x_{1} − x_{2}} ) .  (44)

Using the Girard-Waring formula [4]

\frac{X^{N+1} − Y^{N+1}}{X − Y} = ∑_{i=0}^{⌊ \frac{N}{2} ⌋}(−1)^{i}\binom{N − i}{i}(X + Y)^{N−2i}(XY)^{i},

where, in our case, X = x_{1}, Y = x_{2}, X + Y = α, XY = −β and N = n + k − 2 or N = n + k − 1, the thesis follows. The Girard-Waring formula also holds in the case x_{1} = x_{2}, i.e., D = 0, taking the limit x_{1} → x_{2} on both members. We mention that D = 0 implies A ≠ 0.

Corollary 17. In case of the triangle BIT (a_{0}, a_{1}, α, β; α, β) the rising diagonal sequence \{a_{n−k,k}\}_{k=0}^{⌊ \frac{n}{2} ⌋} is a constant sequence for any k.

Proof. We apply the formula proved in Theorem 16 to a_{n−k,k} and obtain an expression that does not depend on the index k.

Figure 8 shows BIT (a_{0}, a_{1}, 1, 1; 1, 1) as an example for case 1. Using the result of Theorem 16, in the case α = 1 and β = 1, the binomial coefficients are the coefficients of the elements in the rising diagonals. Thus a_{n,k} = a_{0}f_{n+k−1}+a_{1}f_{n+k}, where f_{n} is the n^{th} Fibonacci number (\underline{A000045}), so that, f_{0} = 0, f_{1} = f_{−1} = 1. (We also find from the above relation (44) the connection with Fibonacci numbers.) The special Fibonacci binomial interpolated triangle is BIT (1, 1, 1, 1; 1, 1) (\underline{A199512}). Falcon and Plaza [3] provided an other example in Table 4 for this case, namely BIT (0, 1, 3, 1; 3, 1), which is generated by the 3-Fibonacci sequence (\underline{A006190}).

\begin{matrix}a_{0} \\ a_{1} \\ p + a_{1} \\ a_{0} + a_{1} \\ a_{0} + 2a_{1} \\ 2a_{0} + 3a_{1} \\ a_{0} + 2a_{1} \\ 2a_{0} + 3a_{1} \\ 3a_{0} + 5a_{1} \\ 5a_{0} + 8a_{1} \\ 2a_{0} + 3a_{1} \\ 3a_{0} + 5a_{1} \\ 5a_{0} + 8a_{1} \\ 8a_{0} + 13a_{1} \\ 13a_{0} + 21a_{1} \end{matrix} ; Figure 8: BIT (a_{0}, a_{1}, 1, 1; 1, 1)

4.2 Case 2

From the equations system we obtain

v_{1} = \frac{α − 1 + \sqrt{(α − 1)^{2} + 4β}}{2} ,  u_{1}= \frac{v_{1}^{2}}{β} ,
v_{2} = \frac{α − 1 − \sqrt{(α − 1)^{2} + 4β}}{2} ,  u_{2}= \frac{v_{2}^{2}}{β} .

If (α − 1)^{2} + 4β = 0, i.e., β = −(1/4)(α − 1)^{2}, then, replacing the corresponding values for u and v, after simplification we have

BIT (a_{0}, a_{1}, α, −\frac{(α − 1)^{2}}{4} ; −1, \frac{α − 1}{2}) .  (45)

If (α − 1)^{2} + 4β ≠ 0, then the triangles are

BIT (a_{0}, a_{1}, α, β; u_{1}, v_{1}),  (46)
BIT (a_{0}, a_{1}, α, β; u_{2}, v_{2}).  (47)

Finally, we compare the triangles (43)–(47) with the symmetrical ones (40)–(42). In all the cases for the symmetrical binary interpolated binomial triangle with some calculations we gain the following corollary.

Corollary 18. The symmetrical binary interpolated binomial triangles whose an inner entry could be the sum of values not only left but also directly above it by coefficients u and v are

BIT (a_{0}, −\frac{a_{0}}{2} , −1, −1; −1, −1),

which has only terms a_{0} and ±a_{0}/2 and

BIT (a_{0}, a_{0}, 2, −1; 2, −1),

which has only terms a_{0}.

Remark 19. When both parameters a_{0,0}, a_{1,0} are zero we find the trivial triangle exclusively composed of null entries. The triangle with all entries equal to 1 correspond to more binomial interpolated triangles, for example, BIT (1, 1, 2, −1; −1, 2) or BIT (1, 1, 2, −1; −1, 2). The triangle whose left diagonal and rows are the sequences of natural numbers (\underline{A000027}) is BIT (1, 2, 2, −1; 2, −1) (\underline{A094727}).

5 Acknowledgment

The author would like to thank the anonymous referee for carefully reading the manuscript and for his/her useful suggestions and improvements.

References

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

[2] P. Bhadouria, D. Jhala and B. Singh, Binomial transforms of the k-Lucas sequences and its properties, J. Math. Computer Sci. 8 (2014), 81–92.

[3] S. Falcon and A. Plaza, Binomial transform of k-Fibonacci sequence, Int. J. Nonlin. Sci. Num. 10 (2009), 1527–1538.

[4] H. W. Gould, The Girard-Waring power sum formulas for symmetric functions and Fibonacci sequences, Fibonacci Quart. 37 (1999) 135–140.

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

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

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

[8] Wolfram Math World, Pascal’s triangle,

   http://mathworld.wolfram.com/PascalsTriangle.html.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11B39, 11B65, 11B75. Keywords: binomial operator, binomial transform, binomial interpolated transform, recurrence sequence.

(Concerned with sequences \underline{A000027}, \underline{A000032}, \underline{A000045}, \underline{A006190}, \underline{A094727}, and \underline{A199512}.) Received April 5 2017; revised version received July 13 2017. Published in Journal of Integer Sequences, July 30 2017. Return to Journal of Integer Sequences home page.