8
$\begingroup$

Evaluate $$\sum_{n,k} \frac{1}{\binom{n}{k}}, $$ where the summation ranges over all positive integers $n,k$ with $1<k<n-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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Gratus May 16 at 6:47
  • 3
    $\begingroup$ The link doesn't directly answer the question, but robjohn's answer has a closed form that looks promising... $\endgroup$ – Micah May 16 at 6:50
  • $\begingroup$ Does the sum over $n$ start from 1 or 4? $\endgroup$ – user May 16 at 6:55
  • 1
    $\begingroup$ The sum is $\frac32$. $\endgroup$ – achille hui May 16 at 7:39
  • $\begingroup$ @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. $\endgroup$ – robjohn May 17 at 21:03
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is beautiful! Thanks for reply. I was so far off.. $\endgroup$ – Theoneandonly May 17 at 21:09
  • $\begingroup$ @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 ;-) $\endgroup$ – robjohn May 17 at 21:39
  • $\begingroup$ +1 yup, this is beautiful and sort of unexpected ;-p $\endgroup$ – achille hui May 17 at 21:42
11
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
10
$\begingroup$

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

| cite | improve this answer | |
$\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.