Sums Involving Moments of Reciprocals of Binomial Coefficients

Hacène Belbachir and Mourad Rahmani University of Sciences and Technology Houari Boumediene Faculty of Mathematics P. O. Box 32 El Alia Bab-Ezzouar 16111 Algiers Algeria

               hacenebelbachir@gmail.com
                   mrahmani@usthb.dz

B. Sury Statistics & Mathematics Unit Indian Statistical Institute 8th Mile Mysore Road Bangalore 560059 India

                  sury@isibang.ac.in

Abstract

We investigate sums of the form ∑_{0≤k≤n} k^{m}\binom{n}{k}^{−1}. We establish a recurrence relation and compute its ordinary generating function. As application we give the asymptotic expansion. The results extend the earlier works by various authors. In the last section, we establish that ∑_{0≤k≤n} \frac{k^{m}}{n^{m}} \binom{n}{k}^{−1} tends to 1 as n → ∞ and that ∑_{0≤k≤n−m} k^{m}\binom{n}{k}^{−1} tends to m! as n → ∞.

1 Introduction

For all nonnegative integers n, m, let

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

There are several papers in the literature dealing with sums involving inverses of binomial coefficients [2, 9, 11, 12, 15, 16, 17, 19]. The cases m = 0 and m = 1 were intensively studied.

In 1947, Staver [13], using the identity

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

obtained a relation between S_{n}^{(1)} and S_{n}^{(0)}:

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

and established a recurrence relation for S_{n}^{(0)}

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

Staver also proved for the first time the well-known formula

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

For applications of (4), see Nedemeyer and Smorodinsky [5], Mansour and West [7], and for a probabilistic application, see Letac [4, p. 14]. Finally, for the asymptotic expansion, see Comtet [1, p. 294] and Yang and Zhao [18].

In 1981, using induction and the relation

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

Rockett [9] proved (3) and (4).

In 1993, Sury [14] connected the inverse binomial coefficients to the beta function as follows

\binom{n}{k}^{−1} = (n + 1) ∫_{0}^{1}x^{k} (1 − x)^{n−k} dx

and proved the relation (4) (see also [16]). Some years later, Mansour [6], generalized the idea of Sury [14], and gave an approach based on calculus to obtain the generating function for related combinatorial identities.

Theorem 1 (Mansour [6]). Let r, n ≥ k be any nonnegative integer numbers, and let f (n, k) be given by

f (n, k) = \frac{(n + r)!}{n!}∫_{u_{1}}^{u_{2}}p^{k} (t) q^{n−k} (t) dt,

where p (t) and q (t) are two functions defined on [u_{1}, u_{2}] . Let {a_{n}}_{n≥0} and {b_{n}}_{n≥0} be any two sequences, and let A (x) , B (x) be the corresponding ordinary generating functions. Then

∑_{n=0}^{∞} [∑_{k=0}^{n}f (n, k) a_{k}b_{n−k}] x^{n} = \frac{d^{r}}{dx^{r}} [x^{r}∫_{u_{1}}^{u_{2}}A (xp (t)) B (xq (t)) dt] .  (5)

In particular,

∑_{n≥0}S_{n}^{(0)}x^{n} = \frac{2}{(x − 1) (x − 2)} − \frac{2 ln (1 − x)}{(x − 2)^{2}},

and

∑_{n≥0}S_{n}^{(1)}x^{n} = −\frac{x (3x − 4)}{(x − 1)^{2} (x − 2)^{2}} + \frac{2x ln (1 − x)}{(x − 2)^{3}}.

We shall use the following well-known basic tools [3]:

(i) The Stirling numbers of the second kind \left\{{n \atop k}\right\} (\underline{A008277}), can be defined by the generating function

∏_{j=1}^{k} \frac{x}{1 − jx} = ∑_{n≥k}\left\{{n \atop k}\right\}x^{n}.

The most basic recurrence relation is

\left\{{n + 1 \atop k}\right\} = \left\{{n \atop k − 1}\right\} + k\left\{{n \atop k}\right\},

with \left\{{n \atop 1}\right\} = \left\{{n \atop n}\right\} = 1. An important relation involving \left\{{n \atop k}\right\} is

x^{n} = ∑_{k=0}^{n} (−1)^{n+k} \left\{{n \atop k}\right\}x (x + 1) ⋯ (x + k − 1) .  (6)

(ii) The Eulerian numbers \left⟨{n \atop k}\right⟩ (\underline{A008292}) are defined by

\left⟨{n \atop k}\right⟩ = ∑_{i=0}^{k} (−1)^{i} (k − i)^{n} \binom{n + 1}{i}, n ≥ k ≥ 1.

Which also satisfy the recursive relation

\left⟨{n \atop k}\right⟩ = k\left⟨{n − 1 \atop k}\right⟩ + (n − k + 1) \left⟨{n − 1 \atop k − 1}\right⟩,

with \left⟨{1 \atop 1}\right⟩ = 1.

(iii) The Worpitzky numbers W_{n,k} (\underline{A028246}), are defined by

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

They can also be expressed through the Stirling numbers of the second kind as follows

W_{n,k} = k!\left\{{n + 1 \atop k + 1}\right\}.  (7)

The Worpitzky numbers satisfy the recursive relation

W_{n,k} = (k + 1) W_{n−1,k} + kW_{n−1,k−1} (n ≥ 1, k ≥ 1) .  (8)

Some simple properties related to these three remarkable sequences are

∑_{k=0}^{n}\left⟨{n \atop k}\right⟩x^{k} = ∑_{k=0}^{n} (x − 1)^{n−k} kW_{n−1,k−1},  (9)
∑_{k=0}^{n}\binom{n}{k}\left\{{k \atop t}\right\} = \left\{{n + 1 \atop t + 1}\right\},  (10)

and

∑_{k=0}^{n}\left⟨{n \atop k}\right⟩\binom{k + 1}{t} = W_{n,n−t}.  (11)

2 Some results on S_{n}^{(2)}

In this section, we give some results concerned S_{n}^{(2)}. Applying Theorem 1, for a_{n} = n^{2} and b_{n} = 1, we obtain, for |x| < 1,

A(x) = \frac{x(x + 1)}{(1 − x)^{3}},

and

B(x) = \frac{1}{1 − x},

from (5) we get the generating function for S_{n}^{(2)}

∑_{n≥0}S_{n}^{(2)}x^{n} = \frac{d}{dx} [x∫_{0}^{1} \frac{xt (xt + 1)}{(1 − xt)^{3} (1 − x + xt)}dt]
= \frac{2x (2x^{3} − 3x^{2} − 3x + 5)}{(x − 2)^{3}(x − 1)^{3}} − 2 (x^{2} + 2x − 2) \frac{ln(1 − x)}{(x − 2)^{4}}.  (12)

In addition, we have a relation between S_{n}^{(2)} and S_{n}^{(0)} given by the following theorem.

Theorem 2. If n is a nonnegative integer, then S_{n}^{(2)} satisfies the recursion relation

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

and

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

Proof. We use the WZ method [8]. Denote the summand in S_{n}^{(2)} by L (n, k) := k^{2}\binom{n}{k}^{−1}, by the Zeilberger’s Maple package EKHAD, we construct the function

G (n, k) = (n^{2}k^{2} + n + 3nk − nk^{2} + 2 + 2k − 2k^{2}) (n + 1 − k) \binom{n}{k}^{−1}

such that

(n − 1) (n + 2)^{2} L (n, k) − 2 (n − 2) (n + 1)^{2} L (n + 1, k) = G (n, k + 1) − G (n, k) .

By summing the above telescoping equation over k from 0 to n − 1, we obtain the following recurrence relation

(n − 1) (n + 2)^{2} ∑_{k=0}^{n−1}L (n, k) − 2 (n − 2) (n + 1)^{2} ∑_{k=0}^{n−1}L (n + 1, k) = G (n, n) − G (n, 0) ,

that we can rewrite

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

+ 2 (n − 2) (n + 1)^{2} (\frac{n^{2}}{n + 1} + (n + 1)^{2}) = n^{3}(n − 1),

as desired. We prove the relation (14) by induction on n, the result clearly holds for n = 0, we now show that the formula for n + 1 follows from (13) and induction hypothesis

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

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

Applying (3), we obtain

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

This completes the proof.

Using the relation ∑_{k=0}^{n}k^{3}\binom{n}{k}^{−1} = ∑_{k=0}^{n} (n − k)^{3} \binom{n}{k}^{−1} and relations (2) and (14), we easily

obtain the following identity between S_{n}^{(3)} and S_{n}^{(0)}. Corollary 3. For any nonnegative integers n, we have

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

3 Generalization

Before stating the main result of this section, we need a lemma. Lemma 4.

S_{n+j}^{(0)} = (n + j + 1) (\frac{1}{2^{j} (n + 1)}S_{n}^{(0)} + ∑_{r=0}^{j−1} \frac{1}{2^{r} (n + j − r + 1)}) ,  (15)

Proof. We proceed by induction on j. For j = 0 the identity (15) holds. Now suppose that (15) holds for some j and replace n by n + 1 in (15), then using relation (3) the result follows. Theorem 5. For any nonnegative integers m and n, we have

S_{n}^{(m)} = ∑_{j=0}^{m} (−1)^{m+j} \binom{n + j}{n}W_{m,j} (S_{n+j}^{(0)} − \frac{1}{(n + j)!} ∑_{r=0}^{j−1} r! (n + j − r)!) ,  (16)

with the usual convention that the empty sum is 0. Proof. We can write S_{n}^{(m)} as follows

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

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

and with (6), we obtain

S_{n}^{(m)} = ∑_{k=0}^{n}\binom{n}{k}^{−1}∑_{i=0}^{m} (−1)^{m−i} \binom{m}{i}∑_{j=0}^{i} (−1)^{i+j} \left\{{i \atop j}\right\} (k + 1) ⋯ (k + j) ,

= ∑_{k=0}^{n}∑_{i=0}^{m}∑_{j=0}^{i} \frac{1}{n!} (−1)^{m+j} \binom{m}{i}\left\{{i \atop j}\right\}k! (k + 1) ⋯ (k + j) (n − k)!.

After some rearrangement,

S_{n}^{(m)} = ∑_{k=0}^{n}∑_{i=0}^{m}∑_{j=0}^{i} (−1)^{m+j} \binom{m}{i}\left\{{i \atop j}\right\} (n + 1) ⋯ (n + j) \binom{n + j}{k + j}^{−1},

= ∑_{i=0}^{m}∑_{j=0}^{i} (−1)^{m+j} \binom{m}{i}\left\{{i \atop j}\right\}j!\frac{(n + j)!}{n!j!}∑_{r=j}^{n+j}\binom{n + j}{r}^{−1}.

Now, from (10) and (11), the result holds.

Setting m = 4 in (16), we have the following Corollary 6. If n is a nonnegative integer, then

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

Theorem 7. For any nonnegative integers m and n

S_{n+1}^{(m)} = δ_{0m} + \frac{1}{n + 1} ∑_{j=0}^{m+1}\binom{m + 1}{j}S_{n}^{(j)},  (17)

where δ_{ij} is the Kronecker symbol. Proof. Recall that \binom{n+1}{k} = \frac{n+1}{k} \binom{n}{k−1}, we have

∑_{k=0}^{n+1} \frac{k^{m}}{\binom{n+1}{k}} = δ_{0m} + ∑_{k=1}^{n+1}k^{m}\binom{n + 1}{k}^{−1}

= δ_{0m} + \frac{1}{n + 1}∑_{k=1}^{n+1}k^{m+1}\binom{n}{k − 1}^{−1}

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

= δ_{0m} + \frac{1}{n + 1} ∑_{j=0}^{m+1}\binom{m + 1}{j}∑_{k=0}^{n}k^{j}\binom{n}{k}^{−1}.

This proves the theorem.

Setting m = 1 in (17) and using (14), we have the following Corollary 8. If n is a nonnegative integer, then

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

4 Ordinary generating function

We apply Theorem 1, for a_{n} = n^{m} (m ≥ 1), b_{n} = 1, and for |x| < 1 we have

A (x) = \frac{1}{(1 − x)^{m+1}} ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩x^{k+1} = ∑_{k=0}^{m} \frac{(−1)^{m+k}}{(1 − x)^{k+1}} W_{m,k},
B (x) = ∑_{n≥0}x^{n} = \frac{1}{1 − x}.

From (5), we get

∑_{n≥0}S_{n}^{(m)}x^{n} = \frac{d}{dx} [x∫_{0}^{1} \begin{matrix}∑_{k=0}^{m} & \left⟨{m \atop k}\right⟩ & (xt) & k+1 \\ (1 − xt) & m+1 & (1 − x + xt) \end{matrix}dt] .  (18)

Making the substitution xt = y in the right-hand side of (18), we obtain

∑_{n≥0}S_{n}^{(m)}x^{n} = \frac{d}{dx} [∫_{0}^{x} \frac{∑_{k=0}^{m} \left⟨{m \atop k}\right⟩y^{k+1}}{(1 − y)^{m+1} (1 − x + y)}dy] .

Since the degree of the denominator is at least one higher than that of the numerator, this fraction decomposes into partial fractions of the form

\frac{∑_{k=0}^{m} \left⟨{m \atop k}\right⟩y^{k+1}}{(1 − y)^{m+1} (1 − x + y)} = \frac{α^{(m)} (x)}{1 − x + y} + ∑_{s=0}^{m} \frac{α_{s}^{(m)} (x)}{(1 − y)^{m−s+1}} .  (19)

We note in passing that (19) is equivalent to

∑_{k=0}^{m} \left⟨{m \atop k}\right⟩y^{k+1} = (1 − y)^{m+1} α^{(m)} (x) + (1 − x + y) ∑_{s=0}^{m} (1 − y)^{s} α_{s}^{(m)} (x)  (20)

= ∑_{k=0}^{m} (−1)^{m+k} y (1 − y)^{m−k} W_{m−1,k−1}.

For y = 1 and using the fact that W_{p,p} = p! for p ≥ 0, we immediately obtain the well-known identity

∑_{k=0}^{m} \left⟨{m \atop k}\right⟩ = m!.

Next, if we set y = 0 for |x| < 1, we obtain the following relation between α^{(m)} (x) and α_{s}^{(m)} (x)

∑_{s=0}^{m} α_{s}^{(m)} (x) = \frac{α^{(m)} (x)}{x − 1}.  (21)

Proposition 9. For m ≥ 1, we have

α_{s}^{(m)} (x) = ∑_{k=0}^{m} ∑_{i=0}^{s} \begin{matrix}(−1) & i+s \\ (2 − x) & i+1 \end{matrix} \left⟨{m \atop k}\right⟩\binom{k + 1}{s − i}  (22)

= ∑_{j=m−s}^{m} \begin{matrix}(−1) & m+j \\ (2 − x) & s−m+1+j \end{matrix} W_{m,j}.

and

α^{(m)} (x) = \frac{1}{(2 − x)^{m+1}} ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩ (x − 1)^{k+1}  (23)

= ∑_{j=0}^{m} \begin{matrix}(−1) & m+j \\ (2 − x) & j+1 \end{matrix} W_{m,j},

= α_{m}^{(m)} (x) .

Proof. We verify that (22) and (23) satisfy (20). Denote the right-hand side of (20) by R^{(m)}(y)

R^{(m)}(y) = (1 − y)^{m+1} α^{(m)} (x) + (1 − x + y) ∑_{s=0}^{m} (1 − y)^{s} α_{s}^{(m)} (x) .

After some rearrangement, we get

R^{(m)}(y) = \begin{matrix}(1 − y) & m+1 \\ (2 − x) & m+1 \end{matrix} ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩ (x − 1)^{k+1} +

(1 − x + y) ∑_{s=0}^{m} (1 − y)^{s} ∑_{k=0}^{m} ∑_{i=0}^{s} \begin{matrix}(−1) & i+s \\ (2 − x) & i+1 \end{matrix} \left⟨{m \atop k}\right⟩\binom{k + 1}{s − i}

= ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩ [\begin{matrix}(1 − y) & m+1 \\ (2 − x) & m+1 \end{matrix} (x − 1)^{k+1} +

\frac{1 − x + y}{2 − x} ∑_{s=0}^{m} \begin{matrix}(1 − y) & s \\ (2 − x) & s \end{matrix} ∑_{j=0}^{s} \binom{k + 1}{j} (−1)^{j} (2 − x)^{j}] ,

using binomial formula, we obtain

R^{(m)}(y) = ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩ [\begin{matrix}(1 − y) & m+1 \\ (2 − x) & m+1 \end{matrix} ∑_{j=0}^{k+1} \binom{k + 1}{j}(2 − x)^{j}(−1)^{j} +

∑_{s=0}^{m} \begin{matrix}(1 − y) & s \\ (2 − x) & s \end{matrix} ∑_{j=0}^{s} \binom{k + 1}{j} (−1)^{j} (2 − x)^{j} −

∑_{s=0}^{m} \begin{matrix}(1 − y) & s+1 \\ (2 − x) & s+1 \end{matrix} ∑_{j=0}^{s} \binom{k + 1}{j} (−1)^{j} (2 − x)^{j}] .

Now, for k ≤ m

R^{(m)}(y) = ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩ [ ∑_{s=m+1}^{m+1} \begin{matrix}(1 − y) & s \\ (2 − x) & s \end{matrix} ∑_{j=0}^{m+1} \binom{k + 1}{j}(2 − x)^{j}(−1)^{j} +

∑_{s=0}^{m} \begin{matrix}(1 − y) & s \\ (2 − x) & s \end{matrix} ∑_{j=0}^{s} \binom{k + 1}{j} (−1)^{j} (2 − x)^{j} −

∑_{s=0}^{m} \begin{matrix}(1 − y) & s+1 \\ (2 − x) & s+1 \end{matrix} ∑_{j=0}^{s} \binom{k + 1}{j} (−1)^{j} (2 − x)^{j}]

= ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩ [∑_{s=0}^{m+1} \begin{matrix}(1 − y) & s \\ (2 − x) & s \end{matrix} ∑_{j=0}^{s} \binom{k + 1}{j} (−1)^{j} (2 − x)^{j} −

∑_{s=1}^{m+1} \begin{matrix}(1 − y) & s \\ (2 − x) & s \end{matrix} ∑_{j=0}^{s−1} \binom{k + 1}{j} (−1)^{j} (2 − x)^{j}]

= ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩ [1 + ∑_{s=1}^{m+1} \begin{matrix}(1 − y) & s \\ (2 − x) & s \end{matrix} (∑_{j=0}^{s} \binom{k + 1}{j} (−1)^{j} (2 − x)^{j} −

∑_{j=0}^{s−1} \binom{k + 1}{j} (−1)^{j} (2 − x)^{j})] .

Finally,

R^{(m)}(y) = ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩ (1 + ∑_{s=1}^{k+1} \binom{k + 1}{s} (y − 1)^{s}) = ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩y^{k+1}.

Now, according to (11) and (7), we have

α_{s}^{(m)} (x) = ∑_{i=0}^{s} \begin{matrix}(−1) & i+s \\ (2 − x) & i+1 \end{matrix} ∑_{k=0}^{m} \left⟨{m \atop k}\right⟩\binom{k + 1}{s − i}

= ∑_{i=0}^{s} \frac{(−1)^{i+s} (m − s + i)!}{(2 − x)^{i+1}} \left\{{m + 1 \atop m − s + i + 1}\right\}

= ∑_{i=0}^{s} \begin{matrix}(−1) & i+s \\ (2 − x) & i+1 \end{matrix} W_{m,m−s+i}

= ∑_{j=m−s}^{m} \begin{matrix}(−1) & m+j \\ (2 − x) & s−m+1+j \end{matrix} W_{m,j},

on the other side, it follows from (9) that

α^{(m)} (x) = ∑_{j=0}^{m−1} (−1)^{m+j+1} \frac{(j + 1) (x − 1)}{(2 − x)^{j+2}}W_{m−1,j}

= ∑_{j=0}^{m−1} \begin{matrix}(−1) & m+j \\ (2 − x) & j+1 \end{matrix} (j + 1) W_{m−1,j} − ∑_{j=0}^{m−1} \begin{matrix}(−1) & m+j \\ (2 − x) & j+2 \end{matrix} (j + 1) W_{m−1,j}

= ∑_{j=0}^{m} \begin{matrix}(−1) & m+j \\ (2 − x) & j+1 \end{matrix} (j + 1) W_{m−1,j} + ∑_{j=0}^{m} \begin{matrix}(−1) & m+j \\ (2 − x) & j+1 \end{matrix} jW_{m−1,j−1}.

Using (8), we get α^{(m)} (x) as desired. This completes the proof.

Now, Integrating the right-hand side of (19) over y, we obtain

∫_{0}^{x} \frac{∑_{k=0}^{m} \left⟨{m \atop k}\right⟩y^{k+1}}{(1 − y)^{m+1} (1 − x + y)}dy =

− 2α^{(m)} (x) ln (1 − x) + ∑_{s=0}^{m−1} \frac{α_{s}^{(m)} (x)}{s − m} (1 − (1 − x)^{s−m}) . (24)

By differentiating (24) we get the ordinary generating function of S_{n}^{(m)}

∑_{n≥0}S_{n}^{(m)}x^{n} = −2\frac{d}{dx}α^{(m)} (x) ln (1 − x) + \frac{α^{(m)} (x)}{1 − x}+

∑_{s=0}^{m−1} \frac{\frac{d}{dx}α_{s}^{(m)} (x)}{s − m} (1 − (1 − x)^{s−m}) + ∑_{s=0}^{m} α_{s}^{(m)} (x) (1 − x)^{s−m−1} (25)

with

\frac{d}{dx}α_{s}^{(m)} (x) = ∑_{j=m−s}^{m} \begin{matrix}(s − m + j + 1) & (−1) & m+j \\ (2 − x) & s−m+j+2 \end{matrix} W_{m,j}.

With Proposition 9, we can now rewrite (25) as follows Theorem 10. For any real number x such that |x| < 1 and for all positive integers m ≥ 1, we have

∑_{n≥0}S_{n}^{(m)}x^{n} = (∑_{j=0}^{m} \frac{2 (j + 1) (−1)^{m+j+1}}{(2 − x)^{j+2}} W_{m,j}) ln (1 − x)

+ ∑_{0≤j≤s≤m−1} \frac{(−1)^{j} W_{m,m−j}}{(2 − x)^{s−j+1}} (\frac{(s − j + 1) (1 − (1 − x)^{s−m})}{(s − m) (2 − x)} + (1 − x)^{s−m−1})

+ \frac{1}{1 − x} ∑_{j=0}^{m} \frac{2 (−1)^{j+m}}{(2 − x)^{j+1}} W_{m,j}.

5 Asymptotic expansion

Yang and Zhao [18] proved recently the asymptotic expansions for S_{n}^{(0)} and S_{n}^{(1)} of the following type:

S_{n}^{(0)} ∼ 2 + \frac{2}{n − 1} − \frac{1}{2^{n−1}} , n → ∞,  (26)

and

S_{n}^{(1)} ∼ \frac{n}{2} (2 + \frac{2}{n − 1} − \frac{1}{2^{n−1}} ) , n → ∞.

However, there are finer asymptotics which we proceed to discuss now. We note that the following claim is consistent with Theorem 7.

S_{n}^{(m)} ∼ n^{m}, n → ∞.

It is not difficult to observe that T_{n}^{(m)} := ∑_{k=0}^{n−m}k^{m}\binom{n}{k}^{−1} also converges as n → ∞ and, we

prove alongside the above asymptotic formula that this limit is m!.

Theorem 11. For m > 0, we have

lim_{n→∞}T_{n}^{(m)} = m!,

and

lim_{n→∞} \frac{S_{n}^{(m)}}{n^{m}} = 1.

Proof. Let us denote the sum S_{n}^{(0)} by S_{n} for simplicity just in this proof. One has the recurrence relation S_{n} = \frac{n+1}{2n}S_{n−1} + 1 (see [14], for instance). Using this, it can be shown that

S_{n} → 2,
n(S_{n} − 2) → 2,
n(n(S_{n} − 2) − 2) = n^{2}S_{n} − 2n^{2} − 2n → 4,

and so on. More generally, there are constants a_{0}, a_{1}, a_{2}, … such that, recursively

u_{n}^{(k)} = nu_{n}^{(k−1)} − a_{k−1},
u_{n}^{(k)} → 0 as n → ∞,

where u_{n}^{(0)} = S_{n} − 2. In other words, for all k ≥ 1,

n^{k}S_{n} − (2n^{k} + a_{0}n^{k−1} + ⋯ + a_{k−2}n) → a_{k},

as n → ∞, for some a_{k}. In fact, the sequence a_{0}, a_{1}, … is 2, 4, 16, 88, 616, 5224, … is described by the generating function

∑_{n≥0} a_{n} \frac{x^{n}}{n!} = \frac{2}{(2 − e^{x})^{2}} .

The constants can also be defined as

a_{k} = ∑_{r=0}^{k} (r + 2) W_{k,r} − (r + 1) W_{k−1,r},

or recursively as

a_{k} = 4+∑_{r=1}^{k} (\binom{k + 1}{r} + \binom{k}{r}) (−1)^{r}(2−a_{0} +a_{1} −⋯±a_{r−1})+(−1)^{k+1}(2−a_{0} +⋯±a_{k−1}).

This is seen from

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

= n^{k}((n + 1)S_{n−1} + 2n)

= (n^{k+1} + n^{k})S_{n−1} + 2n^{k+1}

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

Write

X^{m} = c_{0} + c_{1}(X + 1) + c_{2}(X + 1)(X + 2) + ⋯ + c_{m}(X + 1)(X + 2) ⋯ (X + m), (27)

where c_{i}’s depend on m (c_{m} = 1). We have

T_{n}^{(m)} = ∑_{k=0}^{n−m} (c_{0} + c_{1}(k + 1) + c_{2}(k + 1)(k + 2) + ⋯ + c_{m}(k + 1)(k + 2) ⋯ (k + m)) \binom{n}{k}^{−1}

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

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

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

A computation using the above result

n^{k}S_{n} − (2n^{k} + a_{0}n^{k−1} + ⋯ + a_{k−1}n + a_{k}) → 0,

shows

lim_{n→∞} T_{n}^{(m)} = 0!c_{0} + 1!c_{1} + 2!c_{2} + ⋯ + (m − 1)!c_{m−1} + 2(m!)c_{m}.

This can be shown by induction on m. The proof is finished by observing that c_{m} = 1 and

0!c_{0} + 1!c_{1} + 2!c_{2} + ⋯ + m!c_{m} = 0,

which follows by looking at the constant term of (27). This finishes the proof of the first assertion. For the second one, we proceed similarly to the above discussion. We have

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

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

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

Thus, looking at the largest degree factor, we obtain

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

A corollary of the above proof is that the sum

S_{n}^{(0)} = 2 + \frac{2}{n} + \frac{4}{n^{2}} + \frac{16}{n^{3}} + \frac{88}{n^{4}} + \frac{616}{n^{5}} + \frac{5224}{n^{6}} + ⋯,

as n → ∞.

6 Acknowledgment

The authors are indebted to the referee for making constructive suggestions for improvement. The asymptotic result S_{n}^{(m)} ∼ n^{m} was pointed out by the referee and we have revised the paper to replace the earlier asymptotics by it. The referee has a rather different approach to the results of this paper and we look forward to seeing his proof in print soon.

The first and the second author were partially supported by CMEP project 09 MDU 765.

References

[1] L. Comtet, Advanced Combinatorics, Reidel, 1974.

[2] P. Juan, The sum of inverses of binomial coefficients revisited. Fib. Quart. 35 (1997), 342–345.

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

[4] G. Letac, Problèmes de probabilité, Presses Universitaires de France, 1970.

[5] F. Nedemeyer and Y. Smorodinsky, Resistances in the multidimensional cube. Quantum 7 (1) (Sept./Oct. 1996), 12–15, 63.

[6] T. Mansour, Combinatorial identities and inverse binomial coefficients. Adv. in Appl. Math. 28 (2002), 196–202.

[7] T. Mansour and J. West, Avoiding 2-letter signed patterns. Semm. Lothar. Combin. 49 (2002/04), Art. B49a.

[8] M. Petkovsek, H. S. Wilf and D. Zeilberger, A = B, A. K. Peters, 1996.

[9] M. A. Rockett, Sums of the inverses of binomial coefficients. Fib. Quart. 19 (1981), 433–437.

[10] N. J. A. Sloane, The On–Line Encyclopedia of Integer Sequences. Published electroni-

cally at http://www.research.att.com/~njas/sequences, 2010.

[11] A. Sofo, General properties involving reciprocals of binomial coefficients. J. Integer Sequences 9 (2004), Article 06.4.5.

[12] R. Sprugnoli, Sums of the reciprocals of central binomial coefficients. Integers 6 (2006), Paper A27.

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

[14] B. Sury, Sum of the reciprocals of the binomial coefficients. European J. Combin. 14 (1993), 351–353.

[15] B. Sury, Tianming Wang, and Feng-Zhen Zhao. Some identities involving reciprocals of binomial coefficients. J. Integer Sequences 7 (2004), Article 04.2.8.

[16] T. Trif, Combinatorial sums and series involving inverses of binomial coefficients. Fib. Quart. 38 (2000), 79–84.

[17] J.-H. Yang and F.-Z. Zhao. Sums involving the inverses of binomial coefficients. J. Integer Sequences 9 (2006), Article 06.4.2.

[18] J.-H. Yang and F.-Z. Zhao. The asymptotic expansions of certain sums involving inverse of binomial coefficient. International Mathematical Forum 5 (2010) 761–768.

[19] F.-Z. Zhao and T. Wang. Some results for sums of the inverses of binomial coefficients. Integers 5 (2005), Paper A22.

2000 Mathematics Subject Classification: Primary 11B65; Secondary 05A10, 05A16. Keywords: Binomial coefficient, recurrence relation, generating function, asymptotic expansion.

(Concerned with sequences \underline{A008277}, \underline{A008292}, and \underline{A028246}.)

Received December 1 2010; revised versions received December 8 2010; May 28 2011. Published in Journal of Integer Sequences, June 10 2011.

Return to Journal of Integer Sequences home page.