Some Binomial Sums Involving Absolute Values

Richard P. Brent Australian National University

Canberra, ACT 2600

Australia

binomial@rpbrent.com

Hideyuki Ohtsuka Bunkyo University High School

1191-7, Kami, Ageo-City Saitama Pref., 362-0001

Japan

Judy-anne H. Osborn The University of Newcastle

Callaghan, NSW 2308 Australia

Helmut Prodinger Stellenbosch University

7602 Stellenbosch South Africa

Abstract

We consider several families of binomial sum identities whose definition involves the absolute value function. In particular, we consider centered double sums of the form

S_{α,β}(n) := ∑_{k, ℓ} \binom{2n}{n + k}\binom{2n}{n + ℓ}|k^{α} − ℓ^{α}|^{β},

obtaining new results in the cases α = 1, 2. We show that there is a close connection between these double sums in the case α = 1 and the single centered binomial sums considered by Tuenter.

1 Introduction

The problem of finding a closed form for the binomial sum

∑_{k, ℓ} \binom{2n}{n + k}\binom{2n}{n + ℓ}|k^{2} − ℓ^{2}|  (1)

arises in an application of the probabilistic method to the Hadamard maximal determinant problem [7]. Because of the double-summation and the absolute value occurring in (1), it is not obvious how to apply standard techniques [10, 15, 19]. A closed-form solution

2n^{2}\binom{2n}{n}^{2}  (2)

was proved by Brent and Osborn in [6], and simpler proofs were subsequently found [5, 8, 16]. In this paper we consider a wider class of binomial sums with the distinguishing feature that an absolute value occurs in the summand.

Specifically, we consider certain d-fold binomial sums of the form

S(n) := ∑_{k_{1},...,k_{d}} ∏_{i=1}^{d} \binom{2n}{n + k_{i}} |f(k_{1}, …, k_{d})|,  (3)

where f : ℤ^{d} → ℤ is a homogeneous polynomial and |f| will be called the weight function. For example, a simple case is d = 1, f(k) = k. This case was considered by Best [1] in an application to Hadamard matrices. The closed-form solution is

∑_{k} \binom{2n}{n + k}|k| = n\binom{2n}{n}.

A generalization f(k) = k^{r} (for a fixed r ∈ ℕ) was considered by Tuenter [18], and shown to be expressible using Dumont-Foata polynomials [9]. Tuenter gave an interpretation in terms of the moments of the distance to the origin in a symmetric Bernoulli random walk. It is easy to see that this interpretation generalizes: 4^{−nd}S(n) is the expectation of |f(k_{1}, …, k_{d})| if we start at the origin and take 2n random steps ±\frac{1}{2} in each of d dimensions, thus arriving at the point (k_{1}, …, k_{d}) ∈ ℤ^{d} with probability

4^{−nd} ∏_{i=1}^{d} \binom{2n}{n + k_{i}}.

A further generalization replaces \binom{2n}{n+k_{i}} by \binom{2n_{i}}{n_{i}+k_{i}}, allowing the number of random steps (2n_{i}) in dimension i to depend on i. With a suitable modification to the definition of S, we could also drop the restriction to an even number of steps in each dimension.^{1} We briefly consider such a generalization in §2.

Tuenter’s results for the case d = 1 were generalized by the first author [3]. In this paper we concentrate on the case d = 2. Generalizations of some of the results to arbitrary d are known. More specifically, the paper [4] gives closed-form solutions for the d-dimensional generalization of the sum (9) below in the cases α, β ∈ {1, 2}.

There are many binomial coefficient identities in the literature, e.g. 500 are given by Gould [11]. Many such identities can be proved via generating functions [12, 19] or the Wilf-Zeilberger algorithm [15]. Nevertheless, we hope that the reader will find our results interesting, in part because of the applications mentioned above, and also because it is a challenge to generalize the results to higher values of d.

A preliminary version of this paper, with some of the results conjectural, was made available on arXiv [5]. All the conjectures have since been proved by Bostan, Lairez, and Salvy [2], Krattenthaler and Schneider [14], Brent, Krattenthaler, and Warnaar [4], and the present authors.

An outline of the paper follows.

In §2 we consider a special class of double sums that can be reduced to the single sums of [3, 18].

In §3 we consider a generalization of the motivating case (1) described above: f(k, ℓ) = (k^{α} − ℓ^{α})^{β}. In the case α = 2 we give recurrence relations that allow such sums to be evaluated in closed form for any given positive integer β. The recurrence relations naturally split into the cases where β is even (easy) and odd (more difficult).

Theorem 10 in §4 gives a closed form for an analogous triple sum. In [5, Conjecture 2] a closed form for the analogous quadruple sum was conjectured. This conjecture has now been proved by Brent, Krattenthaler, and Warnaar [4]; in fact they give a generalization to arbitrary positive integer d.

In §5 we state several double sum identities that were proved or conjectured by us [5]. The missing proofs have now been provided by Bostan, Lairez, and Salvy [2], and by Krattenthaler and Schneider [14].

1For example, in the case d = 1 we could consider ∑_{k} \binom{n}{k}|f(n − 2k)|.

1.1 Notation

The set of all integers is ℤ, and the set of non-negative integers is ℕ.

The binomial coefficient \binom{n}{k} is defined to be zero if k < 0 or k > n (and hence always if n < 0). Using this convention, we often avoid explicitly specifying upper and lower limits on k or excluding cases where n < 0.

In the definition of the weight function |f|, we always interpret 0^{0} as 1.

2 Some double sums reducible to single sums

Tuenter [18] considered the binomial sum

S_{β}(n) := ∑_{k} \binom{2n}{n + k}|k|^{β},  (4)

and a generalization^{2} to

U_{β}(n) := ∑_{k} \binom{n}{k} |\frac{n}{2} − k|^{β}  (5)

was given by the first author [3].

Tuenter showed that

S_{2β}(n) = Q_{β}(n)2^{2n−β}, S_{2β+1}(n) = P_{β}(n)n\binom{2n}{n},  (6)

where P_{β}(n) and Q_{β}(n) are polynomials of degree β with integer coefficients, satisfying certain three-term recurrence relations, and expressible in terms of Dumont-Foata polynomials [9]. Closed-form expressions for S_{β}(n), P_{β}(n), Q_{β}(n) are known [3].

In this section we consider the double sum

T_{β}(m, n) := ∑_{k, ℓ} \binom{2m}{m + k}\binom{2n}{n + ℓ}|k − ℓ|^{β}  (7)

and show that it can be expressed as a single sum of the form (4).

Theorem 1. For all β, m, n ∈ ℕ, we have

T_{β}(m, n) = S_{β}(m + n),

where T_{β} is defined by (7) and S_{β} is defined by (4).

2It is a generalization because S_{β}(n) = U_{β}(2n), but U_{β}(n) is well-defined for all n ∈ ℕ.

Proof. If β = 0 then T_{0}(m, n) = 2^{2(m+n)} = S_{0}(m + n). Hence, we may assume that β > 0 (so 0^{β} = 0). Let d = |k − ℓ|. We split the sum (7) defining T_{β}(m, n) into three parts, corresponding to k > ℓ, k < ℓ, and k = ℓ. The third part vanishes. If k > ℓ then d = k − ℓ and k = d + ℓ; if k < ℓ then d = ℓ − k and ℓ = d + k. Thus, we get

T_{β}(m, n) = ∑_{d>0} ∑_{ℓ} \binom{2m}{m+d+ℓ}\binom{2n}{n+ℓ}d^{β} + ∑_{d>0} ∑_{k} \binom{2m}{m+k}\binom{2n}{n+k+d}d^{β}

= ∑_{d>0} d^{β} ∑_{ℓ}\binom{2m}{m+d+ℓ}\binom{2n}{n − ℓ} + ∑_{d>0} d^{β} ∑_{k}\binom{2n}{n+k+d}\binom{2m}{m − k}.

By Vandermonde’s identity, the inner sums over k and ℓ are both equal to \binom{2m+2n}{m+n+d}. Thus,

T_{β}(m, n) = 2 ∑_{d>0} \binom{2m + 2n}{m + n + d}d^{β} = ∑_{d} \binom{2m + 2n}{m + n + d}|d|^{β} = S_{β}(m + n).

Remark 2. If m = n then, by the shift-invariance of the weight |k − ℓ|^{β}, we have

T_{β}(n, n) = ∑_{k, ℓ} \binom{2n}{k}\binom{2n}{ℓ}|k − ℓ|^{β} = S_{β}(2n).  (8)

There is no need for the upper argument of the binomial coefficients to be even in (8). We can adapt the proof of Theorem 1 to show that, for all n ∈ ℕ,

∑_{k, ℓ} \binom{n}{k}\binom{n}{ℓ}|k − ℓ|^{β} = S_{β}(n).

3 Centered double sums

In this section we consider the centered double binomial sums defined by^{3}

S_{α,β}(n) := ∑_{k, ℓ} \binom{2n}{n + k}\binom{2n}{n + ℓ}|k^{α} − ℓ^{α}|^{β}.  (9)

Note that S_{1,β}(n) = T_{β}(n, n), so the case α = 1 is covered by Theorem 1. Thus, in the following we can assume that α ≥ 2. Since we mainly consider the case α = 2, it is convenient to define

W_{β}(n) := S_{2,β}(n) = ∑_{k, ℓ} \binom{2n}{n + k}\binom{2n}{n + ℓ}|k^{2} − ℓ^{2}|^{β}.  (10)

3The double sum S_{α,β}(n) should not be confused with the single sum S_{α}(n) of §2.

Remark 3. The sequences (S_{α,β}(n))_{n≥1} for α ∈ {1, 2} and 1 ≤ β ≤ 4 are in the OEIS [17]. Specifically, (S_{1,1}(n))_{n≥1} is a subsequence of A166337 (the entry corresponding to n = 0 must be discarded). (S_{2,1}(n))_{n≥0} is A254408, and (S_{α,β}(n))_{n≥0} for (α, β) = (1, 2), (2, 2), (1, 3), (2, 3), (1, 4), (2, 4) are A268147, A268148, …, A268152, respectively.

3.1 W_{β} for odd β

The analysis of W_{β}(n) naturally splits into two cases, depending on the parity of β. We first consider the case that β is odd. A simpler approach is possible when β is even, as we show in §3.3.

As mentioned in §1, the evaluation of W_{1}(n) was the motivation for this paper, and is given in the following theorem.

Theorem 4 (Brent and Osborn).

W_{1}(n) = ∑_{k, ℓ} \binom{2n}{n + k}\binom{2n}{n + ℓ}|k^{2} − ℓ^{2}| = 2n^{2}\binom{2n}{n}^{2}.

Numerical evidence suggested the following generalization of Theorem 4. It was conjectured by the present authors [5, Conjecture 2], and proved by Krattenthaler and Schneider [14].

Theorem 5 (Krattenthaler and Schneider). For all m, n ∈ ℕ,

∑_{k, ℓ} \binom{2m}{m + k}\binom{2n}{n + ℓ}|k^{2} − ℓ^{2}| ≥ 2mn\binom{2m}{m}\binom{2n}{n},

with equality if and only if m = n.

3.2 Recurrence relations for the odd case

Theorem 4 gives W_{1}(n). We show how W_{3}(n), W_{5}(n), … can be computed using recurrence relations. More precisely, we express the double sums W_{2r+1}(n) in terms of certain single sums G_{r}(n, m), and give a recurrence for the G_{r}(n, m). We then show that W_{2r+1}(n) is a linear combination of P_{r}(n), …, P_{2r}(n), where the polynomials P_{m}(n) are as in (6), and the coefficients multiplying these polynomials satisfy another recurrence relation.

Define

f_{ℓ} = \begin{cases}1, & if ℓ ≠ 0; \\ \frac{1}{2}, & if ℓ = 0. \end{cases}

Using symmetry and the definition (10) of W_{r}(n), we have

W_{2r+1}(n) = 8 ∑_{ℓ=0}^{n} ∑_{k=ℓ}^{n} \binom{2n}{n + k}\binom{2n}{n + ℓ}(k^{2} − ℓ^{2})^{2r+1}f_{ℓ};  (11)

the factor f_{ℓ} allows for terms which would otherwise be counted twice.

Let m = k − ℓ. Since k^{2} − ℓ^{2} = m(m + 2ℓ), we can write the double sum W_{2r+1}(n)/8 in (11) as

∑_{ℓ=0}^{n} ∑_{k=ℓ}^{n} \binom{2n}{n + k}\binom{2n}{n + ℓ}(k^{2} − ℓ^{2})^{2r+1}f_{ℓ} = ∑_{m≥0} m^{2r+1}G_{r}(n, m),  (12)

where

G_{r}(n, m) := ∑_{ℓ≥0} \binom{2n}{n + m + ℓ}\binom{2n}{n + ℓ}(m + 2ℓ)^{2r+1}f_{ℓ}.  (13)

Observe that G_{r}(0, m) = 0. For convenience we define G_{r}(−1, m) = 0. We observe that G_{r}(n, m) satisfies a recurrence relation, as follows.

Lemma 6. For all m, n, r ∈ ℕ,

G_{r+2}(n, m) = 2(4n^{2} + m^{2})G_{r+1}(n, m) − (4n^{2} − m^{2})^{2}G_{r}(n, m)
+ 64n^{2}(2n − 1)^{2}G_{r}(n − 1, m).  (14)

Proof. If n = 0 the proof of (14) is trivial, since G_{r}(0, m) = G_{r}(−1, m) = 0. Hence, suppose that n > 0. We observe that

[(m + 2ℓ)^{4} − 2(4n^{2} + m^{2})(m + 2ℓ)^{2} + (4n^{2} − m^{2})^{2}]\binom{2n}{n + m + ℓ}\binom{2n}{n + ℓ}

= 16(n + m + ℓ)(n − m − ℓ)(n + ℓ)(n − ℓ)\binom{2n}{n + m + ℓ}\binom{2n}{n + ℓ}

= 64n^{2}(2n − 1)^{2}\binom{2n − 2}{n − 1 + m + ℓ}\binom{2n − 2}{n − 1 + ℓ}.

Now multiply each side by (m + 2ℓ)^{2r+1}f_{ℓ} and sum over ℓ ≥ 0.

The recurrence (14) may be used to compute G_{r}(n, m) for given (n, m) and r = 0, 1, 2, …, using the initial values

G_{0}(n, m) = \frac{n}{2} \binom{2n}{n}\binom{2n}{n + m}

and

G_{1}(n, m) = \frac{4n^{2} + (2n − 5)m^{2}}{2n − 1} G_{0}(n, m).

These initial values may be verified from the definition (13) by standard methods [15] – we omit the details.

Write g_{r}(n, m) = 0 if G_{r}(n, m) = 0, and otherwise define g_{r}(n, m) by

G_{r}(n, m) = \binom{2n}{n}\binom{2n}{n + m}g_{r}(n, m).

The recurrence (14) for G_{r} gives a corresponding recurrence for g_{r}:

g_{r+2}(n, m) = 2(4n^{2} + m^{2})g_{r+1}(n, m) − (4n^{2} − m^{2})^{2}g_{r}(n, m)
+ 16n^{2}(n^{2} − m^{2})g_{r}(n − 1, m),  (15)

with initial values

g_{0}(n, m) = \frac{n}{2}, g_{1}(n, m) = \frac{4n^{2} + (2n − 5)m^{2}}{2n − 1} g_{0}(n, m).

Note that the g_{r}(n, m) are rational functions in n and m; if computation with bivariate polynomials over ℤ is desired then g_{r}(n, m) can be multiplied by (2n − 1)(2n − 3) ⋯ (2n − (2r−1)). If n is fixed, then g_{r}(n, m) is an even polynomial in m and, from the recurrence (15), the degree is 2r. This suggests that we should define rational functions γ_{r,j}(n) by

g_{r}(n, m) = ∑_{j=0}^{r} γ_{r,j}(n)m^{2j}.

For j < 0 or j > r we define γ_{r,j}(n) = 0. From the recurrence (15), we obtain the following recurrence for the γ_{r,j}(n):

γ_{r+2,j}(n) = 8n^{2}γ_{r+1,j}(n) + 2γ_{r+1,j−1}(n) − 16n^{4}γ_{r,j}(n) + 8n^{2}γ_{r,j−1}(n)
− γ_{r,j−2}(n) + 16n^{4}γ_{r,j}(n − 1) − 16n^{2}γ_{r,j−1}(n − 1).  (16)

The γ_{r,j}(n) can be computed from (16), using the initial values

γ_{0,0}(n) = n/2,
γ_{1,0}(n) = 2n^{3}/(2n − 1),  (17)
γ_{1,1}(n) = n(2n − 5)/(4n − 2).

Using the definition of γ_{r,j}(n) and (11)–(13), we obtain

W_{2r+1}(n) = 4\binom{2n}{n} ∑_{j=0}^{r} γ_{r,j}(n)S_{2r+2j+1}(n).

Since S_{2r+1}(n) = P_{r}(n)n\binom{2n}{n}, we obtain the following theorem, which shows that the double sums W_{2r+1}(n) may be expressed in terms of the same polynomials P_{m}(n) that occur in expressions for the single sums of [3, 18].

Theorem 7.

W_{2r+1}(n) = 4n ∑_{j=0}^{r} γ_{r,j}(n)P_{r+j}(n) · \binom{2n}{n}^{2},  (18)

where the polynomials P_{r+j}(n) are as in (6), and the γ_{r,j}(n) may be computed from the recurrence (16) and the initial values given in (17).

The factor before the binomial coefficient in (18) is a rational function ω_{r}(n) with denominator (2n − 1)(2n − 3) ⋯ (2n − 2⌈r/2⌉ + 1). Thus, we have the following corollary of Theorem 7.

Corollary 8. If r ∈ ℕ and W_{r}(n) is defined by (10), then

W_{2r+1}(n) = ω_{r}(n)\binom{2n}{n}^{2},

where

ω_{r}(n) ∏_{j=1}^{⌈r/2⌉}(2n − 2j + 1)

is a polynomial of degree 2r + ⌈r/2⌉ + 2 over ℤ. The first four cases are:

ω_{0}(n) = 2n^{2},
ω_{1}(n) = \frac{2n^{3}(8n^{2} − 12n + 5)}{2n − 1} ,
ω_{2}(n) = \frac{2n^{3}(128n^{4} − 512n^{3} + 800n^{2} − 568n + 153)}{2n − 1} , and
ω_{3}(n) = \frac{2n^{3} \overline{ω}_{3}(n)}{(2n − 1)(2n − 3)} , where
\overline{ω}_{3}(n) = 9216n^{7} − 86016n^{6} + 350464n^{5} − 802304n^{4}+
1106856n^{3} − 914728n^{2} + 417358n − 80847.

3.3 W_{β} for even β

Now we consider W_{β}(n) for even β. This case is easier than the case of odd β because the absolute value in the definition (10) has no effect when β is even. Theorem 9 shows that W_{2r}(n) can be expressed in terms of the single sums S_{0}(n), S_{2}(n), …, S_{4r}(n) or, equivalently, in terms of the polynomials Q_{0}(n), Q_{1}(n), …, Q_{2r}(n). It follows that 2^{2r−4n}W_{2r}(n) is a polynomial over ℤ of degree 2r in n.

Theorem 9. For all n ∈ ℕ,

W_{2r}(n) = ∑_{k}(−1)^{k}\binom{2r}{k}S_{2k}(n)S_{4r−2k}(n)

= 2^{4n−2r} ∑_{k}(−1)^{k}\binom{2r}{k}Q_{k}(n)Q_{2r−k}(n),

where Q_{r}(n) and S_{r}(n) are as (4)–(6) of §2, and W_{β}(n) is defined by (10).

Proof. From the definition of W_{2r}(n) we have

W_{2r}(n) = ∑_{i} ∑_{j} \binom{2n}{n + i}\binom{2n}{n + j}(i^{2} − j^{2})^{2r}.

Write

(i^{2} − j^{2})^{2r} = ∑_{k}(−1)^{k}\binom{2r}{k}i^{4r−2k}j^{2k},

change the order of summation in the resulting triple sum, and observe that the inner sums over i and j separate, giving S_{4r−2k}(n)S_{2k}(n). This proves the first part of the theorem. The second part follows from (6).

For example, the first four cases are

W_{0}(n) = 2^{4n},
W_{2}(n) = 2^{4n−1} n(2n − 1),
W_{4}(n) = 2^{4n−2} n(2n − 1)(18n^{2} − 33n + 17),
W_{6}(n) = 2^{4n−3} n(2n − 1)(900n^{4} − 4500n^{3} + 8895n^{2} − 8055n + 2764).

It follows from Theorem 9 that the coefficients of 2^{2r−4n}W_{2r}(n) are in ℤ, but it is not obvious how to prove the stronger result, suggested by the cases above, that the coefficients of 2^{r−4n}W_{2r}(n) are in ℤ. We leave this as a conjecture.

4 A triple sum

In Theorem 10 we give a triple sum that is analogous to the double sum of Theorem 4. A straightforward but tedious proof is given in [5, Appendix]. The result also follows from the case d = 3 of a more general result proved in [4, Proposition 1.1] for the analogous d-fold sum, where the weight function is generalized to the absolute value of a Vandermonde |Δ(i_{1}^{2}, i_{2}^{2}, …, i_{d}^{2})|.

Theorem 10. For all n ∈ ℕ,

∑_{i, j, k}\binom{2n}{n + i}\binom{2n}{n + j}\binom{2n}{n + k}|(i^{2} − j^{2})(i^{2} − k^{2})(j^{2} − k^{2})|

= 3n^{3}(n − 1)\binom{2n}{n}^{2}2^{2n−1}.

5 Further identities

In this section we give various identities that were stated in [5]. Of these, (25), (26), (27),

(30) and (32) were conjectural. The conjectures have since been proved by Bostan, Lairez, and Salvy [2, §7.3.2].

5.1 Centered double sums

Recall that, from the definition (9), we have

S_{α,1}(n) = ∑_{i, j} \binom{2n}{n + i}\binom{2n}{n + j}|i^{α} − j^{α}|.  (19)

We give closed-form expressions for S_{α,1}(n), 1 ≤ α ≤ 8. Observe that (24) follows from Theorem 1 since S_{1,1}(n) = T_{1}(n, n), and (20) is equivalent to Theorem 4. It appears that, for even α, S_{α,1}(n) is a rational function of n multiplied by \binom{2n}{n}^{2}, but for odd α, it is a rational function of n multiplied by \binom{4n}{2n}. This was conjectured in [5], and has been proved by Krattenthaler and Schneider [14].

S_{2,1}(n) = 2n^{2}\binom{2n}{n}^{2},  (20)
S_{4,1}(n) = \frac{2n^{3}(4n − 3)}{2n − 1}\binom{2n}{n}^{2},  (21)
S_{6,1}(n) = \frac{2n^{3}(11n^{2} − 15n + 5)}{2n − 1}\binom{2n}{n}^{2},  (22)
S_{8,1}(n) = \frac{2n^{3}(80n^{4} − 306n^{3} + 428n^{2} − 266n + 63)}{(2n − 1)(2n − 3)}\binom{2n}{n}^{2},  (23)
S_{1,1}(n) = 2n\binom{4n}{2n},  (24)
S_{3,1}(n) = \frac{4n^{2}(5n − 2)}{4n − 1}\binom{4n − 1}{2n − 1},  (25)

S_{5,1}(n) = \frac{8n^{2}(43n^{3} − 70n^{2} + 36n − 6)}{(4n − 2)(4n − 3)}\binom{4n − 2}{2n − 2},  (26)
S_{7,1}(n) = \frac{16n^{2}P_{7,1}(n)}{(4n − 3)(4n − 4)(4n − 5)}\binom{4n − 3}{2n − 3}, n ≥ 2, where
P_{7,1}(n) = 531n^{5} − 1960n^{4} + 2800n^{3} − 1952n^{2} + 668n − 90,  (27)
(S_{7,1}(1) = 12 is a special case).

Following are some similar identities. We observe that, since i^{4} − j^{4} = (i^{2} + j^{2})(i^{2} − j^{2}),

(28) is easily seen to be equivalent to (21). Similarly, since i^{6}−j^{6} = (i^{4}+i^{2}j^{2}+j^{4})(i^{2}−j^{2}), any two of (22), (29) and (31) imply the third. Higher-dimensional generalizations of (30)–(31) are known [4].

∑_{i, j} \binom{2n}{n+i}\binom{2n}{n+j}|i^{2}(i^{2} − j^{2})| = \frac{n^{3}(4n − 3)}{2n − 1} \binom{2n}{n}^{2},  (28)

∑_{i, j} \binom{2n}{n+i}\binom{2n}{n+j}|i^{4}(i^{2} − j^{2})| = \frac{n^{3}(10n^{2} − 14n + 5)}{2n − 1} \binom{2n}{n}^{2},  (29)

∑_{i, j} \binom{2n}{n+i}\binom{2n}{n+j}|ij(i^{2} − j^{2})| = \frac{2n^{3}(n − 1)}{2n − 1} \binom{2n}{n}^{2},  (30)

∑_{i, j} \binom{2n}{n+i}\binom{2n}{n+j}|i^{2}j^{2}(i^{2} − j^{2})| = \frac{2n^{4}(n − 1)}{2n − 1} \binom{2n}{n}^{2},  (31)

∑_{i, j} \binom{2n}{n+i}\binom{2n}{n+j}|i^{3}j^{3}(i^{2} − j^{2})| = \frac{2n^{4}(n − 1)(3n^{2} − 6n + 2)}{(2n − 1)(2n − 3)} \binom{2n}{n}^{2}.  (32)

6 Acknowledgments

We thank Christian Krattenthaler for sending us proofs [14] of some of the conjectures that we made in an earlier version [5] of this paper, and informing us of the work of Bostan et al. [2]. We also thank David Callan for sending us his short proof [8] of (2) using lattice paths (specifically, equations (1.12) and (1.14) of [13]). An anonymous referee encouraged us to avoid some infelicitous notation. The first author was supported in part by Australian Research Council grant DP140101417.

References

[1] M. R. Best, The excess of a Hadamard matrix, Indag. Math. (N.S.) 39 (1977), 357–361.

[2] A. Bostan, P. Lairez, and B. Salvy, Multiple binomial sums, preprint, 2015,

    http://arxiv.org/abs/1510.07487v1.

[3] R. P. Brent, Generalising Tuenter’s binomial sums, J. Integer Seq. 18 (2015), article 15.3.2.

[4] R. P. Brent, C. Krattenthaler, and S. O. Warnaar, Discrete analogues of Mehta-type

    integrals, preprint, 2016, http://arxiv.org/abs/1601.06536v1.

[5] R. P. Brent, H. Ohtsuka, J. H. Osborn, and H. Prodinger, Some binomial sums involving

    absolute values, preprint, 2014, http://arxiv.org/abs/1411.1477v1.

[6] R. P. Brent and J. H. Osborn, Note on a double binomial sum relevant to the Hadamard maximal determinant problem, preprint, 2013, http://arxiv.org/abs/1309.2795v2.

[7] R. P. Brent, J. H. Osborn, and W. D. Smith, Lower bounds on maximal determinants of binary matrices via the probabilistic method, preprint, 2014,

    http://arxiv.org/abs/1402.6817v2.

[8] D. Callan, Remark on “Some binomial sums involving absolute values”, personal communication to H. Prodinger, Nov. 17, 2014.

[9] D. Dumont and D. Foata, Une propriété de symétrie des nombres de Genocchi, Bull. Soc. Math. France 104 (1976), 433–451.

[10] R. W. Gosper, Jr., Decision procedure for indefinite hypergeometric summation, Proc. Natl. Acad. Sci. USA 75 (1978), 40–42.

[11] H. W. Gould, Combinatorial Identities, published by the author, revised edition, Morgantown, West Virginia, 1972.

[12] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

[13] R. K. Guy, C. Krattenthaler, and B. E. Sagan, Lattice paths, reflections, and dimensionchanging bijections, Ars Combin. 34 (1992), 3–15.

[14] C. Krattenthaler and C. Schneider, Evaluation of binomial double sums involving absolute values, preprint, 2015.

[15] M. Petkovšek, H. S. Wilf, and D. Zeilberger, A = B, A. K. Peters, 1996.

[16] H. Prodinger, A short and elementary proof for a double sum of Brent and Osburn,

    preprint, 2013, http://arxiv.org/abs/1309.4351v1.

[17] The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences,

    http://oeis.org.

[18] H. J. H. Tuenter, Walking into an absolute sum, Fibonacci Quart. 40 (2002), 175–180.

[19] H. S. Wilf, generatingfunctionology, 3rd edition, A. K. Peters, 2006.

2010 Mathematics Subject Classification: Primary 05A10, 11B65; Secondary 05A15, 05A19, 44A60, 60G50. Keywords: absolute binomial sum, binomial sum, centered binomial sum, Dumont-Foata polynomial, Tuenter polynomial, Vandermonde kernel.

(Concerned with sequences \underline{A166337}, \underline{A254408}, \underline{A268147}, \underline{A268148}, \underline{A268149}, \underline{A268150}, \underline{A268151}, and \underline{A268152}.)

Received January 30 2016; revised version received March 3 2016. Published in Journal of Integer Sequences, April 6 2016.

Return to Journal of Integer Sequences home page.