Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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? – Arturo Magidin 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. – Brian M. Scott 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 – Fabian May 30 '12 at 8:58

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

share|cite|improve this answer

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

share|cite|improve this answer
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. – Sasha May 30 '12 at 16:16
I see. Better answer like that... :-) – Did May 30 '12 at 16:58

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


As $n\to\infty$, $$ \begin{align} &\frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k} -\frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{n}\\ &=\sum_{k=1}^{n+1}\frac{n+1}{2^{n-k+1}}\left(\frac1k-\frac1n\right)\\ &=\sum_{k\le n-n^{1/3}}\frac{n+1}{2^{n-k+1}}\left(\frac1k-\frac1n\right) &&+\sum_{k\gt n-n^{1/3}}\frac{n+1}{2^{n-k+1}}\left(\frac1k-\frac1n\right)\\ &\le\sum_{k\le n-n^{1/3}}\frac1{2^{n-k+1}} &&+\sum_{k\gt n-n^{1/3}}\left|\,\frac1k-\frac1n\,\right|\\ &\le\sum_{k\ge n^{1/3}}\frac1{2^{k+1}} &&+\sum_{k\lt n^{1/3}}\left|\,\frac1{n-k}-\frac1n\,\right|\\ &\le\frac1{2^{n^{1/3}}} &&+\frac{n^{2/3}}{n(n-n^{1/3})}\\[9pt] &\to0\tag{8} \end{align} $$ Therefore, $$ \begin{align} \lim_{n\to\infty}\frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k} &=\lim_{n\to\infty}\frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{n}\\ &=\lim_{n\to\infty}\frac{n+1}{n}\frac{2^{n+2}-2}{2^{n+1}}\\[12pt] &=2\tag{9} \end{align} $$

share|cite|improve this answer
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! – Jose Brox Feb 22 at 10:57
Nice proof of (7), but how do you get the $n^{2/3}$ in the numerator in the limit argument? – darij grinberg Jul 25 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 at 16:40
Ah, I see; I got the inequality sign wrong. – darij grinberg Jul 25 at 18:23

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.