A Generalization of the Digital Binomial Theorem

Hieu D. Nguyen Department of Mathematics Rowan University Glassboro, NJ 08028 USA

                       nguyen@rowan.edu

Abstract We prove a generalization of the digital binomial theorem by constructing a oneparameter subgroup of generalized Sierpiński matrices. In addition, we derive new formulas for the coefficients of Prouhet-Thue-Morse polynomials and describe group relations satisfied by generating matrices defined in terms of these Sierpiński matrices.

1 Introduction

The classical binomial theorem describes the expansion of (x + y)^{N} in terms of binomial coefficients. More precisely, for any non-negative integer N, we have

(x + y)^{N} = ∑_{k=0}^{N} \binom{N}{k}x^{k}y^{N−k},  (1)

where the binomial coefficients \binom{N}{k} are defined in terms of factorials:

\binom{N}{k} = \frac{N!}{k!(N − k)!}.

The author [9] introduced a digital version of this theorem (based on Callan [3]) where the exponents appearing in (1) are viewed as sums of digits. To illustrate this, consider the binomial theorem for N = 2:

(x + y)^{2} = x^{2}y^{0} + x^{1}y^{1} + x^{1}y^{1} + x^{0}y^{2}.  (2)

It is easy to verify that (2) is equivalent to

(x + y)^{s(3)} = x^{s(3)}y^{s(0)} + x^{s(2)}y^{s(1)} + x^{s(1)}y^{s(2)} + x^{s(0)}y^{s(3)},  (3)

where s(k) denotes the sum of digits of k expressed in binary. For example,

s(3) = s(1 · 2^{1} + 1 · 2^{0}) = 2.

More generally, we have

Theorem 1 (digital binomial theorem [9]). Let n be a non-negative integer. Then

(x + y)^{s(n)} = ∑_{0≤m≤n (m,n−m) carry-free} x^{s(m)}y^{s(n−m)}.  (4)

Here, a pair of non-negative integers (j, k) is said to be carry-free if their addition involves no carries when performed in binary. For example, (8, 2) is carry-free since 8 + 2 = (1 · 2^{3} + 0 · 2^{2} + 0 · 2^{1} + 0 · 2^{0}) + 1 · 2^{1} = 10 involves no carries. It is clear that (j, k) is carry-free if and only if s(j) + s(k) = s(j + k) [2, 9]. Also, observe that if n = 2^{N} − 1, then (4) reduces to (1).

In this paper we generalize Theorem 1 to any base b ≥ 2. To state this result, we shall need to introduce a digital dominance partial order on ℕ as defined by Ball, Edgar, and Juda [2]. Let

n = n_{0}b^{0} + n_{1}b^{1} + ⋯ + n_{N−1}b^{N−1}

represent the base-b expansion of n and denote d_{b,i}(n) := n_{i} to be the i-th digit of n in base b. We shall say that m is digitally less than or equal to n if d_{b,i}(m) ≤ d_{b,i}(n) for all i = 0, 1, …, N − 1. In that case, we shall write m ⪯_{b} n. We are now ready to state our result.

Theorem 2. Let n be a non-negative integer. Then for any base b ≥ 2, we have

∏_{i=0}^{N−1} \binom{x + y + d_{b,i}(n) − 1}{d_{b,i}(n)} = ∑_{0≤m⪯_{b}n} ( ∏_{i=0}^{N−1} \binom{x + d_{b,i}(m) − 1}{d_{b,i}(m)} ∏_{i=0}^{N−1} \binom{y + d_{b,i}(n − m) − 1}{d_{b,i}(n − m)}) .

(5)

Let μ_{j}(n) := μ_{j}^{(b)}(n) denote the multiplicity of the digit j > 0 in the base-b expansion of n, i.e.,

μ_{j}(n) = |{i : d_{b,i}(n) = j}|.

As a corollary, we obtain Corollary 3. Let n be a non-negative integer. Then for any base b ≥ 2, we have

∏_{j=1}^{b−1} \binom{x + y + j − 1}{j}^{μ_{j}(n)} = ∑_{0≤m⪯_{b}n} (∏_{j=1}^{b−1} \binom{x + j − 1}{j}^{μ_{j}(m)} ∏_{j=1}^{b−1} \binom{y + j − 1}{j}^{μ_{j}(n−m)}) .

Observe that if b = 2, then Corollary 3 reduces to Theorem 1.

The source behind Theorem 1 is a one-parameter subgroup of Sierpiński matrices, investigated by Callan [3], which encodes the digital binomial theorem. To illustrate this, define a sequence of lower-triangular matrix functions S_{N}(x) of dimension 2^{N} × 2^{N} recursively by

S_{1}(x) = ( \begin{matrix}1 & 0 \\ x & 1 \end{matrix} ) , S_{N+1}(x) = S_{1}(x) ⊗ S_{N}(x),  (6)

where ⊗ denotes the Kronecker product of two matrices. For example, S_{2}(x) and S_{3}(x) can be computed as follows:

S_{2}(x) = S_{1}(x) ⊗ S_{1}(x) = ( \begin{matrix}1 · S_{1}(x) & 0 · S_{1}(x) \\ x · S_{1}(x) & 1 · S_{1}(x) \end{matrix} ) = ( \begin{matrix}1 & 0 & 0 & 0 \\ x & 1 & 0 & 0 \\ x & 0 & 1 & 0 \\ x^{2} & x & x & 1 \end{matrix} ) ,

S_{3}(x) = S_{1}(x) ⊗ S_{2}(x) = ( \begin{matrix}1 · S_{2}(x) & 0 · S_{2}(x) \\ x · S_{2}(x) & 1 · S_{2}(x) \end{matrix} ) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ x & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ x^{2} & x & x & 1 & 0 & 0 & 0 & 0 \\ x & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ x^{2} & x & 0 & 0 & x & 1 & 0 & 0 \\ x^{2} & 0 & x & 0 & x & 0 & 1 & 0 \\ x^{3} & x^{2} & x^{2} & x & x^{2} & x & x & 1 \end{matrix} ) .

Observe that when x = 1, the infinite matrix S = lim_{N→∞} S_{N}(1) contains Sierpiński’s triangle.

Callan [3] gives a formula for the entries of S_{N}(x) = (α_{N}(j, k, x)), 0 ≤ j, k ≤ 2^{N} − 1, in terms of the sum-of-digits function:

α_{N}(j, k, x) = \{ \begin{matrix}x^{s(j−k)}, & if 0 ≤ k ≤ j ≤ 2^{N} − 1 and (k, j − k) are carry-free; \\ 0, & otherwise. \end{matrix}  (7)

Moreover, Callan proved that S_{N}(x) forms a one-parameter subgroup of SL(2^{N}, ℝ), i.e., the group of 2^{N} × 2^{N} real matrices with determinant one. Namely, we have

S_{N}(x)S_{N}(y) = S_{N}(x + y).  (8)

If we denote the entries of S_{N}(x)S_{N}(y) by t_{N}(j, k), then the equality

t_{N}(j, k) = ∑_{i=0}^{2^{N} −1} α_{N}(j, i, x)α_{N}(i, k, y) = α_{N}(j, k, x + y)

corresponds precisely to Theorem 1 with j = 0 and k = 0. For example, if N = 2, then (8) becomes

( \begin{matrix}1 & 0 & 0 & 0 \\ x & 1 & 0 & 0 \\ x & 0 & 1 & 0 \\ x^{2} & x & x & 1 \end{matrix} ) ( \begin{matrix}1 & 0 & 0 & 0 \\ y & 1 & 0 & 0 \\ y & 0 & 1 & 0 \\ y^{2} & y & y & 1 \end{matrix} ) = ( \begin{matrix}1 & 0 & 0 & 0 \\ x + y & 1 & 0 & 0 \\ x + y & 0 & 1 & 0 \\ (x + y)^{2} & x + y & x + y & 1 \end{matrix} ) .

The rest of this paper is devoted to generalizing Callan’s construction of Sierpiński matrices to arbitrary bases and considering two applications of them. In Section 2, we use these generalized Sierpiński matrices to prove Theorem 2. In Section 3, we demonstrate how these matrices arise in the construction of Prouhet-Thue-Morse polynomials defined by the author [10]. In Section 4, we describe a group presentation in terms of generators defined through these matrices and show that these generators satisfy a relation that generalizes the three-strand braid relation found by Ferrand [4]. This relation suggests that Sierpiński matrices encode not only a digital binomial theorem but also an interesting group structure.

2 Sierpiński triangles

To prove Theorem 2, we consider the following generalization of the Sierpiński matrix S_{N}(x) in terms of binomial coefficients. Define lower-triangular matrices S_{b,N}(x) of dimension b^{N} × b^{N} recursively by

S_{b,1}(x) = ( \begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ \binom{x}{1} & 1 & 0 & ⋯ & 0 \\ \binom{x+1}{2} & \binom{x}{1} & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ \binom{x+b−2}{b−1} & \binom{x+b−3}{b−2} & \binom{x+b−4}{b−3} & ⋯ & 1 \end{matrix} ) = \{ \begin{matrix}\binom{x+j−k−1}{j−k}, & if 0 ≤ k ≤ j ≤ b − 1; \\ 0, & otherwise, \end{matrix}

and for N > 1,

S_{b,N+1}(x) = S_{b,1}(x) ⊗ S_{b,N}(x).

Example 4. To illustrate our generalized Sierpiński matrices, we calculate S_{3,1}(x) and S_{3,2}(x):

S_{3,1}(x) = ( \begin{matrix}1 & 0 & 0 \\ \binom{x}{1} & 1 & 0 \\ \binom{x+1}{2} & \binom{x}{1} & 1 \end{matrix} ) ,
S_{3,2}(x) = S_{3,1}(x) ⊗ S_{3,1}(x)

= ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \binom{x}{1} & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \binom{x+1}{2} & \binom{x}{1} & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \binom{x}{1} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \binom{x}{1}\binom{x}{1} & \binom{x}{1} & 0 & \binom{x}{1} & 1 & 0 & 0 & 0 & 0 \\ \binom{x}{1}\binom{x+1}{2} & \binom{x}{1}\binom{x}{1} & \binom{x}{1} & \binom{x+1}{2} & \binom{x}{1} & 1 & 0 & 0 & 0 \\ \binom{x+1}{2} & 0 & 0 & \binom{x}{1} & 0 & 0 & 1 & 0 & 0 \\ \binom{x+1}{2}\binom{x}{1} & \binom{x+1}{2} & 0 & \binom{x}{1}\binom{x}{1} & \binom{x}{1} & 0 & \binom{x}{1} & 1 & 0 \\ \binom{x+1}{2}\binom{x+1}{2} & \binom{x+1}{2}\binom{x}{1} & \binom{x+1}{2} & \binom{x}{1}\binom{x+1}{2} & \binom{x}{1}\binom{x}{1} & \binom{x}{1} & \binom{x+1}{2} & \binom{x}{1} & 1 \end{matrix} ) .

We now generalize Callan’s result for S_{N}(x) by presenting a formula for the entries of S_{b,N}(x); see [7] for a similar generalization but along a different vein.

Theorem 5. Let α_{N}(j, k) := α_{N}(j, k, x) denote the (j, k)-entry of S_{b,N}(x). Then

α_{N}(j, k) = \{ \begin{matrix}\binom{x+d_{0}−1}{d_{0}}\binom{x+d_{1}−1}{d_{1}} ⋯ \binom{x+d_{N−1}−1}{d_{N−1}}, & if 0 ≤ k ≤ j ≤ b^{N} − 1 and k ⪯_{b} j; \\ 0, & otherwise, \end{matrix} (9)

where j − k = d_{0}b^{0} + d_{1}b^{1} + … + d_{N−1}b^{N−1} is the base-b expansion of j − k, assuming j ≥ k.

Proof. We argue by induction on N. It is clear that (9) holds for S_{b,1}(x). Next, assume that (9) holds for S_{b,N}(x) and let α_{N+1}(j, k) be an arbitrary entry of S_{b,N+1}(x), where pb^{N} ≤ j ≤ (p+1)b^{N} −1 and qb^{N} ≤ k ≤ (q+1)b^{N} −1 for some non-negative integers p, q ∈ {0, 1, …, b−1}. Set j′ = j − pb^{N} and k′ = k − qb^{N}. We consider two cases:

Case 1. p < q. Then j < k and α_{N+1}(j, k) = 0 · α_{N}(j′, k′) = 0.

Case 2. p ≥ q. Then j ≥ k and

α_{N+1}(j, k) = \binom{x + p − q − 1}{p − q}α_{N}(j′, k′).  (10)

Let j − k = d_{0}b^{0} + d_{1}b^{1} + ⋯ + d_{N}b^{N}, where d_{N} = p − q. Then j′ − k′ = d_{0}b^{0} + d_{1}b^{1} + ⋯ + d_{N−1}b^{N−1}. By assumption,

α_{N}(j′, k′) = \{ \begin{matrix}\binom{x+d_{0}−1}{d_{0}}\binom{x+d_{1}−1}{d_{1}} ⋯ \binom{x+d_{N−1}−1}{d_{N−1}} & if 0 ≤ k′ ≤ j′ ≤ b^{N} − 1 and k′ ⪯_{b} j′; \\ 0 & otherwise. \end{matrix} (11)

Since k ⪯_{b} j if and only if k′ ⪯_{b} j′, it follows from (10) and (11) that

α_{N+1}(j, k) = \{ \begin{matrix}\binom{x+d_{0}−1}{d_{0}}\binom{x+d_{1}−1}{d_{1}} ⋯ \binom{x+d_{N} −1}{d_{N}} & if 0 ≤ k ≤ j ≤ b^{N+1} − 1 and k ⪯_{b} j; \\ 0 & otherwise. \end{matrix} (12)

Thus, (9) holds for S_{b,N+1}.

Next, we show that S_{b,N}(x) forms a one-parameter subgroup of SL(b^{N}, ℝ). To prove this, we shall need the following two lemmas; the first is due to Gould [6] and the second follows easily from the first through an appropriate change of variables.

Lemma 6 (Gould [6]).

∑_{k=0}^{n} \binom{x + k}{k}\binom{y + n − k}{n − k} = \binom{x + y + n + 1}{n}.  (13)

Proof. Gould [6] derives (13) as a special case of a generalization of Vandemonde’s convolution formula. We shall prove (13) more directly using a combinatorial argument. Let A, B, and C = {0, 1, …, n} denote three sets containing x, y, and n + 1 elements (all distinct), respectively, where n is a positive integer. For any non-negative integer k, define A_{k} = A ∪ {0, …, k − 1} and B_{k} = B ∪ {k + 1, …, n}. Then given any n-element subset S of A ∪ B ∪ C, there exists a unique integer k_{S} in C − S, called the index of S with respect to A and B, such that |S ∩ A_{k_{S}}| = k_{S} and |S ∩ B_{k_{S}}| = n − k_{S}. To see this, define S_{A} = A ∩ S, S_{B} = B ∩ S, and T = C − S. We begin by deleting |S_{A}| consecutive elements from T, in increasing order and beginning with its smallest element, to obtain a subset T′. We then delete |S_{B}| consecutive elements from T′, in decreasing order and beginning with its largest element, to obtain a subset T′′, which must now contain a single element denoted by k_{S}. It is now clear that |S ∩ A_{k_{S}}| = k_{S} and |S ∩ B_{k_{S}}| = n − k_{S}.

To prove (13), we count the n-element subsets S of A∪B∪C in two different ways. On the one hand, since |A∪B ∪C| = x+y +n+1, the number of such subsets is given by \binom{x+y+n+1}{n}. On the other hand, we partition all such n-element subsets into equivalence classes according to each subset’s index value. Since |S ∩ A_{k}| = k and |S ∩ B_{k}| = n − k, it follows that the number of n-element subsets S having the same index k is given by \binom{x+k}{k}\binom{y+n−k}{n−k} and total number of n-element subsets is given by

∑_{k=0}^{n} \binom{x + k}{k}\binom{y + n − k}{n − k}.

Lastly, we equate the two answers to obtain (13).

Lemma 7. Let p and q be positive integers with q ≤ p. Then

∑_{v=q}^{p} \binom{x + p − v − 1}{p − v}\binom{y + v − q − 1}{v − q} = \binom{x + y + p − q − 1}{p − q}.  (14)

Proof. Set k = v − q and n = p − q. Then (14) can be rewritten as

∑_{w=0}^{p−q} \binom{x + p − q − w − 1}{p − q − w}\binom{y + w − 1}{w} = \binom{x + y + p − q − 1}{p − q},

which follows from Lemma 6.

Theorem 8. For all N ∈ ℕ,

S_{b,N}(x)S_{b,N}(y) = S_{b,N}(x + y).  (15)

Proof. We argue by induction on N. Lemma 6 proves that (15) holds for S_{b,1}(x). Next, assume that (15) holds for S_{b,N}(x). Let t_{N+1}(j, k) denote the (j, k)-entry of S_{b,N+1}(x)S_{b,N+1}(y). Then

t_{N+1}(j, k) = ∑_{m=0}^{b^{N+1}−1} α_{N+1}(j, m, x)α_{N+1}(m, k, y)

= ∑_{v=0}^{b−1} ∑_{r=0}^{b^{N} −1} α_{N+1}(j, vb^{N} + r, x)α_{N+1}(vb^{N} + r, k, y).

As before, assume pb^{N} ≤ j ≤ (p+1)b^{N} −1 and qb^{N} ≤ k ≤ (q+1)b^{N} −1 for some non-negative integers p, q ∈ {0, 1, …, b − 1}. Set j′ = j − pb^{N} and k′ = k − qb^{N}. Again, we consider two cases:

Case 1: j < k. Then α_{N+1}(j, k, x + y) = 0 by definition. On the other hand, we have

t_{N+1}(j, k) = ∑_{m=0}^{j} α_{N+1}(j, m, x)α_{N+1}(m, k, y) + ∑_{m=j+1}^{b^{N+1}−1} α_{N+1}(j, m, x)α_{N+1}(m, k, y)

= ∑_{m=0}^{j} α_{N+1}(j, m, x) · 0 + ∑_{m=j+1}^{b^{N+1}−1} 0 · α_{N+1}(m, k, y)

= 0

and thus (15) holds.

Case 2: j ≥ k. Since S_{b,N+1}(x) = S_{b,1}(x) ⊗ S_{b,N}(x), we have

α_{N+1}(j, vb^{N} + r, x) = \{ \begin{matrix}\binom{x+p−v−1}{p−v}α_{N}(j′, r, x) & if j ≥ vb^{N} + r; \\ 0 & if j < vb^{N} + r. \end{matrix}

Similarly, we have

α_{N+1}(vb^{N} + r, k, y) = \{ \begin{matrix}\binom{y+v−q−1}{v−q}α_{N}(r, k′, y) & if k ≤ vb^{N} + r; \\ 0 & if k > vb^{N} + r. \end{matrix}

It follows that

t_{N+1}(j, k) = ∑_{v=q}^{p} ∑_{r=0}^{b^{N} −1} \binom{x + p − v − 1}{p − v}\binom{y + v − q − 1}{v − q}α_{N}(j′, r, x)α_{N}(r, k′, y)

= (∑_{v=q}^{p} \binom{x + p − v − 1}{p − v}\binom{y + v − q − 1}{v − q}) ∑_{r=0}^{b^{N} −1} α_{N}(j′, r, x)α_{N}(r, k′, y)

= \binom{x + y + p − q − 1}{p − q}α_{N}(j′, k′, x + y)

= α_{N+1}(j, k, x + y),

where we have made use of the inductive assumption and Lemma 7. This proves that (15) holds.

As a corollary, we obtain Theorem 2, which we now prove.

Proof of Theorem 2. Let j = n and k = 0. Then the identity

∑_{m=0}^{b^{N} −1} α_{N}(j, m, x)α_{N}(m, k, y) = α_{N}(j, k, x + y),

which follows from (15), is equivalent to (5).

We end this section by describing the infinitesimal generator of S_{b,N}(x). Define X_{b,1}(x) = (χ_{j,k}) to be a strictly lower-triangular matrix whose entries χ_{j,k} are given by

χ_{j,k} = \{ \begin{matrix}x/(j − k), & if j ≥ k + 1; \\ 0, & otherwise. \end{matrix}  (16)

For N > 1, we define matrices

X_{b,N+1}(x) = X_{b,1}(x) ⊕ X_{b,N}(x) = X_{b,1}(x) ⊗ I_{b^{N}} + I_{b} ⊗ X_{b,N}(x),

where ⊕ denotes the Kronecker sum and I_{b^{N}} denotes the b^{N} × b^{N} identity matrix. Observe that X_{b,1}(x) has the following matrix form:

X_{b,1}(x) = ( \begin{matrix}0 & 0 & 0 & ⋯ & 0 \\ x & 0 & 0 & ⋯ & 0 \\ x/2 & x & 0 & ⋯ & 0 \\ x/3 & x/2 & x & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ x/(b − 1) & x/(b − 2) & x/(b − 3) & ⋯ & 0 \end{matrix} )  (17)

The following lemmas will be needed. The first states a useful identity involving the unsigned Stirling numbers of the first kind, c(n, k), defined by the generating function

x(x + 1)...(x + n − 1) = ∑_{k=0}^{n} c(n, k)x^{k}.

It is well known that c(n, k) counts the number of n-element permutations consisting of k cycles.

Lemma 9. Let l and n be positive integers with l ≥ n. Then

∑_{i=1}^{l−n+1}(i − 1)!\binom{l}{i}c(l − i, n − 1) = nc(l, n).  (18)

Proof. We give a combinatorial argument. Let A = {1, 2, ..., l}. We count in two different ways the number of permutations π = σ_{1}σ_{2} ⋯ σ_{n} of A consisting of n cycles where we distinguish one of the cycles σ_{j} of π. On the one hand, since there are c(l, n) such permutations π and n ways to distinguish a cycle of π, it follows that the answer is given by nc(l, n). On the other hand, we can construct π by first choosing our distinguished cycle σ_{1} consisting of i elements. The number of possibilities for σ_{1} is \binom{l}{i}(i − 1)! since there are \binom{l}{i} ways to choose i elements from A and (i − 1)! ways to construct a cycle from these i elements. It remains to construct the remaining cycles σ_{2}, …, σ_{n}, which we view as a permutation π′ = σ_{2} ⋯ σ_{n} on l − i elements consisting of n − 1 cycles. Since there are c(l − i, n − 1) such possibilities for π′, it follows that the number of permutations π with a distinguished cycle is given by

∑_{i=1}^{l−n+1}(i − 1)!\binom{l}{i}c(l − i, n − 1).

Equating the two answers yields (18) as desired.

Lemma 10. Let n be a positive integer with 1 ≤ n ≤ b − 1. Then

X_{b,1}^{n}(x) = (χ_{n}(j, k)),  (19)

where the entries χ_{n}(j, k) are given by

χ_{n}(j, k) = \{ \begin{matrix}\frac{n!}{(j−k)!}c(j − k, n)x^{n}, & if j ≥ k + n; \\ 0, & otherwise. \end{matrix}  (20)

Proof. We argue by induction on n. It is clear that (20) holds when n = 1. Suppose n > 1. If j < k + n, then χ_{n}(j, k) = 0 because X_{b,1}^{m} is a power of strictly lower-triangular matrices.

Therefore, assume j ≥ k + n. Then

χ_{n}(j, k) = ∑_{i=0}^{b−1} χ_{n−1}(j, i)χ_{1}(i, k) = ∑_{i=k+1}^{j−n+1} χ_{n−1}(j, i)χ_{1}(i, k)

= x^{n} ∑_{i=k+1}^{j−n+1} \frac{(n − 1)!}{(j − i)!}c(j − i, n − 1)\frac{1}{i − k}

= x^{n} ∑_{i=k+1}^{l+k−n+1} \frac{(n − 1)!}{(l + k − i)!}c(l + k − i, n − 1)\frac{1}{i − k}

= \frac{(n − 1)!x^{n}}{l!} ∑_{m=1}^{l−m} \frac{l!}{m(l − m)!}c(l − m, n − 1)

= \frac{(n − 1)!x^{n}}{l!} ∑_{m=1}^{l−n+1}(m − 1)!\binom{l}{m}c(l − m, n − 1),

where l = j − k and m = i − k. It follows from Lemma 9 that

χ_{n}(j, k) = \frac{(n − 1)!x^{n}}{l!} · nc(l, n) = \frac{n!}{(j − k)!}c(j − k, n)x^{n}

as desired.

Lemma 11. We have

exp(X_{b,1}(x)) = S_{b,1}(x).  (21)

Proof. Denote the entries of exp(X_{b,1}(x)) by ξ(j, k). It is clear that ξ(j, k) = 0 for j < k and ξ(j, k) = 1 for j = k since X_{b,1} is strictly lower triangular. Therefore, assume j ≥ k + 1. Since X_{b,1}^{n} = 0 for n ≥ b, we have

ξ(j, k) = ∑_{n=1}^{b−1} \frac{χ_{n}(j, k)}{n!}

= \frac{1}{(j − k)!} ∑_{n=1}^{b−1} c(j − k, n)x^{n}

= \frac{x(x + 1) ⋯ (x + j − k − 1)}{(j − k)!}

= \binom{x + j − k − 1}{j − k}

= α_{1}(j, k).

Thus, (21) holds.

Theorem 12. Let N be a positive integer. Then

exp(X_{b,N}(x)) = S_{b,N}(x).  (22)

Proof. We argue by induction on N. Lemma 11 shows that (22) is true for N = 1. Then since exp(A ⊕ B) = exp(A) ⊗ exp(B) for any two matrices A and B, it follows that

exp(X_{b,N}(x)) = exp(X_{b,1}(x) ⊕ X_{b,N−1}(x)) = S_{b,1}(x) ⊗ S_{b,N−1}(x) = S_{b,N}(x),

which proves (22).

3 Prouhet-Thue-Morse polynomials

In this section we demonstrate how the generalized Sierpiński matrices S_{b,N}(1) arise in the study of Prouhet-Thue-Morse polynomials, first investigated by the author [10]. These polynomials were used in the same paper to give a new proof of the well-known Prouhet-Tarry-Escott problem, which seeks b ≥ 2 sets of non-negative integers S_{0}, S_{1}, …, S_{b−1} that have equal sums of like powers up to degree M ≥ 1, i.e.,

∑_{n∈S_{0}} n^{m} = ∑_{n∈S_{1}} n^{m} = ⋯ = ∑_{n∈S_{b−1}} n^{m}

for all m = 0, 1, …, M. In 1851, E. Prouhet [11] gave a solution (but did not publish a proof; see Lehmer [8] for a proof) by partitioning the first b^{M+1} non-negative integers into the sets S_{0}, S_{1}, …, S_{b−1} according to the assignment

n ∈ S_{u_{b}(n)}.

Here, u_{b}(n) is the generalized Prouhet-Thue-Morse sequence A010060, defined as the residue of the sum of digits of n (base b):

u_{b}(n) = ∑_{j=0}^{d} n_{j} mod b,

where n = n_{0}d^{0} + ⋯ + n_{d}b^{d} is the base-b expansion of n. When b = 2, u(n) := u_{2}(n) generates the classical Prouhet-Thue-Morse sequence: 0, 1, 1, 0, 1, 0, 0, 1, . . ..

Let A = (a_{0}, a_{1}, …, a_{b−1}) be a zero-sum vector, i.e., an ordered collection of b arbitrary complex values that sum to zero:

a_{0} + a_{1} + ⋯ + a_{b−1} = 0.

We define F_{N}(x; A) to be the Prouhet-Thue-Morse (PTM) polynomial of degree b^{N} −1 whose coefficients belong to A and repeat according to u_{b}(n), i.e.,

F_{N}(x; A) = ∑_{n=0}^{b^{N} −1} a_{u_{b}(n)}x^{n}.  (23)

In the case where b = 2, a_{0} = 1, and a_{1} = −1, we obtain the classic product generating function formula

∏_{m=0}^{N}(1 − x^{2^{m}}) = ∑_{n=0}^{2^{N+1}−1}(−1)^{u(n)}x^{n}.  (24)

Lehmer generalized this formula to the case where A = (1, ω, ω^{2}, …, ω^{b−1}) consists of all b-th roots of unity with ω = e^{i2π/b}. The following theorem, proven by the author [10], extends this factorization to F_{N}(x; A) for arbitrary zero-sum vectors.

Theorem 13 ([10]). Let N be a positive integer and A a zero-sum vector. There exists a polynomial P_{N}(x) such that

F_{N}(x; A) = P_{N}(x) ∏_{m=0}^{N−1}(1 − x^{b^{m}}).  (25)

Theorem 13 is useful in that it allows us to establish that the polynomial F_{N}(x, A) has a zero of order N at x = 1, from which Prouhet’s solution follows easily by setting N = M + 1 and differentiating F_{N}(x; A) m times [10].

We now derive formulas for the coefficients of P_{N}(x) in terms of generalized Sierpiński triangles. Towards this end, let

P_{N}(x; c_{N}) = ∑_{n=0}^{b^{N} −1} c_{n}x^{n}

denote a polynomial whose coefficients are given by the column vector c_{N} = (c_{0}, ..., c_{b^{N} −1})^{T}. Also, let

a_{n} = (a_{u_{b}(0)}, a_{u_{b}(1)}, …, a_{u_{b}(b^{N} −1)})^{T}

be a column vector consisting of elements of A generated by the PTM sequence u_{b}(n). Next, define a sequence of b^{N} × b^{N} matrices M_{N} recursively as follows. Set

M_{1} = (m_{j,k}) = ( \begin{matrix}1 & 0 & 0 & ⋯ & 0 & 0 \\ −1 & 1 & 0 & ⋯ & 0 & 0 \\ . & . & . \\ 0 & 0 & 0 & ⋯ & −1 & 1 \end{matrix} )

where

m_{j,k} = \begin{cases}1, & if j = k; \\ −1, & if j − k = 1; \\ 0, & otherwise. \end{cases}

Then for N > 1, define

M_{N+1} = M_{1} ⊗ M_{N} = ( \begin{matrix}M_{N} & 0_{N} & 0_{N} & ⋯ & 0_{N} & 0_{N} \\ −M_{N} & M_{N} & 0 & ⋯ & 0_{N} & 0_{N} \\ . & . & . \\ 0_{N} & 0_{N} & 0_{N} & ⋯ & −M_{N} & M_{N} \end{matrix} ) ,  (26)

where M_{1} ⊗ M_{N} denotes the Kronecker product. The following theorem establishes a matrix relationship between the vectors a_{N} and c_{N}.

Theorem 14. Let A = (a_{0}, …, a_{b−1}) be a zero-sum vector. The polynomial equation

F_{N}(x; A) = P_{N}(x; c_{N}) ∏_{m=0}^{N−1}(1 − x^{b^{m}})  (27)

is equivalent to the matrix equation

a_{N} = M_{N}c_{N}  (28)

together with the condition c_{n} = 0 for any n that contains the digit b − 1 in its base-b expansion, where 0 ≤ n ≤ b^{N} − 1.

To prove Theorem 14, we shall need the following two lemmas, which we state without proof since their results are easy to verify.

Lemma 15. Let A = (a_{0}, a_{1}, …, a_{b−1}) and c_{1} = (c_{0}, …, c_{b−1})^{T}. Then the polynomial equation

∑_{n=0}^{b−1} a_{n}x^{n} = (∑_{n=0}^{b−1} c_{n}x^{n}) (1 − x)

is equivalent to the system of equations

a_{0} = c_{0}
a_{1} = −c_{0} + c_{1}
⋮
a_{b−1} = −c_{b−2} + c_{b−1}

together with the condition c_{b−1} = 0.

Lemma 16. The system of equations in Lemma 15 can be expressed in matrix form as

a_{1} = M_{1}c_{1}.

Proof of Theorem 14. We argue by induction on N. It is clear that (28) holds for N = 1 since the polynomial equation F_{1}(x; A) = P_{1}(x; c_{1})(1−x) is equivalent to a_{1} = M_{1}c_{1} because of Lemmas 15 and 16. Next, assume that (28) holds for case N. We shall prove that (28) holds for case N + 1. Define

P_{N}(x; C_{N}(p)) = ∑_{n=0}^{b^{N} −1} c_{n+pb^{N}} x^{n+pb^{N}}

to be a polynomial whose coefficients are given by the entries of C_{N}(p) = (c_{pb^{N}} , …, c_{(p+1)b^{N} −1}), i.e., those elements in c_{N+1} from position pb^{N} to position (p + 1)b^{N}, so that

P_{N+1}(x; c_{N+1}) = P_{N−1}(x; C_{N}(0)) + ⋯ + P_{N−1}N(x; C_{N}(b − 1)).

We then expand the right-hand side of (25) for case N + 1 as follows:

F_{N+1}(x; A) = (P_{N}(x; C_{N}(0)) + ⋯ + P_{N}(x; C_{N}(b − 1))) ( ∏_{m=0}^{N−1}(1 − x^{b^{m}})) (1 − x^{b^{N}})
= (Q_{N}(x; C_{N}(0)) + ⋯ + Q_{N}(x; C_{N}(b − 1))) (1 − x^{b^{N}})
= Q_{N}(x; C_{N}(0)) + (Q_{N}(x; C_{N}(1)) − x^{b^{N}} Q_{N}(x; C_{N}(0))) + ⋯ +
(Q_{N}(x; C_{N}(b − 1)) − x^{b^{N}} Q_{N}(x; C_{N}(b − 2))) − x^{b^{N}} Q_{N}(x; C_{N}(b − 1)),

where we define

Q_{N}(x; C_{N}(p)) = P_{N}(x; C_{N}(p)) ∏_{m=0}^{N−1}(1 − x^{b^{m}}).

Next, we equate this result with the definition of F_{N+1}(x; A):

F_{N+1}(x; A) = ∑_{n=0}^{b^{N+1}−1} a_{u_{b}(n)}x^{n} = F_{N}(x; A_{N}(0)) + ⋯ + F_{N}(x; A_{N}(b − 1)),

where we define

F_{N}(x; A_{N}(p)) = ∑_{n=0}^{b^{N} −1} a_{u(n+pb^{N})}x^{n+pb^{N}} .

This leads to the system of polynomial equations

F_{N}(x; A_{N}(0)) = Q_{N}(x; C_{N}(0))
F_{N}(x; A_{N}(1)) = Q_{N}(x; C_{N}(1)) − x^{b^{N}} Q_{N}(x; C_{N}(0))
⋮
F_{N}(x; A_{N}(b − 1)) = Q_{N}(x; C_{N}(b − 1)) − x^{b^{N}} Q_{N}(x; C_{N}(b − 2))

together with the condition Q_{N}(x; C_{N}(b−1)) = 0, i.e. c_{n} = 0 for all (b−1)b^{N} ≤ n ≤ b^{N+1}−1. It follows from Lemmas 15 and 16 that this system is equivalent to the system of matrix equations

a_{N}(0) = M_{N}c_{N}(0)
a_{N}(1) = −M_{N}c_{N}(0) + M_{N}c_{N}(1)
⋮
a_{N}(b − 1) = −M_{N}c_{N}(b − 2) + M_{N}c_{N}(b − 1),

where the first matrix equation by assumption satisfies the condition c_{n} = 0 for any 0 ≤ n ≤ b^{N} − 1 that contains the digit b − 1 in its base-b expansion. This in turn is equivalent to the matrix equation a_{N+1} = M_{N+1}c_{N+1} together with the condition that c_{n} = 0 for any 0 ≤ n ≤ b^{N+1} − 1 that contains the digit b − 1 in its base-b expansion. This establishes the theorem for case N + 1 and completes the proof.

Lemma 17. The matrix M_{N} has inverse S_{N} = M_{N}^{−1}, where S_{N} is given recursively by

S_{1} = ( \begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ 1 & 1 & 0 & ⋯ & 0 \\ . & . & . \\ 1 & 1 & 1 & ⋯ & 1 \end{matrix} )  (29)

and for N > 1,

S_{N+1} = S_{1} ⊗ S_{N} = ( \begin{matrix}S_{N} & 0_{N} & 0_{N} & … & 0_{N} \\ S_{N} & S_{N} & 0_{N} & … & 0_{N} \\ . & . & . \\ S_{N} & S_{N} & S_{N} & … & S_{N} \end{matrix} ) .  (30)

Thus, if a_{N} = M_{N}c_{N}, then

c_{N} = S_{N}a_{N}.  (31)

Proof. It is straightforward to verify directly that S_{1} = M_{1}^{−1}. Since S_{N+1} = S_{1} ⊗ S_{N} and M_{N+1} = M_{1} ⊗ M_{N}, it follows that S_{N} = M_{N}^{−1}.

Observe that S_{N} = S_{b,N}(1) is the generalized Sierpiński triangle defined in the previous section. We now present a formula for the coefficients c_{n} in terms of the elements of A.

Theorem 18. Let A = (a_{0}, …, a_{b−1}) be a zero-sum vector. Then the polynomial equation (27) has solution P_{N}(x; C_{N}) whose coefficients c_{n}, 0 ≤ n ≤ b^{N} − 1, are given by

c_{n} = ∑_{k∈I_{b}(n)} a_{u_{b}(k)},  (32)

where I_{b}(n) = {k ∈ ℕ : k ⪯_{b} n}. Moreover, c_{n} = 0 for all n whose base-b expansion contains the digit b − 1.

Proof. From Theorem 5, we know that the non-zero entries in the n-th row of S_{N}, which are all equal to 1, are located at (n, k) where k ⪯_{b} n. Formula (32) now follows from (31). It remains to show that (32) yields c_{n} = 0 for all n whose base-b expansion contains the digit b − 1. Let n = n_{0}b^{0} + ⋯ + n_{L}b^{L} + ⋯ + n_{N−1}b^{N−1} where n_{L} = b − 1. Denote I_{b}(n; L) to be the subset of I_{b}(n) consisting of integers whose base-b expansion has digit 0 at position L, i.e.,

I_{b}(n; L) = {k ∈ ℕ : k ⪯_{b} n, k = k_{0}b^{0} + ⋯ + k_{N}b^{N}, k_{L} = 0}.

Then using the fact that A is a zero-sum vector, i.e., a_{0} + ⋯ + a_{b−1} = 0, we have

c_{n} = ∑_{k∈I_{b}(n;L)} a_{u_{b}(k)} + ∑_{k∈I_{b}(n;L)} a_{u_{b}(k+b^{L})} + ⋯ + ∑_{k∈I_{b}(n;L)} a_{u_{b}(k+(b−1)b^{L}))}

= ∑_{k∈I_{b}(n;L)} (a_{u_{b}(k)} + a_{(u_{b}(k)+1)_{b}} + ⋯ + a_{(u_{b}(k)+(b−1))_{b}})

= 0

as desired.

Next, we specialize Theorem 18 to base b = 3. Define w(n) to be the sum of the digits of n in its base-3 representation modulo 2.

Corollary 19. Suppose b = 3. Let n ∈ ℕ be such that its base-3 representation does not contain the digit 2. Then

c_{n} = (−1)^{w(n)}a_{u_{3}(2n)}.  (33)

Proof. Let n = n_{0}3^{0} + ⋯ + n_{N−1}3^{N−1} be the base-3 representation of n with no digit equal to 2 and leading digit n_{N−1} = 1. We argue by induction on N. It is clear that (33) holds when N = 1 since from (32) we have

c_{1} = a_{0} + a_{1} = −a_{2} = (−1)^{w(n)}a_{u_{3}(2n)}.

Next, assume (33) holds for a given N. To prove that (33) holds for N + 1, we consider two cases by decomposing n = n′ + 3^{N}.

Case 1: n_{i} = 0 for all i = 0, …, N − 1. Then n = 3^{n} and

c_{n} = ∑_{k∈I_{3}(n)} a_{u_{3}(k)} = a_{u_{3}(0)} + a_{u_{3}(n)} = a_{0} + a_{1} = −a_{2}
= (−1)^{w(n)}a_{u_{3}(2n)}.

Case 2: n_{L} = 1 for some 0 ≤ L ≤ N − 1. Then set n′′ = n′ − 3^{L}. It follows that

c_{n} = ∑_{k∈I_{3}(n)} a_{u_{3}(k)} = ∑_{k∈I_{3}(n,L)} a_{u_{3}(k)} + ∑_{k∈I_{3}(n,L)} a_{u_{3}(k+3^{N})}

= ∑_{k∈I_{3}(n′)} a_{u_{3}(k)} + ∑_{k∈I_{3}(n′)} a_{u_{3}(k+3^{L})}

= ∑_{k∈I_{3}(n′)} a_{u_{3}(k)} + ∑_{k∈I_{3}(n′,L)} a_{u_{3}(k+3^{L})} + ∑_{k∈I_{3}(n′,L)} a_{u_{3}(k+2·3^{L})} + ∑_{k∈I_{3}(n′,L)} a_{u_{3}(k)} − ∑_{k∈I_{3}(n′,L)} a_{u_{3}(k)}

= ∑_{k∈I_{3}(n′)} a_{u_{3}(k)} + ∑_{k∈I_{3}(n′,L)} (a_{u_{3}(k)} + a_{(u_{3}(k)+1)_{3}} + a_{(u_{3}(k)+2)_{3}}) − ∑_{k∈I_{3}(n′′)} a_{u_{3}(k)}

= (−1)^{w(n′)}a_{u_{3}(2n′)} − (−1)^{w(n′′)}a_{u_{3}(2n′′)}

= (−1)^{w(n′)}a_{u_{3}(2n′)} + (−1)^{w(n′′+3^{L})}a_{u_{3}(2(n′−3^{L}))}

= (−1)^{w(n′)} (a_{u_{3}(2n′)} + a_{(u_{3}(2n′)−2)_{3}}) = (−1)^{w(n′)} (−a_{(u_{3}(2n′)−1)_{3}})

= (−1)^{w(n′+3^{N})}a_{(u_{3}(2n′)+2)_{3}))} = (−1)^{w(n)}a_{u_{3}(2n′+2·3^{L})}

= (−1)^{w(n)}a_{u_{3}(2n)}.

Thus, (33) holds for N + 1.

4 Group generators and relations

In this section, we reveal further evidence of the rich structure of Sierpiński matrices by describing group generators and relations defined by the matrices S_{N} and M_{N}. Recall that S_{N} and M_{N} are matrices of dimension b^{N} × b^{N} for a given base b. Define T_{N} = M_{N}^{t} to be the transpose of M_{N} and U_{N} = S_{N}T_{N}, V_{N} = T_{N}S_{N}. The following lemma gives a recursive construction of U_{N} andV_{N}.

Lemma 20. We have

U_{N+1} = U_{1} ⊗ U_{N}
V_{N+1} = V_{1} ⊗ V_{N}

Proof. The result follows from the mixed-product property of the Kronecker product. We demonstrate this for U_{N+1}:

U_{N+1} = S_{N+1}T_{N+1} = (S_{1} ⊗ S_{N})(T_{1} ⊗ T_{N}) = (S_{1}T_{1}) ⊗ (S_{N}T_{N}) = U_{1} ⊗ U_{N}.

The calculation is the same for V_{N+1}.

Observe that U_{N} = (u_{i,j}) and V_{N} = (v_{i,j}) are skew-triangular and that V_{N} is the skewtranspose of U_{N}, i.e., v_{i,j} = u_{b−1−j,b−1−i} for i, j = 0, 1, …, b − 1. Here are some examples of U_{N} and V_{N} when b = 2:

U_{1} = ( \begin{matrix}1 & −1 \\ 1 & 0 \end{matrix} ) , U_{2} = ( \begin{matrix}1 & −1 & −1 & 1 \\ 1 & 0 & −1 & 0 \\ 1 & −1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix} ) ,

V_{1} = ( \begin{matrix}0 & −1 \\ 1 & 1 \end{matrix} ) , V_{2} = ( \begin{matrix}0 & 0 & 0 & 1 \\ 0 & 0 & −1 & −1 \\ 0 & −1 & 0 & −1 \\ 1 & 1 & 1 & 1 \end{matrix} ) .

The next lemma establishes that the eigenvalues of U_{N} and V_{N} are (b + 1)-th roots of 1 or −1.

Lemma 21. The set of eigenvalues of U_{1} and V_{1} are exactly the same and consist of all roots of the polynomial equation

−1 + r − r^{2} + ⋯ + (−1)^{b+1}r^{b} = 0.

Proof. Let r be a root of −1 + r − r^{2} + ⋯ + (−1)^{b+1}r^{b} = 0. We claim that r is an eigenvalue of U_{1} with eigenvector v = (v_{1}, …, v_{b})^{T}, where

v_{k} = ∑_{j=1}^{k}(−1)^{j+1}r^{j}

for k = 1, …, b. Observe that v_{b} = 1. Denote w = (U_{1} − rI_{b})v = (w_{1}, …, w_{b})^{T}. It suffices to show w = 0. It is straightforward to verify that

U_{1} = (u_{j,k}) = \begin{cases}1, & if k = 1; \\ −1, & if k = j + 1; \\ 0, & otherwise. \end{cases}

We now calculate w_{j} by considering three cases:

Case 1: k = 1. Then

w_{1} = (u_{1,1} − r)v_{1} + u_{1,2}v_{2} = (1 − r)r − (r − r^{2}) = 0.

Case 2: 1 < k < b. Then

w_{k} = u_{k,1}v_{1} + (u_{k,k} − r)v_{k} + u_{k,k+1}v_{k+1} = r − r ∑_{j=1}^{k}(−1)^{j+1}r^{j} − ∑_{j=1}^{k+1}(−1)^{j+1}r^{j} = 0.

Case 3: k = b. Then

w_{b} = u_{b,1}v_{1} + (u_{b,b} − r)v_{b} = r − r = 0.

Thus, w = 0. It can be shown by a similar argument that the eigenvalues of V_{1} are exactly the same as those of U_{1}.

Theorem 22. The matrices U_{N} and V_{N} satisfy the relation

U_{N}^{b+1} = V_{N}^{b+1} = (−1)^{N(b+1)}I_{b^{N}} ,  (34)

where I_{b^{N}} is the b^{N} × b^{N} identity matrix.

Proof. We shall only prove (34) for U_{N} since the proof for V_{N} is the same. We argue by induction on N. When N = 1, we know from Lemma 21 that all eigenvalues of U_{1} are roots of −1 + r − r^{2} + ⋯ + (−1)^{b+1}r^{b} = 0. It follows that every eigenvalue r satisfies r^{b+1} = (−1)^{b+1}; moreover, since they are all distinct, the corresponding eigenvectors are all linearly independent. Thus, U_{1}^{b+1} = (−1)^{b+1}I_{b}.

Next, assume that (34) holds for U_{N−1}. It follows from the mixed-product property of the Kronecker product that

U_{N}^{b+1} = (U_{1} ⊗ U_{N−1})^{b+1} = U_{1}^{b+1} ⊗ U_{N−1}^{(N−1)(b+1)}
= (−1)^{b+1}I_{b} ⊗ (−1)^{(N−1)(b+1)}I_{b^{N−1}}
= (−1)^{N(b+1)}I_{b^{N}} .

Thus, (34) holds for N.

We note that for b = 2, Ferrand [4] proved that the matrices S_{N} and T_{N} satisfy the three-strand braid relation

S_{N}T_{N}S_{N} = T_{N}S_{N}T_{N}.  (35)

We give an alternate proof of (35) based on Theorem 22. Define Q_{N} = S_{N}T_{N}S_{N} and R_{N} = T_{N}S_{N}T_{N}. Then Q_{N}R_{N} = U_{N}^{3} = (−1)^{3N}I_{2^{N}} = (−1)^{N}I_{2^{N}} because of (34). Moreover, we claim that Q_{N}^{2} = R_{N}^{2} = (−1)^{N}I_{2^{N}}. This follows by induction on N, which we demonstrate for Q_{N} by again using the mixed-product property of the Kronecker product:

Q_{N}^{2} = (S_{N}T_{N}S_{N}^{2}T_{N}S_{N})
= (S_{1}T_{1}S_{1}^{2}T_{1}S_{1}) ⊗ (S_{N−1}T_{N−1}S_{N−1}^{2}T_{N−1}S_{N−1})
= (−I_{2}) ⊗ ((−1)^{N−1}I_{2^{N−1}})
= (−1)^{N}I_{2^{N}}

Thus, Q_{N}R_{N} = Q_{N}^{2}, which implies the braid relation Q_{N} = R_{N}. However, we find that the braid relation fails to hold for b > 2.

References

[1] J.-P. Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in C. Ding, T. Helleseth, and H. Niederreiter, eds., Sequences and Their Applications, Proc. SETA’98, Springer-Verlag, 1999, pp. 1–16.

[2] T. Ball, T. Edgar, and D. Juda, Dominance orders, generalized binomial coefficients, and Kummer’s theorem, Math. Mag. 87 (2014), 135–143.

[3] D. Callan, Sierpinski’s triangle and the Prouhet-Thue-Morse word, preprint,

   http://arxiv.org/abs/math/0610932.

[4] E. Ferrand, Pascal and Sierpinski matrices, and the three strand braid group, preprint,

   http://webusers.imj-prg.fr/~emmanuel.ferrand/publi/PSB.ps.

[5] E. Ferrand, An analogue of the Thue-Morse sequence, Elect. J. Comb. 14 (2007), #R30.

[6] H. W. Gould, Some generalizations of Vandermonde’s convolution, Amer. Math. Monthly 63 (1956), 84–91.

[7] A. Imani and A. R. Moghaddamfar, The inverse of the Pascal lower triangular matrix modulo p, Acta Math. Univ. Comenianae 79 (2010), 135–142.

[8] D. H. Lehmer, The Tarry-Escott problem, Scripta Math. 13 (1947), 37–41.

[9] H. D. Nguyen, A digital binomial theorem, preprint,

   http://arxiv.org/abs/1412.3181.

[10] H. D. Nguyen, A new proof of the Prouhet-Tarry-Escott problem, preprint,

   http://arxiv.org/abs/1411.6168.

[11] E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres, C. R. Acad. Sci. Paris, 33 (1851), 225.

2010 Mathematics Subject Classification: Primary 11C20; Secondary 05A10. Keywords: binomial theorem, Sierpiński triangle, Prouhet-Thue-Morse sequence.

(Concerned with sequence \underline{A010060}.)

Received February 1 2015; revised version received March 30 2015. Published in Journal of Integer Sequences, May 26 2015.

Return to Journal of Integer Sequences home page.