41
$\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$
6
  • 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 '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$ May 30 '12 at 5:10
  • 2
    $\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$ Jul 25 '16 at 15:22
38
$\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$
36
$\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

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

$\endgroup$
7
  • 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 '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$ Jul 25 '16 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 '16 at 16:40
  • $\begingroup$ Ah, I see; I got the inequality sign wrong. $\endgroup$ Jul 25 '16 at 18:23
  • $\begingroup$ A comment almost 7 years later : this is very elegant. $\endgroup$ May 16 '20 at 7:40
20
$\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$
3
  • $\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
13
$\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$
0
$\begingroup$

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

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