34
$\begingroup$

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?

$\endgroup$
  • 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$ – Arturo Magidin May 30 '12 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$ – Brian M. Scott May 30 '12 at 5:10
  • 1
    $\begingroup$ Modified the title (note that there is no infinite series in this problem). $\endgroup$ – Did May 30 '12 at 8:35
  • 1
    $\begingroup$ see A003149 $\endgroup$ – Fabian May 30 '12 at 8:58
  • 1
    $\begingroup$ See also fq.math.ca/Scanned/19-5/rockett.pdf (Theorem 1) and cs.uwaterloo.ca/journals/JIS/VOL7/Sury/sury99.pdf . $\endgroup$ – darij grinberg Jul 25 '16 at 15:22
31
$\begingroup$

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

$\endgroup$
24
$\begingroup$

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

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

$\endgroup$
  • 1
    $\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 '16 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$ – darij grinberg Jul 25 '16 at 15:09
  • $\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 '16 at 16:40
  • $\begingroup$ Ah, I see; I got the inequality sign wrong. $\endgroup$ – darij grinberg Jul 25 '16 at 18:23
18
$\begingroup$

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

$\endgroup$
  • $\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 '12 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 '12 at 16:16
  • $\begingroup$ I see. Better answer like that... :-) $\endgroup$ – Did May 30 '12 at 16:58
10
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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