Alternating Weighted Sums of Inverses of Binomial Coefficients

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

                   renzo.sprugnoli@unifi.it

Abstract

We consider the alternating sums S_{n}^{(m)} = ∑_{k=0}^{n}(−1)^{n−k}k^{m}\binom{n}{k}^{−1}, recently studied by Belbachir, Rahmani, and Sury, and obtain some results complementary to those found by the three authors, especially concerning generating functions, closed forms, and asymptotic approximation.

1 Introduction

In the present note, we wish to study the sums

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

These sums, with (−1)^{k} instead of (−1)^{n−k} have been recently considered by Belbachir, Rahmani, and Sury [2] (see also Gould [3]), where they derive many properties of S_{n}^{(m)}. So, the results reported in the present note are complementary to those obtained by the three authors, and make some points, especially in asymptotic evaluation, more precise. Using (−1)^{n−k} allows us to treat only positive numbers, while maintaining the absolute value of all the quantities taken into account. We think that this approach might improve the readability of the paper.

For future reference, we list here the generating functions of the sums for 0 ≤ m ≤ 5 and 0 ≤ n ≤ 9. These functions have been directly computed by the formula 1, so our result should agree with these values.

S^{(0)}(t) = 1 + \frac{3}{2}t^{2} + \frac{5}{3}t^{4} + \frac{7}{4}t^{6} + \frac{9}{5}t^{8} + ⋯
S^{(1)}(t) = t + \frac{3}{2}t^{2} + \frac{8}{3}t^{3} + \frac{10}{3}t^{4} + \frac{9}{2}t^{5} + \frac{21}{4}t^{6} + \frac{32}{5}t^{7} + \frac{36}{5}t^{8} + \frac{25}{3}t^{9} + ⋯
S^{(2)}(t) = t + \frac{7}{2}t^{2} + 8t^{3} + \frac{85}{6}t^{4} + \frac{45}{2}t^{5} + \frac{651}{20}t^{6} + \frac{224}{5}t^{7} + \frac{294}{5}t^{8} + 75t^{9} + ⋯
S^{(3)}(t) = t + \frac{15}{2}t^{2} + \frac{74}{3}t^{3} + \frac{175}{3}t^{4} + \frac{1143}{10}t^{5} + \frac{3969}{20}t^{6} + \frac{1584}{5}t^{7} + \frac{2376}{5}t^{8} + \frac{14275}{21}t^{9} + ⋯
S^{(4)}(t) = t + \frac{31}{2}t^{2} + 76t^{3} + \frac{1429}{6}t^{4} + \frac{1161}{2}t^{5} + \frac{4823}{4}t^{6} + 2240t^{7} + \frac{134178}{35}t^{8} + \frac{43125}{7}t^{9} + ⋯
S^{(5)}(t) = t + \frac{63}{2}t^{2} + \frac{698}{3}t^{3} + \frac{2905}{3}t^{4} + \frac{5883}{2}t^{5} + \frac{29253}{4}t^{6} + \frac{553744}{35}t^{7} + \frac{1081512}{35}t^{8} + \frac{1171825}{21}t^{9} + · · · .

2 Recurrence relations and generating functions

The sums considered in this note are analogous to those treated in [1, 4], so we will try to follow a similar pattern. Let us show how Staver’s identity is modified in the present context.

Theorem 1 (Staver’s identity). For even values of n ∈ ℕ we have

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

for odd values of n ∈ ℕ we have S_{n}^{(0)} = 0.

Proof. By changing k ↦ n − k, we have

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

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

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

When n is even, (−1)^{k} = (−1)^{n−k} and Staver’s formula follows immediately. If n is odd, the two last terms change sign when we consider (−1)^{n−k} instead of (−1)^{k} and we have S_{n}^{(0)} = 0.

This lemma is not sufficient to go on with our study; the author [4] has shown

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

and this allows to prove the basic result:

Theorem 2. For the sums S_{n}^{(m)} the following recurrence relation holds true:

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

Proof. According to the definition, by isolating the term with k = n + 1, we have

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

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

We now apply the previous observation:

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

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

This identity can be written as:

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

which is what we wanted to prove.

Because of the initial condition (S_{n}^{(0)}), the identity (2) corresponds to two different formulas, according to the fact that n is even or odd. We will see this better in the next sections, where we deal with closed formulas and asymptotic approximation. Presently, we have two possible approaches: either we take formula (2) as it stands and develop everything with unitary expressions for the even and odd positions (as Belbachir, Rahmani, and Sury do), or distinguish between even and odd cases, by introducing two sequences (E_{n}^{(m)}) and (O_{n}^{(m)}), only valid for even and odd indices, respectively (obviously, E stands for “Even” and O for “Odd”).

We decided to follow this latter approach, emphasizing the differences between terms in even and odd positions. Actually, the sequence (E_{n}^{(m)}) assumes a specific value, determined by the recurrence, for every n ∈ ℕ, but S_{n}^{(m)} = E_{n}^{(m)} if and only if n is even (otherwise, the value of E_{n}^{(m)} is not immediately related to our problem). The same happens for O_{n}^{(m)}, relative to n odd. Taking into account this observation, formula (2) splits into two relations:

E_{n}^{(m+1)} = (n + 1) (O_{n+1}^{(m)} + E_{n}^{(m)} − (n + 1)^{m})  (3)
O_{n}^{(m+1)} = (n + 1) (E_{n+1}^{(m)} + O_{n}^{(m)} − (n + 1)^{m}) .  (4)

From the other hand, in terms of generating functions, we immediately have

S^{(m)}(t) = \frac{E^{(m)}(t) + E^{(m)}(−t)}{2} + \frac{O^{(m)}(t) − O^{(m)}(−t)}{2};  (5)

thus obtaining the general formula, in case it is necessary.

We are now in a position to derive our results, some of which had already been found by Belbachir, Rahmani, and Sury.

Theorem 3. The generating function of the sequence (E_{n}^{(0)})_{n∈ℕ} is

E^{(0)}(t) = \frac{2}{t(1 − t)} − \frac{2}{t^{2}} ln (\frac{1}{1 − t}) ,

while for S^{(0)}(t) we have

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

Proof. For m = 0, Staver’s formula shows that O^{(0)}(t) = 0 and E_{n}^{(1)} = \frac{n}{2}E_{n}^{(0)}. So relation (3) corresponds to the differential equation

\frac{t}{2} \frac{d}{dt}E^{(0)}(t) = t\frac{d}{dt}E^{(0)}(t) + E^{(0)}(t) − \frac{1}{(1 − t)^{2}} ;

this equation can be solved in an elementary way, and the result is just the formula given in the assertion of the theorem. Finally, we observe that equation (5) reduces to S^{(0)}(t) = (E^{(0)}(t) + E^{(0)}(−t)/2 and the generating function is immediately obtained.

It is now possible to find the generating function O^{(1)}(t):

Theorem 4. The generating function of the sequence (O_{n}^{(1)})_{n∈ℕ} is

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

Proof. Formula (4) becomes

O^{(1)}(t) = \frac{d}{dt}E^{(0)}(t) − \frac{1}{(1 − t)^{2}}

and the identity in the theorem assertion follows immediately.

Here we took into consideration the fact that O^{(0)}(t) = 0. Analogously, we find the generating function E^{(1)}(t).

Theorem 5. For the sequence (E_{n}^{(1)})_{n∈ℕ} we find the generating function:

E^{(1)}(t) = −\frac{2 − 3t}{t(1 − t)^{2}} + \frac{2}{t^{2}} ln (\frac{1}{1 − t}) .

Proof. This time we use formula (3), obtaining

E^{(1)}(t) = t\frac{d}{dt}E^{(0)}(t) + E^{(0)}(t) − \frac{1}{(1 − t)^{2}} .

At this point, we only have to perform some simple computations.

By using identity (5) we get the generating function:

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

with S^{(0)}(t) a result already obtained by Belbachir, Rahmani, and Sury in [2].

The successive generating functions can be obtained in a similar way, by applying formulas (3) and (4). The method of coefficients gives.

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

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

The generating function G((n+1)^{m}) is well-known and is used to define the Eulerian numbers E_{n,k}^{1}. In fact we have G((n + 1)^{m}) = ∑_{k=0}^{m} E_{m,k}t^{k} and

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

G((n + 1)^{m}) = \frac{1}{t}θ^{m} (\frac{1}{1 − t}) where θ = t\frac{d}{dt}.

The first few instances of E^{(m)}(t) are (see sequence A008292 in OEIS):

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!.

Putting everything together, we have

E^{(2)}(t) = \frac{2(6 − 15t + 12t^{2} − 4t^{3} + 2t^{4})}{t^{3}(1 − t)^{3}} − \frac{2t^{2} + 12}{t^{4}} ln (\frac{1}{1 − t});
O^{(2)}(t) = \frac{2(−6 + 15t − 11t^{2} + t^{3})}{t^{2}(1 − t)^{3}} − \frac{12}{t^{3}} ln (\frac{1}{1 − t});
E^{(3)}(t) = \frac{−72 + 252t − 314t^{2} + 157t^{3} − 22t^{4} + 5t^{5}}{t^{3}(1 − t)^{4}} + \frac{2(t^{2} + 36)}{t^{4}} ln (\frac{1}{1 − t});
O^{(3)}(t) = −\frac{48 − 168t + 236t^{2} − 198t^{3} + 131t^{4} − 58t^{5} + 3t^{6}}{t^{4}(1 − t)^{4}} + \frac{4(7t^{2} + 12)}{t^{5}} ln (\frac{1}{1 − t});

1I hate to use the same letter to denote uncorrelated quantities. This time, however, I have not been able to refrain from using the letter E for Even and Eulerian, and the letter O for Odd and Landau’s O-notation.

To avoid ambiguity, Eulerian numbers are noted by a bold E, while Landau’s notation never uses indices or exponents, always present in odd functions.

and we could continue for every m ∈ ℕ. Finally, we leave to the interested reader the computation of the corresponding functions S^{(m)}(t) by means of identity (5).

3 Closed formulas

By developing generating functions as shown at the end of the previous section, we obtain expressions rapidly growing in complexity. Fortunately, formulas (3) and (4) can be used to derive directly closed formulas, without passing through generating functions. We begin by computing closed formulas for E_{n}^{(0)} and O_{n}^{(0)}, then proceed to compute the formulas relative to m > 0.

Theorem 6. For m = 0 we have

E_{n}^{(0)} = \frac{2(n + 1)}{n + 2}  and  O_{n}^{(0)} = 0

Proof. We have already proved the second identity. For the first one, we use the method of coefficients:

E_{n}^{(0)} = [t^{n}]\frac{2}{t(1 − t)}−[t^{n}]\frac{2}{t^{2}} ln (\frac{1}{1 − t}) = 2[t^{n+1}]\frac{1}{1 − t}−2[t^{n+2}] ln (\frac{1}{1 − t}) = 2−\frac{2}{n + 2} = \frac{2(n + 1)}{n + 2}.

Let us now show how formulas (3) and (4) are used to proceed with closed forms.

Theorem 7. For m = 1 we have

E_{n}^{(1)} = \frac{n(n + 1)}{n + 2}  and  O_{n}^{(1)} = \frac{(n + 1)^{2}}{n + 3} .

Proof. By applying formula (3) we find

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

in the same way, by using (4):

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

We can now go on and find closed formulas for our quantities; we only consider m ≤ 5, so that the reader can compare them and the numerical values given in the Introduction:

E_{n}^{(2)} = \frac{n(n + 1)(n^{2} + 4n + 2)}{(n + 2)(n + 4)};
O_{n}^{(2)} = \frac{n(n + 1)^{2}}{n + 3} ;

E_{n}^{(3)} = \frac{n^{2}(n + 1)^{2}(n + 3)}{(n + 2)(n + 4)};
O_{n}^{(3)} = \frac{(n + 1)^{2}(n^{3} + 5n^{2} + n − 1)}{(n + 3)(n + 5)};
E_{n}^{(4)} = \frac{n(n + 1)(n^{5} + 10n^{4} + 28n^{3} + 22n^{2} − 2n − 4)}{(n + 2)(n + 4)(n + 6)};
O_{n}^{(4)} = \frac{n(n + 1)^{3}(n^{2} + 4n − 2)}{(n + 3)(n + 5)};
E_{n}^{(5)} = \frac{n^{2}(n + 1)^{2}(n^{4} + 9n^{3} + 20n^{2} + 5n − 10)}{(n + 2)(n + 4)(n + 6)};
O_{n}^{(5)} = \frac{(n + 1)^{2}(n^{6} + 12n^{5} + 38n^{4} + 17n^{3} − 22n^{2} − 3n + 5)}{(n + 3)(n + 5)(n + 7)}.

The starting point of the paper by Belbachir, Rahmani, and Sury was identity (2.1) in Gould’s collection [3]. Actually, other identities of that book can be proved by the results above; for instance:

Theorem 8. The two identities (2.7) and (2.8) in Gould’s collection:

∑_{k=1}^{n}(−1)^{k−1}\binom{2n}{k}^{−1} = \frac{1}{2(n + 1)} − \frac{(−1)^{n}}{2} \binom{2n}{n}^{−1};

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

hold true.

Proof. Let us call V_{n} the first sum:

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

relating this sum to E_{2n}^{(0)}. Here, the elements in position 1, 2, …, n−1 equal, by symmetry, the elements in position 2n−1, 2n−2, …, n+1 so that V_{n} is obtained from E_{2n}^{(0)} by deleting the elements with k = 0 and k = 2n, by adding a copy of the central element and finally by dividing everything by 2:

V_{n} = −\frac{1}{2} (E_{2n}^{(0)} − 2 + (−1)^{2n−n}\binom{2n}{n}^{−1}) = −\frac{1}{2} · \frac{2(2n + 1)}{2n + 2} + 1 − \frac{(−1)^{n}}{2} \binom{2n}{n}^{−1}.

By simplifying V_{n} we obtain the closed form in the theorem assertion.

For identity (2.8) we call W_{n} the sum in the left hand side:

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

The sum is thus related to E_{2n}^{(1)} and we have

E_{2n}^{(1)} = 0\binom{2n}{0}^{−1} + (−W_{n}) + 2n\binom{2n}{2n}^{−1};

consequently:

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

As for generating functions, also closed formulas grow rapidly in complexity. Therefore, it is important to have approximate formulas to compute these quantities. The closed formulas can be easily changed into asymptotic expansions, for example substituting 1/x to n, expanding into a Taylor series around x = 0 and finally coming back to n. This procedure yields the following interesting expansions:

E_{n}^{(0)} = 2 − \frac{2}{n} + \frac{4}{n^{2}} − \frac{8}{n^{3}} + O (\frac{1}{n^{4}} );
O_{n}^{(0)} = 0;
E_{n}^{(1)} = n − 1 + \frac{2}{n} − \frac{4}{n^{2}} + \frac{8}{n^{3}} + O (\frac{1}{n^{4}} );
O_{n}^{(1)} = n − 1 + \frac{4}{n} − \frac{12}{n^{2}} + \frac{36}{n^{3}} + O (\frac{1}{n^{4}} );
E_{n}^{(2)} = n^{2} − n + 4 − \frac{14}{n} + \frac{52}{n^{2}} − \frac{200}{n^{3}} + O (\frac{1}{n^{4}} );
O_{n}^{(2)} = n^{2} − n + 4 − \frac{12}{n} + \frac{36}{n^{2}} − \frac{108}{n^{3}} + O (\frac{1}{n^{4}} );
E_{n}^{(3)} = n^{3} − n^{2} + 5n − 19 + \frac{74}{n} − \frac{292}{n^{2}} + \frac{1160}{n^{3}} + O (\frac{1}{n^{4}} );
O_{n}^{(3)} = n^{3} − n^{2} + 5n − 19 + \frac{76}{n} − \frac{324}{n^{2}} + \frac{1452}{n^{3}} + O (\frac{1}{n^{4}} );
E_{n}^{(4)} = n^{4} − n^{3} + 6n^{2} − 26n + 116 − \frac{542}{n} + \frac{2644}{n^{2}} − \frac{13448}{n^{3}} + O (\frac{1}{n^{4}} );
O_{n}^{(4)} = n^{4} − n^{3} + 6n^{2} − 26n + 116 − \frac{540}{n} + \frac{2580}{n^{2}} − \frac{12540}{n^{3}} + O (\frac{1}{n^{4}} );
E_{n}^{(5)} = n^{5} − n^{4} + 7n^{3} − 34n^{2} + 168n − 871 + \frac{4682}{n} − \frac{25924}{n^{2}} + \frac{146888}{n^{3}} + O (\frac{1}{n^{4}} );
O_{n}^{(5)} = n^{5} − n^{4} + 7n^{3} − 34n^{2} + 168n − 871 + \frac{4684}{n} − \frac{26052}{n^{2}} + \frac{148676}{n^{3}} + O (\frac{1}{n^{4}} );

These formulas suggest that we might have E_{n}^{(m)} ∼ O_{n}^{(m)} ∼ n^{m} − n^{m−1}, for every m ∈ ℕ. The next section will be dedicated to show that this is indeed the case, and something more.

4 Asymptotics

If we look at the expansions found in the previous section, we may observe that E_{n}^{(m)} and O_{n}^{(m)} have the same expansion up to the term O(1). If we are able to prove this fact, we are in a position to find an asymptotic expansion of S_{n}^{(m)}, valid for every m ≥ k − 1, if k is the number of terms we determine. In our expansion below, we will consider k = 4, which we think sufficient to approximate all the elements S_{n}^{(m)} of interest.

First of all, we prove that E_{n}^{(m)} and O_{n}^{(m)} have the same expansion up to the term O(1). To this purpose, let us define Δ_{n}^{(m)} = E_{n}^{(m)} − O_{n}^{(m)} and show that this difference is O(1/n), which is precisely our assertion on E_{n}^{(m)} and O_{n}^{(m)}.

Theorem 9. For the sequence of differences Δ_{n}^{(m)} we have

Δ_{n}^{(m)} = −\frac{2}{n} + \frac{2^{m+2}}{n^{2}} + O (\frac{1}{n^{3}} ) .

Proof. For small values of m the property is verified by the expansions in the previous section. So, let us look for a recurrence relation and apply the fixed-point method. By formulas (3) and (4) we obtain

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

We now suppose that Δ_{n}^{(m)} has a certain expansion and verify that it is correct. Imagine that:

Δ_{n}^{(m)} = \frac{λ_{m}}{n} + \frac{μ_{m}}{n^{2}} + \frac{ν_{m}}{n^{3}} + ⋯

where “⋯ ” denotes terms of lower order, and (λ_{m}), (μ_{m}) and (ν_{m}) are coefficients, possibly depending on m but not on n. If we substitute this expansion in the previous recurrence relation, we get

\frac{λ_{m+1}}{n} + \frac{μ_{m+1}}{n^{2}} + ⋯ = −λ_{m} − \frac{μ_{m}}{n + 1} − \frac{ν_{m}}{(n + 1)^{2}} − ⋯ + λ_{m} + \frac{μ_{m}}{n} + \frac{ν_{m}}{n^{2}} + ⋯ + \frac{λ_{m}}{n} + \frac{μ_{m}}{n^{2}} + ⋯

= −\frac{μ_{m}}{n} + \frac{μ_{m}}{n^{2}} + ⋯ + \frac{μ_{m}}{n} + ⋯ + \frac{λ_{m}}{n} + \frac{μ_{m}}{n^{2}} + · · · .

By equating terms in 1/n and 1/n^{2} we obtain two simple recurrence relations:

\{ \begin{matrix}λ_{m+1} = λ_{m} \\ μ_{m+1} = 2μ_{m}. \end{matrix}

The initial conditions can be deduced from the expansions in the previous section: λ_{0} = −2 and μ_{0} = 4 = 2^{2}. This implies λ_{m} = −2 and μ_{m} = 2^{m+2}, for all m ∈ ℕ.

This theorem explains why the formulas for E_{n}^{(m)} and O_{n}^{(m)} coincide up to the constant term (for m > 0), that is, they coincide for the most significant terms in a possible asymptotic expansion. In fact, this is the next step in our analysis. As a consequence of the previous theorem, we can consider the recurrence relation (2) and verify that its asymptotic expansion has the form:

S_{n}^{(m)} = α_{m}n^{m} + β_{m}n^{m−1} + γ_{m}n^{m−2} + δ_{m}n^{m−3} + ⋯

for some values α_{m}, β_{m}, γ_{m}, δ_{m}, possibly depending on m, but not on n. In fact, we will be able to determine explicitly these values. Although the method could be used to obtain a complete asymptotic expansion, we think that four terms are enough to have a reasonable approximation of the S_{n}^{(m)}’s.

Theorem 10. The asymptotic expansion of S_{n}^{(m)} (or, equivalently, of E_{n}^{(m)} or O_{n}^{(m)}) is

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

Proof. Let us suppose that the asymptotic expansion of S_{n}^{(m)} be the one given above, and consider the recurrence relation (2). For the left hand side we have

S_{n}^{(m+1)} = α_{m+1}n^{m+1} + β_{m+1}n^{m} + γ_{m+1}n^{m−1} + δ_{m+1}n^{m−2} + ⋯;

For the right hand side we have three contributions. The first one is

(n + 1)S_{n+1}^{(m)} = α_{m}(n + 1)^{m+1} + β_{m}(n + 1)^{m} + γ_{m}(n + 1)^{m−1} + δ_{m}(n + 1)^{m−2} + ⋯

= α_{m}n^{m+1} + α_{m}(m + 1)n^{m} + α_{m}\binom{m + 1}{2}n^{m−1} + α_{m}\binom{m + 1}{3}n^{m−2} + ⋯

+ β_{m}n^{m} + β_{m}mn^{m−1} + β_{m}\binom{m}{2}n^{m−2} + ⋯

+ γ_{m}n^{m−1} + γ_{m}(m − 1)n^{m−2} + ⋯ + δ_{m}n^{m−2} + ⋯;

the second term is

(n + 1)S_{n}^{(m)} = α_{m}n^{m+1} + β_{m}n^{m} + γ_{m}n^{m−1} + δ_{m}n^{m−2} + ⋯ + α_{m}n^{m} + β_{m}n^{m−1} + γ_{m}n^{m−2} + ⋯;

finally, the third term is

(n + 1)^{m+1} = n^{m+1} + (m + 1)n^{m} + \binom{m + 1}{2}n^{m−1} + \binom{m + 1}{3}n^{m−2} + ⋯;

where we ignored all the terms of order n^{m−3}. We now collect like terms and from the coefficients of n^{m+1} we obtain the recurrence relation:

α_{m+1} = 2α_{m} − 1.

Since the initial condition is α_{0} = 1, the obvious solution is α_{m} = 1 for every m ∈ ℕ. We go on with the coefficients of n^{m}; they determine the relation:

β_{m+1} = (m + 1)α_{m} + β_{m} + β_{m} + α_{m} − (m + 1).

Taking into account that α_{m} = 1, we easily arrive to:

β_{m+1} = 2β_{m} + 1.

We leave to the interested reader to justify our assertion that β_{0} = −1, so that β_{m} = −1 for all m ∈ ℕ. The next case (coefficients of n^{m−1}), gives the recurrence relation:

γ_{m+1} = γ_{m} − \frac{m(m + 1)}{2} + α_{m} \frac{m(m + 1)}{2} + β_{m}m + γ_{m};

γ_{m+1} = 2γ_{m} − (m + 1).

For m = 2, we have γ_{2} = 4, and we can prove by mathematical induction that γ = m + 2. Finally, let us come to δ_{m}, for which we collect terms in n^{m−2}:

δ_{m+1} = δ_{m} + γ_{m} − \frac{m^{3} − m}{6} + α_{m} \frac{m^{3} − m}{6} + β_{m} \frac{m^{2} − m}{2} + γ_{m}(m − 1) + δ_{m}.

By simplifying:

δ_{m+1} = 2δ_{m} + m(m + 2) − \frac{m(m − 1)}{2}.

We have now to determine the initial condition, that is, the value of δ_{0}, which is not so simple because we have δ_{0} = 8 for (E_{n}^{(m)}) and δ_{0} = 0 for (O_{n}^{(m)}). We can proceed in the following way: the solution of the recurrence relation is a polynomial p(m) of degree 2; from the values found in the previous section we know p(3) = 19, p(4) = 26 e p(5) = 34. This information is enough to find:

p(m) = δ_{m} = \frac{m^{2} + 7m + 8}{2}.

As a curiosity, we observe that δ_{m} (for m = 0, 1, 2 is the mean between the values obtained for E^{(m)} and O^{(m)}; besides, it is a shifted version of sequence A034856 in OEIS.

Our concluding remark is that S_{n}^{(m)} ∼ n^{m} − n^{m−1} for the alternating sums discussed in this paper, while S_{n}^{(m)} ∼ n^{m} + n^{m−1} for the absolute values sums considered in previous papers [1, 4].

5 Acknowledgments

The author wishes to thank the referee who pointed out some not-so-clear definitions. In this way he or she allowed me to increase the readability of the paper.

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] H. Belbachir, M. Rahmani, and B. Sury. Alternating sums of the reciprocals of binomial coefficients. J. Integer Sequences, 15 (2012), Article 12.2.8.

[3] H. W. Gould. Combinatorial Identities. Morgantown, WV, 1972.

[4] R. Sprugnoli. Moments of reciprocals of binomial coefficients. J. Integer Sequences, 14 (2011), Article 11.7.8.

2010 Mathematics Subject Classification: Primary 11B65; Secondary 05A15, 05A16. Keywords: binomial coefficient, recurrence relation, generating function, asymptotic approximation.

(Concerned with sequences \underline{A008292} and \underline{A034856}.)

Received April 6 2012; revised version received June 13 2012. Published in Journal of Integer Sequences, June 19 2012.

Return to Journal of Integer Sequences home page.