\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$ & true value & asymptotic value & relative error & approx. Th. \ref{quattro}\\ \hline 1 & 101.0208474 & 100 & 1.02\% & 101.0208000 \\ 2 & 10,100.02174 & 10,000 & 1.00\% & 10100.02 \\ 3 & 1,009,899.024 & 1,000,000 & 0.99\% & 1009899 \\ 4 & 100,979,800.0 & 100,000,000 & 0.98\% & 100979800 \\ 5 & $1.009698040\cdot 10^{10}$ & $10^{10}$ & 0.97\% & $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 < k < 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 > 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}