Moments of Reciprocals of Binomial Coefficients

Renzo Sprugnoli Dipartimento di Sistemi e Informatica Viale Morgagni 65 54134 Firenze Italy

                   renzo.sprugnoli@unifi.it

Abstract

We consider the distribution defined by the reciprocals of binomial coefficients and compute the corresponding moments. We find recurrence relations and the relative ordinary generating functions, which we give explicitly for the first six moments (m = 0, 1, …, 5). Finally we give asymptotic approximations of the moments and of related quantities.

1 Introduction

The present developments on moments of reciprocals of binomial coefficients are motivated by the paper [1] by H. Belbachir, M. Rahmani, and B. Sury on the same subject. The three authors obtain several results, but, in my opinion, a different approach to the problem can conveniently be considered to simplify proofs and to present expansions in a more straightforward way. Therefore, the aim of this note is to present this different approach to the evaluation of the moments in question, that is, the quantities

S_{n}^{(m)} = ∑_{k=0}^{n} k^{m}\binom{n}{k}^{−1}.  (1)

By using this formula, we obtain the generating functions of the first instances m = 0, 1, ⋯, 5, which are as follows:

S^{(0)}(t) = 1 + 2t + \frac{5}{2}t^{2} + \frac{8}{3}t^{3} + \frac{8}{3}t^{4} + \frac{13}{5}t^{5} + \frac{151}{60}t^{6} + \frac{256}{105}t^{7} + \frac{83}{35}t^{8} + \frac{146}{63}t^{9} + ⋯

S^{(1)}(t) = t + \frac{5}{2}t^{2} + 4t^{3} + \frac{16}{3}t^{4} + \frac{13}{2}t^{5} + \frac{151}{20}t^{6} + \frac{128}{15}t^{7} + \frac{332}{35}t^{8} + \frac{72}{7}t^{9} + ⋯

S^{(2)}(t) = t + \frac{9}{2}t^{2} + \frac{32}{3}t^{3} + \frac{115}{6}t^{4} + \frac{297}{10}t^{5} + \frac{2527}{60}t^{6} + \frac{1184}{21}t^{7} + \frac{2538}{35}t^{8} + \frac{815}{9}t^{9} + · · · .

S^{(3)}(t) = t + \frac{17}{2}t^{2} + 30 t^{3} + \frac{217}{3}t^{4} + \frac{283}{2}t^{5} + \frac{4863}{20}t^{6} + \frac{5744}{15}t^{7} + \frac{19832}{35}t^{8} + \frac{5601}{7}t^{9} + ⋯

S^{(4)}(t) = t+ \frac{33}{2}t^{2}+ \frac{260}{3}t^{3}+ \frac{1675}{6}t^{4}+ \frac{6861}{10}t^{5}+ \frac{85351}{60}t^{6}+ \frac{275776}{105}t^{7}+ \frac{156078}{35}t^{8}+ \frac{447725}{63}t^{9}+⋯

S^{(5)}(t) = t+\frac{65}{2}t^{2}+254 t^{3}+\frac{3271}{3}t^{4}+\frac{6715}{2}t^{5}+\frac{167591}{20}t^{6}+\frac{271568}{15}t^{7}+\frac{1232792}{35}t^{8}+\frac{443003}{7}t^{9}+⋯

These values will be useful for checking the formulas obtained below. The only sequence occurring in Sloane’s Encyclopedia [6] is related to S^{(0)}(t), which is the exponential generating function of sequence \underline{A003149}.

2 Basic relations

The first important result was obtained by T. B. Staver [7] more than 60 years ago. It is the starting point for studying the sums S_{n}^{(m)}. Theorem 1 (Staver, 1947). The following relation holds true for every n ∈ ℕ:

S_{n}^{(1)} = \frac{n}{2} S_{n}^{(0)}.

Proof. By the change of variable k ↦ n − k we obtain:

∑_{k=0}^{n} k\binom{n}{k}^{−1} = ∑_{k=0}^{n}(n − k)\binom{n}{k}^{−1}.

From this we get S_{n}^{(1)} = nS_{n}^{(0)} − S_{n}^{(1)} which is the theorem assertion.

The following observation plays a fundamental role in our present approach: Lemma 2. For every k ≤ n we have:

\binom{n + 1}{k}^{−1} = \binom{n}{k}^{−1} − \frac{k}{n + 1}\binom{n}{k}^{−1}.

Proof. We immediately have:

\binom{n + 1}{k}^{−1} = \frac{k!(n + 1 − k)!}{(n + 1)!} = \frac{k!(n − k)!(n + 1 − k)}{n!(n + 1)} = \frac{n + 1 − k}{n + 1} \binom{n}{k}^{−1}

and this is the relation to be proved.

This lemma implies an important recurrence relation, from which the successive results follow:

Theorem 3. The following relation holds true for every m, n ∈ ℕ:

S_{n+1}^{(m)} = S_{n}^{(m)} − \frac{1}{n + 1}S_{n}^{(m+1)} + (n + 1)^{m}.

Proof. We use the previous lemma and obtain:

S_{n+1}^{(m)} = ∑_{k=0}^{n+1} k^{m}\binom{n + 1}{k}^{−1} = ∑_{k=0}^{n} k^{m}\binom{n + 1}{k}^{−1} + (n + 1)^{m}\binom{n + 1}{n + 1}^{−1} =

= ∑_{k=0}^{n} k^{m}\binom{n}{k}^{−1} − ∑_{k=0}^{n} \frac{k^{m+1}}{n + 1}\binom{n}{k}^{−1} + (n + 1)^{m} = S_{n}^{(m)} − \frac{1}{n + 1}S_{n}^{(m+1)} + (n + 1)^{m}.

What follows will be derived by Staver’s theorem and Theorem 3. In fact, we are in a position to prove the recurrence of Staver:

Theorem 4. The sequence (S_{n}^{(0)}) satisfies the recurrence relation:

S_{n+1}^{(0)} = \frac{n + 2}{2(n + 1)}S_{n}^{(0)} + 1

with the initial condition S_{0}^{(0)} = 1.

Proof. We specialize the previous theorem by setting m = 0:

S_{n+1}^{(0)} = S_{n}^{(0)} − \frac{1}{n + 1}S_{n}^{(1)} + (n + 1)^{0},

and apply Staver’s theorem:

S_{n+1}^{(0)} = S_{n}^{(0)} − \frac{n}{2(n + 1)}S_{n}^{(0)} + 1.

This is the recurrence we were looking for.

This is a linear recurrence relation of the first order with non-constant coefficients. Knuth [4, Vol. 1] has shown that these recurrences can be solved with the summing factor method, but let us proceed in another way, passing through the generating function of our sequence.

Theorem 5. The generating function of the sequence (S_{n}^{(0)})_{n∈ℕ} satisfies the following differential equation^{1}:

(2 − t)Ṡ^{(0)}(t) = 2S^{(0)}(t) + \frac{2}{(1 − t)^{2}}

(with S^{(0)}(0) = 1), the solution of which is:

S^{(0)}(t) = \frac{2}{(1 − t)(2 − t)} − \frac{2 ln(1 − t)}{(2 − t)^{2}}.

1A superscripted dot denotes here differentiation by t.

Proof. From the recurrence relation found above, we get:

2(n + 1)S_{n+1}^{(0)} = nS_{n}^{(0)} + 2S_{n}^{(0)} + 2(n + 1).

By using the generating function (1 − t)^{−2} of the sequence (n + 1)_{n∈ℕ} and by applying the method of coefficients (see, e.g., [5]), we find:

2Ṡ^{(0)}(t) = tṠ^{(0)}(t) + 2S^{(0)}(t) + \frac{2}{(1 − t)^{2}}

which is the formula in the assertion. This differential equation can be integrated in an elementary way and the solution is the expression shown.

We now obtain Staver’s formula:

Theorem 6. The numbers S_{n}^{(0)} can be computed by the following non-closed formula:

S_{n}^{(0)} = [t^{n}]\frac{2}{(1 − t)(2 − t)} − [t^{n}]\frac{2 ln(1 − t)}{(2 − t)^{2}} = \frac{n + 1}{2^{n+1}} ∑_{k=1}^{n+1} \frac{2^{k}}{k} .

Proof. By applying partial fraction decomposition, we find:

\frac{2}{(1 − t)(2 − t)} = \frac{2}{1 − t} − \frac{1}{1 − t/2}

and we can easily extract the coefficient of t^{n}:

[t^{n}]\frac{2}{1 − t} − [t^{n}]\frac{1}{1 − t/2} = 2 − \frac{1}{2^{n}} .

We now extract the coefficient of the second part:

[t^{n}]\frac{1}{2(1 − t/2)^{2}} ln \frac{1}{1 − t} = \frac{1}{2} ∑_{k=1}^{n} \frac{1}{k} \frac{n − k + 1}{2^{n−k}} = \frac{n + 1}{2^{n+1}} ∑_{k=1}^{n} \frac{2^{k}}{k} − \frac{1}{2^{n+1}} ∑_{k=1}^{n} 2^{k}.

This latter sum can be extended to k = 0 by adding and subtracting 1; by applying the rule for the sum of a geometric progression, we find:

\frac{1}{2^{n+1}} ∑_{k=1}^{n} 2^{k} = \frac{1}{2^{n+1}} \frac{2^{n+1} − 1}{2 − 1} − \frac{1}{2^{n+1}} = 1 − \frac{1}{2^{n}} .

Finally, we put everything together:

S_{n}^{(0)} = 2 − \frac{1}{2^{n}} + \frac{n + 1}{2^{n+1}} ∑_{k=1}^{n} \frac{2^{k}}{k} − 1 + \frac{1}{2^{n}} = \frac{n + 1}{2^{n+1}} ∑_{k=1}^{n+1} \frac{2^{k}}{k} .

The last passage is true since the contribution of the term with k = n + 1 is just 1.

Bender’s theorem (see [2]) gives S_{n}^{(0)} ∼ 2, but we can obtain an asymptotic expansion:

Theorem 7. We have the following asymptotic expansion:

S_{n}^{(0)} = 2 + \frac{2}{n} + \frac{4}{n(n − 1)} + \frac{12}{n(n − 1)(n − 2)} + O (\frac{1}{n^{4}} ) = 2 + \frac{2}{n} + \frac{4}{n^{2}} + \frac{16}{n^{3}} + O (\frac{1}{n^{4}} ) .

Proof. Since 2^{−n} is exponentially small, in the proof of the previous theorem, we have shown:

[t^{n}]\frac{2}{(1 − t)(2 − t)} = 2 − \frac{1}{2^{n}} ∼ 2.

For the second part, we can expand everything around the dominating singularity t = 1 and obtain:

(2 − 4(1 − t) + 6(1 − t)^{2} + O((1 − t)^{3})) ln (\frac{1}{1 − t}) .

By extracting coefficients, we obtain the expansion in the assertion.

As an example, by considering n = 100, we have a true value S_{100}^{(0)} = 2.020416947 to be compared with the approximate value 2.020416000 given by the formula above.

3 The expansions

In their paper [1], Belbachir, Rahmani, and Sury find relations expressing S_{n}^{(m)} in terms of S_{n}^{(0)}, although they seem not to give particular relevance to these identities. In our approach they are very important, so let us prove some results in this direction. We begin with an apparently obvious fact:

Theorem 8. For every m ∈ ℕ we have:

S_{n}^{(m)} = P^{(m)}(n)S_{n}^{(0)} + Q^{(m)}(n)  (2)

where P^{(m)}(n) and Q^{(m)}(n) are polynomials in n of degree m, except Q^{(0)}(n) = Q^{(1)}(n) = 0.

Proof. We proceed by mathematical induction on m. When m = 0, we consider the obvious identity S_{n}^{(0)} = S_{n}^{(0)}, from which we have the first step of induction and the initial values P^{(0)}(n) = 1, Q^{(0)}(n) = 0. So, let us suppose that (2) holds true for a given m and consider the identity in Theorem 3, which we can write as

S_{n}^{(m+1)} = (n + 1)S_{n}^{(m)} − (n + 1)S_{n+1}^{(m)} + (n + 1)^{m+1}.

By the inductive hypothesis, identity (2) holds true together with the companion formula

S_{n+1}^{(m)} = P^{(m)}(n + 1)S_{n+1}^{(0)} + Q^{(m)}(n + 1).

Let us substitute these values in the previous equation:

S_{n}^{(m+1)} = (n + 1) (P^{(m)}(n)S_{n}^{(0)} + Q^{(m)}(n)) − (n + 1) (P^{(m)}(n + 1)S_{n+1}^{(0)} + Q^{(m)}(n + 1))

+ (n + 1)^{m+1}. (3)

Finally, we use the recurrence for S_{n}^{(0)} in the form of Theorem 4

S_{n+1}^{(0)} = \frac{n + 2}{2(n + 1)}S_{n}^{(0)} + 1;

this is done to eliminate S_{n+1}^{(0)}. By rearranging terms, we find:

S_{n}^{(m+1)} = ((n + 1)P^{(m)}(n) − \frac{n + 2}{2}P^{(m)}(n + 1)) S_{n}^{(0)}+

+(n + 1)Q^{(m)}(n) − (n + 1) (P^{(m)}(n + 1) + Q^{(m)}(n + 1)) + (n + 1)^{m+1}.

This is the required expression, as soon as we set:

P^{(m+1)}(n) = (n + 1)P^{(m)}(n) − \frac{n + 2}{2}P^{(m)}(n + 1);  (4)

Q^{(m+1)}(n) = (n + 1)Q^{(m)}(n) − (n + 1) (P^{(m)}(n + 1) + Q^{(m)}(n + 1)) + (n + 1)^{m+1}. (5)

It is obvious that deg(P^{(m)}(n)) = m, while we leave to the reader the task of verifying that deg(Q^{(m)}(n)) = m for m ≥ 2.

At this point a simple program can be written in any Computer Algebra System computing recursively these polynomials. For example, we have:

S_{n}^{(1)} = \frac{n}{2}S_{n}^{(0)};

S_{n}^{(2)} = \frac{(n + 1)(n − 2)}{4}S_{n}^{(0)} + \frac{(n + 1)^{2}}{2} ;

S_{n}^{(3)} = \frac{n(n^{2} − 3n − 6)}{8}S_{n}^{(0)} + \frac{3n(n + 1)^{2}}{4} ;

S_{n}^{(4)} = \frac{(n + 1)(n^{3} − 7n^{2} − 2n + 16)}{16}S_{n}^{(0)} + \frac{(7n − 8)(n + 1)^{3}}{8} ;

S_{n}^{(5)} = \frac{n(n^{4} − 10n^{3} − 5n^{2} + 70n + 80)}{32}S_{n}^{(0)} + \frac{5n(3n^{2} − n − 8)(n + 1)^{2}}{16} .

By using this result, we can find recurrence relations for S_{n}^{(m)}, m ∈ ℕ. The idea is to start with the relation S_{n+1}^{(m)} = P^{(m)}(n + 1)S_{n+1}^{(0)} + Q^{(m)}(n + 1) and change S_{n+1}^{(0)} into S_{n}^{(0)} by the recurrence relation of that quantity. At this point, we apply (2) backwards, eliminating S_{n}^{(0)} and inserting S_{n}^{(m)}. In this way we obtain the desired recurrence. Formally:

Theorem 9. For every m ∈ ℕ, we have the following recurrence relation:

S_{n+1}^{(m)} = \frac{n + 2}{2(n + 1)} \frac{P^{(m)}(n + 1)}{P^{(m)}(n)}S_{n}^{(m)} − \frac{n + 2}{2(n + 1)} \frac{P^{(m)}(n + 1)}{P^{(m)}(n)}Q^{(m)}(n)+P^{(m)}(n+1)+Q^{(m)}(n+1).

Proof. As announced, we begin with the shifted position:

S_{n+1}^{(m)} = P^{(m)}(n + 1)S_{n+1}^{(0)} + Q^{(m)}(n + 1).

Then use the recurrence relation for S_{n}^{(0)}:

S_{n+1}^{(m)} = P^{(m)}(n + 1) (\frac{n + 2}{2(n + 1)}S_{n}^{(0)} + 1) + Q^{(m)}(n + 1) =

= \frac{n + 2}{2(n + 1)}P^{(m)}(n + 1)S_{n}^{(0)} + P^{(m)}(n + 1) + Q^{(m)}(n + 1).

We now use the relation found in the previous theorem to change S_{n}^{(0)} into S_{n}^{(m)}:

S_{n+1}^{(m)} = \frac{n + 2}{2(n + 1)}P^{(m)}(n+1)\frac{S_{n}^{(m)}}{P^{(m)}(n)}−\frac{n + 2}{2(n + 1)} \frac{P^{(m)}(n + 1)Q^{(m)}(n)}{P^{(m)}(n)}+P^{(m)}(n+1)+Q^{(m)}(n+1).

This result is the relation we were looking for.

We expand our examples up to m = 5:

S_{n+1}^{(1)} = \frac{n + 2}{2n}S_{n}^{(1)} + \frac{n + 1}{2};

S_{n+1}^{(2)} = \frac{(n + 2)^{2}(n − 1)}{2(n + 1)^{2}(n − 2)}S_{n}^{(2)} + \frac{(n + 2)(n^{2} − 2n − 2)}{2(n − 2)};

S_{n+1}^{(3)} = \frac{(n + 2)(n^{2} − n − 8)}{2n(n^{2} − 3n − 6)}S_{n}^{(3)} + \frac{(n + 1)(n^{4} − n^{3} − 17n^{2} − 27n − 12)}{2(n^{2} − 3n − 6)};

S_{n+1}^{(4)} = \frac{(n + 2)^{2}(n^{3} − 4n^{2} − 13n + 8)}{2(n + 1)^{2}(n^{3} − 7n^{2} − 2n + 16)}S_{n}^{(4)}+\frac{(n + 2)(n^{6} − 5n^{5} − 24n^{4} − 2n^{3} + 54n^{2} + 54n + 16)}{2(n^{3} − 7n^{2} − 2n + 16)};

S_{n+1}^{(5)} = \frac{(n + 2)(n^{4} − 6n^{3} − 29n^{2} + 34n + 136)}{2n(n^{4} − 10n^{3} − 5n^{2} + 70n + 80)}S_{n}^{(5)}+

+\frac{(n + 1)(n^{8} − 6n^{7} − 54n^{6} − 21^{5} + 496n^{4} + 1345n^{3} + 1505n^{2} + 790n + 160)}{2(n^{4} − 10n^{3} − 5n^{2} + 70n + 80)}.

Finally, we will find the generating functions S^{(m)}(t). For this purpose, we need the generating functions of the sequences ((n + 1)^{m})_{n∈ℕ}. This is a classical result and involves Eulerian numbers [3, p. 254]. Actually, we have:

G ((n + 1)^{m}) = \frac{E^{(m)}(t)}{(1 − t)^{m+1}}

and this can be taken as a definition of he polynomials E^{(m)}(t). The first instances are:

E^{(1)}(t) = 1
E^{(2)}(t) = 1 + t

E^{(3)}(t) = 1 + 4t + t^{2}
E^{(4)}(t) = 1 + 11t + 11t^{2} + t^{3}
E^{(5)}(t) = 1 + 26t + 66t^{2} + 26t^{3} + t^{4}.

It is well-known that E^{(m)}(1) = m!.

Let us begin with the following result:

Theorem 10. For every m ∈ ℕ, the generating functions S^{(m)}(t) have the form:

S^{(m)}(t) = \frac{F^{(m)}(t)}{(1 − t)^{m+1}} + \frac{G^{(m)}(t)}{(2 − t)^{m+1}} + \frac{H^{(m)}(t)}{(2 − t)^{m+2}} ln (\frac{1}{1 − t})

where F^{(m)}(t), G^{(m)}(t) and H^{(m)}(t) are polynomials in t of degree at most m.

Proof. As we have seen, the generating function S^{(0)}(t) can be written:

S^{(0)}(t) = \frac{2}{1 − t} − \frac{2}{2 − t} + \frac{2}{(2 − t)^{2}} ln (\frac{1}{1 − t}) .

This proves the first step of induction and gives the initial values F^{(0)}(t) = 2, G^{(0)}(t) = −2 and H^{(0)}(t) = 2. So, let us suppose that our assertion holds true for m and apply Theorem 3; after some rearrangement we obtain:

S^{(m+1)}(t) = \frac{F^{(m)}(t)}{(1 − t)^{m+1}} − \frac{Ḟ^{(m)}(t)}{(1 − t)^{m}} − \frac{(m + 1)F^{(m)}(t)}{(1 − t)^{m+1}} + \frac{E^{(m+1)}(t)}{(1 − t)^{m+2}} +

+\frac{G^{(m)}(t)}{(2 − t)^{m+1}} − \frac{(1 − t)Ġ^{(m)}(t)}{(2 − t)^{m+1}} − \frac{(m + 1)(1 − t)G^{(m)}(t)}{(2 − t)^{m+2}} − \frac{H^{(m)}(t)}{(2 − t)^{m+2}} +

+ (\frac{H^{(m)}(t)}{(2 − t)^{m+2}} − \frac{(1 − t)Ḣ^{(m)}(t)}{(2 − t)^{m+2}} − \frac{(m + 2)(1 − t)H^{(m)}(t)}{(2 − t)^{m+3}}) ln (\frac{1}{1 − t}) .

Everything is immediately proven as soon as we set:

F^{(m+1)}(t) = (1 − t)F^{(m)}(t) − (1 − t)^{2}Ḟ^{(m)}(t) − (m + 1)(1 − t)F^{(m)}(t) + E^{(m+1)}(t) (6)

G^{(m+1)}(t) = (2 − t)G^{(m)}(t) − (1 − t)(2 − t)Ġ^{(m)}(t) − (m + 1)(1 − t)G^{(m)}(t) − H^{(m)}(t) (7)

H^{(m+1)}(t) = (2 − t)H^{(m)}(t) − (1 − t)(2 − t)Ḣ^{(m)}(t) − (m + 2)(1 − t)H^{(m)}(t)  (8)

We easily obtain the following generating functions:

S^{(1)}(t) = \frac{1}{(1 − t)^{2}} − \frac{4}{(2 − t)^{2}} + \frac{2t}{(2 − t)^{3}} ln (\frac{1}{1 − t})

S^{(2)}(t) = \frac{2t}{(1 − t)^{3}} − \frac{6t}{(2 − t)^{3}} − \frac{4 − 4t − 2t^{2}}{(2 − t)^{4}} ln (\frac{1}{1 − t})

S^{(3)}(t) = −\frac{1 − 4t − 3t^{2}}{(1 − t)^{4}} + \frac{16 − 16t − 8t^{2}}{(2 − t)^{4}} − \frac{16t − 16t^{2} − 2t^{3}}{(2 − t)^{5}} ln (\frac{1}{1 − t})

S^{(4)}(t) = −\frac{2t − 22t^{2} − 4t^{3}}{(1 − t)^{5}} + \frac{80t − 80t^{2} − 10t^{3}}{(2 − t)^{5}} + \frac{32 − 64t − 12t^{2} + 44t^{3} + 2t^{4}}{(2 − t)^{6}} ln (\frac{1}{1 − t})

S^{(5)}(t) = \frac{3 − 14t + 48t^{2} + 78t^{3} + 5t^{4}}{(1 − t)^{6}} − \frac{192 − 384t − 72t^{2} + 264t^{3} + 12t^{4}}{(2 − t)^{6}} +

+\frac{272t − 544t^{2} + 168t^{3} + 104t^{4} + 2t^{5}}{(2 − t)^{7}} ln (\frac{1}{1 − t})

The interested reader can compare the series expansion of these functions against the values given in the Introduction, directly obtained from the formula (1).

4 Asymptotics

In the previous section we have found recurrence relations and generating functions; they become more and more complex as m grows, so it is important to have asymptotic approximations of our quantities. There are two possible approaches. By using Theorem 8 in conjunction with Theorem 7 (thus taking advantage of our knowledge of the asymptotic behavior of S_{n}^{(0)}) or by starting with Theorem 10 and reasoning in terms of formal power series, i.e., our generating functions.

In the first approach, we consider the following lemma, which is a corollary of Theorem 8:

Lemma 11. The leading terms (i.e., the terms of highest degree), L(P^{(m)}(n)) and L(Q^{(m)}(n)) of the polynomials P^{(m)}(n) and Q^{(m)}(n), are respectively:

L(P^{(m)}(n)) = \frac{n^{m}}{2^{m}} (m ≥ 1) − L(Q^{(m)}(n)) = \frac{(2^{m−1} − 1)n^{m}}{2^{m−1}} (m ≥ 2).

Proof. The initial step can be verified directly. From the recurrence relation (4) for P^{(m)}(n) we have:

L(P^{(m+1)}(n)) = n · \frac{n^{m}}{2^{m}} − \frac{n}{2} \frac{n^{m}}{2^{m}} = \frac{n^{m+1}}{2^{m+1}} .

This proves the induction step. For Q^{(m)}(n), by using the recurrence (5), we find:

L(Q^{(m+1)}(n)) = n · \frac{(2^{m−1} − 1)n^{m}}{2^{m−1}} − n · \frac{n^{m}}{2^{m}} − n · \frac{(2^{m−1} − 1)n^{m}}{2^{m−1}} + n^{m+1} =

= −\frac{n^{m+1}}{2^{m}} + n^{m+1} = \frac{(2^{m} − 1)n^{m+1}}{2^{m}} .

This completes the proof.

We immediately have the asymptotic behavior of our quantities:

Theorem 12. The following asymptotic approximation holds true for every positive m:

S_{n}^{(m)} ∼ n^{m}.

Proof. In Theorem 7 we have seen that S_{n}^{(0)} ∼ 2 and by Theorem 8 and the preceding lemma we find the desired result:

S_{n}^{(m)} ∼ \frac{n^{m}}{2^{m}} · 2 + \frac{(2^{m−1} − 1)n^{m}}{2^{m−1}} = n^{m}.

As an example, we considered n = 100 and in Table 1 we give the exact value S_{100}^{(m)}, its approximate value according to the previous theorem, and the relative error.

m  true value  asymptotic value relative error approx. Th. 13
1  101.0208474  100  1.02%  101.0208000
2  10,100.02174  10,000  1.00%  10100.02
3  1,009,899.024  1,000,000  0.99%  1009899
4  100,979,800.0  100,000,000  0.98%  100979800
5 1.009698040 · 10^{10}  10^{10}  0.97%  1.00969800 · 10^{10}

Table 1: The case n = 100

The asymptotic approximation could be improved by considering other terms, but we wish to quote just the expressions obtained by the first four terms given in Theorem 7 (for n = 100, see last column in Table 1):

Theorem 13. The following approximations hold true

S_{n}^{(1)} ∼ n + 1 + \frac{2}{n} + \frac{8}{n^{2}}

S_{n}^{(2)} ∼ n^{2} + n + \frac{2}{n}

S_{n}^{(3)} ∼ n^{3} + n^{2} − n − 1

S_{n}^{(4)} ∼ n^{4} + n^{3} − 2n^{2} − 2n
S_{n}^{(5)} ∼ n^{5} + n^{4} − 3n^{3} − 2n^{2}.

Proof. These values are derived directly from the formulas after Theorem 8.

For the second approach, let us refer to Theorem 10. The dominating singularity of the generating functions S^{(m)}(t) is t = 1, which is a pole in F^{(m)}(t)/(1 − t)^{m+1} and a logarithmic singularity in the term containing ln(1/(1 − t)). In order to apply Bender’s theorem for asymptotic evaluation, let us compute the values of the polynomials F^{(m)}(t), G^{(m)}(t) and F^{(m)}(t) at t = 1:

Lemma 14. For every m ∈ ℕ we have:

F^{(m)}(1) = m!,  G^{(m)}(1) = −2(n + 1).  H^{(m)}(1) = 2.

Proof. By using the recurrence (6), we find immediately F^{(m)}(1) = E^{(m)}(1) = m!. By (8) we have H^{(m+1)}(1) = H^{(m)}(1); since H^{(0)}(1) = 2 we find H^{(m)}(1) = 2, for every m ∈ ℕ. Finally, by (7) we have G^{(m+1)}(1) = G^{(m)}(1) − 2, and since G^{(0)}(1) = −2, the formula in the assertion follows.

We conclude with another proof of the asymptotic value for S_{n}^{(m)}:

Theorem 15. For every m ≥ 1, we have the asymptotic approximation:

S_{n}^{(m)} ∼ n^{m}.

Proof. Let us consider the decomposition given in Theorem 10. The term with G^{(m)}(t) has the only singularity t = 2 and therefore its contribution is asymptotically small. The term containing the logarithm behaves as H^{(m)}(1) ln(1/(1 − t)) and therefore contributes as 2/n. In conclusion, the relevant part is the term containing F^{(m)}(t) which, however, is dominated by E^{(m)}(t)/(1 − t)^{m+1}, and we find;

S_{n}^{(m)} ∼ [t^{n}]\frac{E^{(m)}(t)}{(1 − t)^{m+1}} ∼ E^{(m)}(1)\binom{−m − 1}{n}(−1)^{n} = m!\binom{n + m}{m} ∼ n^{m}.

It is possible to improve our estimates of the asymptotic value of S_{n}^{(m)} by approaching in a different way a property considered by Belbachir, Rahmani, and Sury. We begin with the following result:

Theorem 16. The term with k = n − m in the sum (1) defining S_{n}^{(m)} is asymptotically m!. More exactly:

(n − m)^{m}\binom{n}{n − m}^{−1} ∼ m! (1 − \frac{m^{2} + m}{2n}) .

Proof. In fact we have the desired result:

(n − m)^{m}\binom{n}{n − m}^{−1} = (n − m)^{m} \frac{m!}{(n)_{m}} ∼ \frac{n^{m} exp(−m^{2}/n) · m!}{n^{m} exp(−(0 + 1/n + 2/n + ⋯ + (m − 1)/n))} =

= \frac{exp(−m^{2}/n) · m!}{exp(−m(m − 1)/(2n))} = m! exp (−\frac{m^{2} + m}{2n}) ∼ m! (1 − \frac{m^{2} + m}{2n}) ∼ m!.

For example, we consider m = 4 and n = 1000; the true value of 996^{4}\binom{1000}{996}^{−1} is 23.76060024. The approximate value obtained by the previous theorem is 23.76000000.

The two terms preceding k = n − m are asymptotically small:

Lemma 17. For fixed m, the terms with k = n − m − 1 and k = n − m − 2 in the sum (1) are O(1/n) and O(1/n^{2}), respectively.

Proof. By a straight-forward computation we find:

(n − m − 1)^{m}\binom{n}{n − m − 1} ∼ \frac{m + 1}{n}(n − m)^{m}\binom{n}{n − m}^{−1} ∼ \frac{(m + 1)!}{n}.

This is found when we use the previous theorem. The proof for k = n−m−2 is analogous.

For fixed m, at the other end of the sum (1), the terms with k = 1 and k = 2 are small. Actually, we have:

1^{m}\binom{n}{1}^{−1} = \frac{1}{n} and 2^{m}\binom{n}{2}^{−1} = \frac{2^{m+1}}{n(n − 1)} = O (\frac{1}{n^{2}} ) .

The following observation now becomes very important:

Theorem 18. The distribution of the terms in the sum (1) is unimodal and attains its minimum near k = (n − m − 1)/2.

Proof. Let us observe that:

(k + 1)^{m}\binom{n}{k + 1}^{−1} = (k + 1)^{m} \frac{k + 1}{n − k} \binom{n}{k}^{−1};

and consider the difference of two consecutive terms:

(k + 1)^{m}\binom{n}{k + 1}^{−1} − k^{m}\binom{n}{k}^{−1} = \binom{n}{k}^{−1} \frac{k^{m}}{n − k} ((k + 1) (1 + \frac{1}{k})^{m} − n + k) .

The terms are increasing when the quantity between parentheses is positive and decreasing when negative. The threshold value is obtained when

n ≈ (k + 1) (1 + \frac{1}{k})^{m} + k ≈ (k + 1) (1 + \frac{m}{k}) + k.

For fixed m, when n and k are large, we are reduced to the equation n = 2k + m + 1, the solution of which is our assertion. In our hypotheses, the solution is unique and the distribution is unimodal.

We are now in a position to prove the theorem:

Theorem 19 (Belbachir, Rahmani, and Sury). We have:

∑_{k=0}^{n−m} k^{m}\binom{n}{k}^{−1} ∼ m!.

Proof. The sum is composed: (1) of the term with k = n − m, the asymptotic value of which is m!; (2) of the terms with k = 1 and k = n−m−1 which are O(1/n); (3) of the terms with k = 2 and k = n − m − 2 which are O(1/n^{2}); (4) of all the terms with 2 < k < n − m − 2 which are all O(1/n^{2}) by unimodality. Summing all these contributions, we conclude:

∑_{k=0}^{n−m} k^{m}\binom{n}{k}^{−1} = O (\frac{1}{n}) + (n − m − 2)O (\frac{1}{n^{2}} ) + O (\frac{1}{n}) + m! = m! + O (\frac{1}{n}) .

This proves our assertion.

For our purposes it is sufficient to observe that the central terms of the sum are O(1/n^{2}), but in reality they are much smaller. To have an idea thereof, we can consider the central term, which, as we have seen, is not too far from the smallest term; we immediately have the value:

(\frac{n}{2})^{m} \binom{n}{n/2}^{−1} ∼ \frac{n^{m}}{2^{n+m}} \sqrt{\frac{πn}{2}},

where we used the classical approximation of the central binomial coefficients. For m = 4 and n = 1000 the true value of the central term is 0.23117682 × 10^{−288} and the approximate value is 0.23123462 × 10^{−288}, both values close to the minimum 0.22938294 × 10^{−288} attained at k = 498.

The fact that the term distribution is unimodal and all the terms from k = 1 to k = n − m − 1 are smaller and smaller as n → ∞ suggests another approach to the evaluation of the asymptotic value of S_{n}^{(m)}, when m > 0: it is sufficient to consider the last terms of the sum, which are dominating due to the lemmas and theorems we have just proved. In particular, we obtain the following result by using the last four terms of the sum (1):

Theorem 20. The asymptotic value of the sum (1) is:

S_{n}^{(m)} ∼ n^{m} + n^{m−1} − (m − 2)n^{m−2} + \frac{m^{2} − 9m + 16}{2}n^{m−3}.

Proof. The leading term, obtained by setting k = n, is obviously n^{m}. The second term, corresponding to k = n − 1 is:

(n−1)^{m} \frac{1}{n} = \frac{n^{m}(1 − 1/n)^{m}}{n} ∼ n^{m−1} (1 − \frac{m}{n} + \frac{m(m − 1)}{2n^{2}}) = n^{m−1}−mn^{m−2}+\frac{m(m − 1)}{2}n^{m−3}.

The next term gives:

\frac{2(n − 2)^{m}}{n(n − 1)} ∼ 2n^{m} (1 − \frac{2m}{n}) (1 + \frac{1}{n}) ∼ 2n^{m−2} − (4m − 2)n^{m−3}.

Finally, the fourth term contributes for 6n^{m−3}, and putting everything together we find the expression in the assertion.

We observe that these values agree with the formulas obtained in Theorem 13.

References

[1] H. Belbachir, M. Rahmani, and B. Sury. Sums involving moments of reciprocals of binomial coefficients. J. Integer Sequences 14 (2011), Article 11.6.6.

[2] E. A. Bender. Asymptotic methods in enumeration. SIAM Review 16 (1974), 485–515.

[3] R. Graham, D. E. Knuth and O. Patashnik. Concrete Mathematics. Addison-Wesley, 1994.

[4] D. E. Knuth. The Art of Computer Programming. Addison-Wesley, 1968.

[5] D. Merlini, R. Sprugnoli, and M. C. Verri. The method of coefficients. Amer. Math. Monthly, 114 (2007) 40–57.

[6] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. http://oeis.org.

[7] T. B. Staver. Om summasjon av potenser av binomialkoeffisientene. Norsk Mat. Tidsskrift 29 (1947), 97–103.

[8] J.-H. Yang and F.-Z. Zhao. The asymptotic expansion of certain sums involving inverse of binomial coefficients. Int. Math. Forum, 5 (2010), 761–768.

2010 Mathematics Subject Classification: Primary 60C05; Secondary 05A15, 62E15. Keywords: inverse binomial distribution, moments, generating functions.

(Concerned with sequence \underline{A003149}.)

Received March 19 2011; revised version received July 18 2011. Published in Journal of Integer Sequences, September 5 2011

Return to Journal of Integer Sequences home page.