Generalizing Tuenter’s Binomial Sums

Tuenter considered centered binomial sums of the form

$\begin{displaymath}S_r(n) = \sum_{k=0}^{2n} \binom{2n}{k}\vert n-k\vert^r,\end{displaymath}$

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

$\begin{displaymath}U_r(n) = \sum_{k=0}^n \binom{n}{k}\vert n/2-k\vert^r,\end{displaymath}$

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.

Generalizing Tuenter’s Binomial Sums

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

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