# Calculate sums of inverses of binomial coefficients

How to calculate the sum of sequence $$\frac{1}{\binom{n}{1}}+\frac{1}{\binom{n}{2}}+\frac{1}{\binom{n}{3}}+\cdots+\frac{1}{\binom{n}{n}}=？$$ How about its limit?

• Is $C^{i}_j$ meant to be the binomial coefficient $i$ choose $j$, $\binom{i}{j}$, or a constant $C_n$ raised to different powers? May 30 '12 at 5:08
• @Arturo: My guess is that $C_n^k$ is meant to be $\binom{n}k$, with the subscript and superscript interchanged for some reason. I’ve seen that reversal here at least once before. May 30 '12 at 5:10
• Modified the title (note that there is no infinite series in this problem).
– Did
May 30 '12 at 8:35
• see A003149 May 30 '12 at 8:58
• See also fq.math.ca/Scanned/19-5/rockett.pdf (Theorem 1) and cs.uwaterloo.ca/journals/JIS/VOL7/Sury/sury99.pdf . Jul 25 '16 at 15:22

When interested in the limit only, just observe that for $2 \leq k \leq n-2$, we have $$\frac{1}{\binom{n}{k}} \leq \frac{1}{\binom{n}{2}} = \frac{2}{n(n-1)}.$$ Thus $$2 \leq \sum_{k=0}^{n} \frac{1}{\binom{n}{k}} \leq 2 + \frac{2}{n} + \frac{2(n-3)}{n(n-1)} \xrightarrow[n\to\infty]{} 2$$ and therefore $$\lim_{n\to\infty} \sum_{k=0}^{n} \frac{1}{\binom{n}{k}} = 2.$$

Here is a method that I just came up with in chat \begin{align} \frac1{\binom{n}{k\vphantom{+1}}}&=\frac{n-k}{n}\frac1{\binom{n-1}{k}}\tag{1}\\ \frac1{\binom{n}{k+1}}&=\frac{k+1}{n}\frac1{\binom{n-1}{k}}\tag{2}\\ \sum_{k=0}^{n-1}\left(\frac1{\binom{n}{k\vphantom{+1}}}+\frac1{\binom{n}{k+1}}\right) &=\frac{n+1}{n}\sum_{k=0}^{n-1}\frac1{\binom{n-1}{k}}\tag{3}\\ 2\sum_{k=0}^n\frac1{\binom{n}{k\vphantom{+1}}} &=2+\frac{n+1}{n}\sum_{k=0}^{n-1}\frac1{\binom{n-1}{k}}\tag{4}\\ \frac{2^{n+1}}{n+1}\sum_{k=0}^n\frac1{\binom{n}{k\vphantom{+1}}} &=\frac{2^{n+1}}{n+1}+\frac{2^n}{n}\sum_{k=0}^{n-1}\frac1{\binom{n-1}{k}}\tag{5}\\ \frac{2^{n+1}}{n+1}\sum_{k=0}^n\frac1{\binom{n}{k\vphantom{+1}}} &=\sum_{k=1}^{n+1}\frac{2^k}{k}\tag{6}\\ \sum_{k=0}^n\frac1{\binom{n}{k\vphantom{+1}}} &=\frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k}\tag{7}\\ \end{align} Explanation

$$(1)$$: Binomial identity: $$\frac{n!}{k!(n-k)!}=\frac{n}{n-k}\frac{(n-1)!}{k!(n-k-1)!}$$
$$(2)$$: Binomial identity: $$\frac{n!}{(k+1)!(n-k-1)!}=\frac{n}{k+1}\frac{(n-1)!}{k!(n-k-1)!}$$
$$(3)$$: Add $$(1)$$ and $$(2)$$ and sum $$\vphantom{\frac{()}{()}}$$
$$(4)$$: Add $$\frac1{\binom{n}{n\vphantom{+1}}}+\frac1{\binom{n}{0}}=2$$ to both sides
$$(5)$$: multiply both sides by $$\frac{2^n}{n+1}$$
$$(6)$$: $$a_n=\frac{2^{n+1}}{n+1}+a_{n-1}$$ where $$a_n=\frac{2^{n+1}}{n+1}\sum\limits_{k=0}^n\frac1{\binom{n}{k\vphantom{+1}}}$$
$$(7)$$: multiply both sides by $$\frac{n+1}{2^{n+1}}$$

Limit

For $$2\le k\le n-2$$, we have that $$\binom{n}{k}\ge\binom{n}{2}$$. Thus, for $$n\ge4$$, \begin{align} \sum_{k=0}^n\frac1{\binom{n}{k}} &=\overset{\substack{k=0\\k=n\\\downarrow\\[3pt]\,}}{2\vphantom{\frac2n}}+\overset{\substack{k=1\\k=n-1\\\downarrow\\[3pt]\,}}{\frac2n}+\sum_{k=2}^{n-2}\frac1{\binom{n}{k}}\tag8\\ &\le2+\frac2n+\frac{n-3}{\binom{n}{2}}\tag9\\ &\le2+\frac4n\tag{10} \end{align} Therefore, for $$n\ge4$$, $$2+\frac2n\le\sum_{k=0}^n\frac1{\binom{n}{k}}\le2+\frac4n\tag{11}$$ and the Squeeze Theorem says $$\lim_{n\to\infty}\sum_{k=0}^n\frac1{\binom{n}{k}}=2\tag{12}$$

• This elementary approach, based on the fact that the sum of two consecutive reciprocals of binomials is the reciprocal of a binomial times a factor is really nice! Feb 22 '16 at 10:57
• Nice proof of (7), but how do you get the $n^{2/3}$ in the numerator in the limit argument? Jul 25 '16 at 15:09
• @darijgrinberg: $\left|\frac1{n-k}-\frac1n\right|=\frac{k}{n(n-k)}\le\frac{n^{1/3}}{n(n-n^{1/3})}$ because it's biggest when $k$ is. Furthermore, there are $n^{1/3}$ terms, so the sum is bounded by $\frac{n^{2/3}}{n(n-n^{1/3})}$
– robjohn
Jul 25 '16 at 16:40
• Ah, I see; I got the inequality sign wrong. Jul 25 '16 at 18:23
• A comment almost 7 years later : this is very elegant. May 16 '20 at 7:40

Assuming $C_n^k$ stands for $\binom{n}{k} = \frac{n!}{(n-k)! \cdot k!}$, and using, for $k>0$: $$\frac{1}{\binom{n}{k}} = k \operatorname{Beta}(k,n-k+1) = k \int_0^1 (1-x)^{k-1} x^{n-k} \mathrm{d} x$$ Hence $$S = \sum_{k=1}^n \frac{1}{\binom{n}{k}} = \int_0^1 \sum_{k=0}^n k (1-x)^{k-1} x^{n-k} \mathrm{d} x = \int_0^1 \frac{x^{n+1} -(1-x)^n ((2n+1)x-n)}{(1-2x)^2} \mathrm{d} x$$ Now changing integration variable $x = \frac{1}{2} + u$: $$\begin{eqnarray} S &=& \int_{-1/2}^{1/2} \frac{\mathrm{d} u}{4 u^2} \left( \left(\frac{1}{2}+u\right)^{n+1} - \frac{1}{2} \left(\frac{1}{2}-u\right)^n \left( 1 + 2 (2n+1) u\right)\right) \\ &=& \int_{-1/2}^{1/2} \frac{\mathrm{d} u}{4 u^2} \sum_{k=2}^{n+1} 2^{k-n-1} \left((-1)^k \left((2 n+1) \binom{n}{k-1}-\binom{n}{k}\right)+\binom{n+1}{k}\right) u^{k} \\ &=& \sum_{k=1}^{\lfloor\frac{n+1}{2}\rfloor} 2^{2k-n-1} \left(\left((2 n+1) \binom{n}{2k-1}-\binom{n}{2k}\right)+\binom{n+1}{2k}\right) \underbrace{\int_{-1/2}^{1/2} \frac{\mathrm{d} u}{4 u^2} u^{2 k}}_{\frac{1}{4^k} \frac{1}{2k-1}} \\ &=& \sum_{k=1}^{\lfloor\frac{n+1}{2}\rfloor} \frac{1}{2^{n}} \frac{1}{2k-1}\frac{(n+1)!}{ (2k-1)! (n-2k+1)!} \stackrel{\ast}{=} \sum_{k=1}^n \frac{n+1}{n+1-k} \frac{1}{2^k} \end{eqnarray}$$ Thus $$\sum_{k=0}^n \frac{1}{\binom{n}{k}} = \sum_{k=0}^n \frac{n+1}{n+1-k} \frac{1}{2^k}$$ For large $n$ the sum approaches the value of $2$ from above:

I am hoping this sum has a nice probabilistic underpinnings to it.

Added: Derivation of equality $\stackrel{\ast}{=}$ above
$$\begin{eqnarray} S &=& \sum_{k=1}^{\lfloor\frac{n+1}{2}\rfloor} \frac{1}{2^{n}} \frac{1}{2k-1}\frac{(n+1)!}{ (2k-1)! (n-2k+1)!} = \frac{n+1}{2^n} \underbrace{\sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor} \frac{1}{2k+1} \binom{n}{2k+1}}_{A_n} \end{eqnarray}$$ We will now establish that $A_{n+1} - A_{n} = \frac{2^{n}}{n+1}$, which would imply $$A_n = \sum_{k=1}^n \frac{2^{k-1}}{k} \stackrel{k \to n+1-k}{=} \sum_{k=1}^n \frac{2^{n-k}}{n+1-k}$$ We thus proceed, firstly for even, $n=2m$: $$\begin{eqnarray} A_{2m+1} -A_{2m} &=& \sum_{k=0}^{m} \frac{1}{2k+1} \left( \underbrace{\binom{2m+1}{2k+1} - \binom{2m}{2k+1}}_{\binom{2m}{2k}}\right) \\ &=& \sum_{k=0}^{m} \frac{1}{2k+1} \binom{2m}{2k} = \frac{1}{2}\int_0^1 \left( (1+x)^{2m} + (1-x)^{2m} \right) \mathrm{d} x = \frac{2^{n}}{n+1} \end{eqnarray}$$ and then, similarly, for odd, $n=2m+1$: $$\begin{eqnarray} A_{2m+2}-A_{2m+1} &=& \sum_{k=0}^m \frac{1}{2k+1} \binom{2m+1}{2k} \\ &=& \frac{1}{2}\int_0^1 \left( (1+x)^{2m+1} + (1-x)^{2m+1} \right) \mathrm{d} x = \frac{2^n}{n+1} \end{eqnarray}$$

• I got lost at the moment when the sum on $k\leqslant\lfloor\frac{n+1}{2}\rfloor$ becomes a sum on $k\leqslant n$ (last equality before Thus). You might want to add some more explanations on this step.
– Did
May 30 '12 at 7:26
• @did I have updated the answer. The identity was initially discovered using Zeilberger's algorithm, with the derivation filled in after the fact. May 30 '12 at 16:16
• I see. Better answer like that... :-)
– Did
May 30 '12 at 16:58

The determination of the limit is direct, keeping only the first and last terms and bounding the others. To get an exact formula, one can use a method similar to @Sasha's while (i) being somewhat simpler and (ii) avoiding a step I find unclear. Like @Sasha, one starts with a beta representation, namely, $${n\choose k}^{-1}=(n+1)\int_0^1x^{n-k}(1-x)^k\mathrm dx.$$ Summing up, $$S_n=\sum_{k=0}^n{n\choose k}^{-1}=(n+1)\int_0^1u_n(x)\mathrm dx,\quad u_n(x)=\sum_{k=0}^nx^{n-k}(1-x)^k.$$ Note that $u_n(x)$ is a geometric series, hence $$u_n(x)=\frac{x^{n+1}-(1-x)^{n+1}}{2x-1}.$$ Using the change of variables $x=\frac12(1+z)$ with $-1\leqslant z\leqslant 1$ yields $$u_n(x)=\frac{(1+z)^{n+1}-(1-z)^{n+1}}{2^{n+1}z}=\frac1{2^{n}}\sum_k{n+1\choose 2k+1}z^{2k}.$$ Thus, $$S_n=\frac{n+1}{2^n}\sum_k{n+1\choose 2k+1}\frac1{2k+1}\left[z^{2k+1}\right]_{0}^1,$$ and finally $$\sum_{k=1}^n{n\choose k}^{-1}=S_n-1=\frac1{2^n}\sum_{k=0}^{\lfloor\frac{n}2\rfloor}{n+1\choose 2k+1}\frac{n+1}{2k+1}-1.$$

As an alternative, starting from this result by robjohn's answer [tag (7)]

$$\sum_{k=0}^n\frac1{\binom{n}{k}}=\frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k}=\frac{\sum_{k=1}^{n+1}\frac{2^k}{k}}{\frac{2^{n+1}}{n+1}}$$

by Stolz-Cesaro we obtain

$$\frac{\frac{2^{n+2}}{n+2}}{\frac{2^{n+2}}{n+2}-\frac{2^{n+1}}{n+1}}=\frac{2}{2-\frac{n+2}{n+1}}\to 2$$