<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}

\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 
Moments of Reciprocals of \\
\vskip .1in
Binomial Coefficients
}
\vskip 1cm
\large
Renzo Sprugnoli\\
Dipartimento di Sistemi e Informatica \\
Viale Morgagni 65\\
54134 Firenze \\
Italy\\
\href{mailto:renzo.sprugnoli@unifi.it}{\tt renzo.sprugnoli@unifi.it} \\
\end{center}

\vskip .2 in

%
%\documentclass[twoside]{article}
%\usepackage{epsfig,pstricks,pst-node,pst-tree,ifthen}
%\usepackage{amssymb,eurosym,url}
%\textwidth 16.5cm \textheight 23cm \topmargin -1cm \oddsidemargin 0cm \evensidemargin 0cm

\newcommand{\N}{\mbox{$\mathbb{N}$}}
\newcommand{\NS}{\mbox{\scriptsize${\mathbb{N}}$}}
\newcommand{\Q}{\mbox{$\mathbb{Q}$}}
\newcommand{\C}{\mbox{${\tiny \mathbb{C}}$}}
\newcommand{\FF}{\mbox{$\mathbb{F}$}}
\newcommand{\R}{\mbox{$\mathbb{R}$}}
\newcommand{\Z}{\mbox{$\mathbb{Z}$}}
\newcommand{\F}{\mbox{$\mathcal{F}$}}
\newcommand{\G}{\mbox{$\mathcal{G}$}}
\renewcommand{\L}{\mbox{$\mathcal{L}$}}
\newcommand{\Ra}{\mbox{$\mathcal{R}$}}
\newcommand{\ord}{\mbox{{\rm ord}}}
\newcommand{\SEP}{\ \Bigm|\ }
\newcommand{\de}{\mbox{\rm d}}
\newcommand{\EQ}[1]{\mbox{$\stackrel{\ \small #1}{=}\ $}}
\def\Gf#1{\G\left( #1\right)}
\def\matrice#1{\left(#1_{n,k}\right)_{n,k\in N}}
\def\insieme#1{\left\{#1\right\}}
\def\sequ#1{\left(#1_k\right)_{k\in N}}
\def\stdue#1#2{\left\{{#1\atop#2}\right\}}
\def\stuno#1#2{\left[{#1\atop#2}\right]}


\begin{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,\ \ldots,\ 5$).
Finally we give asymptotic approximations of the moments and of related
quantities.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%
The present developments on moments of reciprocals of binomial
coefficients are motivated by the paper \cite{Belbachir} 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
\begin{equation} \label{somma}
    S^{(m)}_n = \sum_{k=0}^n k^m {n \choose k}^{-1}.
\end{equation}

By using this formula, we obtain the generating functions of the first instances $m = 0,\ 1,\ \cdots,\ 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 + \cdots$$
  $$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 + \cdots$$
  $$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 + \cdots.$$
  $$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} + \cdots$$
  $$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}+ \cdots$$
  $$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} + \cdots$$


These values will be useful for checking the formulas obtained below.
The only sequence occurring in Sloane's {\it Encyclopedia} \cite{Sloane} is
related to $S^{(0)}(t)$, which is the exponential generating function
of sequence \seqnum{A003149}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Basic relations}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The first important result was obtained by T.\ B.\ Staver \cite{Staver}
more than 60 years ago. It is the starting point for studying the sums
$S^{(m)}_n$.

\begin{theorem}[Staver, 1947]
  The following relation holds true for every $n \in \N$:
  $$S^{(1)}_n = \frac{n}{2}\,S^{(0)}_n.$$
\end{theorem}
\begin{proof}
  By the change of variable $k \mapsto n-k$ we obtain:
  $$\sum_{k=0}^n k {n \choose k}^{-1} = \sum_{k=0}^n (n-k) {n \choose k}^{-1}.$$
  From this we get $S^{(1)}_n = nS^{(0)}_n - S^{(1)}_n$ which is the theorem assertion.
\end{proof}

The following observation plays a fundamental role in our present approach:
\begin{lemma}
  For every $k \leq n$ we have:
  $${n+1 \choose k}^{-1} = {n \choose k}^{-1} - \frac{k}{n+1} {n \choose k}^{-1}.$$
\end{lemma}
\begin{proof}
  We immediately have:
  $${n+1 \choose 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} {n \choose k}^{-1}$$
  and this is the relation to be proved.
\end{proof}

This lemma implies an important recurrence relation, from which the successive results follow:
\begin{theorem} \label{sprugnoli}
  The following relation holds true for every $m, n \in \N$:
  $$S^{(m)}_{n+1} = S^{(m)}_n - \frac{1}{n+1} S^{(m+1)}_n + (n+1)^m.$$
\end{theorem}
\begin{proof}
  We use the previous lemma and obtain:
  $$S^{(m)}_{n+1} = \sum_{k=0}^{n+1} k^m {n+1 \choose k}^{-1} = \sum_{k=0}^n k^m {n+1
  \choose k}^{-1} + (n+1)^m {n+1 \choose n+1}^{-1} =$$
  $$= \sum_{k=0}^n k^m {n \choose k}^{-1} - \sum_{k=0}^n \frac{k^{m+1}}{n+1} {n \choose
  k}^{-1} + (n+1)^m = S^{(m)}_n - \frac{1}{n+1} S^{(m+1)}_n + (n+1)^m.$$
\end{proof}

What follows will be derived by Staver's theorem and Theorem \ref{sprugnoli}. In fact, we are in a
position to prove the recurrence of Staver:
\begin{theorem} \label{Szero}
  The sequence $(S^{(0)}_n)$ satisfies the recurrence relation:
  $$S^{(0)}_{n+1} = \frac{n+2}{2(n+1)} S^{(0)}_n + 1$$
  with the initial condition $S^{(0)}_0 = 1$.
\end{theorem}
\begin{proof}
  We specialize the previous theorem by setting $m=0$:
  $$S^{(0)}_{n+1} = S^{(0)}_n - \frac{1}{n+1} S^{(1)}_n + (n+1)^0,$$
  and apply Staver's theorem:
  $$S^{(0)}_{n+1} = S^{(0)}_n - \frac{n}{2(n+1)} S^{(0)}_n + 1.$$
  This is the recurrence we were looking for.
\end{proof}

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

\begin{theorem}
  The generating function of the sequence $(S^{(0)}_n)_{n \in \NS}$ satisfies the following
  differential equation\footnote{A superscripted dot denotes here differentiation by $t$.}:
  $$(2-t) \dot{S}^{(0)}(t) = 2 S^{(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}.$$
\end{theorem}
\begin{proof}
  From the recurrence relation found above, we get:
  $$2(n+1) S^{(0)}_{n+1} = nS^{(0)}_n + 2S^{(0)}_n + 2(n+1).$$
  By using the generating function $(1-t)^{-2}$ of the sequence $(n+1)_{n \in \NS}$ and by applying
  the method of coefficients (see, e.g., \cite{Merlini}), we find:
  $$2 \dot{S}^{(0)}(t) = t \dot{S}^{(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.
\end{proof}

We now obtain Staver's formula:
\begin{theorem}
  The numbers $S^{(0)}_n$ can be computed by the following non-closed formula:
  $$S^{(0)}_n = [t^n] \frac{2}{(1-t)(2-t)} - [t^n]\frac{2 \ln(1-t)}{(2-t)^2} = \frac{n+1}{2^{n+1}}
  \sum_{k=1}^{n+1} \frac{2^k}{k}.$$
\end{theorem}
\begin{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} \sum_{k=1}^n \frac{1}{k}
  \frac{n-k+1}{2^{n-k}} = \frac{n+1}{2^{n+1}} \sum_{k=1}^n \frac{2^k}{k} - \frac{1}{2^{n+1}}
  \sum_{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}} \sum_{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^{(0)}_n = 2 - \frac{1}{2^n} + \frac{n+1}{2^{n+1}} \sum_{k=1}^n \frac{2^k}{k} -
  1 + \frac{1}{2^n} = \frac{n+1}{2^{n+1}} \sum_{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.
\end{proof}

Bender's theorem (see \cite{Bender}) gives $S^{(0)}_n \sim 2$, but we can obtain an asymptotic expansion:
\begin{theorem} \label{ASS0}
  We have the following asymptotic expansion:
  $$S^{(0)}_n = 2 + \frac{2}{n} + \frac{4}{n(n-1)} + \frac{12}{n(n-1)(n-2)} + O\left(
  \frac{1}{n^4} \right) = 2 + \frac{2}{n} + \frac{4}{n^2} + \frac{16}{n^3} + O\left(
  \frac{1}{n^4} \right).$$
\end{theorem}
\begin{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} \sim 2.$$
  For the second part, we can expand everything
  around the dominating singularity $t = 1$ and obtain:
  $$\left(2 - 4(1-t) + 6(1-t)^2 +O((1-t)^3)\right) \ln\left( \frac{1}{1-t} \right).$$
  By extracting coefficients, we obtain the expansion in the assertion.
\end{proof}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The expansions}
%%%%%%%%%%%%%%%%%%%%%%%%%%

In their paper \cite{Belbachir}, Belbachir, Rahmani, and Sury find relations expressing $S^{(m)}_n$ in terms of $S^{(0)}_n$, 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:
\begin{theorem} \label{DAS0}
  For every $m \in \N$ we have:
\begin{equation} \label{Smn}
      S^{(m)}_n = P^{(m)}(n) S^{(0)}_n + Q^{(m)}(n)
\end{equation}
  where $P^{(m)}(n)$ and $Q^{(m)}(n)$ are polynomials in $n$ of degree $m$, except $Q^{(0)}(n) =
  Q^{(1)}(n) = 0$.
\end{theorem}
\begin{proof}
  We proceed by mathematical induction on $m$. When $m = 0$, we consider the obvious identity
  $S^{(0)}_n = S^{(0)}_n$, 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 (\ref{Smn}) holds true for a given
  $m$ and consider the identity in Theorem \ref{sprugnoli}, which we can write as
  $$S^{(m+1)}_n = (n+1)S^{(m)}_n  - (n+1)S^{(m)}_{n+1} + (n+1)^{m+1}.$$
By the inductive hypothesis, identity (\ref{Smn}) holds true together with the companion formula
  $$S^{(m)}_{n+1} = P^{(m)}(n+1) S^{(0)}_{n+1} + Q^{(m)}(n+1).$$
Let us substitute these values in the previous equation:
\begin{multline}
S^{(m+1)}_n = (n+1) \left( P^{(m)}(n) S^{(0)}_n + Q^{(m)}(n) \right) - (n+1) \left( P^{(m)}
  (n+1) S^{(0)}_{n+1} + Q^{(m)}(n+1) \right) \\
  + (n+1)^{m+1}.
\end{multline}
  Finally, we use the recurrence for $S^{(0)}_n$ in the form of Theorem \ref{Szero}
  $$S^{(0)}_{n+1} = \frac{n+2}{2(n+1)} S^{(0)}_n + 1;$$
  this is done to eliminate $S^{(0)}_{n+1}$. By rearranging terms, we find:
  $$S^{(m+1)}_n = \left( (n+1)P^{(m)}(n) - \frac{n+2}{2}P^{(m)}(n+1) \right)S^{(0)}_n +$$
  $$+ (n+1)Q^{(m)}(n) - (n+1) \left( P^{(m)}(n+1) + Q^{(m)}(n+1) \right) + (n+1)^{m+1}.$$
  This is the required expression, as soon as we set:
  \begin{equation} \label{Prec}
    P^{(m+1)}(n) = (n+1)P^{(m)}(n) - \frac{n+2}{2}P^{(m)}(n+1);
\end{equation}
  \begin{equation} \label{Qrec}
    Q^{(m+1)}(n) = (n+1)Q^{(m)}(n) - (n+1) \left( P^{(m)}(n+1) + Q^{(m)}(n+1) \right) + (n+1)^{m+1}.
\end{equation}
  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 \geq 2$.
\end{proof}

At this point a simple program can be written in any Computer Algebra System computing recursively
these polynomials. For example, we have:
  $$S^{(1)}_n = \frac{n}{2} S^{(0)}_n;$$
  $$S^{(2)}_n = \frac{(n+1)(n-2)}{4} S^{(0)}_n + \frac{(n+1)^2}{2};$$
  $$S^{(3)}_n = \frac{n(n^2-3n-6)}{8} S^{(0)}_n + \frac{3n(n+1)^2}{4};$$
  $$S^{(4)}_n = \frac{(n+1)(n^3-7n^2-2n+16)}{16} S^{(0)}_n + \frac{(7n-8)(n+1)^3}{8};$$
  $$S^{(5)}_n = \frac{n(n^4-10n^3-5n^2+70n+80)}{32} S^{(0)}_n + \frac{5n(3n^2-n-8)(n+1)^2}{16}.$$

By using this result, we can find recurrence relations for $S^{(m)}_n$, $m \in \N$. The idea is to
start with the relation $S^{(m)}_{n+1} = P^{(m)}(n+1) S^{(0)}_{n+1} + Q^{(m)}(n+1)$ and change
$S^{(0)}_{n+1}$ into $S^{(0)}_n$ by the recurrence relation of that quantity. At this point, we
apply (\ref{Smn}) backwards, eliminating $S^{(0)}_n$ and inserting $S^{(m)}_n$. In this way we
obtain the desired recurrence. Formally:
\begin{theorem}
  For every $m \in \N$, we have the following recurrence relation:
  $$S^{(m)}_{n+1} = \frac{n+2}{2(n+1)} \frac{P^{(m)}(n+1)}{P^{(m)}(n)} S^{(m)}_n - \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).$$
\end{theorem}
\begin{proof}
  As announced, we begin with the shifted position:
  $$S^{(m)}_{n+1} = P^{(m)}(n+1) S^{(0)}_{n+1} + Q^{(m)}(n+1).$$
  Then use the recurrence relation for $S^{(0)}_n$:
  $$S^{(m)}_{n+1} = P^{(m)}(n+1) \left( \frac{n+2}{2(n+1)} S^{(0)}_n + 1 \right) + Q^{(m)}(n+1) =$$
  $$= \frac{n+2}{2(n+1)} P^{(m)}(n+1) S^{(0)}_n + P^{(m)}(n+1) + Q^{(m)}(n+1).$$
  We now use the relation found in the previous theorem to change $S^{(0)}_n$ into $S^{(m)}_n$:
  $$S^{(m)}_{n+1} = \frac{n+2}{2(n+1)} P^{(m)}(n+1) \frac{S^{(m)}_n}{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.
\end{proof}

We expand our examples up to $m=5$:
  $$S^{(1)}_{n+1} = \frac{n+2}{2n} S^{(1)}_n + \frac{n+1}{2};$$
  $$S^{(2)}_{n+1} = \frac{(n+2)^2 (n-1)}{2(n+1)^2 (n-2)} S^{(2)}_n + \frac{(n+2)(n^2-2n-2)}{2(n-2)};$$
  $$S^{(3)}_{n+1} = \frac{(n+2) (n^2-n-8)}{2n(n^2-3n-6)} S^{(3)}_n + \frac{(n+1)(n^4-n^3-17n^2-27n-12)}
  {2(n^2-3n-6)};$$
  $$S^{(4)}_{n+1} = \frac{(n+2)^2 (n^3-4n^2-13n+8)}{2(n+1)^2 (n^3-7n^2-2n+16)} S^{(4)}_n + \frac{(n+2)
  (n^6-5n^5-24n^4-2n^3+54n^2+54n+16)} {2(n^3-7n^2-2n+16)};$$
  $$S^{(5)}_{n+1} = \frac{(n+2) (n^4-6n^3-29n^2+34n+136)} {2n (n^4-10n^3-5n^2+70n+80)} S^{(5)}_n +$$
  $$+ \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 \in \NS}$. This is a classical result and
involves Eulerian numbers \cite[p. 254]{Graham}. Actually, we have:
  $$\G\left( (n+1)^m \right) = \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:
\begin{theorem} \label{FGH}
  For every $m \in \N$, 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\left( \frac{1}{1-t} \right)$$
  where $F^{(m)}(t)$, $G^{(m)}(t)$ and $H^{(m)}(t)$ are polynomials in $t$ of degree at most $m$.
\end{theorem}
\begin{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\left( \frac{1}{1-t} \right).$$
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
\ref{sprugnoli}; after some rearrangement we obtain:
  $$S^{(m+1)}(t) = \frac{F^{(m)}(t)}{(1-t)^{m+1}} - \frac{\dot{F}^{(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) \dot{G}^{(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}} +$$
  $$ + \left( \frac{H^{(m)}(t)}{(2-t)^{m+2}} - \frac{(1-t) \dot{H}^{(m)}(t)}{(2-t)^{m+2}} - \frac
  {(m+2)(1-t) H^{(m)}(t)}{(2-t)^{m+3}} \right) \ln\left( \frac{1}{1-t} \right).$$
Everything is immediately proven as soon as we set:
  \begin{equation} \label{Frec}
    F^{(m+1)}(t) = (1-t)F^{(m)}(t) - (1-t)^2 \dot{F}^{(m)}(t) - (m+1)(1-t) F^{(m)}(t) + E^{(m+1)}(t)
\end{equation}
  \begin{equation} \label{Grec}
    G^{(m+1)}(t) = (2-t)G^{(m)}(t) - (1-t)(2-t) \dot{G}^{(m)}(t) - (m+1)(1-t) G^{(m)}(t) - H^{(m)}(t)
\end{equation}
  \begin{equation} \label{Hrec}
    H^{(m+1)}(t) = (2-t)H^{(m)}(t) - (1-t)(2-t) \dot{H}^{(m)}(t) - (m+2)(1-t) H^{(m)}(t)
\end{equation}
\end{proof}

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\left( \frac{1}{1-t}
  \right)$$
  $$S^{(2)}(t) = \frac{2t}{(1-t)^3} - \frac{6t}{(2-t)^3} - \frac{4-4t-2t^2}{(2-t)^4} \ln\left(
  \frac{1}{1-t} \right)$$
  $$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\left( \frac{1}{1-t} \right)$$
  $$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\left( \frac{1}{1-t} \right)$$
  $$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\left( \frac{1}{1-t} \right)$$

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

%%%%%%%%%%%%%%%%%%%%%
\section{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 \ref{DAS0} in conjunction with
Theorem \ref{ASS0} (thus taking advantage of our knowledge of the asymptotic behavior of
$S^{(0)}_n$) or by starting with Theorem \ref{FGH} 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 \ref{DAS0}:
\begin{lemma}
  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} \quad (m\geq 1) \quad - \quad L(Q^{(m)}(n)) = \frac{(2^{m-1}-1)
  n^m}{2^{m-1}} \quad (m\geq 2).$$
\end{lemma}
\begin{proof}
  The initial step can be verified directly. From the recurrence relation (\ref{Prec}) for
  $P^{(m)}(n)$ we have:
  $$L(P^{(m+1)}(n)) = n \cdot \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 (\ref{Qrec}), we find:
  $$L(Q^{(m+1)}(n)) = n \cdot \frac{(2^{m-1}-1)n^m}{2^{m-1}} -n \cdot \frac{n^m}{2^m} - n \cdot
  \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.
\end{proof}

We immediately have the asymptotic behavior of our quantities:
\begin{theorem}
  The following asymptotic approximation holds true for every positive $m$:
  $$S^{(m)}_n \sim n^m.$$
\end{theorem}
\begin{proof}
  In Theorem \ref{ASS0} we have seen that $S^{(0)}_n \sim 2$ and by Theorem \ref{DAS0} and
  the preceding lemma we find the desired result:
  $$S^{(m)}_n \sim \frac{n^m}{2^m} \cdot 2 + \frac{(2^{m-1}-1) n^m}{2^{m-1}} = n^m.$$
\end{proof}

As an example, we considered $n=100$ and in Table \ref{cento} we give the exact value
$S^{(m)}_{100}$, its approximate value according to the previous theorem, and the relative error.

\begin{table}[H] \centering
  \begin{tabular} {|c|c|c|c|c|} \hline
  $m$ &amp; true value &amp; asymptotic value &amp; relative error &amp; approx. Th. \ref{quattro}\\ \hline
  1 &amp; 101.0208474 &amp; 100 &amp; 1.02\% &amp; 101.0208000 \\
  2 &amp; 10,100.02174 &amp; 10,000 &amp; 1.00\% &amp; 10100.02 \\
  3 &amp; 1,009,899.024 &amp; 1,000,000 &amp; 0.99\% &amp; 1009899 \\
  4 &amp; 100,979,800.0 &amp; 100,000,000 &amp; 0.98\% &amp; 100979800 \\
  5 &amp; $1.009698040\cdot 10^{10}$ &amp; $10^{10}$ &amp; 0.97\% &amp; $1.00969800\cdot 10^{10}$ \\ \hline
  \end{tabular}
  \caption{The case $n=100$} \label{cento}
\end{table}

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 \ref{ASS0} (for $n=100$, see last column in Table \ref{cento}):
\begin{theorem} \label{quattro}
The following approximations hold true
  $$S^{(1)}_n \sim n + 1 + \frac{2}{n} + \frac{8}{n^2}$$
  $$S^{(2)}_n \sim n^2 + n + \frac{2}{n}$$
  $$S^{(3)}_n \sim n^3 + n^2 - n - 1$$
  $$S^{(4)}_n \sim n^4 + n^3 - 2n^2 - 2n$$
  $$S^{(5)}_n \sim n^5 + n^4 - 3n^3 - 2n^2.$$
\end{theorem}
\begin{proof}
These values are derived directly from the formulas after Theorem \ref{DAS0}.
\end{proof}

For the second approach, let us refer to Theorem \ref{FGH}. 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$:
\begin{lemma}
For every $m \in \N$ we have:
  $$F^{(m)}(1) = m!, \qquad G^{(m)}(1) = -2(n+1). \qquad H^{(m)}(1) = 2.$$
\end{lemma}
\begin{proof}
By using the recurrence (\ref{Frec}), we find immediately $F^{(m)}(1) = E^{(m)}(1) = m!$. By
(\ref{Hrec}) we have $H^{(m+1)}(1) = H^{(m)}(1)$; since $H^{(0)}(1) = 2$ we find $H^{(m)}(1) = 2$,
for every $m \in \N$. Finally, by (\ref{Grec}) we have $G^{(m+1)}(1) = G^{(m)}(1) - 2$, and since
$G^{(0)}(1) = -2$, the formula in the assertion follows.
\end{proof}

We conclude with another proof of the asymptotic value for $S^{(m)}_n$:
\begin{theorem}
  For every $m \geq 1$, we have the asymptotic approximation:
  $$S^{(m)}_n \sim n^m.$$
\end{theorem}
\begin{proof}
Let us consider the decomposition given in Theorem \ref{FGH}. 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^{(m)}_n \sim [t^n] \frac{E^{(m)}(t)}{(1-t)^{m+1}} \sim E^{(m)}(1) {-m-1 \choose n} (-1)^n = m!
  {n+m \choose m} \sim n^m.$$
\end{proof}

It is possible to improve our estimates of the asymptotic value of $S^{(m)}_n$ by approaching in a
different way a property considered by Belbachir, Rahmani, and Sury. We begin with the following
result:
\begin{theorem}
The term with $k=n-m$ in the sum (\ref{somma}) defining $S^{(m)}_n$ is asymptotically $m!$. More exactly:
  $$(n-m)^m {n \choose n-m}^{-1} \sim m! \left( 1 - \frac{m^2+m}{2n} \right).$$
\end{theorem}
\begin{proof}
In fact we have the desired result:
  $$(n-m)^m {n \choose n-m}^{-1} = (n-m)^m \frac{m!}{(n)_m} \sim \frac{n^m \exp(-m^2/n) \cdot m!} {n^m
  \exp(-(0 + 1/n + 2/n + \cdots + (m-1)/n))} =$$
  $$= \frac{\exp(-m^2/n) \cdot m!}{\exp(-m(m-1)/(2n))} = m! \exp\left( - \frac{m^2+m}{2n} \right) \sim
  m! \left( 1 - \frac{m^2+m}{2n} \right) \sim m!.$$
\end{proof}

For example, we consider $m=4$ and $n=1000$; the true value of $996^4 {1000 \choose 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:
\begin{lemma}
For fixed $m$, the terms with $k=n-m-1$ and $k=n-m-2$ in the sum (\ref{somma}) are $O(1/n)$ and
$O(1/n^2)$, respectively.
\end{lemma}
\begin{proof}
By a straight-forward computation we find:
  $$(n-m-1)^m {n \choose n-m-1} \sim \frac{m+1}{n} (n-m)^m {n \choose n-m}^{-1} \sim \frac{(m+1)!}{n}.$$
This is found when we use the previous theorem. The proof for $k=n-m-2$ is analogous.
\end{proof}

For fixed $m$, at the other end of the sum (\ref{somma}), the terms with $k=1$ and $k=2$ are small. Actually, we have:
  $$1^m {n \choose 1}^{-1} = \frac{1}{n} \qquad {\rm and} \qquad 2^m {n \choose 2}^{-1} = \
  \frac{2^{m+1}} {n(n-1)} = O \left( \frac{1}{n^2} \right).$$
The following observation now becomes very important:
\begin{theorem}
The distribution of the terms in the sum (\ref{somma}) is unimodal and attains its minimum near $k
= (n-m-1)/2$.
\end{theorem}
\begin{proof}
Let us observe that:
  $$(k+1)^m {n \choose k+1}^{-1} = (k+1)^m \frac{k+1}{n-k} {n \choose k}^{-1};$$
and consider the difference of two consecutive terms:
  $$(k+1)^m {n \choose k+1}^{-1} - k^m {n \choose k}^{-1} = {n \choose k}^{-1} \frac{k^m}{n-k}
  \left( (k+1)\left( 1 + \frac{1}{k} \right)^m -n + k \right).$$
The terms are increasing when the quantity between parentheses is positive and decreasing when
negative. The threshold value is obtained when
  $$n \approx (k+1)\left( 1 + \frac{1}{k} \right)^m + k \approx (k+1)\left( 1 + \frac{m}{k}
  \right) + 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.
\end{proof}

We are now in a position to prove the theorem:
\begin{theorem} [Belbachir, Rahmani, and Sury]
We have:
  $$\sum_{k=0}^{n-m} k^m {n \choose k}^{-1} \sim m!.$$
\end{theorem}
\begin{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 &lt; k &lt; n-m-2$ which are all $O(1/n^2)$ by unimodality. Summing
all these contributions, we conclude:
  $$\sum_{k=0}^{n-m} k^m {n \choose k}^{-1} = O\left( \frac{1}{n} \right) + (n-m-2) O\left( \frac{1}{n^2}
  \right) + O\left( \frac{1}{n} \right) + m! = m! + O\left( \frac{1}{n} \right).$$
 This proves our assertion.
\end{proof}

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:
  $$\left( \frac{n}{2} \right)^{m} {n \choose n/2}^{-1} \sim \frac{n^m}{2^{n+m}} \sqrt{\frac{\pi
  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\times 10^{-288}$ and the approximate
value is $0.23123462\times 10^{-288}$, both values close to the minimum $0.22938294\times
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 \to \infty$ suggests another approach to the evaluation of the asymptotic
value of $S^{(m)}_n$, when $m &gt; 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 (\ref{somma}):
\begin{theorem}
The asymptotic value of the sum (\ref{somma}) is:
  $$S^{(m)}_n \sim n^m + n^{m-1} - (m-2)n^{m-2} + \frac{m^2 - 9m + 16}{2}n^{m-3}.$$
\end{theorem}
\begin{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} \sim n^{m-1} \left( 1 - \frac{m}{n} + \frac{m(m-1)}
  {2n^2} \right) = 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)} \sim 2n^m \left( 1 - \frac{2m}{n} \right) \left( 1 + \frac{1}{n} \right)
  \sim 2n^{m-2} - (4m-2) n^{m-3}.$$
Finally, the fourth term contributes for $6 n^{m-3}$, and putting everything together we find the
expression in the assertion.
\end{proof}

We observe that these values agree with the formulas obtained in Theorem \ref{quattro}.

\begin{thebibliography}{9}

\bibitem{Belbachir}
H.\ Belbachir, M.\ Rahmani, and B. Sury.
\newblock Sums involving moments of reciprocals of binomial coefficients.
\newblock {\it J. Integer Sequences} {\bf 14} (2011), 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Rahmani/rahmani3.html}{Article 11.6.6}.

\bibitem{Bender}
E.\ A.\ Bender.
\newblock Asymptotic methods in enumeration.
\newblock \textit{SIAM Review} {\bf 16} (1974), 485--515.

\bibitem{Graham}
R.\ Graham, D.\ E.\ Knuth and O.\ Patashnik.
\newblock \textsl{Concrete Mathematics}.
\newblock Addison-Wesley, 1994.

\bibitem{Knuth}
D.\ E.\ Knuth.
\newblock \textsl{The Art of Computer Programming}. 
\newblock Addison-Wesley, 1968.

\bibitem{Merlini}
D.\ Merlini, R.\ Sprugnoli, and M.\ C.\ Verri.
\newblock The method of coefficients.
\newblock \textit{Amer. Math. Monthly}, {\bf 114} (2007) 40--57.

\bibitem{Sloane}
N.\ J.\ A.\ Sloane.
\newblock \textsl{The On-Line Encyclopedia of Integer Sequences}.
\newblock \url{http://oeis.org}.

\bibitem{Staver}
T.\ B.\ Staver.
\newblock Om summasjon av potenser av binomialkoeffisientene.
\newblock \textit{Norsk Mat. Tidsskrift} {\bf 29} (1947), 97--103.

\bibitem{Yang}
J.-H.\ Yang and F.-Z.\ Zhao.
\newblock The asymptotic expansion of certain sums involving inverse of binomial coefficients.
\newblock \textit{Int. Math. Forum}, {\bf 5} (2010), 761--768.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 60C05; Secondary 05A15, 62E15.

\noindent \emph{Keywords: } inverse binomial distribution,
moments, generating functions.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A003149}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 19 2011;
revised version received  July 18 2011.
Published in {\it Journal of Integer Sequences}, September 5 2011

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>