Generalizing Tuenter’s Binomial Sums

Richard P. Brent Mathematical Sciences Institute Australian National University Canberra, ACT 2614 Australia

                   sums@rpbrent.com

Abstract

Tuenter considered centered binomial sums of the form

S_{r}(n) = ∑_{k=0}^{2n} \binom{2n}{k}|n − k|^{r},

where r and n are non-negative integers. We consider sums of the form

U_{r}(n) = ∑_{k=0}^{n} \binom{n}{k}|n/2 − k|^{r},

which are a generalization of Tuenter’s sums and may be interpreted as moments of a symmetric Bernoulli random walk with n steps. The form of U_{r}(n) depends on the parities of both r and n. In fact, U_{r}(n) is the product of a polynomial (depending on the parities of r and n) times a power of two or a binomial coefficient. In all cases the polynomials can be expressed in terms of Dumont-Foata polynomials. We give recurrence relations, generating functions and explicit formulas for the functions U_{r}(n) and/or the associated polynomials.

1 Introduction

We consider centered binomial sums of the form

U_{r}(n) = ∑_{k=0}^{n} \binom{n}{k} |\frac{n}{2} − k|^{r} ,  (1)

where r, n ≥ 0. These generalize the binomial sums

S_{r}(n) = ∑_{k=0}^{2n} \binom{2n}{k}|n − k|^{r},  (2)

previously considered by Tuenter [7] and other authors, since S_{r}(n) = U_{r}(2n), but U_{r}(n) is well-defined for both even and odd values of n. The generalization arises naturally in the study of certain two-fold centered binomial sums of the form ∑_{j} ∑_{k} \binom{2n}{n+j}\binom{2n}{n+k}P (j, k), see Brent et al. [2, Lemma 6.4].

In definitions such as (1) and (2) we always interpret 0^{0} as 1. Thus U_{0}(n) = 2^{n} for all n ≥ 0. We define U_{r}(m) = 0 if m < 0.

For r > 0 we can avoid the absolute value function in (1) by writing

U_{r}(n) = 2 ∑_{k=0}^{⌊n/2⌋} \binom{n}{k} (\frac{n}{2} − k)^{r} .

Tuenter [7] showed in a direct manner that, for r ≥ 0 and n > 0, S_{r}(n) satisfies the recurrence

S_{r+2}(n) = n^{2}S_{r}(n) − 2n(2n − 1)S_{r}(n − 1).  (3)

Observe that this recurrence splits into two separate recurrences, one involving odd values of r and the other involving even values of r. Also, S_{0}(n) = 2^{2n} and S_{1}(n) = n\binom{2n}{n}. It follows that, for r, n ≥ 0,

S_{2r}(n) = Q_{r}(n)2^{2n−r} and S_{2r+1}(n) = P_{r}(n)n\binom{2n}{n},  (4)

where P_{r}(n) and Q_{r}(n) are polynomials of degree r with integer coefficients, satisfying the recurrences

P_{r+1}(n) = n^{2}P_{r}(n) − n(n − 1)P_{r}(n − 1),  (5)
Q_{r+1}(n) = 2n^{2}Q_{r}(n) − n(2n − 1)Q_{r}(n − 1)  (6)

for r ≥ 0, with initial conditions P_{0}(n) = Q_{0}(n) = 1.

The Dumont-Foata polynomials F_{r}(x, y, z) are 3-variable polynomials satisfying the recurrence relation

F_{r+1}(x, y, z) = (x + z)(y + z)F_{r}(x, y, z + 1) − z^{2}F_{r}(x, y, z)  (7)

for r ≥ 1, with F_{1}(x, y, z) = 1. Dumont and Foata [4] gave a combinatorial interpretation for the coefficients of F_{r}(x, y, z) and showed that F_{r}(x, y, z) is symmetric in the three variables x, y, z.

Tuenter [7] showed that P_{r}(n) and Q_{r}(n) may be expressed in terms of Dumont-Foata polynomials. In fact, for r ≥ 1,

P_{r}(n) = (−1)^{r−1}nF_{r}(1, 1, −n) and Q_{r}(n) = (−2)^{r−1}nF_{r}(\frac{1}{2}, 1, −n).  (8)

Thus, we can obtain explicit formulas and generating functions for the polynomials P_{r}(n) and Q_{r}(n) as special cases of the results of Carlitz [3] on Dumont-Foata polynomials.

We show that all the above results for S_{r}(n) can be generalized to cover U_{r}(n). In particular, Theorem 1 shows that U_{r}(n) satisfies a recurrence (9) similar to the recurrence (3) satisfied by S_{r}(n). Also, U_{r}(n) is the product of a polynomial (depending on the parity of r) times a power of two or a binomial coefficient, and Theorem 2 shows that these polynomials satisfy three-term recurrence relations analogous to (5)–(6). Using the recurrences, the polynomials can be expressed in terms of Dumont-Foata polynomials, so the results of Carlitz allow us to obtain explicit formulas (in §3) and exponential generating functions (in §4).

2 Recurrence relations

Theorems 1–2 give recurrence relations for U_{r}(n) and associated polynomials. The recurrence (9) in Theorem 1 implies the recurrence (3) satisfied by S_{r}(n).

Theorem 1. For all r, n ≥ 0, U_{r}(n) satisfies the recurrence

4U_{r+2}(n) = n^{2}U_{r}(n) − 4n(n − 1)U_{r}(n − 2),  (9)

and may be computed from the recurrence using the initial conditions

U_{0}(n) = 2^{n}, U_{1}(2n) = n\binom{2n}{n}, U_{1}(2n + 1) = (2n + 1)\binom{2n}{n} for all n ≥ 0.

Proof. We have

4U_{r+2}(n) = ∑_{k=0}^{n} 4\binom{n}{k} |\frac{n}{2} − k|^{r+2} = ∑_{k=0}^{n} \binom{n}{k} |\frac{n}{2} − k|^{r} (n − 2k)^{2},  (10)

n^{2}U_{r}(n) = ∑_{k=0}^{n} \binom{n}{k} |\frac{n}{2} − k|^{r} n^{2},  (11)

and

4n(n − 1)U_{r}(n − 2) = ∑_{k=0}^{n−2} 4n(n − 1)\binom{n − 2}{k} |\frac{n − 2}{2} − k|^{r}

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

= ∑_{k=1}^{n−1} 4k(n − k)\binom{n}{k} |\frac{n}{2} − k|^{r} .  (12)

Since (n − 2k)^{2} − n^{2} − 4k(n − k) = 0, the recurrence (9) follows from (10)–(12).

For the initial conditions, it is easily verified that U_{0}(n) = 2^{n}. The solution by Hillman [5] to the Putnam problem 35-A4 gives U_{1}(n) = n\binom{n−1}{⌊n/2⌋}, and taking account of the parity of n gives the remaining conditions.

It is now clear that the structure of U_{r}(n) depends upon the parities of both r and n, and one can elucidate the recursion (9) by the following substitutions:

U_{2r+1}(2n − 1) = 2^{−(2r+1)}n\overline{P}_{r}(n)\binom{2n}{n},  (13)
U_{2r}(2n + 1) = 2^{2n+1−2r}\overline{Q}_{r}(n).  (14)

It is easily verified that \overline{P}_{r}(n) and \overline{Q}_{r}(n) are polynomials in n of degree r. By substitution into (9), we obtain the following theorem.

Theorem 2. For r ≥ 0, the polynomials \overline{P}_{r}(n) and \overline{Q}_{r}(n) defined by equations (13)–(14) satisfy the following recurrence relations:

\overline{P}_{r+1}(n) = (2n − 1)^{2} \overline{P}_{r}(n) − 4(n − 1)^{2} \overline{P}_{r}(n − 1),  (15)
\overline{Q}_{r+1}(n) = (2n + 1)^{2} \overline{Q}_{r}(n) − 2n(2n + 1)\overline{Q}_{r}(n − 1),  (16)

with initial conditions \overline{P}_{0}(n) = \overline{Q}_{0}(n) = 1.

3 Explicit formulas

Using the recurrence (7) and matching the initial conditions, we can verify that the polynomials \overline{P}_{r}(n) and \overline{Q}_{r}(n) can be expressed in terms of Dumont-Foata polynomials, as follows:

\overline{P}_{r}(n) = (−4)^{r}F_{r+1} (\frac{1}{2}, \frac{1}{2}, \frac{1}{2} − n) ,  (17)
\overline{Q}_{r}(n) = (−1)^{r−1}2^{2r−1} (n + \frac{1}{2}) F_{r} (\frac{1}{2}, 1, −n − \frac{1}{2}) .  (18)

Also, replacing n by n + \frac{1}{2} in the second half of (8) shows that

\overline{Q}_{r}(n) = 2^{r}Q_{r}(n + \frac{1}{2}) .  (19)

Carlitz [3, eqns. (1.13) and (1.16)] gives an explicit formula for the Dumont-Foata polynomials. We follow Carlitz and let (z)_{k} denote the Pochhammer symbol or “rising factorial”. Note that, although F_{r+1}(x, y, z) is symmetric in x, y and z, the representation given in Proposition 3 is not symmetric. Thus, it is sometimes necessary to permute variables before applying Proposition 3.

Proposition 3 (Carlitz). For r ≥ 0 and z > 0,

F_{r+1}(x, y, z) = ∑_{k=0}^{r}(−1)^{r−k}(x + z)_{k}(y + z)_{k} A_{r,k}(z),

where A_{r,k}(z) = \frac{2}{k!} ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}\frac{(z + j)^{2r+1}}{(2z + j)_{k+1}} .

Application of Proposition 3 gives, after some simplification, the following formulas for U_{r}(n), valid for r ≥ 1 and n ≥ 0:

U_{2r}(n) = 2^{n+1} ∑_{1≤j≤k≤r}(−1)^{j} \frac{(−\frac{n}{2})_{k} (\frac{1}{2})_{k}}{(k − j)!(k + j)!} j^{2r},  (20)

U_{2r+1}(2n) = 2n\binom{2n}{n} ∑_{1≤j≤k≤r}(−1)^{j} \frac{(−n)_{k}}{(k − j)! (k + 1)_{j}} j^{2r},  (21)

U_{2r−1}(2n − 1) = \binom{2n}{n} ∑_{1≤j≤k≤r}(−1)^{j} \frac{(−n)_{k}}{(k − j)! (k)_{j}} (j − \frac{1}{2})^{2r−1} .  (22)

4 Generating functions

The exponential generating function (egf)

∑_{r≥0} U_{2r}(n)\frac{z^{2r}}{(2r)!} = 2^{n} cosh^{n}(z/2).  (23)

generalizes the egf

∑_{r≥0} S_{2r}(n)\frac{z^{2r}}{(2r)!} = 2^{2n} cosh^{2n}(z/2)  (24)

given by Tuenter [7, §5], since replacing n by 2n in (23) gives (24). The proof of (23) is straightforward, and does not require the results of Carlitz.

We can obtain other egfs from the results of Carlitz. First, we note that Carlitz [3, eqn. (4.2)] gives the egf

∑_{r≥1}(−1)^{r}F_{r}(x, y, 1)\frac{z^{2r}}{(2r)!} = \frac{1}{xy} ∑_{k≥1}(−1)^{k} \frac{(x)_{k}(y)_{k}}{(2k)!} (2 sinh \frac{z}{2})^{2k} .  (25)

In view of (4) and (8), this allows us to obtain an egf for U_{2r+1}(2n):

∑_{r≥0} U_{2r+1}(2n)\frac{z^{2r}}{(2r)!} = n\binom{2n}{n} ∑_{k=0}^{n} 2^{2k}\binom{n}{k}\binom{2k}{k}^{−1} sinh^{2k} (\frac{z}{2}) .  (26)

In order to calculate U_{2r+1}(2n) from (26), it is only necessary to sum the terms on the right-hand side for k ≤ min(r, n).

The remaining case U_{2r+1}(2n − 1) is more difficult because (25) does not apply. We can use the egf

∑_{r≥0}(−1)^{r}F_{r+1}(x, y, z)\frac{u^{2r+1}}{(2r + 1)!}

= 2 ∑_{k=0}^{∞} ∑_{j=0}^{k} \frac{(−1)^{j}(x + z)_{k}(y + z)_{k}(2z)_{j}}{j!(k − j)!(2z)_{k+1}(2z + k + 1)_{j}} sinh((z + j)u),  (27)

which follows from the discussion in Carlitz [3, pp. 221–222]. Using (13), (17) and (27), after some simplification followed by a change of variables (u ↦ z), we obtain the egf:

∑_{r≥0} U_{2r+1}(2n − 1)\frac{z^{2r+1}}{(2r + 1)!}

= n\binom{2n}{n} ∑_{0≤j≤k<n} \frac{(−1)^{k−j}\binom{n−1}{k}\binom{2k}{k−j}}{\binom{2k}{k}} \frac{sinh ((j + \frac{1}{2}) z)}{j + k + 1} ,  (28)

which is valid for n ≥ 1.

5 Acknowledgment

Thanks are due to an anonymous referee for detailed and helpful comments on a preliminary version of this paper. This research was supported by Australian Research Council grant DP140101417.

Appendix 1: The polynomials \overline{P}_{r}, \overline{Q}_{r} for r ≤ 5

\overline{P}_{0}(n) = 1,
\overline{P}_{1}(n) = 4n − 3,
\overline{P}_{2}(n) = 32n^{2} − 56n + 25,
\overline{P}_{3}(n) = 384n^{3} − 1184n^{2} + 1228n − 427,
\overline{P}_{4}(n) = 6144n^{4} − 29184n^{3} + 52416n^{2} − 41840n + 12465,
\overline{P}_{5}(n) = 122880n^{5} − 829440n^{4}+
2258688n^{3} − 3076288n^{2} + 2079892n − 555731,
\overline{Q}_{0}(n) = 1,
\overline{Q}_{1}(n) = 2n + 1,
\overline{Q}_{2}(n) = 12n^{2} + 8n + 1,
\overline{Q}_{3}(n) = 120n^{3} + 60n^{2} + 2n + 1,
\overline{Q}_{4}(n) = 1680n^{4} − 168n^{2} + 128n + 1,
\overline{Q}_{5}(n) = 30240n^{5} − 25200n^{4} + 5040n^{3} + 7320n^{2} − 2638n + 1.

A similar table for Tuenter’s polynomials P_{r}(n), Q_{r}(n) may be found in Brent [1]. The triangles of coefficients of −P_{r}(−n)/n, −Q_{r}(−n)/n, and \overline{Q}_{r}(−n) for r ≥ 1 are OEIS [6] sequences \underline{A036970}, \underline{A083061}, and \underline{A160485} respectively. We have contributed the coefficients of \overline{P}_{r}(n) as sequence \underline{A245244}. The values (−1)^{r}\overline{P}_{r}(0) are sequence \underline{A009843} (see Appendix 2 for details).

The bijection (19) between \underline{A083061} and \underline{A160485} (by a shift of ±\frac{1}{2} and scaling by a power of 2) was not mentioned in the relevant OEIS entries as at July 14, 2014; we have now contributed comments to this effect.

Appendix 2: Special values of P_{r}, Q_{r}, \overline{P}_{r}, \overline{Q}_{r}

In Table 1, we give values of the polynomials P_{r}, Q_{r}, \overline{P}_{r}, and \overline{Q}_{r} at 0, 1, ∞. Here P (∞) denotes the leading coefficient of the polynomial P (z), δ_{i,j} is the Kronecker delta, and S_{r} is the r-th Secant number. The values (−1)^{r}\overline{P}_{r}(0) are OEIS sequence \underline{A009843}, and are given by the egf

∑_{r=0}^{∞} \overline{P}_{r}(0)\frac{x^{2r+1}}{(2r + 1)!} = \frac{x}{cosh x} .  (29)

They may be expressed in terms of the Secant numbers S_{r}, which comprise OEIS sequence \underline{A000364}. In view of (17), we obtain a special value of the Dumont-Foata polynomials:

F_{r+1} (\frac{1}{2}, \frac{1}{2}, \frac{1}{2}) = 2^{−2r}(2r + 1)S_{r}.  (30)

\begin{matrix}z & P_{r}(z) & Q_{r}(z) & \overline{P}_{r}(z) & \overline{Q}_{r}(z) \\ 0 & δ_{0,r} & δ_{0,r} & (−1)^{r}(2r + 1)S_{r} & 1 \\ 1 & 1 & max(1, 2^{r−1}) & 1 & (3^{2r} + 3)/4 \\ ∞ & r! & (2r)!/(2^{r}r!) & 2^{2r}r! & (2r)!/r! \end{matrix}

Table 1: Special values of the polynomials

The values \overline{Q}_{r}(1) comprise OEIS sequence \underline{A054879}. The values in the last row of Table 1 may also be found in OEIS: they are sequences \underline{A000142}, \underline{A001147}, \underline{A047053}, and \underline{A001813}.

Tuenter [7] observed that, for r ≥ 1, the constant terms of −P_{r}(n)/n are the Genocchi numbers (\underline{A001469}), and the constant terms of (−1)^{r−1}Q_{r}(n)/n are the reduced tangent numbers (\underline{A002105}).

References

[1] R. P. Brent, Generalising Tuenter’s binomial sums, preprint,

   http://arxiv.org/abs/1407.3533v4/, January 19 2015.

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

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

November 6 2014.

[3] L. Carlitz, Explicit formulas for the Dumont-Foata polynomial, Discrete Math. 30 (1980), 211–225.

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

[5] A. P. Hillman, The William Lowell Putnam mathematical competition, Amer. Math. Monthly 82 (1975), 905–912.

[6] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, published elec-

   tronically at http://oeis.org.

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

2010 Mathematics Subject Classification: Primary 05A10; Secondary 11B65, 05A15, 05A19, 44A60, 60G50. Keywords: Bernoulli random walk, binomial sum identity, Catalan number, Dumont-Foata polynomial, explicit formula, generating function, Genocchi number, moment, polynomial interpolation, secant number, tangent number.

(Concerned with sequences \underline{A000142}, \underline{A000364}, \underline{A001147}, \underline{A001469}, \underline{A001813}, \underline{A002105}, \underline{A009843}, \underline{A036970}, \underline{A047053}, \underline{A054879}, \underline{A083061}, \underline{A160485}, and \underline{A245244}.)

Received July 16 2014; revised versions received January 18 2015; January 25 2015. Published in Journal of Integer Sequences, January 26 2015.

Return to Journal of Integer Sequences home page.