# Evaluate $\sum_{n,k} \binom{n}{k}^{-1}$

Evaluate $$\sum_{n,k} \frac{1}{\binom{n}{k}},$$ where the summation ranges over all positive integers $$n,k$$ with $$1.

## Thouhgts:

We are trying to evaluate $$\sum_{n=4}^{\infty} \sum_{k=2}^{n-2} \binom{n}{k}^{-1}$$

We may try to find a closed form of the inner summation which is of the form :

$$\frac{1}{ {n \choose 2} } + \frac{1}{{n \choose 3} }+ \dotsb + \frac{1}{{n \choose n-2} }.$$

Notice that we may write $$\frac{1}{ {n \choose 2} } = \frac{2! }{n(n-1)}$$ and if keep doing the same for the other terms we obtain the following:

$$\frac{ (n-2)! + (n-3)! (n-(n-2)) + (n-4)!(n-(n-2))(n-(n-3)) + \dotsb + 2! (n-3)! }{n!},$$

which equals

$$\frac{ (n-2)! + 2!(n-3)! + 3! (n-4)! + \dotsb + (n-3)! 2! }{n!}$$

and so this equals:

$$\frac{1}{n(n-1)} + \frac{2}{n(n-1)(n-2)} + \dfrac{6}{n(n-1)(n-2)} + \dotsb + \dfrac{2}{n(n-1)(n-2) }.$$

But half of this terms are identical. Therefore, we are trying to sum up series of the form $$\sum_{n \geq k} \frac{1}{(n-1)(n-2)(n-3)\dotso(n-k)} ,$$ which can be done by a telescoping trick, but it seems very formidable. Am I approaching this problem the right way? Any hints/suggestions?

• The link @AnuragA has given is about sum on $k$, not on both $k$ and $n$. It does not really answer the question, I think. OP, are you sure this have some good closed-form? Or are you looking for limits / Asymptotic behavior of this summation? – Gratus May 16 at 6:47
• The link doesn't directly answer the question, but robjohn's answer has a closed form that looks promising... – Micah May 16 at 6:50
• Does the sum over $n$ start from 1 or 4? – user May 16 at 6:55
• The sum is $\frac32$. – achille hui May 16 at 7:39
• @Micah: I couldn't find a way to use that form, but using some partial fractions and telescoping sums, the double sum can be computed. – robjohn May 17 at 21:03

Partial Fractions and Telescoping Sums \begin{align} \sum_{n=4}^\infty\sum_{k=2}^{n-2}\frac1{\binom{n}{k}} &=\sum_{k=2}^\infty\sum_{n=k+2}^\infty\frac1{\binom{n}{k}}\tag1\\ &=\sum_{k=2}^\infty\frac{k}{k-1}\sum_{n=k+2}^\infty\left(\frac1{\binom{n-1}{k-1}}-\frac1{\binom{n}{k-1}}\right)\tag2\\ &=\sum_{k=2}^\infty\frac{k}{k-1}\frac1{\binom{k+1}{k-1}}\tag3\\ &=\sum_{k=2}^\infty\frac2{(k-1)(k+1)}\tag4\\ &=\sum_{k=2}^\infty\left(\frac1{k-1}-\frac1{k+1}\right)\tag5\\[3pt] &=1+\frac12\tag6\\[9pt] &=\frac32\tag7 \end{align} Explanation:
$$(1)$$: change order of summation
$$(2)$$: $$\frac1{\binom{n-1}{k-1}}-\frac1{\binom{n}{k-1}}=\frac{\frac nk}{\binom{n}{k}}-\frac{\frac{n-k+1}k}{\binom{n}{k}}=\frac{\frac{k-1}k}{\binom{n}{k}}$$
$$(3)$$: telescoping sum
$$(4)$$: $$\binom{k+1}{k-1}=\binom{k+1}{2}=\frac{(k+1)k}2$$
$$(5)$$: partial fractions
$$(6)$$: telescoping sum
$$(7)$$: simplify

• This is beautiful! Thanks for reply. I was so far off.. – Theoneandonly May 17 at 21:09
• @Theoneandonly: you weren't so far off: you had the idea of summing $\sum\limits_{n \gt k} \frac1{(n-1)(n-2)(n-3)\cdots(n-k)}$ using telescoping sums. That is essentially what is done in my answer. I just wrote those products more compactly as binomial coefficients. Note that we need $n\gt k$ since $n-k$ appears in the denominator ;-) – robjohn May 17 at 21:39
• +1 yup, this is beautiful and sort of unexpected ;-p – achille hui May 17 at 21:42

Let $$\ell = n -k$$, we have

\begin{align} \sum_{n=4}^\infty\sum_{k=2}^{n-2} \binom{n}{k}^{-1} &= \sum_{k=2}^\infty\sum_{n=k+2}^\infty \binom{n}{k}^{-1}\\ &= \sum_{k=2}^\infty\sum_{\ell=2}^\infty \binom{k+\ell}{k}^{-1} = \sum_{k=2}^\infty\sum_{\ell=2}^\infty \frac{k!\ell!}{(k+\ell)!}\\ &= \sum_{k=2}^\infty\sum_{\ell=2}^\infty (k+\ell+1)\frac{\Gamma(k+1)\Gamma(\ell+1)}{\Gamma(k+\ell+2)}\\ &= \sum_{k=2}^\infty\sum_{\ell=2}^\infty (k+\ell+1)\int_0^1 t^k (1-t)^\ell dt\\ &= \int_0^1 \sum_{k=2}^\infty\sum_{\ell=2}^\infty \left[ (k+\ell+1) t^k (1-t)^\ell\right] dt \end{align} Notice when $$s$$ and $$t$$ are independent, we have

\begin{align} \sum_{k=2}^\infty\sum_{\ell=2}^\infty (k+\ell+1)t^k s^\ell = & \sum_{k=2}^\infty\sum_{\ell=2}^\infty \left(t\frac{\partial}{\partial t} + s\frac{\partial}{\partial s} + 1 \right)t^k s^\ell \\ = & \left(t\frac{\partial}{\partial t} + s\frac{\partial}{\partial s} + 1 \right) \frac{t^2s^2}{(1-t)(1-s)}\\ = & \frac{s^2t^2(5-4(s+t)+3st)}{(1-s)^2(1-t)^2} \end{align}

Substitute $$s$$ by $$1-t$$, we obtain

$$\sum_{k=2}^\infty\sum_{\ell=2}^\infty (k+\ell+1) t^k (1-t)^\ell = 1 + 3t(1-t)$$

As a result,

$$\sum_{n=4}^\infty\sum_{k=2}^{n-2} \binom{n}{k}^{-1} = \int_0^1 (1 + 3t(1-t)) dt = \frac32$$

Generally similar sums can be evaluated using the Beta function: $$B(x+1,y+1)=\int_0^1 t^{x}(1-t)^{y}dt=\frac{\Gamma(x+1)\Gamma(y+1)}{\Gamma(x+y+2)}= \frac{x!y!}{(x+y+1)!}=\frac{1}{x+y+1}\binom{x+y}x^{-1}.$$

Applying this in your case ($$x=n-k,y=k$$) one has: $$\binom{n}{k}^{-1}=(n+1)\int_0^1 t^{n-k}(1-t)^{k}dt$$ or \begin{align} I_n=\frac1{n+1}\sum_{k=2}^{n-2}\binom{n}{k}^{-1} &=\sum_{k=2}^{n-2}\int_0^1 t^{n-k}(1-t)^kdt\\ &=\int_0^1\left[ t^n \sum_{k=2}^{n-2}\left(\frac{1-t}t\right)^k\right] dt\\ &=\int_0^1 t^n\left(\frac{1-t}t\right)^2 \frac{1-\left(\frac{1-t}t\right)^{n-3}}{1-\frac{1-t}t}dt\\ \end{align} and, finally, \begin{align} \sum_{n=4}^\infty (n+1)I_n& =\int_0^1\left[\frac{(1-t)^2}{2t-1}\sum_{n=4}^\infty (n+1)\left(t^{n-1}-t^2(1-t)^{n-3}\right)\right]dt\\ &=\int_0^1(1+3t-3t^2)dt=\frac32. \end{align}