Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
1  
@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
1  
see A003149 –  Fabian May 30 '12 at 8:58

4 Answers 4

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|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|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}\frac1{\binom{n}{k\vphantom{+1}}}+\frac1{\binom{n}{k+1}} &=\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} $$

share|improve this answer

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|improve this answer

Your Answer

 
discard

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.