A criterion for unimodality

George Boros Department of Mathematics, University of New Orleans New Orleans, LA 70148

                         gboros@math.uno.edu

Victor H. Moll^{1} Department of Mathematics, Tulane University New Orleans, LA 70118

                         vhm@math.tulane.edu

Submitted: January 23, 1999; Accepted February 2, 1999 Classification 05, 33, 40

Abstract

We show that if P (x) is a polynomial with nondecreasing, nonnegative coefficients, then the coefficient sequence of P (x + 1) is unimodal. Applications are given.

1. Introduction

A finite sequence of real numbers {d_{0}, d_{1}, ⋯, d_{m}} is said to be unimodal if there exists an index 0 ≤ m^{∗} ≤ m, called the mode of the sequence, such that d_{j} increases up to j = m^{∗} and decreases from then on, that is, d_{0} ≤ d_{1} ≤ ⋯ ≤ d_{m^{∗}} and d_{m^{∗}} ≥ d_{m^{∗}+1} ≥ ⋯ ≥ d_{m}. A polynomial is said to be unimodal if its sequence of coefficients is unimodal.

Unimodal polynomials arise often in combinatorics, geometry and algebra. The reader is referred to [2] and [3] for surveys of the diverse techniques employed to prove that specific families of polynomials are unimodal.

A sequence of positive real numbers {d_{0}, d_{1}, ⋯, d_{m}} is said to be logarithmically concave (or log-concave for short) if d_{j+1}d_{j−1} ≤ d_{j}^{2} for 1 ≤ j ≤ m − 1. It is easy to see that if a sequence is log-concave then it is unimodal [4]. A sufficient condition for log-concavity of a polynomial is given by the location of its zeros: if all the zeros of a polynomial are real and negative, then it is log-concave and therefore unimodal [4]. A second criterion for the log-concavity of a polynomial was determined by Brenti [2]. A sequence of real numbers is said to have no internal zeros if whenever d_{i}, d_{k} ≠ 0 and i < j < k then d_{j} ≠ 0. Brenti’s criterion states that if P (x) is a log-concave polynomial with nonnegative coefficients and with no internal zeros, then P (x + 1) is log-concave.

1www: <http://www.math.tulane.edu:80/~vhm>

2. The main result

Theorem 2.1. If P (x) is a polynomial with positive nondecreasing coefficients, then P (x + 1) is unimodal.

Proof. Observe first that P_{m,r}(x) := (1 + x)^{m+1} − (1 + x)^{r} with 0 ≤ r ≤ m is unimodal with mode at 1 + ⌊\frac{m}{2}⌋. This follows by induction on m ≥ r using P_{m+1,r}(x) = P_{m,r}(x) + x(1 + x)^{m+1}. For m even, P_{m+1,r} is the sum of two unimodal polynomials with the same mode. For m = 2t + 1, the modes are shifted by 1, so it suffices to check

a_{t+1} + \binom{m + 1}{t} ≤ a_{t+2} + \binom{m + 1}{t + 1} ,  (2.1)

where a_{t+1} is the coefficient of x^{t} in P_{m,r}(x). The case t ≥ r yields equality in (2.1). If t ≤ r − 2 then (2.1) is equivalent to r ≤ m + 2. The final case t = r − 1 amounts to 0 = \binom{m+1}{r−1} − \binom{m+1}{r+1} ≤ 1,

Now P (x + 1) = \frac{1}{x} (b_{0}P_{m,0}(x) + (b_{1} − b_{0})P_{m,1}(x) + ⋯ + (b_{m} − b_{m−1})P_{m,m}(x)), so P (x+1) is a sum of unimodal polynomials with the same mode, and hence unimodal.

We now restate Theorem 2.1 and offer an alternative proof.

Theorem 2.2. Let b_{k} > 0 be a nondecreasing sequence. Then the sequence

c_{j} := ∑_{k=j}^{m} b_{k} \binom{k}{j} , 0 ≤ j ≤ m  (2.2)

is unimodal with mode m^{∗} := ⌊\frac{m−1}{2}⌋.

Proof. For 0 ≤ j ≤ m − 1 we have

(j + 1)(c_{j+1} − c_{j}) = ∑_{k=j}^{m} b_{k} \binom{k}{j} × (k − 2j − 1).  (2.3)

Suppose first that j ≥ m^{∗}, and let m be odd so that m = 2m^{∗} + 1; the case m even is treated in a similar fashion. Every term in (2.3) is negative because, if j > m^{∗}, then k − 2j − 1 ≤ m − 2j − 1 = 2(m^{∗} − j) < 0, and for j = m^{∗},

(m^{∗} + 1)(c_{m^{∗}+1} − c_{m^{∗}}) = ∑_{k=m^{∗}}^{m−1} b_{k} \binom{k}{m^{∗}} × (k − m) < 0.  (2.4)

Thus c_{j+1} < c_{j}.

Now suppose 0 ≤ j < m^{∗} and define

T_{1} := ∑_{k=j}^{2j} b_{k} \binom{k}{j} (2j + 1 − k)  (2.5)

the electronic journal of combinatorics 6 (1999), #R10 3

and

T_{2} := ∑_{k=2j+2}^{m} b_{k} \binom{k}{j} (k − 2j − 1)  (2.6)

so that (j + 1)(c_{j+1} − c_{j}) = T_{2} − T_{1}. Then

T_{1} < b_{2j+2} ∑_{k=j}^{2j} \binom{k}{j} (2j + 1 − k) = b_{2j+2} \binom{2j + 2}{j} < T_{2}.

Thus c_{j+1} > c_{j}.

3. Examples

Example 1. The case P (x) = x^{n} in Theorem 2.1 gives the unimodality of the binomial coefficients. Example 2. For 0 ≤ k ≤ m − 1, define

b_{k}(m) := 2^{−2m+k} \binom{2m − 2k}{m − k} \binom{m + k}{m} (a + 1)^{k}

for 0 ≤ k ≤ m − 1. Then

\frac{b_{k+1}(m)}{b_{k}(m)} = \frac{(m − k)(m + k + 1)}{(2m − 2k − 1)(k + 1)} > 1

so the polynomial

P_{m}(a) := ∑_{k=0}^{m} b_{k}(m)(a + 1)^{k}

is unimodal. We encountered P_{m} in the integral formula [1]

∫_{0}^{∞} \frac{dx}{(x^{4} + 2ax^{2} + 1)^{m+1}} = \frac{π P_{m}(a)}{2^{m+3/2}(a + 1)^{m+1/2}} .  (3.1)

This does not appear in the standard tables. Example 3. For 0 ≤ k ≤ m − 1, define

b_{k}(m) := \frac{(−m − β)_{m}}{m!} \frac{(−m)_{k}(m + 1 + α + β)_{k}}{(β + 1)_{k} k! 2^{k}} .

Then, with α = m + ϵ_{1} and β = −(m + ϵ_{2}), we have

\frac{b_{k+1}(m)}{b_{k}(m)} = \frac{m − k}{m − k + ϵ_{2} − 1} × \frac{k − 1 + m + ϵ_{1} − ϵ_{2}}{2(k + 1)} > 1

provided 0 < ϵ_{1} ≤ ϵ_{2} < 1. Therefore the polynomial

P_{m}^{(α,β)}(a) := ∑_{k=0}^{m} b_{k}(m)(a + 1)^{k}

is unimodal. This is a special case of the Jacobi family, where the parameters α and β are not standard since they depend on m. These polynomials do not have real zeros, so their unimodality is not immediate. The case of Example 2 corresponds to ϵ_{1} = ϵ_{2} = \frac{1}{2}.

Example 4. Let n, m ∈ ℕ be fixed. Then the sequences

α_{j} := ∑_{k=j}^{m} n^{k} \binom{k}{j} , β_{j} := ∑_{k=j}^{m} k^{n} \binom{k}{j} , and γ_{j} := ∑_{k=j}^{m} k^{k} \binom{k}{j}

are unimodal for 0 ≤ j ≤ m.

Example 5. Let 2 < a_{1} < ⋯ < a_{p} and n_{1}, ⋯, n_{p} be two sequences of p positive integers. For 0 ≤ j ≤ m, define

c_{j} := ∑_{k=j}^{m} \binom{a_{1}m}{k}^{n_{1}} \binom{a_{2}m}{k}^{n_{2}} ⋯ \binom{a_{p}m}{k}^{n_{p}} \binom{k}{j} .  (3.2)

Then c_{j} is unimodal.

Acknowledgement. The authors wish to thank Doron Zeilberger for comments on an earlier version of this paper.

References

[1] BOROS, G. - MOLL, V.: An integral hidden in Gradshteyn and Rhyzik, J. Comp. Appl. Math., to appear.

[2] BRENTI, F.: Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry: an update. Contemporary Mathematics, 178, 71-84, 1994.

[3] STANLEY, R.: Log-concave and unimodal sequences in algebra, combinatorics and geometry. Graph theory and its applications: East and West (Jinan, 1986), 500-535, Ann. New York Acad. Sci., 576, New York, 1989.

[4] WILF, H.S.: generatingfunctionology. Academic Press, 1990.