What is the simplest way to obtain asymptotics of $\sum_{k=0}^n \binom{n}{k} \frac{1}{(1+k)^2}$?

Question

In the middle of a proof, I have had to analyze the asymptototic behavior of $$ \mathbb{E}\left[\frac{1}{(1+X)^2}\right] = \frac{1}{2^n}\sum_{k=0}^n \binom{n}{k}\frac{1}{(1+k)^2}\tag{1} $$ where $X$ is Binomially distributed with parameters $n$ and $1/2$. (I also had to handle $\mathbb{E}\left[\frac{1}{(1+X)^4}\right]$, but let's start with the square).

Now, it is easy to compute $\mathbb{E}\left[\frac{1}{1+X}\right], \mathbb{E}\left[\frac{1}{(1+X)(2+X)}\right]$, but (1) does not have any closed form (the hypergeometric function is not considered by me as a closed form).

I know that, as $n\to\infty$, $$ \mathbb{E}\left[\frac{1}{(1+X)^2}\right] = \frac{4}{n^2} - \frac{4}{n^3} + O\left(\frac{1}{n^4}\right) \tag{2} $$ (see e.g. [1], which implies this but deals with general probability $p$ and power $r$ instead of $p=1/2$ and $r=2$), but that seems overkill.

What is the simplest and most elegant way to derive (2)?

• Via a simple argument (concentration of the Binomial around $n/2+O(\sqrt{n})$) is it easy to show that is it $\Theta(1/n^2)$. Applying Jensen also shows a lower bound of $\frac{4}{n^2}+\Theta\left(\frac{1}{n^3}\right)$.

• via a still simple argument, involving comparing it to the (explicitly computable) $\mathbb{E}\left[\frac{1}{(1+X)(2+X)}\right]$ and bounding the difference, it is not hard to show it is $\frac{4}{n^2} + \Theta\left(\frac{1}{n^3}\right)$.

But that's not necessarily elegant, and also doesn't quite lead to (2) (I reckon the second approach can be made work, but it'll get messy, and will definitely not end up being a "proof from the book")

---

[1] Francisco Cribari-Neto, Nancy Lopes Garcia, and Klaus LP Vasconcellos. A note on inverse moments of binomial variates. Brazilian Review of Econometrics, 20(2):269– 277, 2000.

Answer 1

New Answer. If $p(x)$ is a non-constant polynomial of degree $d$ having no zero on $\mathbb{N}_0 = \{0,1,\cdots\}$ and $m \geq d$, then we may expand

$$ \frac{1}{p(x)} = \sum_{k=d}^{m} \frac{c_k}{(x+1)\cdots(x+k)} + r(x),$$

where $c_k$'s are constants and $r(x)$ has no pole on $\mathbb{N}_0$ and satisfies $r(x) = \mathcal{O}(\lvert x\rvert^{-m-1})$ near $\infty$. Constants $c_k$'s may be determined by comparing Laurent expansions of both sides at $\infty$, or by clever algebraic manipulation in nice situations. Then it follows that

$$ \mathbf{E}\bigg[\frac{1}{p(X)}\bigg] = \sum_{k=d}^{m} \frac{c_k 2^k}{(n+1)\cdots(n+k)} + \mathcal{O}\left(\frac{1}{n^{m+1}}\right). $$

Example 1. For each $m\geq2$, we have

$$ \frac{1}{(x+1)^2} = \sum_{k=2}^{m} \frac{(k-2)!}{(x+1)\cdots(x+k)} + \frac{(m-1)!}{(x+1)^2(x+2)\cdots(x+m)} $$

So

$$ \mathbf{E}\bigg[\frac{1}{(x+1)^2}\bigg] = \sum_{k=2}^{m} \frac{(k-2)!2^k}{(n+1)\cdots(n+k)} + \mathcal{O}\left(\frac{1}{n^{m+1}}\right) $$

Similarly,

Example 2. Comparing the Laurent expansion near $x=\infty$, we find that

$$ \frac{1}{(x+1)^4} = \frac{1}{(x+1)\cdots(x+4)} + \frac{6}{(x+1)\cdots(x+5)} + r(x)$$

where $r(x) = \frac{109 + 120 x + 35 x^2}{(x+1)^4(x+2)\cdots(x+5)}$ is $\mathcal{O}(x^{-6})$ as $x\to\infty$. This gives

$$ \mathbf{E}\bigg[\frac{1}{(x+1)^4}\bigg] = \frac{16}{(n+1)\cdots(n+4)} + \frac{192}{(n+1)\cdots(n+5)} + \mathcal{O}\left(\frac{1}{n^6}\right). $$

---

Old Answer. Write $X = Y+Z$, where $Y$ and $Z$ are independent and $Y\sim\operatorname{Bin}\big(n-1,\frac{1}{2}\big)$ and $Z\sim\operatorname{Ber}\big(\frac{1}{2}\big)$. Then by conditioning on $Y$,

\begin{align*} \mathbf{E}\bigg[ \frac{1}{(1+X)^2} \bigg] &= \frac{1}{2}\mathbf{E}\bigg[ \frac{1}{(1+Y)^2} + \frac{1}{(2+Y)^2} \bigg] \\ &= \mathbf{E}\bigg[ \frac{1}{(1+Y)(2+Y)} \bigg] + \frac{1}{2}\mathbf{E}\bigg[ \bigg( \frac{1}{1+Y} - \frac{1}{2+Y} \bigg)^2 \bigg]. \end{align*}

Now using the probability generating function $f(z)=\mathbf{E}[z^Y] = \left(\frac{1+z}{2}\right)^{n-1}$, for each $k = 1, 2, \cdots$ we check that

\begin{align*} \mathbf{E}\bigg[ \frac{1}{(1+Y)\cdots(k+Y)} \bigg] &= \int_{0}^{1} \frac{(1-z)^{k-1}}{(k-1)!} f(z) \, dz \\ &= \int_{\frac{1}{2}}^{1} \frac{2^k}{(k-1)!} (1-w)^{k-1}w^{n-1}\,dw \\ &= \int_{0}^{1} \frac{2^k}{(k-1)!} (1-w)^{k-1}w^{n-1}\,dw + \mathcal{O}_k(2^{-n}) \\ &= \frac{2^k (n-1)!}{(n+k-1)!} + \mathcal{O}_k(2^{-n}). \end{align*}

Here, the implicit bounds depend only on $k$. In particular,

• $ \mathbf{E}\Big[ \frac{1}{(1+Y)(2+Y)} \Big] = \frac{4}{n(n+1)} + \mathcal{O}(2^{-n}) $,

• $ \mathbf{E}\Big[ \Big( \frac{1}{1+Y} - \frac{1}{2+Y} \Big)^2 \Big] = \mathbf{E}\Big[ \frac{1}{(1+Y)^2(2+Y)^2} \Big] \leq \mathbf{E}\Big[ \frac{6}{(1+Y)(2+Y)(3+Y)(4+Y)} \Big] = \mathcal{O}\Big(\frac{1}{n^4}\Big). $ Here, we utilized the simple inequality that if $x \geq 0$ and $0 < a < b$ then $\frac{a}{a+x} \leq \frac{b}{b+x}$.

Therefore it follows that

$$ \mathbf{E}\bigg[ \frac{1}{(1+X)^2} \bigg] = \frac{4}{n(n+1)} + \mathcal{O}\left(\frac{1}{n^4}\right) = \frac{4}{n^2} - \frac{4}{n^3} + \mathcal{O}\left(\frac{1}{n^4}\right). $$

Answer 2

Note that we can write

$$\begin{align} \frac1{2^n}\sum_{k=0}^n\binom{n}{k}\frac{1}{(1+k)^2}&=\frac1{2^n}\sum_{k=0}^n\binom{n}{k}\int_0^1 x^k\,dx\int_0^1 y^k\,dx\\\\ &=\frac1{2^n}\int_0^1\int_0^1 (1+xy)^n\,dx\,dy\\\\ &=\frac1{2^n}\frac1{n+1}\int_0^1 \frac{(1+x)^{n+1}-1}{x}\,dx\\\\ &=-\int_0^1 \log(x)\left(\frac{1+x}2\right)^n\,dx\tag1 \end{align}$$

Observing that the term $\left(\frac{1+x}2\right)^n$ in the integrand of $(1)$ decays rapidly away from $1$, we are motivated to expand the logarithm around $x=1$. The integration of the first term reveals

$$\begin{align} \frac1{2^n}\int_0^1 (1-x)(1+x)^n\,dx&=\frac{4-(n+3)2^{-n}}{(n+1)(n+2)}\\\\ &=\frac4{n^2}-\frac{12}{n^3}+O\left(\frac1{n^4}\right) \end{align}$$

Continuing, the integration of the second term reveals

$$\begin{align} \frac1{2^n}\int_0^1 \frac12 (1-x)^2(1+x)^n\,dx&=\frac{8-(n^2+7n+14)2^{-(n+1)}}{(n+1)(n+2)(n+3)}\\\\ &=\frac8{n^3}+O\left(\frac1{n^4}\right) \end{align}$$

Putting all of this together, we have

$$\frac1{2^n}\sum_{k=0}^n\binom{n}{k}\frac{1}{(1+k)^2}\sim \frac{4}{n^2}-\frac{4}{n^3}+O\left(\frac1{n^4}\right)$$

as was to be shown!

---

NOTE:

To make things more rigorous, let $\delta \in (0,1)$ and write

$$-\int_0^1 \log(x)\left(\frac{1+x}2\right)^n\,dx=-\int_0^\delta \log(x)\left(\frac{1+x}2\right)^n\,dx-\int_\delta^1 \log(x)\left(\frac{1+x}2\right)^n\,dx\tag2$$

The first integral on the right-hand side of $(1)$ decays faster than any reciprocal power of $n$. And for the second integral, there exist a number $\xi$, $\delta\le x<\xi<1$, such that

$$\log(x)=(x-1)-\frac12(x-1)^2+\frac1{3\xi^3}(x-1)^3$$

Bounds for the integral $\int_\delta^1 \frac{1}{3\xi^3}(x-1)^3(1+x)^n\,dx$ can easily be obtained to show that $\int_\delta^1 \frac{1}{3\xi^3}(x-1)^3(1+x)^n\,dx=O\left(\frac1{n^4}\right)$.