Unimodality of Certain Sequences Connected With Binomial Coefficients

Hacène Belbachir and Farid Bencherif

Department of Mathematics USTHB Po. Box 32

El Alia, Algiers

Algeria

hbelbachir@usthb.dz
hacenebelbachir@gmail.com
fbencherif@usthb.dz
fbencherif@yahoo.fr

László Szalay^{1}

Institute of Mathematics and Statistics

University of West Hungary Erzsébet utca 9 H-9400 Sopron Hungary

laszalay@ktk.nyme.hu

Abstract

This paper is devoted to the study of certain unimodal sequences related to binomial coefficients. Although the paramount purpose is to prove unimodality, in a few cases we even determine the maxima of the sequences. Our new results generalize some earlier theorems on unimodality. The proof techniques are quite varied.

1This research is supported by the János Bolyai Scholarship of HAS, and by the Hungarian National Foundation for Scientific Research Grant No. T 048954 MAT, No. K 61800 FT2.

1 Introduction

Let {H_{n}}_{n=0}^{∞} denote a binary recurrence sequence defined by the initial values H_{0} ∈ ℝ and H_{1} ∈ ℝ, not both zero, and the recurrence relation

H_{n} = AH_{n−1} + BH_{n−2}, (n ≥ 2),

where the coefficients A and B are also real numbers. Moreover, let

h_{n,k} = A^{n−2k}B^{k}\binom{n − k}{k} (H_{1} + \frac{k}{n − 2k + 1}AH_{0}) ,  k = 0, …, ⌊\frac{n}{2}⌋ .  (1)

The sequences {H_{n}}_{n} and {h_{n,k}}_{k} are strongly linked since

H_{n+1} = (n mod 2) · B^{\frac{n+1}{2}} H_{0} + \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} h_{n,k}, (n ≥ 0).

In what follows, for the natural numbers n and k we denote the floor ⌊\frac{n}{k}⌋ by n_{k}.

For instance, if A = B = H_{1} = 1 and H_{0} = 0 then the Fibonacci sequence {F_{n}}_{n=0}^{∞}, and the well-known F_{n+1} = ∑_{k=0}^{n_{2}} \binom{n−k}{k} identity are obtained.

One of the purposes of this paper is to investigate the unimodality of the sequence {h_{n,k}}_{k}. A finite sequence of real numbers {a_{k}}_{k=0}^{m} (m ≥ 1) is unimodal if there exists an integer l ∈ {0, …, m} such that the subsequence {a_{k}}_{k=0}^{l} increases, while {a_{k}}_{k=l}^{m} decreases. If a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{l_{0}−1} < a_{l_{0}} = ⋯ = a_{l_{1}} > a_{l_{1}+1} ≥ ⋯ ≥ a_{m} then the integers l_{0}, …, l_{1} are the modes of {a_{k}}_{k=0}^{m}. In case of l_{0} = l_{1} we talk about a peak, otherwise the set of modes is called a plateau. Naturally, these definitions can even be extended to infinite sequences. For positive sequences, unimodality is implied by strict log-concavity. A sequence {a_{k}}_{k=0}^{m} is said to be strictly log-concave (SLC for short) if a_{l}^{2} > a_{l−1}a_{l+1}, 1 ≤ l ≤ m − 1.

Theorems 2.1-2.3 discuss three classes of (1) and generalize most of the earlier results on unimodality of the sequences related to binomial coefficients. Generally, {h_{n,k}}_{k} is not unimodal, not even if A and B are positive. For example, let A = B = 1, further H_{0} = −8, H_{1} = 5. Now

h_{8,k} = 5, 27, 27, − 30, − 27, (k = 0, …, 4)

is not unimodal.

The first result dealing with unimodality of the elements of the Pascal triangle is due to Tanny & Zuker [3], who showed that \binom{n−k}{k} (k = 0, …, n_{2}) is unimodal. They [4, 5] also investigated the unimodality of \binom{n−αk}{k}. In this work we also treat certain cases of the binomial sequence \binom{n+αk}{βk}.

Benoumhani [2] proved the unimodality of the sequence \frac{n}{n−k} \binom{n−k}{k} connected to Lucas numbers. Recently, Belbachir and Bencherif [1] proved that the sequences 2^{n−2k}\binom{n−k}{k} and 2^{n−2k} \frac{n}{n−k} \binom{n−k}{k} linked to Pell sequence and its companion sequence are unimodal. In all the aforesaid cases the authors descibe the peaks and the plateaus with two elements, the elements in which the monotonity changes.

2 Results

Theorem 2.1. Suppose that A and B are given real numbers with A > 0, moreover H_{0} = 0 and H_{1} = 1. Assuming that n ≥ 2, the sequence

h_{n,k} = A^{n−2k}B^{k}\binom{n − k}{k}, (k = 0, …, n_{2})

is unimodal if and only if B ≥ 0. In this case the peak k = p_{n} of {h_{n,k}} satisfies

p_{n} ∈ \{⌊\frac{n}{2} (1 − \frac{1}{\sqrt{4c + 1}})⌋ , ⌈\frac{n}{2} (1 − \frac{1}{\sqrt{4c + 1}})⌉\} ,

and the plateau with two elements may occur at the places p_{n} and p_{n} + 1.

Obviously, h_{n,k} cannot be unimodal with negative B, and trivially unimodal when B = 0. Considering A and B as two natural numbers, a combinatorial interpretation of A^{n−2k}B^{k}\binom{n−k}{k} is the number of words formed with the letters R, S_{1}, …, S_{A}, T_{1}, …, T_{B} of length n, beginning vith k consecutive R’s and containing exactly k letters choosing among {T_{1}, …, T_{B}}.

A similar theorem to Theorem 2.1 is true for the companion sequence of H_{n}.

Theorem 2.2. Let A > 0 and B denote real numbers, H_{0} = 2, H_{1} = A and let n ≥ 2 be an integer. The sequence

h_{n−1,k} = A^{n−2k}B^{k} \frac{n}{n − k} \binom{n − k}{k}, (k = 0, …, n_{2})

is unimodal if and only if B ≥ 0. The description of peaks and plateaus coincide as we have in Theorem 2.1.

The choice H_{0} = 0 and H_{1} = 1 makes the formula (1) as simple as possible. The following theorem does not fix the initial values, but only the coefficients.

Theorem 2.3. Assume that the initial values H_{0} and H_{1} are positive, A = B = 1 and n ≥ 2. Under these conditions the sequence

h_{n,k} = \binom{n − k}{k} (H_{1} + \frac{k}{n − 2k + 1}H_{0}) , (k = 0, …, n_{2})

is also unimodal.

Another direction is to investigate the unimodality of the sequence \binom{n+αk}{βk}, where α and β ≥ 0 are integers. If either α or β is zero then unimodality is trivial, as well as with (α, β) = (1, 1). The case (α, β) = (−1, 1) has been treated in [3], while α < −1, β = 1 in [4] and [5].

The first pair worth considering is (α, β) = (−1, 2), when h_{n,k} = \binom{n−k}{2k}. Note that if a_{n} = ∑_{k=0}^{n_{3}} \binom{n−k}{2k} then the terms of \{a_{n}\} satisfy the recurrence relation a_{n} = a_{n−1}+a_{n−2}+a_{n−4} with the initial values a_{0} = a_{1} = a_{2} = 1 and a_{3} = 2 (Sloane: A005251).

Theorem 2.4. The sequence h_{n,k} = \binom{n−k}{2k} is unimodal (k = 0, …, n_{3}).

A more interesting pair is (α, β) = (1, 2). Now F_{2n+1} = ∑_{k=0}^{n} \binom{n+k}{2k} (Sloane: A001519). Note that the sequence a_{n} = F_{2n+1} satisfies a_{n} = 3a_{n−1} − a_{n−2} (n ≥ 2).

Theorem 2.5. The sequence h_{n,k} = \binom{n+k}{2k} is unimodal (k = 0, …, n). A plateau exists if and only if n = (F_{12u+4} − 1)/2 or n = (F_{12u+8} − 1)/2 with k = (L_{12u+4} − 7)/10 or k = (L_{12u+8} − 7)/10 (u ∈ ℕ), respectively.

For numerical examples, see the following two tables.

\begin{matrix}u & F_{12u+4} & n & L_{12u+4} & k & \binom{n+k}{2k} = \binom{n+k+1}{2k+2} \\ 0 & 3 & 1 & 7 & 0 & \binom{1}{0} = \binom{2}{2} \\ 1 & 987 & 493 & 2207 & 220 & \binom{713}{440} = \binom{714}{442} \\ 2 & 317811 & 158905 & 710647 & 71064 & \binom{229969}{142128} = \binom{229970}{142130} \end{matrix}

\begin{matrix}u & F_{12u+8} & n & L_{12u+8} & k & \binom{n+k}{2k} = \binom{n+k+1}{2k+2} \\ 0 & 21 & 10 & 47 & 4 & \binom{14}{8} = \binom{15}{10} \\ 1 & 6765 & 3382 & 15127 & 1512 & \binom{4894}{3024} = \binom{4895}{3026} \\ 2 & 2178309 & 1089154 & 4870847 & 487084 & \binom{1576238}{974168} = \binom{1576239}{974170} \end{matrix}

Finally, let us consider the case (1, β). For instance, if β = 3 then the numbers ∑_{k=0}^{n_{2}} \binom{n+k}{3k} give every third term of the Padovan sequence {p_{n}} determined by p_{n} = p_{n−2} + p_{n−3} and p_{0} = 1, p_{1} = p_{2} = 0 (Sloane: A003522). Theorem 2.6 partially generalizes Theorem 2.5.

Theorem 2.6. The sequence h_{n,k} = \binom{n+k}{βk} is unimodal (2 ≤ β ∈ ℕ, k = 0, …, n_{β−1}).

The strict log-concavity is only utilized in the proof of Theorem 2.6, because it really simplifies the treatment. In the rest of the cases we start from the definition of unimodality, which is useful mainly where the peaks and plateaus are also aimed to determined. Finally, we draft two conjectures on Pascal triangles.

Conjecture 1. Let \binom{n}{k} be a fixed element of the Pascal triangle crossed by a ray. The sequence of binomial coefficents located along this ray is unimodal.

Conjecture 2. Take a generalized Pascal triangle corresponded to the Tribonacci sequence given by T_{n} = T_{n−1} + T_{n−2} + T_{n−3} (n ≥ 3) and T_{0} = T_{1} = 0, T_{2} = 1. This triangle contains the elements

\binom{n}{k}_{2} = \begin{matrix}⌊ & \frac{k}{2} & ⌋ \\ ∑ \\ i=m \end{matrix} \frac{n!}{i! · (k − 2i)! · (n − k + i)!} = \begin{matrix}⌊ & \frac{k}{2} & ⌋ \\ ∑ \\ i=m \end{matrix} \binom{n}{n − i}\binom{n − i}{k − 2i}

with m = max\{0 , k − n\}. We conjecture that the sequence \binom{n−k}{k}_{2} is unimodal.

3 Proofs

Proof of Theorem 2.1. There remains only the case B > 0 to consider. The inequality

A^{n−2k}B^{k}\binom{n − k}{k} ≤ A^{n−2(k+1)}B^{k+1}\binom{n − (k + 1)}{k + 1}, (k = 0, …, n_{2} − 1)

is equivalent to

0 ≤ (4c + 1)k^{2} − (4c + 1)kn + cn^{2} + (2c + 1)k − (c + 1)n  (2)

with c = B/A^{2} > 0. Multiplying (2) by 4(4c + 1) it can be rewritten as

(4c + 1)(n + 1)^{2} + 4c^{2} ≤ ((4c + 1)(2k − n) + (2c + 1))^{2} .  (3)

It is easy to check that (4c + 1)(2k − n) + (2c + 1) < 0. Consequently, by (3) we have

k ≤ t_{n} = \frac{(4c + 1)n − (2c + 1) − \sqrt{(4c + 1)(n + 1)^{2} + 4c^{2}}}{2(4c + 1)} .  (4)

Put t_{n}^{⋆} = (n/2)(1 − 1/\sqrt{4c + 1}). From −1 < t_{n} − t_{n}^{⋆} < 0 it follows that the peak p_{n} of \{h_{n,k}\} is one of ⌊t_{n}^{⋆}⌋ and ⌈t_{n}^{⋆}⌉. When t_{n} is a natural number then {h_{n,k}} possesses a plateau with two elements at k = p_{n} and k = p_{n} + 1. Obviously, plateaus can be identified by the positive integer solutions x, y of the Pell equation (4c + 1)(x + 1)^{2} + 4c^{2} = y^{2}.

Remark 3.1. Formula (4) returns with

k ≤ \frac{5n − 3 − \sqrt{5n^{2} + 10n + 9}}{10} and k ≤ \frac{4n − 3 − \sqrt{8n^{2} + 16n + 9}}{8}

in the particular case of Fibonacci and Pell sequences (see [3] and [1]), respectively.

Proof of Theorem 2.2. Suppose that B > 0 and follow the steps of the proof of Theorem 2.1. Thus we can transform h_{n,k} ≤ h_{n,k+1} into

0 ≤ (4c + 1)k^{2} − (4c + 1)kn + cn^{2} + (2c + 2)k − (c + 1)n + 1,  (5)

(c = B/A^{2}) and by a suitable multiplication of (5) we have

(4c + 1)n^{2} + 4c(c − 2) ≤ ((4c + 1)(2k − n) + (2c + 2))^{2} .

Hence

k ≤ \frac{(4c + 1)n − (2c + 2) − \sqrt{(4c + 1)n^{2} + 4c(c − 2)}}{2(4c + 1)}.  (6)

Now we find again that p_{n} is ⌊t_{n}^{⋆}⌋ or ⌈t_{n}^{⋆}⌉ with the same t_{n}^{⋆} we had in Theorem 2.1. For plateaus the diophantine equation (4c + 1)x^{2} + 4c(c − 2) = y^{2} should be investigated.

Remark 3.2. The inequality (6) provides formulae

k ≤ \frac{5n − 4 − \sqrt{5n^{2} − 4}}{10} and k ≤ \frac{4n − 5 − \sqrt{8n^{2} − 7}}{8}

in case of Lucas numbers and the companion sequence of Pell numbers (see [2] and [1]), respectively.

Proof of Theorem 2.3. Now A = B = 1 and the inequality h_{n,k} ≤ h_{n,k+1} provides

(n − k)(k + 1) (H_{1}(n − 2k + 1) + H_{0}k) ≤
(n − 2k + 1)(n − 2k) (H_{1}(n − 2k − 1) + H_{0}(k + 1)) ,

which is equivalent to 0 ≤ f_{n}(k) = ∑_{i=0}^{3} e_{i}(n)k^{i}, where

e_{0}(n) = n^{3} + (h − 1)n^{2} + (h − 2)n,
e_{1}(n) = (h − 7)n^{2} + (−4h + 2)n + (−2h + 3),
e_{2}(n) = (−5h + 15)n + (3h − 1),
e_{3}(n) = 5h − 10,

and h = H_{0}/H_{1} > 0. The special case h = 2 has essentially been treated by Benoumhani [2]. Therefore, by the sign of e_{3}(n), we must distinguish two cases.

Firstly, we assume that h > 2, which entails positive leading coefficient in the polynomial f_{n}(k) of degree three. Since f_{n}(0) = e_{0}(n) > 0 and f_{n}(n/2) = −(hn^{3}+(2h+2)n^{2}+4n)/8 < 0, it follows that f_{n}(k) possesses exactly one zero in the interval [0; n/2]. Hence h_{n,k} is unimodal.

Now, the assertion 0 < h < 2 implies e_{3}(n) < 0. The reader can easily verify that f_{n}(0) = n(n^{2} + (h − 1)n + (h − 2)) is positive if n ≥ 2 and f_{n}(n/2) < 0 as it has already been occurred previously. But the negative leading coefficient e_{3}(n) causes ambiguous structure for the zeros of f_{n}(k). Therefore a deeper analysis is necessary to clarify the situation.

The polynomial

f′_{n}(k) = (15h − 30)k^{2} + ((−10h + 30)n + (6h − 2)) k+
+ ((h − 7)n^{2} + (−4h + 2)n + (−2h + 3))

has two distinct real zeros because its discriminant

D = 20(2h^{2} − 3h + 3)n^{2} + 40(3h^{2} − 5h + 3)n + 4(39h^{2} − 111h + 91)

is positive when 0 < h < 2. Indeed, 2h^{2} − 3h + 3 > 0 and the discriminant

D_{1} = −960(h − 2)^{2}(11h^{2} − 19h + 19)

of D takes negative values on the interval ]0, 2[.

To finish the proof it is sufficient to show that the larger real zero f_{2} of f′_{n}(k) satisfies n/2 < f_{2}, more exactly

f_{2} = \frac{(10h − 30)n + (2 − 6h) − \sqrt{D}}{30h − 60} > \frac{n}{2}.

To do this it is enough to see that 2 − 6h − 5hn < \sqrt{D}, which is trivially true when h ≥ 1/3. Contrary, if h < 1/3, it suffices to confirm

0 < (−h + 2)n^{2} + (−4h + 4)n + (−8h + 12).  (7)

And (7) is fulfilled since its right hand side has no real zero under the given conditions.

Proof of Theorem 2.4. Starting with \binom{n−k}{2k} ≤ \binom{n−k−1}{2k+2}, we obtain

0 ≤ f(k) = −23k^{3} + (23n − 21)k^{2} + (−9n^{2} + 12n − 4)k + (n^{3} − 3n^{2}).

Since f(0) = n^{2}(n − 3) ≥ 0 if n ≥ 3, further f(n/3) = −4n(n + 3)(2n + 3)/27 < 0, it is sufficient to verify that f(k) is strictly monotone decreasing. And, really, if n ≥ 3 then f′(k) ≠ 0 implies the required monotonity.

Proof of Theorem 2.5. Assuming h_{n,k} ≤ h_{n,k+1}, it provides

0 ≤ f(k) = −5k^{2} − 7k + (n^{2} + n − 2).

Since k = −0.7 is the only solution of f′(k) = 0, it follows that f(k) is strictly decreasing in the interval [0; n − 1]. Further, the zeros of the polynomial f(k) are

f_{1,2} = \frac{7 ± \sqrt{20n^{2} + 20n + 9}}{−10},  (8)

the smaller f_{1} is negative, the larger f_{2} is approximately 0.45n since

f (\frac{n}{\sqrt{5}} − 1) · f (\frac{n}{\sqrt{5}}) = −\frac{4}{5}(4 + \sqrt{5})n^{2} − \frac{2}{5}(5 + 3\sqrt{5})n < 0

implies n/\sqrt{5} − 1 < f_{2} < n/\sqrt{5}. Thus h_{n,k} is unimodal, and its smallest mode k_{n} = ⌈f_{2}⌉ satisfies ⌊n/\sqrt{5}⌋ ≤ k_{n} ≤ ⌈n/\sqrt{5}⌉.

Now we inspect the existence of plateaus. By (8), we need to solve the Pell equation 20x^{2} + 20x + 9 = y^{2}. It is well known that

y^{2} − 5(2x + 1)^{2} = 4

implies y = L_{2v} and 2x + 1 = F_{2v}. A Fibonacci number with even suffix is odd if and only if 3 does not divide v. Put v = 3u ± 1. A simple verification shows that L_{6u±2} ≡ ±7 ( mod 10) depending on the parity of u. Choosing the appropriate cases we obtain f_{2} as positive integer.

Remark 3.3. Another proof can be obtained by introducing the function G_{n} (x) = ∑_{0≤k≤n} \binom{n+k}{2k}x^{k}, for which

G_{n} (x) = \frac{1}{x^{n}\sqrt{x^{2} + 4x}} ((\frac{x + \sqrt{x^{2} + 4x}}{2})^{2n+1} − (\frac{x − \sqrt{x^{2} + 4x}}{2})^{2n+1}) .

It suffices to see that

G_{n} (x) = (x + 2) G_{n−1} (x) − G_{n−2} (x) , G_{0} (x) = 1, G_{1} (x) = x + 1.

We deduce that G_{n} (x) admits n distinct real zeros given by

x_{k} = −2 (1 + cos \frac{2kπ}{2n + 1}) , k = 1, 2, …, n,

and then the sequence \binom{n+k}{2k} is SLC, which gives unimodality with a peak or a plateau with two elements.

For m ≥ 3 let denote {α_{m}}_{m≥−1} and {β_{m}}_{m≥−1} sequences defined by

\{ \begin{matrix}(α_{−1}, α_{0}, α_{1}, α_{2}) = (−11, −2, 1, 10) and α_{m} = 322α_{m−2} − α_{m−4} + 160, \\ (β_{−1}, β_{0}, β_{1}, β_{2}) = (4, 0, 0, 4) and β_{m} = 322β_{m−2} − β_{m−4} + 224. \end{matrix}

The integers n for which the sequences \binom{n+k}{2k}, (k = 0, 1, …, n) admit a plateau with two elements {k_{n}, k_{n} + 1} are exactly the integers α_{s}, s ≥ 1 such that k_{α_{s}} = β_{s} for s ≥ 1.

\begin{matrix}s & n = α_{s} & k_{n} = β_{s} \\ 1 & 1 & 0 \\ 2 & 10 & 4 \\ 3 & 493 & 220 \\ 4 & 3382 & 1512 \\ 5 & 158905 & 71064 \\ 6 & 1089154 & 487084 \end{matrix}

Proof of Theorem 2.6 We show that h_{n,k} is strictly log-concave, or more precisely

\binom{n + k}{βk}^{2} > \binom{n + k − 1}{βk − β}\binom{n + k + 1}{βk + β}.  (9)

Put b = β − 1 ≥ 1. Thus (9) is equivalent to

\frac{(n + k)(n − bk + 1)}{(n + k + 1)(n − bk)} · ∏_{i=0}^{β−1} (1 + \frac{β}{βk − i}) · ∏_{j=1}^{b−1} (1 + \frac{b + 1}{n − bk − j} ) > 1.

Since (n + k)(n − bk + 1) > (n + k + 1)(n − bk) > 0, further the other multipliers are trivially greater than 1, the statement is proved.

References

[1] H. Belbachir and F. Bencherif, Unimodality of sequences associated to Pell numbers, preprint.

[2] M. Benoumhani, A sequence of binomial coefficients related to Lucas and Fibonacci numbers, J. Integer Seq., 6 (2003), Article 03.2.1.

[3] S. Tanny and M. Zuker, On a unimodality sequence of binomial coefficients, Discrete Math., 9 (1974), 79–89.

[4] S. Tanny and M. Zuker, On a unimodal sequence of binomial coefficients, J. Combin. Inform. System Sci., 1 (1976), 81–91.

[5] S. Tanny and M. Zuker, Analytic methods applied to a sequence of binomial coefficients, Discrete Math., 24 (1978), 299–310.

2000 Mathematics Subject Classification: Primary 11B65; Secondary 05A10, 11B39 . Keywords: binomial coefficients, unimodality, log-concavity, linear recurrences.

(Concerned with sequences \underline{A001519}, \underline{A003522}, and \underline{A005251}.)

Received November 27 2006; revised version received January 16 2007. Published in Journal of Integer Sequences, January 17 2007.

Return to Journal of Integer Sequences home page.