On a Conjecture of Andrica and Tomescu

Blair D. Sullivan^{1} Oak Ridge National Laboratory 1 Bethel Valley Road Oak Ridge, TN 37831 USA

                      sullivanb@ornl.gov

Abstract For positive integers n congruent to 0 or 3 (mod 4), let S(n) be the coefficient of x^{n(n+1)/4} in the expansion of (1 + x)(1 + x^{2}) ⋯ (1 + x^{n}) We prove a conjecture of Andrica and Tomescu that S(n) is asymptotically equal to \sqrt{\frac{6}{π}} · 2^{n} · n^{−3/2}.

1 Introduction

For positive integers n congruent to 0 or 3 (mod 4), let S(n) denote the coefficient of the middle term of the expansion of the polynomial (1 + x)(1 + x^{2}) ⋯ (1 + x^{n}). (In the case n ≡ 1, 2 (mod 4), the quantity n(n + 1)/4 is not an integer, and the expansion has no middle term.) This number also represents the number of partitions of T_{n}/2 = n(n + 1)/4 into distinct parts less than or equal to n, where T_{n} is the nth triangular number. Andrica and Tomescu conjectured that as n approaches infinity, S(n) behaves asymptotically like \sqrt{\frac{6}{π}} · 2^{n} · n^{−3/2}. More formally, writing f(n) ∼ g(n) as usual to denote

lim_{n→∞} \frac{f(n)}{g(n)} = 1,

we have Conjecture 1. [Andrica, Tomescu [1]] S(n) ∼ \sqrt{\frac{6}{π}} · 2^{n} · n^{−3/2} for n ≡ 0 or 3 (mod 4).

1The submitted manuscript has been authored by a contractor of the U.S. Government under Contract No. DE-AC05-00OR22725. Accordingly, the U.S. Government retains a non-exclusive, royalty-free license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes.

From [1], one can write S(n) in integral form via Cauchy’s formula as

S(n) = \frac{2^{n−1}}{π} ∫_{0}^{2π} cos(t) cos(2t) ⋯ cos(nt) dt.

We will use the Laplace method to estimate this integral [2]. Rewriting, we have S(n) = \frac{2^{n−1}}{π} ∫_{0}^{2π} f_{n}(t) dt where f_{n}(t) = ∏_{k=1}^{n} cos(kt). In Section 2, we analyze the behavior of f_{n}(t) and note a technical lemma needed for the main proof of Conjecture 1, which is presented in Section 3. We note that a similar approach was suggested in a review of [1] by Hwang [3] published in Mathematical Reviews.

2 Behavior of f_{n}(t)

Lemma 2. Let 0 < ε < 1/4, and f_{n}(t) = ∏_{k=1}^{n} cos(kt). Then ∫_{n^{−(3/2−ε)}<|t|<π/2} |f_{n}(t)| dt = o(n^{−3/2}) as n → ∞.

Proof. We break the integral into three pieces based on the value of |t|.

Case 1. n^{−( \frac{3}{2} −ε)} ≤ |t| ≤ \frac{1}{n}:

Since cos(x) = cos(−x), and cos is a monotone decreasing function on [0, π], f_{n}(t) = f_{n}(−t) is also monotone decreasing for t ∈ [0, 1/n], and it suffices to give an appropriate upper bound on f_{n}(n^{−(3/2−ε)}).

Since we need ∫_{n^{−(3/2−ε)}<|t|<π/2} f_{n}(t) dt = o(n^{−3/2}), given that 0 < ε < 1/4, it suffices to show that for a constant c > 0,

f_{n}(n^{−(3/2−ε)}) ≤ exp(−cn^{2ε}(1 + o(1))).

Using the Taylor series expansion, we know cos(kt) ≤ 1 − \frac{(kt)^{2}}{2!} + \frac{(kt)^{4}}{4!} . Substitution then yields

f_{n}(t) = ∏_{k=1}^{n} cos(kt) ≤ ∏_{k=1}^{n} (1 − \frac{(kt)^{2}}{2!} + \frac{(kt)^{4}}{4!} ) ,

since k ≤ n and |t| ≤ 1/n implies kt ≤ 1. When t = n^{−(3/2−ε)}, we have

f_{n}(t) ≤ ∏_{k=1}^{n} (1 − \frac{k^{2}n^{−(3−2ε)}}{2} + \frac{k^{4}n^{−(6−4ε)}}{24} ) .

To evaluate, we note the terms of this product are all in [0, 1], and apply log(1 − x) ≤ −x:

log ∏_{k=1}^{n} (1 − (\frac{k^{2}n^{−(3−2ε)}}{2} − \frac{k^{4}n^{−(6−4ε)}}{24} )) ≤ ∑_{k=1}^{n} (−\frac{k^{2}n^{−(3−2ε)}}{2} + \frac{k^{4}n^{−(6−4ε)}}{24} ) .

Writing ∑_{k=1}^{n} k^{2} = (1/3 + o(1))n^{3} and ∑_{k=1}^{n} k^{4} = (1/5 + o(1))n^{5}, we have

log f_{n} = − (\frac{1}{6} + o(1)) n^{3}n^{−(3−2ε)} + (\frac{1}{120} + o(1)) n^{5}n^{−(6−4ε)}.

Letting c = 1/6, f_{n} ≤ exp(−c(1 + o(1))n^{2ε} + c(1 + o(1))n^{−1+4ε}), and recalling ε < 1/4, f_{n} ≤ exp(−c(1 + o(1))n^{2ε}) as desired.

Case 2. \frac{1}{n} ≤ |t| ≤ \frac{π}{n}:

Here we use will the monotonicity of f_{n}(t) in n. It follows directly from f_{n}(t) = ∏_{k=1}^{n} cos(kt) and 0 ≤ cos(x) ≤ 1 that |f_{n}(t)| ≤ |f_{m}(t)| for n ≥ m. Let h_{n} = ⌊n/4⌋ be the greatest integer in n/4. Then |f_{n}(t)| ≤ |f_{h_{n}}(t)|. From Case 1, f_{h_{n}}(t) ≤ exp(−ch_{n}^{2ε}(1 + o(1))) for h_{n}^{−( \frac{3}{2} −ε)} ≤ |t| ≤ 1/h_{n}. Since 1/n > h_{n}^{−5/4} ≥ h_{n}^{−( \frac{3}{2} −ε)} for n > 1050 and h_{n} ≤ n/4 ≤ n/π implies π/n ≤ 1/h_{n}, we get |f_{n}(t)| ≤ exp(−ch_{n}^{2ε}(1 + o(1))) for t ≤ π/n as n → ∞.

Case 3. \frac{π}{n} ≤ |t| ≤ \frac{π}{2}:

Note that it suffices to show that |f_{n}(t)| ≤ c^{n} for a constant c < 1, since then

∫_{π/n≤|t|<π/2} |f_{n}(t)| dt ≤ π · c^{n} = o(n^{−3/2}).

To accomplish this, we first transform f_{n}(t) from a product to a sum using the arithmeticgeometric mean inequality:

(f_{n}^{2}(t))^{1/n} = (∏_{k=1}^{n} cos^{2}(kt))^{1/n} ≤ \frac{1}{n} ∑_{k=1}^{n} cos^{2}(kt).  (1)

The sum on the right-hand side can be simplified as

∑_{k=1}^{n} cos^{2}(kt) = \frac{n}{2} + \frac{1}{2} ∑_{k=1}^{n} cos(2kt) = \frac{n}{2} + \frac{cos((n + 1)t)}{2} \frac{sin(nt)}{sin(t)}.  (2)

Combining equations 1 and 2, we can write

|f_{n}(t)| ≤ (\frac{1}{2} + \frac{1}{2n} \frac{1}{sin(t)})^{n/2} .  (3)

We will now apply the Jordan-style concavity inequality | sin(t)| ≥ \frac{2|t|}{π} for 0 ≤ |t| ≤ π/2. For π/n ≤ |t| ≤ π/2, substitution in equation 3 gives

|f_{n}(t)| ≤ (\frac{1}{2} + \frac{1}{2n} \frac{π}{2|t|})^{n/2} = (\frac{1}{2} + \frac{π}{4n|t|})^{n/2} .

Observing that the right-hand side is monotonically decreasing in |t|, we have |f_{n}(t)| ≤ f_{n}(π/n). Evaluating, we see

|f_{n}(t)| ≤ (\frac{1}{2} − \frac{1}{2n})^{n/2}

proving |f_{n}(t)| ≤ (\sqrt{7/16})^{n} (since we may assume 2n ≥ 16 as n → ∞).

We will also need the following straightforward lemma from analysis.

Lemma 3. Let c ∈ ℝ and a(c), b(c) be real-valued functions such that

lim_{c→∞} −a(c)\sqrt{c} = lim_{c→∞} b(c)\sqrt{c} = ∞.

Then

∫_{a(c)}^{b(c)} e^{−ct^{2}} dt ∼ ∫_{−∞}^{∞} e^{−ct^{2}} dt

as c → ∞.

3 Main Result

We now prove Conjecture 1.

Theorem 4. For n ≡ 0 or 3 (mod 4), we have S(n) ∼ \sqrt{\frac{6}{π}} · 2^{n} · n^{−3/2}.

Proof. When n ≡ 0 or 3 (mod 4), f_{n}(t + mπ) = f_{n}(t) for any integer m, so

S(n) = \frac{2 · 2^{n−1}}{π} ∫− \frac{π}{2}^{\frac{π}{2}} f_{n}(t) dt,  (4)

and we may assume |t| ≤ π/2 when evaluating f_{n}(t).

By Lemma 2, ∫_{n^{−(3/2−ε)}<|t|<π/2} |f_{n}(t)| dt = o(n^{−3/2}), so it suffices to consider |t| < n^{−(3/2−ε)} when estimating f_{n}(t) around t = 0. Recalling

f_{n}(t) = ∏_{k=1}^{n} e^{ln(cos(kt))},

we first use Taylor series to approximate g_{k}(t) = ln(cos(kt)) at t = 0. We have g_{k}(t) = −k^{2}t^{2}/2+R_{2}, where R_{2} is the Lagrange remainder. Then R_{2} is bounded by a constant times t^{3}g_{k}^{(3)}(t_{0}) for some t_{0} near 0. Since g_{k}^{(3)}(t) = −2k^{3} sin(kt)/ cos^{3}(kt), and t_{0} is small (since |t| < n^{−(3/2−ε)}), we have that R_{2} ≤ ak^{3}t^{3} where a is constant. The absolute error for g_{k}(t) is thus bounded by ak^{3}n^{−(9/2−3ε)}.

Around t = 0, f_{n}(t) can be approximated as δ ∏_{k=1}^{n} e^{− \frac{k^{2}t^{2}}{2}} with error δ ≤ ∏_{k=1}^{n} e^{ak^{3}n^{−(9/2−3ε)}}. This simplifies to

f_{n}(t) ≈ e^{−t^{2}/2 ∑_{k=1}^{n} k^{2}} = e^{−t^{2}n(n+1)(2n+1)/12}.  (5)

Our error bound simultaneously simplifies to

δ ≤ e^{an^{−(9/2−3ε)} ∑_{k=1}^{n} k^{3}} = e^{an^{−(9/2−3ε)}n^{2}(n+1)^{2}/4}.

This proves that the error goes to one as n approaches infinity whenever ε < \frac{1}{6}. Substituting (5) for f_{n}(t) in equation 4, and applying Lemma 2, we find that

\frac{πS(n)}{2^{n}} = (1 + o(1)) ∫_{−n^{−(3/2−ε)}}^{n^{−(3/2−ε)}} e^{−n(n+1)(2n+1)t^{2}/12} dt + o(n^{−3/2}).

By Lemma 3, this implies

\frac{πS(n)}{2^{n}} = (1 + o(1)) ∫_{−∞}^{∞} e^{−n(n+1)(2n+1)t^{2}/12} dt + o(n^{−3/2}).

Using

∫_{−∞}^{∞} e^{−Ct^{2}} dt = \sqrt{\frac{π}{C}}

for any constant C > 0 and n(n + 1)(2n + 1) ∼ 2n^{3}, we have

S(n) ∼ \frac{2^{n}}{π} \sqrt{\frac{12π}{2n^{3}}} = \sqrt{\frac{6}{π}} · 2^{n} · n^{−3/2},

as desired.

4 Acknowledgments

This research was partially completed while the author was an intern at Microsoft Research, Redmond, WA. We thank Henry Cohn for suggesting the problem and providing comments which greatly improved the manuscript. Special thanks are due to Xavier Gourdon, who pointed out a flaw in an earlier version of the paper, and suggested the arithmetic-geometric mean inequality approach now used in the third case of Lemma 2.

References

[1] D. Andrica and I. Tomescu, On an integer sequence related to a product of trigonometric functions, and its combinatorial relevance, J. Integer Sequences 5 (2002), Article 02.2.4.

[2] N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, 1981.

[3] H.-K. Hwang, Review of [1], Math. Reviews, MR1938223 (2003j:05005).

2000 Mathematics Subject Classification: Primary 05A16. Secondary 11B75, 05A15, 05A18.

Keywords: triangular number, generating function, partition, asymptotic evaluation.

(Concerned with sequence \underline{A025591}.)

Received September 18 2008; revised versions received September 14 2012; February 14 2013. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page.