Some Number Arrays Related to Pascal and Lucas Triangles

Claudio de J. Pita Ruiz V. Universidad Panamericana Mexico City Mexico

                        cpita@up.edu.mx

Abstract

By taking repeated convolutions of the sequence n^{p} with the constant sequence 1, we form the number arrays of the coefficients resulting when we write the mentioned convolutions as linear combinations of certain binomial coefficients. According to this procedure, Pascal and Lucas triangles correspond to the cases p = 1 and p = 2 respectively. We show that these arrays have some properties similar to the well-known properties of Pascal and Lucas triangles.

1 Introduction

Pascal’s triangle has been one of the favorite objects for many mathematicians during the last 3 centuries. Taking this object as inspiration, we have nowadays a number of interesting research works, in which Pascal’s triangle generalizations are considered (a classic and obligatory reference is [4]). Just to mention some: modify the boundary of Pascal’s triangle and keep the recurrence to obtain an infinite collection of new triangles [13, 15], and then consider generalizations of them [14]. Begin with two arbitrary sequences with the same first term, together with a recurrence relation (resembling the Pascal’s triangle recurrence; involving the elements of the given sequences), to obtain certain infinite matrices, and study the determinants of some submatrices [1, 11], and then more properties of the mentioned infinite matrices [12]. Consider the Riordan arrays machinery to study new triangles, keeping some properties of Pascal’s triangle, like symmetry and invertibility [2]. Focus on the 11’s powers property in rows of Pascal’s triangle, and change the 11 for a different number to obtain more triangles [7]. Divisibility properties in Pascal’s triangle are also a source for new studies [17]. And the story continues. This article is yet another work in this list. The “triangles” here are constructed with the coefficients of certain linear combinations (of binomials) of certain convolutions. We obtain in this way an infinite collection of number arrays, the first of which is Pascal’s triangle, and the second of which is the also famous Lucas triangle. We will see that many of the properties of Pascal’s triangle are preserved (some generalized versions of them) in these arrays. In this section we recall some mathematical topics involved in the rest of the work. We also show explicitly the construction of the first two arrays.

We will be working with Stirling numbers of the second kind S (n, k) (\underline{A008277}), where n, k ∈ ℕ′ (non-negative integers), n ≥ k. These numbers obey the recurrence

S (n + 1, k) = kS (n, k) + S (n, k − 1) ,  (1)

with S (0, 0) = 1 and S (0, n) = S (n, 0) = 0 for n ∈ ℕ. In particular we have S (n, 1) = 1 for all n ∈ ℕ. An explicit formula for S (n, k) is

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

We will work with the Z-Transform (see [21] and references therein). For the reader’s convenience, we recall some basic facts of the Z-Transform to be used throughout this work. The Z-Transform of a complex sequence a_{n} = (a_{0}, a_{1}, …) is defined as the holomorphic function A (z) given by the Laurent series A (z) = ∑_{n=0}^{∞} \frac{a_{n}}{z^{n}} (of course, defined for those z ∈ ℂ such that A (z) converges). We will use also the notation Z (a_{n}) for the Z-Transform of the sequence a_{n}. Some properties are

(1) It is linear and injective.

(2) (Advance shifting) The Z-Transform of the sequence a_{n+k} = (a_{k}, a_{k+1}, …) is given by

Z (a_{n+k}) = z^{k} (Z (a_{n}) − a_{0} − \frac{a_{1}}{z} − ⋯ − \frac{a_{k−1}}{z^{k−1}} ) .  (3)

(3) (Multiplication by the sequence n) If Z (a_{n}) = A (z), then

Z (na_{n}) = −z \frac{d}{dz} A (z) .  (4)

(4) (Convolution Theorem) The Z-Transform of the convolution a_{n} ∗ b_{n} of the sequences a_{n} and b_{n} (defined as a_{n} ∗ b_{n} = ∑_{t=0}^{n} a_{t}b_{n−t}) is the product of the Z-Transforms of the sequences a_{n} and b_{n}. That is, we have

Z (a_{n} ∗ b_{n}) = Z (a_{n}) Z (b_{n}) .  (5)

Remark 1. In this work we will be dealing with convolutions a_{n} ∗ 1 of a sequence a_{n} = (a_{0}, a_{1}, a_{2}, …) with 1, that is, the sequence of partial sums of a_{n}, namely a_{n}∗1 = (∑_{t=0}^{n} a_{t})_{n=0}^{∞} = (a_{0}, a_{0} + a_{1}, a_{0} + a_{1} + a_{2}, …). In general, after k convolutions of the sequence a_{n} with 1, we get the sequence of the k-th partial sums of a_{n}, namely a_{n}∗^{k}1 = (∑_{i_{k}=0}^{n} ⋯ ∑_{i_{2}=0}^{i_{3}} ∑_{i_{1}=0}^{i_{2}} a_{i_{1}})_{n=0}^{∞}.

Plainly we have (the Z-Transform of the sequence λ^{n}, where λ ∈ ℂ − {0})

Z (λ^{n}) = \frac{z}{z − λ},  (6)

and, according to (4) and (6) we have that

Z (n) = −z \frac{d}{dz} \frac{z}{z − 1} = \frac{z}{(z − 1)^{2}} ,  (7)
Z (n^{2}) = −z \frac{d}{dz} \frac{z}{(z − 1)^{2}} = \frac{z (z + 1)}{(z − 1)^{3}},  (8)

and so on. We will also need the Z-Transform of the sequence \binom{n}{r}, where r ∈ ℕ′ is given:

Z (\binom{n}{r}) = \frac{z}{(z − 1)^{r+1}} .  (9)

Observe that, according to (3), we have that (for 0 ≤ r_{0} ≤ r)

Z (\binom{n + r_{0}}{r}) = \frac{z^{r_{0}+1}}{(z − 1)^{r+1}} .  (10)

It is easy to see that

\binom{n}{r_{1}} ∗ \binom{n}{r_{2}} = \binom{n + 1}{r_{1} + r_{2} + 1},  (11)

(both sides have the same Z-Transform: z^{2} (z − 1)^{−(r_{1}+r_{2}+2)}).

We consider the sequence n = \binom{n}{1} and its convolution with 1. According to (5), (6) and (7) we have

Z (n ∗ 1) = \frac{z^{2}}{(z − 1)^{3}} = \frac{z}{(z − 1)^{2}} + \frac{z}{(z − 1)^{3}} ,  (12)

which means that

n ∗ 1 = \binom{n}{1} + \binom{n}{2}.  (13)

Similarly we have

Z (n ∗^{2} 1) = \frac{z^{3}}{(z − 1)^{4}} = \frac{z}{(z − 1)^{2}} + 2\frac{z}{(z − 1)^{3}} + \frac{z}{(z − 1)^{4}} ,  (14)

which means that

n ∗^{2} 1 = \binom{n}{1} + 2\binom{n}{2} + \binom{n}{3}.  (15)

Continuing in this way (considering repeated convolutions of the sequence n with 1, and expanding the corresponding Z-Transform in partial fractions), we obtain for k ≥ 1 that

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

The coefficients a_{k,j}^{(1)} = \binom{k−1}{j−1}, j = 1, 2, …, k, k = 1, 2, … give us the triangular array of Pascal’s triangle:

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 \\ 1 & 3 & 3 & 1 & 0 & 0 & ⋯ \\ 1 & 4 & 6 & 4 & 1 & 0 \\ 1 & 5 & 10 & 10 & 5 & 1 \\ ⋮ & & & ⋮ & & & ... \end{matrix} ] .

We repeat the previous procedure beginning now with the sequence n^{2}. Observe that

Z (n^{2}) = \frac{z (z + 1)}{(z − 1)^{3}} = \frac{z}{(z − 1)^{2}} + 2\frac{z}{(z − 1)^{3}} ,  (17)

which means that

n^{2} = \binom{n}{1} + 2\binom{n}{2}.  (18)

The Z-Transform of the first convolution of n^{2} with 1 is

Z (n^{2} ∗ 1) = \frac{z^{2} (z + 1)}{(z − 1)^{4}} = \frac{z}{(z − 1)^{2}} + 3\frac{z}{(z − 1)^{3}} + 2\frac{z}{(z − 1)^{4}} ,  (19)

which means that

n^{2} ∗ 1 = \binom{n}{1} + 3\binom{n}{2} + 2\binom{n}{3}.  (20)

A new convolution with 1 gives us the sequence n^{2} ∗^{2} 1, with Z-Transform

Z (n^{2} ∗^{2} 1) = \frac{z^{3} (z + 1)}{(z − 1)^{5}} = \frac{z}{(z − 1)^{2}} + 4\frac{z}{(z − 1)^{3}} + 5\frac{z}{(z − 1)^{4}} + 2\frac{z}{(z − 1)^{5}} .  (21)

which means that

n^{2} ∗^{2} 1 = \binom{n}{1} + 4\binom{n}{2} + 5\binom{n}{3} + 2\binom{n}{4}.  (22)

In general, we can see that for k ≥ 2

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

The coefficients a_{k,j}^{(2)} = \binom{k−2}{j−1} + 2\binom{k−2}{j−2}, j = 1, 2, …, k, k = 2, 3, … give us the following array (the Lucas triangle):

[ \begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ⋯ \\ 1 & 2 & 0 & 0 & 0 & 0 \\ 1 & 3 & 2 & 0 & 0 & 0 \\ 1 & 4 & 5 & 2 & 0 & 0 & ⋯ \\ 1 & 5 & 9 & 7 & 2 & 0 \\ 1 & 6 & 14 & 16 & 9 & 2 \\ ⋮ & & & ⋮ & & & ... \end{matrix} ] .

We cancelled the first row since the sequence n^{2} ∗^{k−2} 1 makes sense only for k ≥ 2. However, in the Lucas triangle it is common to fill out position k = j = 1 with the number 2 (and zeros in the rest of the row), in order to have the Lucas sequence in the (sum of) rising diagonals beginning with L_{0} = 2. According to the procedure above, used to obtain the Lucas triangle, this can be considered as a generalization of Pascal’s triangle. (See [15] and [16]; the paper of Benjamin [3] discusses combinatorial interpretations of the Lucas triangle entries.)

We can repeat the themes above (of taking convolutions of a given sequence with 1), beginning with sequences of the form n^{p}, with p ∈ ℕ given, and obtain in this way number arrays with elements a_{k,j}^{(p)}, j = 1, 2, …, k, k = p, p + 1, …, corresponding to the coefficients resulting when we express the convolutions n^{p} ∗^{k−p} 1 as linear combinations of the binomials \binom{n}{j}, j = 1, 2, …, k. So these arrays are infinite lower triangular matrices with their first p − 1 rows cancelled. We will call them “p-arrays”, and as with the Lucas triangle, all of them can be considered as generalizations of Pascal’s triangle. This is what we will do in section 2 . In section 3 we begin the study of properties of the p-arrays, considering the rows and columns of them. The well-known results about row sums, 11’s powers in rows, and hockey stick property in columns of Pascal’s triangle, will become the particular case p = 1 of Propositions 4, 5 and 7, respectively, where we show the generalized versions of the mentioned results for the p-arrays. The falling diagonals are studied in section 4. It turns out that the (p + 1)-th falling diagonal in the p-array is the sequence n^{p}. This fact, together with the hockey stick property (the corresponding version for falling diagonals: Proposition 9), gives us as corollary that the falling diagonals below the (p + 1)-th one, contain the partial sums of the sequence n^{p}. Section 5, where we study the rising diagonals of the p-arrays, contain some quite surprising results, and in some sense this section justifies the title of the article. We know that the rising diagonals of Pascal’s triangle contain Fibonacci numbers, and that the rising diagonals of Lucas triangle contain Lucas numbers. We prove in section 5 that the rising diagonals of the p-arrays contain also Fibonacci numbers, when p is odd, and contain Lucas numbers, when p is even, times some constant that depends only on the parameter p. It turns out that the sequence of these multiplicative constants (\underline{A050946}) is (1, 1, 7, 13, 151, 421, …) (the so-called Stirling-Bernoulli transform of Fibonacci numbers). Thus, the rising diagonals of the 1-array (the Pascal’s triangle) contain 1×Fibonaccis, the rising diagonals of the 2-array (the Lucas triangle) contain 1×Lucas, the rising diagonals of the 3-array contain 7×Fibonaccis, the rising diagonals of the 4-array contain 13×Lucas, and so on. In section 6 we consider some new number arrays obtained by taking the same fixed row of each of the p-arrays. We call them “(p + t)-rows arrays”, and we show that their elements obey certain recurrences, and that their columns have also some interesting properties.

2 The p-arrays

We begin by showing how to express the sequence n^{p} as linear combination of binomials \binom{n}{j}, j = 1, 2, …, p.

Proposition 2. For p ∈ ℕ and n ∈ ℕ′ we have

n^{p} = ∑_{j=1}^{p} j!S (p, j) \binom{n}{j}.  (24)

Proof. We proceed by induction on p. For p = 1 the result is clear. If we suppose that (24) is true for a given p ∈ ℕ then

∑_{j=1}^{p+1} j!S (p + 1, j) \binom{n}{j} = ∑_{j=1}^{p+1} j! (jS (p, j) + S (p, j − 1)) \binom{n}{j}

= ∑_{j=1}^{p} j!jS (p, j) \binom{n}{j} + ∑_{j=1}^{p} (j + 1)!S (p, j) \binom{n}{j + 1}

= ∑_{j=1}^{p} j!jS (p, j) \binom{n}{j} + ∑_{j=1}^{p} j! (n − j) S (p, j) \binom{n}{j}

= n ∑_{j=1}^{p} j!S (p, j) \binom{n}{j}
= n^{p+1},

as claimed.

Clearly n = \binom{n}{1} is the case p = 1 of (24), and (18) is the case p = 2.

Proposition 3. For k ≥ p, we have

n^{p} ∗^{k−p} 1 = ∑_{j=1}^{k} a_{k,j}^{(p)}\binom{n}{j},  (25)

where the coefficients a_{k,j}^{(p)} are given by

a_{k,j}^{(p)} = ∑_{i=1}^{j} \binom{k − p}{j − i}i!S (p, i) ,  (26)

for j = 1, 2, …, k, and k ≥ p.

Proof. We proceed by induction on k. For k = p formula (25) is (24). Let us assume that formula (25) is valid for a given k ≥ p. That is, let us suppose that

n^{p} ∗^{k−p} 1 = ∑_{j=1}^{k} ∑_{i=1}^{j} \binom{k − p}{j − i}i!S (p, i) \binom{n}{j}.  (27)

Thus we have (taking the convolution with 1 in both sides of (27) and using (11))

n^{p} ∗^{k+1−p} 1 = ∑_{j=1}^{k} ∑_{i=1}^{j} \binom{k − p}{j − i}i!S (p, i) \binom{n + 1}{j + 1}.

The proof ends if we prove that

∑_{j=1}^{k} ∑_{i=1}^{j} \binom{k − p}{j − i}i!S (p, i) \binom{n + 1}{j + 1} = ∑_{j=1}^{k+1} ∑_{i=1}^{j} \binom{k + 1 − p}{j − i}i!S (p, i) \binom{n}{j}.

In fact, we have

∑_{j=1}^{k} ∑_{i=1}^{j} \binom{k − p}{j − i}i!S (p, i) \binom{n + 1}{j + 1} = ∑_{j=1}^{k} ∑_{i=1}^{j} \binom{k − p}{j − i}i!S (p, i) (\binom{n}{j} + \binom{n}{j + 1})

= ∑_{j=1}^{k+1} ∑_{i=1}^{j} \binom{k − p}{j − i}i!S (p, i) \binom{n}{j} + ∑_{j=1}^{k+1} ∑_{i=1}^{j} \binom{k − p}{j − 1 − i}i!S (p, i) \binom{n}{j}

= ∑_{j=1}^{k+1} ∑_{i=1}^{j} (\binom{k − p}{j − i} + \binom{k − p}{j − 1 − i}) i!S (p, i) \binom{n}{j} = ∑_{j=1}^{k+1} ∑_{i=1}^{j} \binom{k + 1 − p}{j − i}i!S (p, i) \binom{n}{j},

as claimed.

Expressions (16) and (23) are the cases p = 1 and p = 2 of (27), respectively. Observe that the coefficients a_{k,j}^{(p)} are equal to 0 if j > k. Note also that for any k ≥ p we have a_{k,k}^{(p)} = p!.

Next we give some more examples of p-arrays.

If p = 3, we have for k ≥ 3

n^{3} ∗^{k−3} 1 = ∑_{j=1}^{k} a_{k,j}^{(3)}\binom{n}{j}, where a_{k,j}^{(3)} = \binom{k − 3}{j − 1} + 6\binom{k − 3}{j − 2} + 6\binom{k − 3}{j − 3},

and the array of coefficients a_{k,j}^{(3)} is

[ \begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ⋯ \\ ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ \\ 1 & 6 & 6 & 0 & 0 & 0 & 0 \\ 1 & 7 & 12 & 6 & 0 & 0 & 0 & ⋯ \\ 1 & 8 & 19 & 18 & 6 & 0 & 0 \\ 1 & 9 & 27 & 37 & 24 & 6 & 0 \\ 1 & 10 & 36 & 64 & 61 & 30 & 6 & ⋯ \\ ⋮ & & & ⋮ & & & ⋮ & ... \end{matrix} ] .

(This array is a close relative of the so-called “Clark Triangle” [19].) If p = 4, we have for k ≥ 4

n^{4}∗^{k−4}1 = ∑_{j=1}^{k} a_{k,j}^{(4)}\binom{n}{j}, where a_{k,j}^{(4)} = \binom{k − 4}{j − 1}+14\binom{k − 4}{j − 2}+36\binom{k − 4}{j − 3}+24\binom{k − 4}{j − 4},

and the array of coefficients a_{k,j}^{(4)} is

[ \begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ⋯ \\ ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ \\ 1 & 14 & 36 & 24 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 15 & 50 & 60 & 24 & 0 & 0 & 0 \\ 1 & 16 & 65 & 110 & 84 & 24 & 0 & 0 \\ 1 & 17 & 81 & 175 & 194 & 108 & 24 & 0 & ⋯ \\ 1 & 18 & 98 & 256 & 369 & 302 & 132 & 24 \\ ⋮ & & & ⋮ & & & ⋮ & & ... \end{matrix} ] .

If p = 5, we have for k ≥ 5

n^{5} ∗^{k−5} 1 = ∑_{j=1}^{k} a_{k,j}^{(5)}\binom{n}{j},
where a_{k,j}^{(5)} = \binom{k − 5}{j − 1} + 30\binom{k − 5}{j − 2} + 150\binom{k − 5}{j − 3} + 240\binom{k − 5}{j − 4} + 120\binom{k − 5}{j − 5},

and the array of coefficients a_{k,j}^{(5)} is

[ \begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ⋯ \\ ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ⋯ \\ 1 & 30 & 150 & 240 & 120 & 0 & 0 & 0 & 0 \\ 1 & 31 & 180 & 390 & 360 & 120 & 0 & 0 & 0 \\ 1 & 32 & 211 & 570 & 750 & 480 & 120 & 0 & 0 & ⋯ \\ 1 & 33 & 243 & 781 & 1320 & 1230 & 600 & 120 & 0 \\ 1 & 34 & 276 & 1024 & 2101 & 2550 & 1830 & 720 & 120 \\ ⋮ & & & ⋮ & & & ⋮ & & & ... \end{matrix} ] .

3 Properties I: Rows and Columns

We begin this section by noting that in each of the p-arrays we have the Pascal’s triangle property a_{k,j}^{(p)} + a_{k,j+1}^{(p)} = a_{k+1,j+1}^{(p)}. That is, this property which is known to be valid for the case p = 1, is clearly valid for any p ∈ ℕ since

∑_{i=1}^{j} \binom{k − p}{j − i}i!S (p, i) + ∑_{i=1}^{j+1} \binom{k − p}{j + 1 − i}i!S (p, i) = ∑_{i=1}^{j+1} \binom{k + 1 − p}{j + 1 − i}i!S (p, i) .

In Pascal’s triangle, the sum of the elements of the row k ≥ 1 is 2^{k−1}. What we have in the p-arrays is the following natural generalization.

Proposition 4. (Row sums) The sum of the elements of the k-th row (k ≥ p) in the parray, is 2^{k−p} times the sum of the elements of its p-th row. That is, we have ∑_{j=1}^{k} a_{k,j}^{(p)} = 2^{k−p} ∑_{j=1}^{p} a_{p,j}^{(p)}, or

∑_{j=1}^{k} ∑_{i=1}^{j} \binom{k − p}{j − i}i!S (p, i) = 2^{k−p} ∑_{j=1}^{p} j!S (p, j) .  (28)

Proof. Write l = k − p. Then

∑_{j=1}^{k} a_{k,j}^{(p)} = ∑_{j=1}^{p+l} ∑_{i=1}^{j} \binom{l}{j − i}i!S (p, i) = ∑_{i=0}^{l} \binom{l}{i} ∑_{j=1}^{p} j!S (p, j) = 2^{l} ∑_{j=1}^{p} j!S (p, j) ,

as claimed.

The sequence (∑_{j=1}^{p} j!S (p, j))_{p=1}^{∞} of the sum of the elements of the p-th rows of the

p-arrays is (1, 3, 13, 75, …) (\underline{A000670}).

For k > p, one can easily rewrite the proof of Proposition 4 for the case of alternating sums of rows of the p-arrays, to conclude that ∑_{j=1}^{k} (−1)^{j} a_{k,j}^{(p)} = 0. In the case k = p, a simple induction argument on p shows us that ∑_{j=1}^{p} (−1)^{j} j!S (p, j) = (−1)^{p}. That is, the alternating sums of rows in the p-arrays are given by

∑_{j=1}^{k} (−1)^{j} a_{k,j}^{(p)} = \begin{cases}(−1)^{p} , & if k = p; \\ 0, & if k > p. \end{cases}  (29)

Thus, ignoring the cancelled rows, the alternating sums of the elements of rows in a p-array is the sequence ((−1)^{p} , 0, 0, 0, …).

The well-known property related to 11’s powers in the rows of Pascal’s triangle has the following generalization in the p-arrays.

Proposition 5. (11’s powers) Making the row k ≥ p a single number (the elements of the row being the digits, and carrying over when appear elements with more than one digit), this number is equal to 11^{k−p}N_{p}, where N_{p} is the (single) number corresponding to row p.

Proof. It is clear that N_{p} = ∑_{j=1}^{p} j!S (p, j) 10^{p−j}. Write k = p+l. The number corresponding to the k-th row is

N_{k} = ∑_{j=1}^{p+l} a_{p+l,j}^{(p)}10^{p+l−j} = ∑_{j=1}^{p+l} ∑_{i=1}^{j} \binom{l}{j − i}i!S (p, i) 10^{p+l−j}

= ∑_{j=1}^{p} j!S (p, j) 10^{p−j} ∑_{j=0}^{l} \binom{l}{j}10^{l−j} = 11^{k−p}N_{p},

as claimed.

In Tables 1 and 2 we have some examples of Propositions 4 and 5.

We now consider the sequences of the columns in the p-arrays.

Array

\begin{matrix}Row \\ k ≥ p \end{matrix}

Elements of the row Sum of the elements...

...which is equal to...

Alternating sum of the elements...

p = 1 k = 1  (1)  1  2^{0}  −1
k = 2  (1, 1)  2  2^{1}  0
k = 3  (1, 2, 1)  4  2^{2}  0
⋮  ⋮  ⋮  ⋮  ⋮
p = 2 k = 2  (1, 2)  3  3 (2^{0})  1
k = 3  (1, 3, 2)  6  3 (2^{1})  0
k = 4  (1, 4, 5, 2)  12  3 (2^{2})  0
⋮  ⋮  ⋮  ⋮  ⋮
p = 3 k = 3  (1, 6, 6)  13  13 (2^{0})  −1
k = 4  (1, 7, 12, 6)  26  13 (2^{1})  0
k = 5  (1, 8, 19, 18, 6)  52  13 (2^{2})  0
⋮  ⋮  ⋮  ⋮  ⋮
p = 4 k = 4  (1, 14, 36, 24)  75  75 (2^{0})  1
k = 5  (1, 15, 50, 60, 24)  150  75 (2^{1})  0
k = 6 (1, 16, 65, 110, 84, 24)  300  75 (2^{2})  0
⋮  ⋮  ⋮  ⋮  ⋮

Table 1: Row sums in the p-arrays

Proposition 6. (Columns)

(a) For l = 1, 2, …, p, the l-th column C_{l}^{(p)} of the p-array is the sequence (beginning in the p-th row)

C_{l}^{(p)} = (∑_{j=1}^{l} \binom{n}{l − j}j!S (p, j))_{n=0}^{∞} ,  (30)

(b) The (p + l)-th column of the p-array (beginning in the (p + l)-th row, l = 0, 1, 2, …) is

C_{p+l}^{(p)} = (∑_{j=1}^{p+l} \binom{n + l}{p + l − j}j!S (p, j))_{n=0}^{∞} ,  (31)

Proof. Formulas (30) and (31) follow from (26).

Observe that the p-th column of the p-array is (from formula (30) with l = p, or from formula (31) with l = 0)

C_{p}^{(p)} = (∑_{j=1}^{p} \binom{n}{p − j}j!S (p, j))_{n=0}^{∞} ,  (32)

Array Row k ≥ p Elements of the row Written as a single number...

... which is equal to...

p = 1  k = 1  (1)  1  1 (11^{0})
k = 2  (1, 1)  11  1 (11^{1})
k = 3  (1, 2, 1)  121  1 (11^{2})
⋮  ⋮  ⋮  ⋮
p = 2  k = 2  (1, 2)  12  12 (11^{0})
k = 3  (1, 3, 2)  132  12 (11^{1})
k = 4  (1, 4, 5, 2)  1452  12 (11^{2})
⋮  ⋮  ⋮  ⋮
p = 3  k = 3  (1, 6, 6)  166  166 (11^{0})
k = 4  (1, 7, 12, 6)  1826  166 (11^{1})
k = 5  (1, 8, 19, 18, 6)  20086  166 (11^{2})
⋮  ⋮  ⋮  ⋮
p = 4  k = 4  (1, 14, 36, 24)  2784  2784 (11^{0})
k = 5  (1, 15, 50, 60, 24)  30624  2784 (11^{1})
k = 6  (1, 16, 65, 110, 84, 24)  336864  2784 (11^{2})
⋮  ⋮  ⋮  ⋮

Table 2: Property of 11’s in the rows of the p-arrays.

Two particular cases from (30) are:

(a) (First column) By setting l = 1 in (30) we see that the first column of the p-array is the sequence (S (p, 1))_{n=0}^{∞} = (1, 1, 1, …).

(b) (Second column) By setting l = 2 in (30) (and using that S (p, 2) = 2^{p−1} − 1), we see that the second column of the corresponding p-array is

C_{2} = (∑_{j=1}^{2} \binom{n}{2 − j}j!S (p, j))_{n=0}^{∞} = (n + 2S (p, 2))_{n=0}^{∞} = (n + 2^{p} − 2)_{n=0}^{∞} .  (33)

We have the hockey stick property for j-th columns j ≥ p.

Proposition 7. (Partial sums of columns: hockey stick property) The sum of the elements of the j-th column (j ≥ p), up to line m, is equal to the element in the falling diagonal next to the last element added in the column. That is, for j ≥ p and m ∈ ℕ′ we have ∑_{l=p}^{p+m} a_{l,j}^{(p)} = a_{p+m+1,j+1}^{(p)}, or

∑_{l=p}^{p+m} ∑_{i=1}^{j} \binom{l − p}{j − i}i!S (p, i) = ∑_{i=1}^{j+1} \binom{m + 1}{j + 1 − i}i!S (p, i) .  (34)

Proof. Easy induction argument on m, left to the reader.

Beginning with the p-th column C_{p}^{(p)} (32), the hockey stick property tells us that the (p + 1)-th column is C_{p+1}^{(p)} = C_{p}^{(p)} ∗ 1. Thus we have that

∑_{j=1}^{p} \binom{n + 1}{p + 1 − j}j!S (p, j) = ∑_{j=1}^{p} \binom{n}{p − j}j!S (p, j) ∗ 1 = ∑_{i=0}^{n} ∑_{j=1}^{p} \binom{i}{p − j}j!S (p, j) . (35)

Similarly, we have C_{p+2}^{(p)} = C_{p+1}^{(p)} ∗ 1 = C_{p}^{(p)} ∗^{2} 1, C_{p+3}^{(p)} = C_{p+2}^{(p)} ∗ 1 = C_{p}^{(p)} ∗^{3} 1, and so on. In general we have C_{p+l+1}^{(p)} = C_{p+l}^{(p)} ∗ 1 = C_{p}^{(p)} ∗^{l+1} 1, for l = 0, 1, 2, . . .. That is

∑_{j=1}^{p} \binom{n + l + 1}{p + l + 1 − j}j!S (p, j) = ∑_{i=0}^{n} ∑_{j=1}^{p} \binom{i + l}{p + l − j}j!S (p, j) = ∑_{i_{l+1}=0}^{n} ⋯ ∑_{i_{2}=0}^{i_{3}} ∑_{i_{1}=0}^{i_{2}} ∑_{j=1}^{p} \binom{i_{1}}{p − j}j!S (p, j) .

(36)

In Tables 3 and 4 we show some examples from Propositions (30) and (31).

Array \begin{matrix}Column \\ l = 1, …, p \end{matrix}  Sequence (∑_{j=1}^{l} \binom{n}{l−j}j!S (p, j))_{n=0}^{∞}
p = 1  l = 1  C_{1}^{(1)} = (1) = (1, 1, 1, 1, …)
p = 2  l = 1  C_{1}^{(2)} = (1) = (1, 1, 1, 1, …)
l = 2  C_{2}^{(2)} = (n + 2) = (2, 3, 4, 5, …)
p = 3 l = 1 C_{1}^{(3)} = (1) = (1, 1, 1, 1, …)
l = 2  C_{2}^{(3)} = (n + 6) = (6, 7, 8, 9, …)
l = 3  C_{3}^{(3)} = (\binom{n}{2} + 6\binom{n}{1} + 6\binom{n}{0}) = (6, 12, 19, 27, …)
p = 4 l = 1 C_{1}^{(4)} = (1) = (1, 1, 1, 1, …)
l = 2  C_{2}^{(4)} = (n + 14) = (14, 15, 16, 17, …)
l = 3  C_{3}^{(4)} = (\binom{n}{2} + 14\binom{n}{1} + 36\binom{n}{0}) = (36, 50, 65, 81, …)
l = 4  C_{4}^{(4)} = (\binom{n}{3} + 14\binom{n}{2} + 36\binom{n}{1} + 24\binom{n}{0}) = (24, 60, 110, 175, …)

Table 3: First p columns in the p-arrays

4 Properties II: Falling Diagonals

In the following proposition we describe the sequences in the falling diagonals of the p-arrays.

Array Column p + l Sequence (∑_{j=1}^{p+l} \binom{n+l}{p+l−j}j!S (p, j))_{n=0}^{∞}
p = 1  l = 1  C_{2}^{(1)} = C_{1}^{(1)} ∗ 1 = (1, 2, 3, 4, …)
l = 2  C_{3}^{(1)} = C_{1}^{(1)} ∗^{2} 1 = (1, 3, 6, 10, …)
l = 3  C_{4}^{(1)} = C_{1}^{(1)} ∗^{3} 1 = (1, 4, 10, 20, …)
⋮  ⋮
p = 2  l = 1  C_{3}^{(2)} = C_{2}^{(2)} ∗ 1 = (2, 5, 9, 14, …)
l = 2  C_{4}^{(2)} = C_{2}^{(2)} ∗^{2} 1 = (2, 7, 16, 30, …)
l = 3  C_{5}^{(2)} = C_{2}^{(2)} ∗^{3} 1 = (2, 9, 25, 55, …)
⋮  ⋮
p = 3  l = 1  C_{4}^{(3)} = C_{3}^{(3)} ∗ 1 = (6, 18, 37, 64, …)
l = 2  C_{5}^{(3)} = C_{3}^{(3)} ∗^{2} 1 = (6, 24, 61, 125, …)
l = 3  C_{6}^{(3)} = C_{3}^{(3)} ∗^{3} 1 = (6, 30, 91, 216, …)
⋮  ⋮
p = 4  l = 1  C_{5}^{(4)} = C_{4}^{(4)} ∗ 1 = (24, 84, 194, 369, …)
l = 2  C_{6}^{(4)} = C_{4}^{(4)} ∗^{2} 1 = (24, 108, 302, 671, …)
l = 3  C_{7}^{(4)} = C_{4}^{(4)} ∗^{3} 1 = (24, 132, 434, 1105, …)
⋮  ⋮

Table 4: Columns p + 1, p + 2, … of the p-arrays

Proposition 8. (Falling diagonals)

(a) The falling diagonal beginning in row k = 1, 2, …, p is the sequence

( ∑_{i=0}^{p+1−k} \binom{p + 1 − k}{i} (−1)^{i} (p + n − k − i)^{p})_{n=1}^{∞} .  (37)

(b) The falling diagonal beginning in row k ≥ p is the sequence

(∑_{i=1}^{n} \binom{k − 1 + n − p}{n − i}i!S (p, i))_{n=1}^{∞} .  (38)

Proof. (a) According to (26) the falling diagonal beginning in the row k = 1, 2, …, p is the sequence

a_{n+p−1,p−k+n}^{(p)} = ∑_{i=1}^{p+n−k} \binom{n − 1}{n + p − k − i}i!S (p, i) ,  (39)

where n ∈ ℕ. Thus, we have to prove that for k = 1, 2, …, p and n ∈ ℕ, the following identity holds:

∑_{i=0}^{p+1−k} \binom{p + 1 − k}{i} (−1)^{i} (p + n − k − i)^{p} = ∑_{i=1}^{p+n−k} \binom{n − 1}{p + n − k − i}i!S (p, i) . (40)

We proceed by induction on n. For n = 1 the result is clear (one can see that both sides of (4.4) are equal to (p + 1 − k)!S (p, p + 1 − k)). Suppose the result is true for a given n ∈ ℕ. Then

∑_{i=1}^{p+n+1−k} \binom{n}{p + n + 1 − k − i}i!S (p, i)

= ∑_{i=1}^{p+n+1−k} (\binom{n − 1}{p + n + 1 − k − i} + \binom{n − 1}{p + n − k − i}) i!S (p, i)

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

= (p + n + 1 − k)^{p} + ∑_{i=1}^{p+2−k} (\binom{p + 2 − k}{i} − \binom{p + 1 − k}{i − 1}) (−1)^{i} (p + n + 1 − k − i)^{p}

= ∑_{i=0}^{p+1−k} \binom{p + 1 − k}{i} (−1)^{i} (p + n + 1 − k − i)^{p} ,

as claimed.

(b) Formula (38) gives us (according to (26)), the elements a_{k−1+n,n}^{(p)}, n ∈ ℕ, of the falling diagonal beginning in row k ≥ p.

Some particular cases are the following:

(a) (First falling diagonal) If we set k = 1 in (39), we see that the corresponding sequence of the falling diagonal beginning in the first row is the constant sequence p!. Thus, according to (40) we have that (for any n ∈ ℕ)

∑_{i=0}^{p} \binom{p}{i} (−1)^{i} (p + n − 1 − i)^{p} = p!  (41)

(b) ((p + 1)-th falling diagonal) From (38) we see that the falling diagonal beginning in row k = p + 1 is (according to (24))

∑_{i=1}^{n} \binom{n}{i}i!S (p, i) = n^{p}.  (42)

(c) (p-th falling diagonal) From (37) we see that the falling diagonal beginning in row k = p is

(∑_{i=0}^{1} \binom{1}{i} (−1)^{i} (n − i)^{p})_{n=1}^{∞} = (n^{p} − (n − 1)^{p})_{n=1}^{∞} .  (43)

(This sequence can also be obtained by setting k = p in (38), since ∑_{j=1}^{n} \binom{n−1}{j−1}j!S (p, j) = n^{p} − (n − 1)^{p}; proof left to the reader.)

We have also the hockey stick property for falling diagonals.

Proposition 9. (Partial sums of falling diagonals: hockey stick property) The sum of the elements of a falling diagonal (beginning in the first column and in the row k ≥ p), up to column m, is equal to the element just below the last element added in the diagonal (in the same column of it). That is, we have (for k ≥ p) that ∑_{l=0}^{m−1} a_{k+l,1+l}^{(p)} = a_{k+m,m}^{(p)}, or

∑_{l=0}^{m} ∑_{i=1}^{l+1} \binom{k + l − p}{l + 1 − i}i!S (p, i) = ∑_{i=1}^{m+1} \binom{k + m + 1 − p}{m + 1 − i}i!S (p, i) .  (44)

Proof. Easy induction argument on m, left to the reader.

As in the case of columns, the hockey stick property of the falling diagonals tells us that each falling diagonal beginning in row k > p is formed by the partial sums of the previous diagonal, that is, from the convolution of the previous diagonal with the constant sequence 1. Since the diagonal beginning in row k = p + 1 is n^{p}, what we have in the following diagonals (beginning in rows k = p + r, r = 2, 3, …) are the sequences (of “hyper-sums of powers of integers”): ∑_{i_{1}=1}^{n} i_{1}^{p}, ∑_{i_{2}=1}^{n} ∑_{i_{1}=1}^{i_{2}} i_{1}^{p}, ∑_{i_{3}=1}^{n} ∑_{i_{2}=1}^{i_{3}} ∑_{i_{1}=1}^{i_{2}} i_{1}^{p}, and so on. In general we have for l = 1, 2, …

n^{p} ∗^{l} 1 = ∑_{i_{l}=1}^{n} ⋯ ∑_{i_{2}=1}^{i_{3}} ∑_{i_{1}=1}^{i_{2}} i_{1}^{p} = ∑_{i=1}^{n} \binom{n + l}{n − i}i!S (p, i) .  (45)

(Formula (45) is also obtained in [5].) Observe that the falling diagonal beginning in row k = p + 1, that is, the sequence n^{p}, can also be seen as the partial sums of the falling diagonal beginning in row k = p (the partial sums of the sequence (n^{p} − (n − 1)^{p})_{n=1}^{∞}).

5 Properties III: Rising Diagonals

In this section we will deal with the sequence of Fibonacci numbers (F_{n})_{n=0}^{∞} = (0, 1, 1, 2, 3, 5, …) and the sequence of Lucas numbers (L_{n})_{n=0}^{∞} = (2, 1, 3, 4, 7, 11, …). These sequences are defined by the same second-order linear recurrence a_{n+2} = a_{n+1} + a_{n}, with initial conditions F_{0} = 0, F_{1} = 1 in the Fibonacci case, and L_{0} = 2, L_{1} = 1 in the Lucas case. We have Binet’s formulas F_{n} = \frac{1}{\sqrt{5}} (α^{n} − β^{n}), L_{n} = α^{n} + β^{n}, where α = \frac{1}{2} (1 + \sqrt{5}) and β = \frac{1}{2} (1 − \sqrt{5}). These formulas, together with the well-known identity ∑_{j=0}^{m} \binom{m−j}{j} = F_{m+1}, will be used without additional comments throughout this section.

Array Falling diagonal beginning in row

k = 1, …, p

Sequence ( ∑_{i=0}^{p+1−k} \binom{p+1−k}{i} (−1)^{i} (p + n − k − i)^{p})_{n=1}^{∞} OEIS

p = 1  k = 1  (1) = (1, 1, 1, 1, …)  \underline{A000012}
p = 2  k = 1  (2) = (2, 2, 2, 2, …)
k = 2  (2n − 1) = (1, 3, 5, 7, …)  \underline{A005408}
p = 3  k = 1  (6) = (6, 6, 6, 6, …)
k = 2  (6n) = (6, 12, 18, 24, …)  \underline{A008588}
k = 3  (3n^{2} − 3n + 1) = (1, 7, 19, 37, …)  \underline{A003215}
p = 4  k = 1  (24) = (24, 24, 24, 24, …)
k = 2  (24n + 12) = (36, 60, 84, 108, …)  \underline{A101103}
k = 3  (12n^{2} + 2) = (14, 50, 110, 194, …)  \underline{A005914}
k = 4  (4n^{3} − 6n^{2} + 4n − 1) = (1, 15, 65, 175, …)  \underline{A005917}

Table 5: First p falling diagonals of the p-arrays.

Array Fall. diag. beginning

in row k ≥ p + 1

Sequence (∑_{i=1}^{n} \binom{k−1+n−p}{n−i}i!S (p, i))_{n=1}^{∞} OEIS

p = 1  k = 2  n = (1, 2, 3, 4, …)  \underline{A000027}
k = 3  n ∗ 1 = ∑_{t=0}^{n} t = (1, 3, 6, 10, …)  \underline{A000217}
k = 4  n ∗^{2} 1 = ∑_{s=0}^{n} ∑_{t=0}^{s} t = (1, 4, 10, 20, …)  \underline{A000292}
⋮  ⋮
p = 2  k = 3  n^{2} = (1, 4, 9, 16, …)  \underline{A000290}
k = 4  n^{2} ∗ 1 = ∑_{t=0}^{n} t^{2} = (1, 5, 14, 30, …)  \underline{A000330}
k = 5  n^{2} ∗^{2} 1 = ∑_{s=0}^{n} ∑_{t=0}^{s} t^{2} = (1, 6, 20, 50, …) \underline{A002415}
⋮  ⋮  ⋮
p = 3  k = 4  n^{3} = (1, 8, 27, 64, …)  \underline{A000578}
k = 5  n^{3} ∗ 1 = ∑_{t=0}^{n} t^{3} = (1, 9, 36, 100, …)  \underline{A000537}
k = 6  n^{3} ∗^{2} 1 = ∑_{s=0}^{n} ∑_{t=0}^{s} t^{3} = (1, 10, 46, 146, …) \underline{A024166}
⋮  ⋮  ⋮
p = 4  k = 5  n^{4} = (1, 16, 81, 256, …)  \underline{A000583}
k = 6  n^{4} ∗ 1 = ∑_{t=0}^{n} t^{4} = (1, 17, 98, 354, …)  \underline{A000538}
k = 7  n^{4} ∗^{2} 1 = ∑_{s=0}^{n} ∑_{t=0}^{s} t^{4} = (1, 18, 116, 470, …) \underline{A101089}
⋮  ⋮  ⋮

Table 6: Falling diagonals p + 1, p + 2, … of the p-arrays.

The goal of this section is to prove the following result

\frac{\begin{aligned}⌊ & \frac{k+1}{2} & ⌋ \\ & ∑ \\ & j=1 \end{aligned} ∑_{i=1}^{j} \binom{k − j + 1 − p}{j − i}i!S (p, i)}{∑_{i=1}^{p+1} (−1)^{i} (i − 1)!S (p + 1, i) F_{i−1}} = \begin{cases}F_{k−p+1}, & if p is odd and k ≥ 2p − 1; \\ L_{k−p+1}, & if p is even and k ≥ 2p − 2. \end{cases}  (46)

Observe that, according to (26), the numerator of the left-hand side of (46) is the sum of the elements of the rising diagonals beginning in the row k in the p-array. The sequence of the denominators is the Stirling-Bernoulli transform of Fibonacci numbers:

(∑_{i=1}^{p+1} (−1)^{i} (i − 1)!S (p + 1, i) F_{i−1})_{p=1}^{∞} = (1, 1, 7, 13, 151, 421, …)

(\underline{A050946}). That is, we will prove that the sum of the elements of the rising diagonals in the p-arrays (beginning in row k ≥ 2p − 1 when p is odd, or in row k ≥ 2p − 2 when p is even) is equal to a Stirling-Bernoulli transform of Fibonacci numbers (which depends only on the parameter p), times the Fibonacci F_{k−p+1} when p is odd, or times the Lucas L_{k−p+1} when p is even. We will do this in Proposition 13. This proof will need a previous result (Proposition 12) about some identities involving the sums ∑_{i=1}^{2p−1} i!S (2p − 1, i) F_{2p−i} and ∑_{i=1}^{2p−1} i!S (2p, i) F_{2p−i}, and in turn, the proof of these identities will require to know that ∑_{k=1}^{2p−1} (−1)^{k} k!S (2p − 1, k) F_{k−1} = ∑_{k=1}^{2p} (−1)^{k} k!S (2p, k) L_{k−1} = 0 (corollary 11). Finally, the proof of these last results will come as corollary of a property of certain polynomials that we will study first. So we begin this section considering the polynomials

∑_{k=1}^{p} k!S (p, k) x^{k−1}.  (47)

What we will need of these polynomials is a nice property stated (and proved) in the next proposition. We comment that polynomials (47) have been studied for a long time. Recently they appeared in some work of Kellner (see [8, 9]). In fact, the result we need of these polynomials appears implicitly in the 1975 paper of Tanny [18], and probably appears in some older papers. (I thank Bernd Kellner [10] for calling my attention to this reference.) However, the argument we present here to prove the desired property (48) is different, direct and more elementary. That is why we think it is worthy to present it in this work.

Proposition 10. The following property of polynomials (47) holds:

∑_{k=1}^{p} k!S (p, k) x^{k−1} = (−1)^{p} ∑_{k=1}^{p} (−1)^{k} k!S (p, k) (x + 1)^{k−1} .  (48)

Proof. By induction on p. For p = 1 the formula is trivial. Suppose formula (47) is valid for a given p ∈ ℕ. Then

∑_{k=1}^{p+1} k!S (p + 1, k) x^{k−1} = ∑_{k=1}^{p+1} k! (kS (p, k) + S (p, k − 1)) x^{k−1}

= ∑_{k=1}^{p} k!kS (p, k) x^{k−1} + x ∑_{k=1}^{p} (k + 1)!S (p, k) x^{k−1}

= (x + 1) ∑_{k=1}^{p} k!kS (p, k) x^{k−1} + ∑_{k=1}^{p} k!S (p, k) x^{k}

= \frac{d}{dx} ((x + 1) ∑_{k=1}^{p} k!S (p, k) x^{k})

= \frac{d}{dx} ((x + 1) x (−1)^{p} ∑_{k=1}^{p} (−1)^{k} k!S (p, k) (x + 1)^{k−1}) ,

where we used the induction hypothesis in the last step. Some further simplifications give us

∑_{k=1}^{p+1} k!S (p + 1, k) x^{k−1}

= \frac{d}{dx} (x ∑_{k=1}^{p} (−1)^{k+p} k!S (p, k) (x + 1)^{k})

= x ∑_{k=1}^{p} (−1)^{k+p} k!kS (p, k) (x + 1)^{k−1} + ∑_{k=1}^{p} (−1)^{k+p} k!S (p, k) (x + 1)^{k}

= ∑_{k=1}^{p} (−1)^{k+p} k!kS (p, k) (x + 1)^{k} + ∑_{k=1}^{p} (−1)^{k+p} k!S (p, k) (x + 1)^{k}

− ∑_{k=1}^{p} (−1)^{k+p} k!kS (p, k) (x + 1)^{k−1}

= ∑_{k=1}^{p} (−1)^{k+p} (k + 1)!S (p, k) (x + 1)^{k} − ∑_{k=1}^{p} (−1)^{k+p} k!kS (p, k) (x + 1)^{k−1}

= ∑_{k=2}^{p+1} (−1)^{k+p+1} k!S (p, k − 1) (x + 1)^{k−1} − ∑_{k=1}^{p} (−1)^{k+p} k!kS (p, k) (x + 1)^{k−1}

= (−1)^{p+1} ∑_{k=1}^{p+1} (−1)^{k} k! (S (p, k − 1) + kS (p, k)) (x + 1)^{k−1}
= (−1)^{p+1} ∑_{k=1}^{p+1} (−1)^{k} k!S (p + 1, k) (x + 1)^{k−1} ,

as claimed. Corollary 11. The following identities hold:

∑_{k=1}^{2p−1} (−1)^{k} k!S (2p − 1, k) F_{k−1} = 0.  (49)
∑_{k=1}^{2p} (−1)^{k} k!S (2p, k) L_{k−1} = 0.  (50)

Proof. Let us consider (48) when p is odd, 2p − 1 say. This is

∑_{k=1}^{2p−1} k!S (2p − 1, k) x^{k−1} = ∑_{k=1}^{2p−1} k!S (2p − 1, k) (−x − 1)^{k−1} .  (51)

Replace x by x − \frac{1}{2} in (51) to get

∑_{k=1}^{2p−1} (−1)^{k} k!S (2p − 1, k) (\frac{1}{2} − x)^{k−1} = ∑_{k=1}^{2p−1} (−1)^{k} k!S (2p − 1, k) (\frac{1}{2} + x)^{k−1} . (52)

Set x = \frac{\sqrt{5}}{2} in (52) to obtain that

∑_{k=1}^{2p−1} (−1)^{k} k!S (2p − 1, k) β^{k−1} = ∑_{k=1}^{2p−1} (−1)^{k} k!S (2p − 1, k) α^{k−1},  (53)

from where (49) follows.

Similarly, if p is even, 2p say, we have from (48) that

∑_{k=1}^{2p} k!S (2p, k) x^{k−1} = − ∑_{k=1}^{2p} k!S (2p, k) (−x − 1)^{k−1} .  (54)

Replace x by x − \frac{1}{2} in (54) to get

∑_{k=1}^{2p} (−1)^{k} k!S (2p, k) (\frac{1}{2} − x)^{k−1} = − ∑_{k=1}^{2p} (−1)^{k} k!S (2p, k) (\frac{1}{2} + x)^{k−1} .  (55)

Set x = \frac{\sqrt{5}}{2} in (55) to obtain that

∑_{k=1}^{2p} (−1)^{k} k!S (2p, k) β^{k−1} = − ∑_{k=1}^{2p} (−1)^{k} k!S (2p, k) α^{k−1},  (56)

from where (50) follows.

In the proof of the following proposition we will use the identities

F_{2p−i} + (−1)^{i} F_{2p−1}F_{i−2} = (−1)^{i} F_{2p−2}F_{i−1},  (57)

and

F_{2p−i} = (−1)^{i+1} (F_{i−2}L_{2p−1} − F_{2p−2}L_{i−1}) .  (58)

These identities are consequences of the so-called “index-reduction formulas”:

F_{M}F_{N} − F_{M+K}F_{N−K} = (−1)^{N−K} F_{M+K−N}F_{K},  (59)

and

L_{M}F_{N} − L_{M+K}F_{N−K} = (−1)^{N−K} L_{M+K−N}F_{K},  (60)

respectively (see [6]). In fact, if we set M = 2p − 2, N = i − 1 and K = 1 in (59) we obtain (57), and if we set M = i − 1, N = 2p − 2 and K = 2p − i in (60) we obtain (58). Proposition 12. The following identities hold:

∑_{i=1}^{2p−1} i!S (2p − 1, i) F_{2p−i} = (∑_{i=1}^{2p} (−1)^{i} (i − 1)!S (2p, i) F_{i−1}) F_{2p−1}.  (61)
∑_{i=1}^{2p−1} i!S (2p, i) F_{2p−i} = (∑_{i=1}^{2p+1} (−1)^{i} (i − 1)!S (2p + 1, i) F_{i−1}) L_{2p−1}.  (62)

Proof. By using (57) and (49), we begin with the left-hand side of (61) to obtain

∑_{i=1}^{2p−1} i!S (2p − 1, i) F_{2p−i}

= ∑_{i=1}^{2p−1} (−1)^{i} i!S (2p − 1, i) (F_{2p−2}F_{i−1} − F_{2p−1}F_{i−2})
= (∑_{i=1}^{2p−1} (−1)^{i} i!S (2p − 1, i) (F_{i−1} − F_{i})) F_{2p−1}
= (∑_{i=1}^{2p−1} (−1)^{i+1} (i + 1)!S(2p − 1, i + 1)F_{i} + ∑_{i=1}^{2p−1} (−1)^{i+1} i!S(2p − 1, i)F_{i})F_{2p−1}
= (∑_{i=1}^{2p−1} (−1)^{i+1} i! ((i + 1) S (2p − 1, i + 1) + S (2p − 1, i)) F_{i}) F_{2p−1}
= (∑_{i=1}^{2p} (−1)^{i} (i − 1)!S (2p, i) F_{i−1}) F_{2p−1},

as claimed. Similarly, by using (58) and (50), we can write the left-hand side of (62) as

∑_{i=1}^{2p} i!S (2p, i) F_{2p−i} = L_{2p−1} ∑_{i=1}^{2p} (−1)^{i} i!S (2p, i) F_{i−2} − F_{2p−2} ∑_{i=1}^{2p} (−1)^{i} i!S (2p, i) L_{i−1}
= (∑_{i=1}^{2p} (−1)^{i} i!S (2p, i) (F_{i−1} − F_{i})) L_{2p−1}
= (∑_{i=1}^{2p} (−1)^{i+1} (i + 1)!S (2p, i + 1) F_{i} + ∑_{i=1}^{2p} (−1)^{i+1} i!S (2p, i) F_{i}) L_{2p−1}
= (∑_{i=1}^{2p} (−1)^{i+1} i! ((i + 1) S (2p, i + 1) + S (2p, i)) F_{i}) L_{2p−1}
= (∑_{i=1}^{2p+1} (−1)^{i} (i − 1)!S (2p + 1, i) F_{i−1}) L_{2p−1},

as claimed. Proposition 13. (a) For k ≥ 4p − 3 we have

\begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} ∑_{i=1}^{j} \binom{k − j + 2 − 2p}{j − i}i!S (2p − 1, i) = (∑_{i=1}^{2p} (−1)^{i} (i − 1)!S (2p, i) F_{i−1}) F_{k−2p+2}. (63)

(b) For k ≥ 4p − 2

\begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} ∑_{i=1}^{j} \binom{k − j + 1 − 2p}{j − i}i!S (2p, i) = (∑_{i=1}^{2p+1} (−1)^{i} (i − 1)!S (2p + 1, i) F_{i−1}) L_{k−2p+1}.

(64)

Proof. (a) Induction on k. For k = 4p − 3, we have to see that

∑_{j=1}^{2p−1} ∑_{i=1}^{j} \binom{2p − 1 − j}{j − i}i!S (2p − 1, i) = (∑_{i=1}^{2p} (−1)^{i} (i − 1)!S (2p, i) F_{i−1}) F_{2p−1}.  (65)

We have

∑_{j=1}^{2p−1} ∑_{i=1}^{j} \binom{2p − 1 − j}{j − i}i!S (2p − 1, i)

= ∑_{j=1}^{2p−1} ∑_{i=1}^{2p−1} \binom{2p − 1 − j}{j − i}i!S (2p − 1, i) = ∑_{i=1}^{2p−1} i!S (2p − 1, i) ∑_{j=i}^{2p−1} \binom{2p − 1 − j}{j − i}

= ∑_{i=1}^{2p−1} i!S (2p − 1, i) ∑_{j=0}^{2p−1−i} \binom{2p − 1 − j − i}{j} = ∑_{i=1}^{2p−1} i!S (2p − 1, i) F_{2p−i}

= (∑_{i=1}^{2p} (−1)^{i} (i − 1)!S (2p, i) F_{i−1}) F_{2p−1},

as claimed (we used (61) in the last step).

If (63) is true for a given k > 4p − 3, we will show that it is also true for k + 1. In fact, we have

(∑_{i=1}^{2p} (−1)^{i} (i − 1)!S (2p, i) F_{i−1}) F_{k−2p+3}

= (∑_{i=1}^{2p} (−1)^{i} (i − 1)!S (2p, i) F_{i−1}) F_{k−2p+2} + (∑_{i=1}^{2p} (−1)^{i} (i − 1)!S (2p, i) F_{i−1}) F_{k−2p+1}

= \begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} ∑_{i=1}^{j} \binom{k − j + 2 − 2p}{j − i}i!S (2p − 1, i) + \begin{matrix}⌊ & \frac{k}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} ∑_{i=1}^{j} \binom{k − j + 1 − 2p}{j − i}i!S (2p − 1, i)

= \begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} ∑_{i=1}^{j} \binom{k − j + 2 − 2p}{j − i}i!S (2p − 1, i) + ∑_{j=1}^{⌊\frac{k}{2}⌋+1} ∑_{i=1}^{j} \binom{k − j + 2 − 2p}{j − 1 − i}i!S (2p − 1, i)

= \begin{matrix}⌊ & \frac{k+2}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} ∑_{i=1}^{j} \binom{k − j + 3 − 2p}{j − i}i!S (2p − 1, i) ,

as claimed.

(b) The proof is similar to (a) (induction on k). For k = 4p − 2 we have to prove that

∑_{j=1}^{2p−1} ∑_{i=1}^{j} \binom{2p − j − 1}{j − i}i!S (2p, i) = (∑_{i=1}^{2p+1} (−1)^{i} (i − 1)!S (2p + 1, i) F_{i−1}) L_{2p−1}.  (66)

We have (by using (62))

∑_{j=1}^{2p−1} ∑_{i=1}^{j} \binom{2p − j − 1}{j − i}i!S (2p, i) = ∑_{j=1}^{2p−1} ∑_{i=1}^{2p−1} \binom{2p − 1 − j}{j − i}i!S (2p, i)

= ∑_{i=1}^{2p−1} i!S (2p, i) ∑_{j=i}^{2p−1} \binom{2p − 1 − j}{j − i}

= ∑_{i=1}^{2p−1} i!S (2p, i) ∑_{j=0}^{2p−1−i} \binom{2p − 1 − j − i}{j} = ∑_{i=1}^{2p−1} i!S (2p, i) F_{2p−i}.

= (∑_{i=1}^{2p+1} (−1)^{i} (i − 1)!S (2p + 1, i) F_{i−1}) L_{2p−1},

which proves (66). Suppose the result is valid for a given k > 4p − 2. Then

(∑_{i=1}^{2p+1} (−1)^{i} (i − 1)!S (2p + 1, i) F_{i−1}) L_{k−2p+2}

= (∑_{i=1}^{2p+1} (−1)^{i} (i − 1)!S (2p + 1, i) F_{i−1}) L_{k−2p+1} + (∑_{i=1}^{2p+1} (−1)^{i} (i − 1)!S (2p + 1, i) F_{i−1}) L_{k−2p}

= \begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} ∑_{i=1}^{j} \binom{k − j + 1 − 2p}{j − i}i!S (2p, i) + \begin{matrix}⌊ & \frac{k}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} ∑_{i=1}^{j} \binom{k − j − 2p}{j − i}i!S (2p, i)

= \begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} ∑_{i=1}^{j} \binom{k − j + 1 − 2p}{j − i}i!S (2p, i) + ∑_{j=1}^{⌊\frac{k}{2}⌋+1} ∑_{i=1}^{j} \binom{k + 1 − j − 2p}{j − 1 − i}i!S (2p, i)

= ∑_{j=1}^{⌊\frac{k}{2}⌋+1} ∑_{i=1}^{j} \binom{k − j + 2 − 2p}{j − i}i!S (2p, i) ,

as claimed.

Both results (63) and (64) of Proposition 13 prove the desired result (46). Some examples are the following:

In the case p = 1, we have for k ≥ 1

\begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} \binom{k − j}{j − 1} = F_{k}.

In the case p = 2, we have for k ≥ 2

\begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} (\binom{k − j − 1}{j − 1} + 2\binom{k − j − 1}{j − 2}) = L_{k−1}.

In the case p = 3, we have for k ≥ 5

\begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} (\binom{k − j − 2}{j − 1} + 6\binom{k − j − 2}{j − 2} + 6\binom{k − j − 2}{j − 3}) = 7F_{k−2}.

In the case p = 4, we have for k ≥ 6

\begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} (\binom{k − j − 3}{j − 1} + 14\binom{k − j − 3}{j − 2} + 36\binom{k − j − 3}{j − 3} + 24\binom{k − j − 3}{j − 4}) = 13L_{k−3}.

In the case p = 5, we have for k ≥ 9

\begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} (\binom{k − j − 3}{j − 1} + 30\binom{k − j − 3}{j − 2} + 150\binom{k − j − 3}{j − 3} + 240\binom{k − j − 3}{j − 4} + 120\binom{k − j − 3}{j − 5})
= 151F_{k−4}.

In Tables 7 and 8 we have some more concrete examples.

6 Some related arrays

With the p-arrays described in section 2, we will form some new arrays. Taking the p-th row of each of the p-arrays (the first row of Pascal’s triangle, the second row of Lucas triangle, the third row of the 3-array, and so on; or, if you want, taking the first non-cancelled row of each p-array), we form the p-rows array (observe that now p ∈ ℕ is the running index).

Array Beginning in row k ≥ 2p − 1 The rising diagonal is… The sum of the elements is...

... which is equal to...

p = 1  k = 1  (1)  1  F_{1}
k = 2  (1)  1  F_{2}
k = 3  (1, 1)  2  F_{3}
⋮  ⋮  ⋮  ⋮
p = 3  k = 5  (1, 7, 6)  14  7F_{3}
k = 6  (1, 8, 12)  21  7F_{4}
k = 7  (1, 9, 19, 6)  35  7F_{5}
⋮  ⋮  ⋮  ⋮
p = 5  k = 9  (1, 33, 211, 390, 120)  755  151F_{5}
k = 10  (1, 34, 243, 570, 360)  1208  151F_{6}
k = 11  (1, 35, 276, 781, 750, 120)  1963  151F_{7}
⋮  ⋮  ⋮  ⋮

Table 7: The sum of the rising diagonals in the p-arrays, with p odd, is a constant times a Fibonacci number.

Array Beginning in row k ≥ 2p − 2 The rising diagonal is… The sum is ...

... which is equal to...

p = 2  k = 2  (1)  1  L_{1}
k = 3  (1, 2)  3  L_{2}
k = 4  (1, 3)  4  L_{3}
⋮  ⋮  ⋮  ⋮
p = 4  k = 6  (1, 15, 36)  52  13L_{3}
k = 7  (1, 16, 50, 24)  91  13L_{4}
k = 8  (1, 17, 65, 60)  143  13L_{5}
⋮  ⋮  ⋮  ⋮
p = 6  k = 10  (1, 65, 665, 2100, 1800)  4631  421L_{5}
k = 11  (1, 66, 729, 2702, 3360, 720)  7578  421L_{6}
k = 12  (1, 67, 794, 3367, 5460, 2520)  12209  421L_{7}
⋮  ⋮  ⋮  ⋮

Table 8: The sum of the rising diagonals in the p-arrays, with p even, is a constant times a Lucas number.

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 0 & 0 & 0 \\ 1 & 6 & 6 & 0 & 0 \\ 1 & 14 & 36 & 24 & 0 & ⋯ \\ 1 & 30 & 150 & 240 & 120 \\ ⋮ & & & ⋮ & & ... \end{matrix} ] .

Taking now the (p + 1)-th row of each of the p-arrays (equivalently, taking the second non-cancelled row of each p-array), we form the (p + 1)-rows array

[ \begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ⋯ \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 3 & 2 & 0 & 0 & 0 \\ 1 & 7 & 12 & 6 & 0 & 0 & ⋯ \\ 1 & 15 & 50 & 60 & 24 & 0 \\ 1 & 31 & 180 & 390 & 360 & 120 \\ ⋮ & & & ⋮ & & & ... \end{matrix} ] .

Similarly, we can form the (p + 2)-rows array

[ \begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ⋯ \\ ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 1 & 4 & 5 & 2 & 0 & 0 & 0 & ⋯ \\ 1 & 8 & 19 & 18 & 6 & 0 & 0 \\ 1 & 16 & 65 & 110 & 84 & 24 & 0 \\ 1 & 32 & 211 & 570 & 750 & 480 & 120 & ⋯ \\ ⋮ & & & ⋮ & & & ⋮ & ... \end{matrix} ] .

The (p + 3)-rows array

[ \begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ⋯ \\ ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ \\ 1 & 3 & 3 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 5 & 9 & 7 & 2 & 0 & 0 & 0 \\ 1 & 9 & 27 & 37 & 24 & 6 & 0 & 0 \\ 1 & 17 & 81 & 175 & 194 & 108 & 24 & 0 & ⋯ \\ 1 & 33 & 243 & 781 & 1320 & 1230 & 600 & 120 \\ ⋮ & & & ⋮ & & & ⋮ & & ... \end{matrix} ] ,

and so on.

According to (26), we see at once that the elements of the (p + t)-rows array (t = 0, 1, 2, …), denoted as a_{κ,j}^{(t)}, are

a_{κ,j}^{(t)} = ∑_{i=1}^{j} \binom{t}{j − i}i!S (κ − t, i) ,  (67)

where κ ≥ t + 1 and j = 1, 2, …, κ. Thus (for j = 1, 2, …, κ), the elements of the prows array are a_{κ,j}^{(0)} = j!S (κ, j), where κ ≥ 1; the elements of the (p + 1)-rows array are a_{κ,j}^{(1)} = (j − 1)!S (κ, j), where κ ≥ 2; the elements of the (p + 2)-rows array are a_{κ,j}^{(2)} = j!S (κ − 2, j) + (j − 1)!2S (κ − 2, j − 1) + (j − 2)!S (κ − 2, j − 2), where κ ≥ 3, and so on. Observe also that in any of the (p + t)-rows array we have a_{κ,j}^{(t)} = 0 for j > k (we have —as in the p-arrays— infinite triangular lower matrices with its first t rows cancelled), and a_{t+n,t+n}^{(t)} = n! for n ∈ ℕ (the main falling diagonal —ignoring the cancelled elements— is always the sequence n!).

In the following proposition we describe the recurrence of the elements in the (p + t)-rows arrays.

Proposition 14. For j = 1, 2, …, κ + 1

ja_{κ,j}^{(t)} + (j − t) a_{κ,j−1}^{(t)} = a_{κ+1,j}^{(t)}.  (68)

Proof. Observe that expression (68) is true when j = κ + 1 (both sides are (κ + 1 − t)!). So we consider only j = 1, 2, …, κ. We want to see that

j ∑_{i=1}^{j} \binom{t}{j − i}i!S (κ − t, i)+(j − t) ∑_{i=1}^{j} \binom{t}{j − 1 − i}i!S (κ − t, i) = ∑_{i=1}^{j} \binom{t}{j − i}i!S (κ + 1 − t, i) .

(69)

Clearly (69) holds if t = 0 (both sides are j!S (κ + 1, j)). So let us consider the cases t ≥ 1. We have

j ∑_{i=1}^{j} \binom{t}{j − i}i!S (κ − t, i) + (j − t) ∑_{i=1}^{j} \binom{t}{j − 1 − i}i!S (κ − t, i)

= j ∑_{i=1}^{j} \binom{t}{j − i} (i − 1)! (iS (κ − t, i) + S (κ − t, i − 1)) − t ∑_{i=1}^{j} \binom{t}{j − i} (i − 1)!S (κ − t, i − 1)

= j ∑_{i=1}^{j} \binom{t}{j − i} (i − 1)!S (κ + 1 − t, i) − t ∑_{i=1}^{j} \binom{t}{j − i} (i − 1)!S (κ − t, i − 1) .

Then, we need to prove that

j ∑_{i=1}^{j} \binom{t}{j − i} (i − 1)!S (κ + 1 − t, i) − t ∑_{i=1}^{j} \binom{t}{j − i} (i − 1)!S (κ − t, i − 1)

= ∑_{i=1}^{j} \binom{t}{j − i}i!S (κ + 1 − t, i) ,  (70)

or (after some easy simplification)

∑_{i=1}^{j} \binom{t − 1}{j − i − 1} (i − 1)!S (κ + 1 − t, i) = ∑_{i=1}^{j} \binom{t}{j − i} (i − 1)!S (κ − t, i − 1) .  (71)

We have

∑_{i=1}^{j} \binom{t}{j − i} (i − 1)!S (κ − t, i − 1)

= ∑_{i=1}^{j} (\binom{t − 1}{j − i} + \binom{t − 1}{j − i − 1}) (i − 1)!S (κ − t, i − 1)

= ∑_{i=1}^{j} \binom{t − 1}{j − i − 1}i!S(κ − t, i) + ∑_{i=1}^{j} \binom{t − 1}{j − i − 1} (i − 1)!S(κ − t, i − 1)

= ∑_{i=1}^{j} \binom{t − 1}{j − i − 1} (i − 1)! (iS (κ − t, i) + S (κ − t, i − 1))

= ∑_{i=1}^{j} \binom{t − 1}{j − i − 1} (i − 1)!S (κ + 1 − t, i) ,

as claimed.

There are some interesting surprises hidden in the columns of the (p + t)-rows arrays, that we show next. Observe that the j-th column (beginning in the (t + 1)-th row) of the (p + t)-rows array is, according to (67), the sequence

(∑_{i=1}^{j} \binom{t}{j − i}i!S (n, i))_{n=1}^{∞} .  (72)

Observe that if j = t (with t ≥ 1), the elements of the sequence (72) are (according to (24))

∑_{i=1}^{t} \binom{t}{i}i!S (n, i) = t^{n}.  (73)

That is, the t-th column of the (p + t)-rows array is (t^{n})_{n=1}^{∞}. Some other particular cases of sequences in the columns of the (p + t)-th rows array are the following (where t ≥ 2 and 1 ≤ j ≤ t − 1, i.e., the previous columns to the t-th one):

(a) Expression (72) with j = 1 gives us (S (n, 1))_{n=1}^{∞}. That is, the first column in the (p + t)-rows arrays is the constant sequence 1.

(b) The second column in the (p + t)-rows array is the sequence (2^{n} + t − 2)_{n=1}^{∞}, since

∑_{i=1}^{2} \binom{t}{2 − i}i!S (n, i) = t + 2S (n, 2) = t + 2 (2^{n−1} − 1) = 2^{n} + t − 2.  (74)

(c) According to (72), the sequence of the (t − 1)-th column in the (p + t)-rows array is

(∑_{i=1}^{t−1} \binom{t}{i + 1}i!S (n, i))_{n=1}^{∞} .  (75)

We claim that

∑_{i=1}^{t−1} \binom{t}{i + 1}i!S (n, i) = 1^{n} + 2^{n} + ⋯ + (t − 1)^{n} .  (76)

In fact, if t = 2 formula (76) is clearly true. If we suppose formula (76) is valid for a given t ≥ 2, then, using (73) we have

∑_{i=1}^{t} \binom{t + 1}{i + 1}i!S (n, i) = ∑_{i=1}^{t} (\binom{t}{i + 1} + \binom{t}{i}) i!S (n, i)  (77)

= ∑_{i=1}^{t−1} \binom{t}{i + 1}i!S (n, i) + ∑_{i=1}^{t} \binom{t}{i}i!S (n, i)
= 1^{n} + 2^{n} + ⋯ + t^{n},  (78)

which proves the claim. Thus, in the (t − 1)-th column of the (p + t)-rows array we have the sequence (1^{n} + 2^{n} + ⋯ + (t − 1)^{n})_{n=1}^{∞}. For example, for t = 3, 4, 5 and 6 we have the sequences

(1^{n} + 2^{n})_{n=1}^{∞} = (3, 5, 9, 17, …)
(1^{n} + 2^{n} + 3^{n})_{n=1}^{∞} = (6, 14, 36, 98, …)
(1^{n} + 2^{n} + 3^{n} + 4^{n})_{n=1}^{∞} = (10, 30, 100, 354, …)
(1^{n} + 2^{n} + 3^{n} + 4^{n} + 5^{n})_{n=1}^{∞} = (15, 55, 225, 979, …) ,

respectively (\underline{A000051}, \underline{A001550}, \underline{A001551} and \underline{A001552}, respectively).

In the following proposition we show that columns j > t (after the t-th column) of the (p + t)-rows arrays are nice sequences related with some convolutions.

Proposition 15. For t ≥ 1 and r = 0, 1, 2, …, the (t + r)-th column of the (p + t)-rows array is the sequence

(r! (t^{n} ∗ (t + 1)^{n} ∗ ⋯ ∗ (t + r)^{n}))_{n=0}^{∞} .  (79)

Proof. The case r = 0 was proved before (see (73)) . Suppose the result is valid for a given r > 0. Write a_{n} = r! (t^{n} ∗ (t + 1)^{n} ∗ ⋯ ∗ (t + r)^{n}) (the non-zero elements of the (t + r)- th column), and b_{n} for the sequence of the (t + r + 1)-th column. We have a_{0} = r! and b_{0} = (r + 1)!. Observe that the Z-Transform of the sequence a_{n} is

Z (a_{n}) = \frac{r!z^{r+1}}{∏_{j=0}^{r} (z − t − j)}.  (80)

According to the recurrence (68), we have

(t + r + 1) b_{n} + (r + 1) a_{n+1} = b_{n+1}.  (81)

Taking the Z-Transform in both sides of (81) we get

(t + r + 1) Z (b_{n}) + (r + 1) z (Z (a_{n}) − r!) = z (Z (b_{n}) − (r + 1)!) .  (82)

That is, we have

(t + r + 1) Z (b_{n}) + (r + 1) z (\frac{r!z^{r+1}}{∏_{j=0}^{r} (z − t − j)} − r!) = z (Z (b_{n}) − (r + 1)!) ,  (83)

from where

Z (b_{n}) = \frac{(r + 1)!z^{r+2}}{∏_{j=0}^{r+1} (z − t − j)},  (84)

which means that b_{n} = (r + 1)! (t^{n} ∗ (t + 1)^{n} ∗ ⋯ ∗ (t + r)^{n} ∗ (t + r + 1)^{n}), as claimed.

An immediate corollary from Proposition 15 is the following identity, valid for any t ∈ ℕ and r, n = 0, 1, 2, …

∑_{i=1}^{n+r} \binom{t}{i − r}i!S (n + r, i) = r! (t^{n} ∗ (t + 1)^{n} ∗ ⋯ ∗ (t + r)^{n}) .  (85)

In Tables 9 and 10 we show some concrete examples.

7 Acknowledgments

I want to thank the referee for the careful reading of the work and the comments on a different perspective of some of the results related to p-arrays we presented here.

(p + t) -rows array

j-th column 1 ≤ j ≤ t Sequence (∑_{i=1}^{j} \binom{t}{j−i}i!S (n, i))_{n=1}^{∞}

t = 1  j = 1  (1, 1, 1, 1, …)
t = 2  j = 1  (1, 1, 1, 1, …)
j = 2  (2^{n}) = (2, 4, 8, 16, …)
t = 3 j = 1 (1, 1, 1, 1, …)
j = 2  (2^{n} + 1) = (3, 5, 9, 17, …)
j = 3  (3^{n}) = (3, 9, 27, 81, …)
t = 4 j = 1 (1, 1, 1, 1, …)
j = 2  (2^{n} + 2) = (4, 6, 10, 18, …)
j = 3  (1^{n} + 2^{n} + 3^{n}) = (6, 14, 36, 98, …)
j = 4  (4^{n}) = (4, 16, 64, 256, …)

Table 9: First t columns of the (p + t)-rows arrays.

(p + t) -rows array

(t + r) -th column Sequence (∑_{i=1}^{n+r} \binom{t}{i−r}i!S (n + r, i))_{n=0}^{∞}

t = 1 r = 1 1 ∗ 2^{n} = (1, 3, 7, 15, …)
r = 2  2 (1 ∗ 2^{n} ∗ 3^{n}) = (2, 12, 50, 180, …)
r = 3  6 (1 ∗ 2^{n} ∗ 3^{n} ∗ 4^{n}) = (6, 60, 390, 2100, …)
⋮  ⋮
t = 2  r = 1  2^{n} ∗ 3^{n} = (1, 5, 19, 65, …)
r = 2  2 (2^{n} ∗ 3^{n} ∗ 4^{n}) = (2, 18, 110, 570, …)
r = 3  6 (2^{n} ∗ 3^{n} ∗ 4^{n} ∗ 5^{n}) = (6, 84, 750, 5460, …)
⋮  ⋮
t = 3  r = 1  3^{n} ∗ 4^{n} = (1, 7, 37, 175, …)
r = 2  2 (3^{n} ∗ 4^{n} ∗ 5^{n}) = (2, 24, 194, 1320, …)
r = 3  6 (3^{n} ∗ 4^{n} ∗ 5^{n} ∗ 6^{n}) = (6, 108, 1230, 11340, …)
⋮ ⋮

Table 10: Columns t + 1, t + 2, … of the (p + t)-rows arrays.

References

[1] R. Bacher, Determinants of matrices related to the Pascal triangle, J. Théorie Nombres Bordeaux 14 (2002), 19–41.

[2] P. Barry, On integer-sequence-based constructions of generalized Pascal triangles, J. Integer Seq. 9 (2006). Article 06.2.4.

[3] A. T. Benjamin, The Lucas triangle recounted, Congressus Numerantium, Proceedings of the Twelfth Conference on Fibonacci Numbers and their Applications, (William Webb, ed.), 2010, pp. 169–177.

[4] B. A. Bondarenko, Generalized Pascal Triangles and Pyramids. Their Fractals, Graphs and Applications, Fibonacci Association, 1993.

[5] Y. Inaba, Hyper-Sums of Powers of Integers and the Akiyama-Tanigawa Matrix, J. Integer Seq. 8 (2005). Article 05.2.7.

[6] R. C. Johnson, Fibonacci numbers and matrices,. Preprint available at

http://www.dur.ac.uk/bob.johnson/fibonacci/.

[7] G. Kallós, The generalization of Pascal’s triangle from algebraic point of view, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae, 24 (1997), 11–18.

[8] B. C. Kellner, Identities between polynomials related to Stirling and Harmonic numbers.

Preprint available at http://arxiv.org/abs/1209.1018.

[9] B. C. Kellner, On quotients of Riemann zeta values at odd and even integer arguments.

Preprint available at http://arxiv.org/abs/1209.4329.

[10] B. C. Kellner, Personal communication.

[11] C. Krattenthaler, Evaluations of some determinants of matrices related to the Pascal

triangle. Preprint available at http://arxiv.org/abs/math/0111328.

[12] A. R. Moghaddamfar and S. M. H. Pooya, Generalized Pascal triangles and Toeplitz

matrices. Preprint available at http://arxiv.org/abs/0901.2597.
[13] OeisWiki, (a, b)-Pascal triangle. http://oeis.org/wiki/(a,b)-Pascal_triangle.
[14] OeisWiki, (a(n), b(n))-Pascal triangle. http://oeis.org/wiki/(a(n),b(n))-Pascal_triangle.
[15] OeisWiki, (1, 2)-Pascal triangle. http://oeis.org/wiki/Lucas_triangle.

[16] N. Robbins, The Lucas triangle revisited, Fibonacci Quart. 43 (2005), 142–148.

[17] V. Shevelev, On Stephan’s conjectures concerning Pascal triangle modulo 2 and their polynomial generalization. Preprint available at http://arxiv.org/abs/1011.6083.

[18] S. M. Tanny, On some numbers related to the Bell numbers, Canad. Math. Bull. 17 (1975), 733–738.

[19] Weisstein, Eric W. “Clark’s Triangle.” From MathWorld–A Wolfram Web Resource.

    Available at http://mathworld.wolfram.com/ClarksTriangle.html.

[20] Weisstein, Eric W. “Pascal’s Triangle.” From MathWorld–A Wolfram Web Resource.

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

[21] Weisstein, Eric W. ‘Z-Transform’, From MathWorld–A Wolfram Web Resource, avail-

    able at http://mathworld.wolfram.com/Z-Transform.html.

2010 Mathematics Subject Classification: Primary 11B99; Secondary 11B83. Keywords: Pascal’s triangle, Lucas triangle, Z-Transform.

(Concerned with sequences \underline{A000012}, \underline{A000027}, \underline{A000051}, \underline{A000217}, \underline{A000290}, \underline{A000292}, \underline{A000330}, \underline{A000537}, \underline{A000538}, \underline{A000578}, \underline{A000583}, \underline{A000670}, \underline{A001550}, \underline{A001551}, \underline{A001552}, \underline{A002415}, \underline{A003215}, \underline{A005408}, \underline{A005914}, \underline{A005917}, \underline{A008277}, \underline{A008588}, \underline{A024166}, \underline{A050946}, \underline{A101089}, and \underline{A101103}.)

Received February 25 2013; revised version received May 14 2013. Published in Journal of Integer Sequences, June 4 2013.

Return to Journal of Integer Sequences home page.