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?

  • 2
    $\begingroup$ 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? $\endgroup$ May 30, 2012 at 5:08
  • 2
    $\begingroup$ @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. $\endgroup$ May 30, 2012 at 5:10
  • 2
    $\begingroup$ Modified the title (note that there is no infinite series in this problem). $\endgroup$
    – Did
    May 30, 2012 at 8:35
  • 1
    $\begingroup$ see A003149 $\endgroup$
    – Fabian
    May 30, 2012 at 8:58
  • 2
    $\begingroup$ See also fq.math.ca/Scanned/19-5/rockett.pdf (Theorem 1) and cs.uwaterloo.ca/journals/JIS/VOL7/Sury/sury99.pdf . $\endgroup$ Jul 25, 2016 at 15:22

5 Answers 5


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}}$


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} $$

  • 2
    $\begingroup$ 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! $\endgroup$
    – Jose Brox
    Feb 22, 2016 at 10:57
  • $\begingroup$ Nice proof of (7), but how do you get the $n^{2/3}$ in the numerator in the limit argument? $\endgroup$ Jul 25, 2016 at 15:09
  • 1
    $\begingroup$ @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})}$ $\endgroup$
    – robjohn
    Jul 25, 2016 at 16:40
  • $\begingroup$ Ah, I see; I got the inequality sign wrong. $\endgroup$ Jul 25, 2016 at 18:23
  • $\begingroup$ A comment almost 7 years later : this is very elegant. $\endgroup$ May 16, 2020 at 7:40

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.$$


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: enter image description here

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} $$

  • $\begingroup$ 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. $\endgroup$
    – Did
    May 30, 2012 at 7:26
  • $\begingroup$ @did I have updated the answer. The identity was initially discovered using Zeilberger's algorithm, with the derivation filled in after the fact. $\endgroup$
    – Sasha
    May 30, 2012 at 16:16
  • $\begingroup$ I see. Better answer like that... :-) $\endgroup$
    – Did
    May 30, 2012 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)]


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$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .