\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\def\N{{\mathbb{N}}}
\newcommand{\NS}{\mbox{\scriptsize${\mathbb{N}}$}}
\newcommand{\de}{\mbox{\rm d}}
\newcommand{\G}{\mbox{$\mathcal{G}$}}
\newcommand{\E}{\mbox{$\mathbf{E}$}}
\newcommand{\OO}{\mbox{$O$}} %\mathbf{O}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Alternating Weighted Sums \\
\vskip .1in
of Inverses of Binomial Coefficients
}
\vskip 1cm
\large
Renzo Sprugnoli \\
Dipartimento di Sistemi e Informatica \\
Viale Morgagni 65 \\
50134 Firenze \\
Italy \\
\href{mailto:renzo.sprugnoli@unifi.it}{\tt renzo.sprugnoli@unifi.it}\\
\end{center}
\vskip .2 in
\begin{abstract}
We consider the alternating sums $S^{(m)}_n = \sum_{k=0}^n (-1)^{n-k}
k^m {n \choose 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.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%
In the present note, we wish to study the sums
\begin{equation} \label{somma}
S^{(m)}_n = \sum_{k=0}^n (-1)^{n-k} k^m {n \choose k}^{-1}.
\end{equation}
These sums, with $(-1)^k$ instead of $(-1)^{n-k}$ have been recently considered by Belbachir, Rahmani, and
Sury \cite{BRS99} (see also Gould \cite{Gou72}), where they derive many properties of $S^{(m)}_n$. 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 \leq m \leq 5$ and
$0 \leq n \leq 9$. These functions have been directly computed by the formula \ref{somma}, so our
result should agree with these values.
\begin{align*}
S^{(0)}(t) &= 1 + \frac{3}{2}t^2 + \frac{5}{3} t^4 + \frac{7}{4}t^6 + \frac{9}{5}t^8 + \cdots \\
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 + \cdots \\
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 + \cdots \\
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 + \cdots \\
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 + \cdots \\
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 +
\cdots.
\end{align*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Recurrence relations and generating functions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The sums considered in this note are analogous to those treated in \cite{BRS11, Spr11}, so we will
try to follow a similar pattern. Let us show how Staver's identity is modified in the present
context.
\begin{theorem}[Staver's identity]
For even values of $n \in \N$ we have
$$S^{(1)}_n = \frac{n}{2}S^{(0)}_n;$$
for odd values of $n \in \N$ we have $S^{(0)}_n = 0$.
\end{theorem}
\begin{proof}
By changing $k \mapsto n-k$, we have
\begin{align*}
S^{(1)}_n &= \sum_{k=0}^n (-1)^{n-k}k {n \choose k}^{-1} \\
&= \sum_{k=0}^n (-1)^k (n-k) {n \choose k}^{-1} \\
&= n \sum_{k=0}^n (-1)^k {n \choose k}^{-1} - \sum_{k=0}^n (-1)^k k {n \choose k}^{-1}.
\end{align*}
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^{(0)}_n = 0$.
\end{proof}
This lemma is not sufficient to go on with our study; the author \cite{Spr11} has shown
$${n+1 \choose k}^{-1} = {n \choose k}^{-1} - \frac{k}{n+1} {n \choose k}^{-1}$$
and this allows to prove the basic result:
\begin{theorem}
For the sums $S^{(m)}_n$ the following recurrence relation holds true:
\begin{equation} \label{dunzi}
S^{(m+1)}_n = (n+1) \left( S^{(m)}_{n+1} + S^{(m)}_n - (n+1)^m \right).
\end{equation}
\end{theorem}
\begin{proof}
According to the definition, by isolating the term with $k = n+1$, we have
\begin{align*}
S^{(m)}_{n+1} &= \sum_{k=0}^{n+1} (-1)^{n+1-k} k^m {n+1 \choose k}^{-1} \\
&= - \sum_{k=0}^{n} (-1)^{n-k} k^m {n+1 \choose k}^{-1} + (n+1)^m {n+1 \choose n+1}.
\end{align*}
We now apply the previous observation:
\begin{align*}
S^{(m)}_{n+1} &= -\sum_{k=0}^{n} (-1)^{n-k} k^m {n \choose k}^{-1} + \sum_{k=0}^{n}
(-1)^{n-k} \frac{k}{n+1} k^m {n \choose k}^{-1} + (n+1)^m \\
&= - S^{(m)}_n + \frac{1}{n+1} S^{(m+1)}_n + (n+1)^m.
\end{align*}
This identity can be written as:
$$S^{(m+1)}_n = (n+1) \left( S^{(m)}_{n+1} + S^{(m)}_n - (n+1)^m \right)$$
which is what we wanted to prove.
\end{proof}
Because of the initial condition $(S^{(0)}_n)$, the identity (\ref{dunzi}) 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 (\ref{dunzi}) 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^{(m)}_n)$ and $(O^{(m)}_n)$, 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^{(m)}_n)$ assumes a specific value, determined by the recurrence, for every $n \in \N$, but $S^{(m)}_n = E^{(m)}_n$ if and only if $n$ is even (otherwise, the value of $E^{(m)}_n$ is not immediately related to our problem). The same happens for $O^{(m)}_n$, relative to $n$ odd. Taking into account this observation, formula (\ref{dunzi}) splits into two relations:
\begin{equation} \label{E1}
E^{(m+1)}_n = (n+1) \left( O^{(m)}_{n+1} + E^{(m)}_n - (n+1)^m \right)
\end{equation}
\begin{equation} \label{O1}
O^{(m+1)}_n = (n+1) \left( E^{(m)}_{n+1} + O^{(m)}_n - (n+1)^m \right).
\end{equation}
From the other hand, in terms of generating functions, we immediately have
\begin{equation} \label{SEO}
S^{(m)}(t) = \frac{E^{(m)}(t) + E^{(m)}(-t)}{2} + \frac{O^{(m)}(t) - O^{(m)}(-t)}{2};
\end{equation}
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.
\begin{theorem}
The generating function of the sequence $(E^{(0)}_n)_{n\in\NS}$ is
$$E^{(0)}(t) = \frac{2}{t(1-t)}- \frac{2}{t^2} \ln\left( \frac{1}{1-t} \right),$$
while for $S^{(0)}(t)$ we have
$$S^{(0)}(t) = \frac{2}{1-t^2} - \frac{1}{t^2} \ln\left( \frac{1}{1-t^2} \right).$$
\end{theorem}
\begin{proof}
For $m=0$, Staver's formula shows that $O^{(0)}(t) = 0$ and $E^{(1)}_n = \frac{n}{2} E^{(0)}_n$. So
relation (\ref{E1}) corresponds to the differential equation
$$\frac{t}{2} \frac{\de}{\de t}E^{(0)}(t) = t\frac{\de}{\de t}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 (\ref{SEO}) reduces to $S^{(0)}(t) = (E^{(0)}(t) + E^{(0)}(-t)/2$ and the generating function is immediately obtained.
\end{proof}
It is now possible to find the generating function $O^{(1)}(t)$:
\begin{theorem}
The generating function of the sequence $(O^{(1)}_n)_{n\in\NS}$ is
$$O^{(1)}(t) = -\frac{4-6t+t^2}{t^2(1-t)^2} + \frac{4}{t^3} \ln\left( \frac{1}{1-t} \right).$$
\end{theorem}
\begin{proof}
Formula (\ref{O1}) becomes
$$O^{(1)}(t) = \frac{\de}{\de t}E^{(0)}(t) - \frac{1}{(1-t)^2}$$
and the identity in the theorem assertion follows immediately.
\end{proof}
Here we took into consideration the fact that $O^{(0)}(t) = 0$. Analogously, we find the generating
function $E^{(1)}(t)$.
\begin{theorem}
For the sequence $(E^{(1)}_n)_{n\in\NS}$ we find the generating function:
$$E^{(1)}(t) = - \frac{2-3t}{t(1-t)^2} + \frac{2}{t^2} \ln\left( \frac{1}{1-t} \right).$$
\end{theorem}
\begin{proof}
This time we use formula (\ref{E1}), obtaining
$$E^{(1)}(t) = t \frac{\de}{\de t}E^{(0)}(t) + E^{(0)}(t) - \frac{1}{(1-t)^2}.$$
At this point, we only have to perform some simple computations.
\end{proof}
By using identity (\ref{SEO}) we get the generating function:
$$S^{(1)}(t) = - \frac{2-3t}{t(1-t)^2} + \frac{2+t}{t^3} \ln\left( \frac{1}{1-t^2} \right):$$
with $S^{(0)}(t)$ a result already obtained by Belbachir, Rahmani, and Sury in \cite{BRS99}.
The successive generating functions can be obtained in a similar way, by applying formulas
(\ref{E1}) and (\ref{O1}). The method of coefficients gives.
$$E^{(m+1)}(t) = \frac{\de}{\de t} O^{(m)}(t) + t\frac{\de}{\de t}E^{(m)}(t) + E^{(m)}(t)
- \G((n+1)^{m+1});$$
$$O^{(m+1)}(t) = \frac{\de}{\de t} E^{(m)}(t) + t\frac{\de}{\de t}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}$\footnote{I 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 \emph{odd} functions.}. In
fact we have $\G((n+1)^m) = \sum_{k=0}^m \E_{m,k}t^k$ and
$$\G\left( (n+1)^m \right) = \frac{\E^{(m)}(t)}{(1-t)^{m+1}}$$
$$\G((n+1)^m) = \frac{1}{t} \theta^m \left( \frac{1}{1-t} \right) \qquad {\rm where} \qquad
\theta = t\frac{\de}{\de t}.$$
The first few instances of $\E^{(m)}(t)$ are (see sequence A008292 in OEIS):
\begin{align*}
\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.
\end{align*}
It is well-known that $\E^{(m)}(1) = m!$.
Putting everything together, we have
\begin{align*}
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\left(
\frac{1}{1-t} \right); \\
O^{(2)}(t) &= \frac{2(-6+15t-11t^2+t^3)}{t^2(1-t)^3} - \frac{12}{t^3}\ln\left( \frac{1}
{1-t} \right); \\
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\left( \frac{1}{1-t} \right); \\
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+1
2)}{t^5}\ln\left( \frac{1}{1-t} \right);
\end{align*}
and we could continue for every $m \in \N$. Finally, we leave to the interested reader the computation of the corresponding functions $S^{(m)}(t)$ by means of identity (\ref{SEO}).
%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Closed formulas}
%%%%%%%%%%%%%%%%%%%%%%%%%
By developing generating functions as shown at the end of the previous section, we obtain
expressions rapidly growing in complexity. Fortunately, formulas (\ref{E1}) and (\ref{O1}) can be
used to derive directly closed formulas, without passing through generating functions. We begin by
computing closed formulas for $E^{(0)}_n$ and $O^{(0)}_n$, then proceed to compute the formulas
relative to $m > 0$.
\begin{theorem}
For $m = 0$ we have
$$E^{(0)}_n = \frac{2(n+1)}{n+2} \qquad {\rm and} \qquad O^{(0)}_n = 0$$
\end{theorem}
\begin{proof}
We have already proved the second identity. For the first one, we use the method of coefficients:
$$E^{(0)}_n = [t^n] \frac{2}{t(1-t)} - [t^n] \frac{2}{t^2} \ln\left( \frac{1}{1-t} \right) = 2
[t^{n+1}] \frac{1}{1-t} - 2 [t^{n+2}]\ln\left( \frac{1}{1-t} \right) = 2 - \frac{2}{n+2} =
\frac{2(n+1)}{n+2}.$$
\end{proof}
Let us now show how formulas (\ref{E1}) and (\ref{O1}) are used to proceed with closed forms.
\begin{theorem}
For $m=1$ we have
$$E^{(1)}_n = \frac{n(n+1)}{n+2} \qquad {\rm and} \qquad O^{(1)}_n = \frac{(n+1)^2}{n+3}.$$
\end{theorem}
\begin{proof}
By applying formula (\ref{E1}) we find
$$E^{(1)}_n = (n+1) \left( 0 + \frac{2(n+1)}{n+2} - 1 \right) = \frac{n(n+1)}{n+2};$$
in the same way, by using (\ref{O1}):
$$O^{(1)}_n = (n+1) \left( \frac{2(n+2)}{n+3} + 0 - 1 \right) = \frac{(n+1)^2}{n+3}.$$
\end{proof}
We can now go on and find closed formulas for our quantities; we only consider $m \leq 5$, so that
the reader can compare them and the numerical values given in the Introduction:
\begin{align*}
E^{(2)}_n &= \frac{n(n+1)(n^2+4n+2)}{(n+2)(n+4)}; \\
O^{(2)}_n &= \frac{n(n+1)^2}{n+3};
\end{align*}
\begin{align*}
E^{(3)}_n &= \frac{n^2(n+1)^2(n+3)}{(n+2)(n+4)}; \\
O^{(3)}_n &= \frac{(n+1)^2(n^3+5n^2+n-1)}{(n+3)(n+5)}; \\
E^{(4)}_n &= \frac{n(n+1)(n^5+10n^4+28n^3+22n^2-2n-4)}{(n+2)(n+4)(n+6)}; \\
O^{(4)}_n &= \frac{n(n+1)^3(n^2+4n-2)}{(n+3)(n+5)}; \\
E^{(5)}_n &= \frac{n^2(n+1)^2(n^4+9n^3+20n^2+5n-10)}{(n+2)(n+4)(n+6)}; \\
O^{(5)}_n &= \frac{(n+1)^2(n^6+12n^5+38n^4+17n^3-22n^2-3n+5)}{(n+3)(n+5)(n+7)}.
\end{align*}
The starting point of the paper by Belbachir, Rahmani, and Sury was identity (2.1) in Gould's collection \cite{Gou72}. Actually, other identities of that book can be proved by the results above; for instance:
\begin{theorem}
The two identities (2.7) and (2.8) in Gould's collection:
$$\sum_{k=1}^n (-1)^{k-1} {2n \choose k}^{-1} = \frac{1}{2(n+1)} - \frac{(-1)^n}{2} {2n \choose n}^{-1};$$
$$\sum_{k=1}^{2n-1} (-1)^{k-1} k {2n \choose k}^{-1} = \frac{n}{n+1}$$
hold true.
\end{theorem}
\begin{proof}
Let us call $V_n$ the first sum:
$$V_n = \sum_{k=1}^n (-1)^{k-1} {2n \choose k}^{-1} = - \sum_{k=1}^n (-1)^{2n-k} {2n \choose k}^{-1},$$
relating this sum to $E^{(0)}_{2n}$. Here, the elements in position $1,\ 2,\ \ldots,\ n-1$ equal, by symmetry, the elements in position $2n-1,\ 2n-2,\ \ldots,\ n+1$ so that $V_n$ is obtained from $E^{(0)}_{2n}$ 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} \left( E^{(0)}_{2n} - 2 + (-1)^{2n-n}{2n \choose n}^{-1} \right) = - \frac{1}{2} \cdot \frac{2 (2n+1)}{2n+2} + 1 - \frac{(-1)^n}{2} {2n \choose 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 = - \sum_{k=1}^{2n-1} (-1)^{2n-k} k {2n \choose k}^{-1}.$$
The sum is thus related to $E^{(1)}_{2n}$ and we have
$$E^{(1)}_{2n} = 0 {2n \choose 0}^{-1} + (-W_n) + 2n{2n \choose 2n}^{-1};$$
consequently:
$$W_n = - E^{(1)}_{2n} + 2n = 2n - \frac{2n(2n+1)}{2n+2} = \frac{2n^2 + 2n - 2n^2 - n}{n+1} = \frac{n}{n+1}.$$
\end{proof}
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:
\begin{align*}
E^{(0)}_n &= 2 - \frac{2}{n} + \frac{4}{n^2} - \frac{8}{n^3} + \OO\left( \frac{1}{n^4} \right); \\
O^{(0)}_n &= 0; \\
E^{(1)}_n &= n - 1 + \frac{2}{n} - \frac{4}{n^2} + \frac{8}{n^3} + \OO\left( \frac{1}{n^4}
\right); \\
O^{(1)}_n &= n - 1 + \frac{4}{n} - \frac{12}{n^2} + \frac{36}{n^3} + \OO\left( \frac{1}{n^4}
\right); \\
E^{(2)}_n &= n^2 - n + 4 - \frac{14}{n} + \frac{52}{n^2} - \frac{200}{n^3} + \OO\left( \frac{1}
{n^4} \right); \\
O^{(2)}_n &= n^2 - n + 4 - \frac{12}{n} + \frac{36}{n^2} - \frac{108}{n^3} + \OO\left( \frac{1}
{n^4} \right); \\
E^{(3)}_n &= n^3 - n^2 + 5n - 19 + \frac{74}{n} - \frac{292}{n^2} + \frac{1160}{n^3} + \OO\left(
\frac{1}{n^4} \right); \\
O^{(3)}_n &= n^3 - n^2 + 5n - 19 + \frac{76}{n} - \frac{324}{n^2} + \frac{1452}{n^3} + \OO\left(
\frac{1}{n^4} \right); \\
E^{(4)}_n &= n^4 - n^3 + 6n^2 - 26n + 116 - \frac{542}{n} + \frac{2644}{n^2} - \frac{13448}{n^3}
+ \OO\left( \frac{1}{n^4} \right); \\
O^{(4)}_n &= n^4 - n^3 + 6n^2 - 26n + 116 - \frac{540}{n} + \frac{2580}{n^2} - \frac{12540}{n^3}
+ \OO\left( \frac{1}{n^4} \right); \\
E^{(5)}_n &= n^5 - n^4 + 7n^3 - 34n^2 + 168n - 871 + \frac{4682}{n} - \frac{25924}{n^2} + \frac
{146888}{n^3} + \OO\left( \frac{1}{n^4} \right); \\
O^{(5)}_n &= n^5 - n^4 + 7n^3 - 34n^2 + 168n - 871 + \frac{4684}{n} - \frac{26052}{n^2} + \frac
{148676}{n^3} + \OO\left( \frac{1}{n^4} \right);
\end{align*}
These formulas suggest that we might have $E^{(m)}_n \sim O^{(m)}_n \sim n^m - n^{m-1}$, for every $m
\in \N$. The next section will be dedicated to show that this is indeed the case, and something
more.
%%%%%%%%%%%%%%%%%%%%%
\section{Asymptotics}
%%%%%%%%%%%%%%%%%%%%%
If we look at the expansions found in the previous section, we may observe that $E^{(m)}_n$ and
$O^{(m)}_n$ have the same expansion up to the term $\OO(1)$. If we are able to prove this fact, we
are in a position to find an asymptotic expansion of $S^{(m)}_n$, valid for every $m \geq 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^{(m)}_n$ of interest.
First of all, we prove that $E^{(m)}_n$ and $O^{(m)}_n$ have the same expansion up to the term
$\OO(1)$. To this purpose, let us define $\Delta^{(m)}_n = E^{(m)}_n - O^{(m)}_n$ and show that
this difference is $\OO(1/n)$, which is precisely our assertion on $E^{(m)}_n$ and $O^{(m)}_n$.
\begin{theorem}
For the sequence of differences $\Delta^{(m)}_n$ we have
$$\Delta^{(m)}_n = -\frac{2}{n} + \frac{2^{m+2}}{n^2} + \OO\left( \frac{1}{n^3} \right).$$
\end{theorem}
\begin{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 (\ref{E1}) and
(\ref{O1}) we obtain
$$\Delta^{(m+1)}_n = -(n+1)\Delta^{(m)}_{n+1} + n\Delta^{(m)}_n + \Delta^{(m)}_n.$$
We now suppose that $\Delta^{(m)}_n$ has a certain expansion and verify that it is correct. Imagine
that:
$$\Delta^{(m)}_n = \frac{\lambda_m}{n} + \frac{\mu_m}{n^2} + \frac{\nu_m}{n^3} + \cdots$$
where ``$\cdots$'' denotes terms of lower order, and $(\lambda_m)$, $(\mu_m)$ and $(\nu_m)$ are
coefficients, possibly depending on $m$ but not on $n$. If we substitute this expansion in the
previous recurrence relation, we get
\begin{align*}
\frac{\lambda_{m+1}}{n} + \frac{\mu_{m+1}}{n^2} + \cdots &= -\lambda_m - \frac{\mu_m}{n+1} -
\frac{\nu_m}{(n+1)^2} - \cdots + \lambda_m + \frac{\mu_m}{n} + \frac{\nu_m}{n^2} + \cdots +
\frac{\lambda_m}{n} + \frac{\mu_m}{n^2} + \cdots \\
&= - \frac{\mu_m}{n} + \frac{\mu_m}{n^2} + \cdots + \frac{\mu_m}{n} + \cdots + \frac{\lambda_m}{n} +
\frac{\mu_m}{n^2} + \cdots .
\end{align*}
By equating terms in $1/n$ and $1/n^2$ we obtain two simple recurrence relations:
$$\left\{ \begin{array} {l} \lambda_{m+1} = \lambda_m \\
\mu_{m+1} = 2 \mu_m.
\end{array} \right.$$
The initial conditions can be deduced from the expansions in the previous section: $\lambda_0 = -2$
and $\mu_0 = 4 = 2^2$. This implies $\lambda_m = -2$ and $\mu_m = 2^{m+2}$, for all $m \in \N$.
\end{proof}
This theorem explains why the formulas for $E^{(m)}_n$ and $O^{(m)}_n$ 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 (\ref{dunzi}) and verify that its
asymptotic expansion has the form:
$$S^{(m)}_n = \alpha_m n^m + \beta_m n^{m-1} + \gamma_m n^{m-2} + \delta_m n^{m-3} + \cdots$$
for some values $\alpha_m,\ \beta_m,\ \gamma_m,\ \delta_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^{(m)}_n$'s.
\begin{theorem}
The asymptotic expansion of $S^{(m)}_n$ (or, equivalently, of $E^{(m)}_n$ or $O^{(m)}_n$) is
$$S^{(m)}_n = n^m - n^{m-1} + (m+2)n^{m-2} - \frac{m^2+7m+8}{2}n^{m-3} + \OO(n^{m-4}).$$
\end{theorem}
\begin{proof}
Let us suppose that the asymptotic expansion of $S^{(m)}_n$ be the one given above, and consider
the recurrence relation (\ref{dunzi}). For the left hand side we have
$$S^{(m+1)}_n = \alpha_{m+1}n^{m+1} + \beta_{m+1}n^m + \gamma_{m+1}n^{m-1} + \delta_{m+1}n^{m-2}
+ \cdots;$$
For the right hand side we have three contributions. The first one is
\begin{align*}
(n+1)S^{(m)}_{n+1} &= \alpha_{m}(n+1)^{m+1} + \beta_{m}(n+1)^m + \gamma_{m}(n+1)^{m-1} +
\delta_{m}(n+1)^{m-2} + \cdots \\
&= \alpha_{m}n^{m+1} + \alpha_{m}(m+1)n^m + \alpha_{m} {m+1 \choose 2}n^{m-1} + \alpha_{m}
{m+1 \choose 3}n^{m-2} + \cdots \\
&+ \beta_{m}n^m + \beta_{m}mn^{m-1} + \beta_{m}{m \choose 2}n^{m-2} + \cdots \\
&+ \gamma_{m} n^{m-1} + \gamma_{m}(m-1)n^{m-2} + \cdots + \delta_{m}n^{m-2} + \cdots;
\end{align*}
the second term is
$$(n+1)S^{(m)}_n = \alpha_{m}n^{m+1} + \beta_m n^m + \gamma_m n^{m-1} + \delta_m n^{m-2} +
\cdots + \alpha_m n^m + \beta_m n^{m-1} + \gamma_m n^{m-2} + \cdots;$$
finally, the third term is
$$(n+1)^{m+1} = n^{m+1} + (m+1)n^m + {m+1 \choose 2}n^{m-1} + {m+1 \choose 3}n^{m-2} + \cdots;$$
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:
$$\alpha_{m+1} = 2\alpha_m - 1.$$
Since the initial condition is $\alpha_0 = 1$, the obvious solution is $\alpha_m = 1$ for every $m
\in \N$. We go on with the coefficients of $n^m$; they determine the relation:
$$\beta_{m+1} = (m+1)\alpha_m + \beta_m + \beta_m + \alpha_m - (m+1).$$
Taking into account that $\alpha_m = 1$, we easily arrive to:
$$\beta_{m+1} = 2 \beta_m + 1.$$
We leave to the interested reader to justify our assertion that $\beta_0 = -1$, so that $\beta_m =
-1$ for all $m \in \N$. The next case (coefficients of $n^{m-1}$), gives the recurrence relation:
$$\gamma_{m+1} = \gamma_m - \frac{m(m+1)}{2} + \alpha_m \frac{m(m+1)}{2} + \beta_mm + \gamma_m;$$
$$\gamma_{m+1} = 2\gamma_m - (m+1).$$
For $m=2$, we have $\gamma_2 = 4$, and we can prove by mathematical induction that $\gamma = m+2$.
Finally, let us come to $\delta_m$, for which we collect terms in $n^{m-2}$:
$$\delta_{m+1} = \delta_m + \gamma_m - \frac{m^3-m}{6} + \alpha_m \frac{m^3-m}{6} + \beta_m \frac{m^2-m}{2} + \gamma_m(m-1) + \delta_m.$$
By simplifying:
$$\delta_{m+1} = 2\delta_m + m(m+2) - \frac{m(m-1)}{2}.$$
We have now to determine the initial condition, that is, the value of $\delta_0$, which is not so simple because we have $\delta_0 = 8$ for $(E^{(m)}_n)$ and $\delta_0 = 0$ for $(O^{(m)}_n)$. 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) = \delta_m = \frac{m^2+7m+8}{2}.$$
As a curiosity, we observe that $\delta_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.
\end{proof}
Our concluding remark is that $S^{(m)}_n \sim n^m - n^{m-1}$ for the
alternating sums discussed in this paper, while $S^{(m)}_n \sim n^m +
n^{m-1}$ for the absolute values sums considered in previous papers
\cite{BRS11, Spr11}.
\section{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.
\begin{thebibliography}{99}
\normalsize
\bibitem{BRS11}
H. Belbachir, M. Rahmani, and B. Sury.
\newblock Sums involving moments of reciprocals of binomial coefficients.
\newblock \textit{J. Integer Sequences}, \textbf{14} (2011),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Rahmani/rahmani3.html}{Article 11.6.6}.
\bibitem{BRS99}
H. Belbachir, M. Rahmani, and B. Sury.
\newblock Alternating sums of the reciprocals of binomial coefficients.
\newblock \textit{J. Integer Sequences}, \textbf{15} (2012),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Rahmani/rahmani3.html}{Article 12.2.8}.
\bibitem{Gou72}
H. W. Gould.
\newblock \textit{Combinatorial Identities}.
\newblock Morgantown, WV, 1972.
\bibitem{Spr11}
R. Sprugnoli.
\newblock Moments of reciprocals of binomial coefficients.
\newblock \textit{J. Integer Sequences}, \textbf{14} (2011),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Sprugnoli/sprugnoli4.html}{Article 11.7.8}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B65; Secondary 05A15, 05A16.
\noindent \emph{Keywords: } binomial coefficient,
recurrence relation, generating function, asymptotic approximation.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A008292} and
\seqnum{A034856}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received April 6 2012;
revised version received June 13 2012.
Published in {\it Journal of Integer Sequences}, June 19 2012.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}