Mean Value Inequalities for Motzkin Numbers

Takashi Agoh Department of Mathematics Tokyo University of Science

Noda, Chiba 278-8510

Japan

agoh takashi@ma.noda.tus.ac.jp

Horst Alzer Morsbacher Straße 10

51545 Waldbröl

Germany

h.alzer@gmx.de

Abstract

Following up on results of Aigner, we present some inequalities for Motzkin numbers M_{n}. In particular, we prove that the sequence (1/M_{n})_{n≥1} is strictly convex.

1 Introduction

The Motzkin numbers, named after the American mathematician Theodore S. Motzkin (1908–1970), are defined by

M_{n} = ∑_{k=0}^{⌊n/2⌋} \frac{1}{k + 1}\binom{2k}{k}\binom{n}{2k} (n = 0, 1, 2, …).

They satisfy the recurrence relation

M_{n} = \frac{2n + 1}{n + 2}M_{n−1} + \frac{3(n − 1)}{n + 2}M_{n−2} (n ≥ 2).  (1)

The generating function is given by

\frac{1}{2x^{2}} (1 − x − \sqrt{1 − 2x − 3x^{2}})= ∑_{n=0}^{∞} M_{n}x^{n}.

Here are the first few Motzkin numbers (see the sequence \underline{A001006} in [3]):

1, 1, 2, 4, 9, 21, 51, 127, 323, 835.

The Motzkin numbers have interesting applications in number theory and geometry, and they play an important role in various counting problems. For instance, M_{n} is the number of paths from (0, 0) to (n, 0) in the integer plane ℤ × ℤ which never dip below the x-axis and use only steps (1, 0), (1, 1) and (1, −1). Donaghey and Shapiro [2] presented a selection of 14 situations where these numbers occur; also see Stanley [4].

This note was inspired by an interesting paper published by Aigner [1] in 1998. He used tools from linear algebra to prove the inequalities

M_{n} < 3M_{n−1} (n ≥ 1),  (2)
M_{n}^{2} ≤ M_{n−1}M_{n+1} (n ≥ 1),  (3)

and the limit relation

lim_{n→∞} \frac{M_{n−1}}{M_{n}} = \frac{1}{3}.

A combinatorial proof of (3) was given by Sun and Wang [5]. From (3) we conclude that the sequence (M_{n})_{n≥0} is log-convex.

Here, we present counterparts of (3). In particular, we show that the sequence (1/M_{n})_{n≥1} is strictly convex. This result and (3) lead to the double-inequality

\frac{2}{1/M_{n−1} + 1/M_{n+1}} < M_{n} ≤ \sqrt{M_{n−1}M_{n+1}} (n ≥ 2).

Therefore, we see that if n ≥ 2, then M_{n} separates the harmonic and geometric means of M_{n−1} and M_{n+1}.

We introduce the following notation. Let a and b be positive real numbers. The weighted harmonic and geometric means of a and b are defined by

H_{t}(a, b) = \frac{1}{t/a + (1 − t)/b} and G_{t}(a, b) = a^{t}b^{1−t} (0 ≤ t ≤ 1),

respectively. For t = 1/2 we obtain the unweighted harmonic and geometric means of a and b as follows:

H(a, b) = \frac{2ab}{a + b} and G(a, b) = \sqrt{ab}.

Moreover, let

F_{t}(a, b) = tG(a, b) + (1 − t)H(a, b) (t ∈ ℝ).

We remark that there is a connection between F_{t}(a, b) and the so-called Heron means,

K_{t}(a, b) = tA(a, b) + (1 − t)G(a, b),

where A(a, b) = (a + b)/2 denotes the arithmetic mean of a and b. We have

A(a, b)F_{t}(a, b) = G(a, b)K_{t}(a, b).

2 Inequalities

First, we offer lower and upper bounds for M_{n} in terms of weighted harmonic and geometric means of M_{n−1} and M_{n+1}.

Theorem 1. Let v, w ∈ (0, 1). The inequalities

H_{v}(M_{n−1}, M_{n+1}) ≤ M_{n} ≤ G_{w}(M_{n−1}, M_{n+1})  (4)

hold for all n ≥ 2 if and only if v ≥ 5/14 = 0.35714 … and w ≤ 1/2.

Proof. We assume that (4) is valid for all n ≥ 2. Then,

H_{v}(M_{2}, M_{4}) ≤ M_{3} and M_{2} ≤ G_{w}(M_{1}, M_{3}).

This leads to

\frac{1}{v/2 + (1 − v)/9} ≤ 4 and 2 ≤ 4^{1−w}.

It follows that v ≥ 5/14 and w ≤ 1/2.

Next, let w ≤ 1/2 and λ_{n} = M_{n−1}/M_{n}. From (3) we obtain λ_{n} ≤ λ_{2} = 1/2 for n ≥ 2. Thus,

G_{w}(M_{n−1}, M_{n+1}) = (λ_{n}λ_{n+1})^{w}M_{n+1}
≥ (λ_{n}λ_{n+1})^{1/2}M_{n+1}
= G_{1/2}(M_{n−1}, M_{n+1}) ≥ M_{n}.

The left-hand side of (4) is equivalent to

Q_{n} ≤ v, where

Q_{n} = \frac{M_{n−1}(M_{n+1} − M_{n})}{M_{n}(M_{n+1} − M_{n−1})} = \frac{λ_{n}(1 − λ_{n+1})}{1 − λ_{n}λ_{n+1}}.

It remains to show that for n ≥ 2,

Q_{n} ≤ \frac{5}{14}.  (5)

We have Q_{2} = 1/3 and Q_{3} = 5/14. Let n ≥ 4. Inequality (5) can be written as

0 ≤ \frac{5}{λ_{n}} + 9λ_{n+1} − 14.

Applying (1) gives

\frac{1}{λ_{n}} = \frac{2n + 1 + 3(n − 1)λ_{n−1}}{n + 2} and λ_{n+1} = \frac{n + 3}{2n + 3 + 3nλ_{n}} .  (6)

From (3) we conclude that λ_{n} ≤ λ_{n−1}, so that we get

λ_{n+1} ≥ \frac{n + 3}{2n + 3 + 3nλ_{n−1}} .  (7)

Using (6) and (7) yields

\frac{5}{λ_{n}} + 9λ_{n+1} − 14 ≥ \frac{5(2n + 1 + 3(n − 1)λ_{n−1})}{n + 2} + \frac{9(n + 3)}{2n + 3 + 3nλ_{n−1}} − 14
= \frac{S_{n}}{(n + 2)(2n + 3 + 3nλ_{n−1})},

where

S_{n} = n^{2} − 13n − 15 + 9(2n^{2} − 6n − 5)λ_{n−1} + 45(n^{2} − n)λ_{n−1}^{2}.

From (2) we obtain λ_{n−1} > 1/3. Thus,

S_{n} > n^{2} − 13n − 15 + 9(2n^{2} − 6n − 5)\frac{1}{3} + 45(n^{2} − n)\frac{1}{9} = 6(2n^{2} − 6n − 5) > 0.

This implies that (5) holds. The proof of Theorem 1 is now complete.

Our second result yields sharp bounds for M_{n} in terms of F_{t}(M_{n−1}, M_{n+1}). The following companion to (4) is valid. Theorem 2. Let α, β ∈ ℝ. The inequalities

F_{α}(M_{n−1}, M_{n+1}) ≤ M_{n} ≤ F_{β}(M_{n−1}, M_{n+1})  (8)

hold for all n ≥ 2 if and only if

α ≤ \frac{8}{3(11\sqrt{2} − 12)} = 0.74983 … and β ≥ 1.

Proof. First, we assume that (8) is valid for all n ≥ 2. Then we have

F_{α}(M_{2}, M_{4}) ≤ M_{3} and M_{2} ≤ F_{β}(M_{1}, M_{3}),

and hence,

\sqrt{18}α + \frac{36}{11}(1 − α) ≤ 4 and 2 ≤ 2β + \frac{8}{5}(1 − β).

Therefore, it follows that

α ≤ \frac{8}{3(11\sqrt{2} − 12)} and 1 ≤ β.

Applying (3) and the fact that F_{t}(a, b) is increasing with respect to t we obtain for β ≥ 1 and n ≥ 2,

M_{n} ≤ F_{1}(M_{n−1}, M_{n+1}) ≤ F_{β}(M_{n−1}, M_{n+1}).

Let

α_{0} = \frac{8}{3(11\sqrt{2} − 12)}.

We have to show that for n ≥ 2,

F_{α_{0}}(M_{n−1}, M_{n+1}) ≤ M_{n},

or, equivalently,

α_{0} ≤ R_{n},

where

R_{n} = \frac{M_{n} − H(M_{n−1}, M_{n+1})}{G(M_{n−1}, M_{n+1}) − H(M_{n−1}, M_{n+1})}.

By direct computation we find

R_{2} = 1, R_{3} = α_{0}, R_{4} = 0.932 …, R_{5} = 0.930 …, R_{6} = 0.958 …,

R_{7} = 0.966 …, R_{8} = 0.974 …, R_{9} = 0.979 …, R_{10} = 0.983 ….

Let n ≥ 11. It suffices to prove that R_{n} > 3/4, or, equivalently,

3G(M_{n−1}, M_{n+1}) + H(M_{n−1}, M_{n+1}) < 4M_{n}.  (9)

As before, let λ_{n} = M_{n−1}/M_{n}. Then, (9) can be written as

0 < U_{n} − V_{n},

where

U_{n} = 4 − 2(\frac{1}{λ_{n}} + λ_{n+1})^{−1} and V_{n} = 3\sqrt{λ_{n} \frac{1}{λ_{n+1}}} .

Using (6) gives

U_{n} = 4 − 2(\frac{1}{λ_{n}} + \frac{n + 3}{2n + 3 + 3nλ_{n}} )^{−1}

= \frac{2(4n + 6 + 3(n + 1)λ_{n} + 3nλ_{n}(1 − λ_{n}))}{2n + 3 + (4n + 3)λ_{n}}

and

V_{n} = 3\sqrt{λ_{n} \frac{2n + 3 + 3nλ_{n}}{n + 3}} .

Now we have

\begin{matrix}(U_{n}^{2} − V_{n}^{2})(n + 3)(2n + 3 + (4n + 3)λ_{n})^{2} \\ = P_{1}(λ_{n})n^{3} + P_{2}(λ_{n})n^{2} + P_{3}(λ_{n})n + P_{4}(λ_{n}) \end{matrix}  (10)

with

P_{1}(t) = −396t^{4} − 864t^{3} − 348t^{2} + 120t + 64,
P_{2}(t) = −540t^{4} − 2340t^{3} − 1260t^{2} + 636t + 384,
P_{3}(t) = −243t^{4} − 1512t^{3} − 1503t^{2} + 810t + 720,
P_{4}(t) = −243t^{3} − 378t^{2} + 189t + 432.

Since P′′_{j}(t) < 0 (j = 1, 2, 3, 4) for t ≥ 0, we conclude that the functions P_{1}, P_{2}, P_{3}, and P_{4} are concave on [0, ∞). It follows that, for t ∈ [0, 0.38],

P_{j}(t) ≥ m_{j} (j = 1, 2, 3, 4),

where

m_{j} = min{P_{j}(0), P_{j}(0.38)}.

We have

m_{1} = 3.68 …, m_{2} = 304.07 …, m_{3} = 720, m_{4} = 432.

Thus, it follows that P_{j}(t) > 0 (j = 1, 2, 3, 4). Since (λ_{n})_{n≥1} is decreasing, we obtain λ_{n} ≤ λ_{11} = 0.377 . . .. From (10) we conclude that U_{n}^{2} − V_{n}^{2} > 0, so that U_{n} + V_{n} > 0 leads to U_{n} − V_{n} > 0. This completes the proof of Theorem 2.

Remark 3.

(i) Computer calculations reveal that for n = 4, 5, …, 500 the lower bound given in (8) with α = 8/(33\sqrt{2} − 36) is greater than the lower bound in (4) with v = 5/14.

(ii) Aigner’s inequality (3) can be written as

\frac{M_{n} − M_{n−1}}{M_{n+1} − M_{n}} ≤ \frac{M_{n}}{M_{n+1}} .  (11)

It is possible to show that the following counterpart of (11) holds.

Theorem 4. For all n ≥ 2 we have

c_{0} \frac{M_{n}}{M_{n+1}} ≤ \frac{M_{n} − M_{n−1}}{M_{n+1} − M_{n}} ≤ c_{1} \frac{M_{n}}{M_{n+1}}

with the best possible constant factors c_{0} = 9/10 and c_{1} = 1.

This result can be proved by using the same method as in the proof of Theorem 2. So we omit the details.

3 Acknowledgments

We thank the referee for helpful comments.

References

[1] M. Aigner, Motzkin numbers, European J. Combin. 19 (1998), 663–675.

[2] R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory Ser. A 23 (1977), 291–301.

[3] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

   at https://oeis.org.

[4] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[5] H. Sun and Y. Wang, A combinatorial proof of the log-convexity of Catalan-like numbers, J. Integer Sequences 17 (2014), Article 14.5.2.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 05A20, 11B83. Keywords: Motzkin number, inequality, mean value.

(Concerned with sequences \underline{A001006} and \underline{A114473}.)

Received December 1 2020; revised version received May 27 2021. Published in Journal of Integer Sequences, June 2 2021.

Return to Journal of Integer Sequences home page.