6
$\begingroup$

I'm trying to find a closed solution to the following binomial sum, without success. I would appreciate any assistance towards a solution.

$$ \sum\limits_{k=0}^{n-1}\dfrac{1}{\binom{n}{k}(n-k)} $$

Perhaps the following alternative form presents the problem in a better light:

$$ \dfrac{1}{n!}\sum\limits_{k=0}^{n-1}k![(n-1)-k]! $$

UPDATE:

Since Peter Košinár's and Phira's kind and informative responses, I have found some other equivalent expressions:

$$ \sum\limits_{k=0}^{n-1}\dfrac{1}{2^k (n-k)} $$

and

$$ \dfrac{1}{2^n}\sum\limits_{k=1}^{n}\dfrac{2^k}{k} $$

The first can be proved from the identity stated here (Wayback Machine).

The second I have seen merely stated, but cannot prove from my original expression.

$\endgroup$
  • $\begingroup$ There is something close to your question here ---> math.stackexchange.com/a/548570/85343 $\endgroup$ – Felix Marin Jan 4 '14 at 23:25
  • $\begingroup$ Your first update expression matches my $(2)$. Your second update expression would be the same as your first if you divide by $2^n$ instead of $n$ (as it stands, it is not correct). $\endgroup$ – robjohn Jan 7 '14 at 0:56
  • $\begingroup$ You are correct about the $2^n$ - I will update this now. $\endgroup$ – jamesthenabignumber Jan 7 '14 at 1:41
  • $\begingroup$ Now your two expressions are the same, only differing by a change of index $k\mapsto n-k$. $\endgroup$ – robjohn Jan 7 '14 at 2:40
2
$\begingroup$

Equation $(8)$ from this answer says $$ \sum_{m=0}^nm!(n-m)!=\frac{(n+1)!}{2^n}\sum_{k=0}^n\frac{2^k}{k+1}\tag{1} $$ Applying this to your sum gives $$ \begin{align} \sum_{k=0}^{n-1}\frac1{\binom{n}{k}(n-k)} &=\frac1{n!}\sum_{k=0}^{n-1}k!(n-k-1)!\\ &=\frac1{2^{n-1}}\sum_{k=0}^{n-1}\frac{2^k}{k+1}\\ &\sim\frac2n+\frac2{n(n-1)}+\frac4{n(n-1)(n-2)}\\ &+\frac{12}{n(n-1)(n-2)(n-3)}\\ &+\frac{48}{n(n-1)(n-2)(n-3)(n-4)}+O\left(\frac1{n^6}\right)\tag{2} \end{align} $$ where we used $(6)$ below to get the asymptotic expansion.


Asymptotic Expansion

Note that $$ \begin{align} &\frac{(n-j+1)!}{n!}\sum_{k=0}^{n-j}\frac{(k+j)!}{k!}\frac{2^{-k-j}}{n-j-k+1}\\ -&\frac{(n-j+1)!}{n!}\sum_{k=0}^{n-j}\frac{(k+j)!}{k!}\frac{2^{-k-j}}{n-j+1}\\ =&\frac{(n-j+1)!}{n!}\sum_{k=0}^{n-m}\frac{(k+j)!}{k!}\frac{k\,2^{-k-j}}{(n-j-k+1)(n-j+1)}\\ =&\frac{(n-(j+1)+1)!}{n!}\sum_{k=0}^{n-(j+1)}\frac{(k+(j+1))!}{k!}\frac{2^{-k-(j+1)}}{n-(j+1)-k+1}\tag{3} \end{align} $$ Thus, $$ \begin{align} (n+1)\sum_{k=0}^n\frac{2^{-k}}{n-k+1} &=\sum_{j=0}^{m-1}\frac{(n-j)!}{n!}\sum_{k=0}^{n-j}\frac{(k+j)!}{k!}2^{-k-j}\\ &+\frac{(n-m+1)!}{n!}\sum_{k=0}^{n-m}\frac{(k+m)!}{k!}\frac{2^{-k-m}}{n-m-k+1}\\ &=\sum_{j=0}^{m-1}\frac{2}{\binom{n}{j}}+O\left(\frac1{n^m}\right)\tag{4} \end{align} $$ since $$ \begin{align} \sum_{k=0}^\infty\frac{(k+j)!}{k!}2^{-k-j} &=j!\sum_{k=0}^\infty\binom{k+j}{k}2^{-k-j}\\ &=j!2^{-j}\sum_{k=0}^\infty(-1)^k\binom{-j-1}{k}2^{-k}\\ &=j!2^{-j}\left(1-\frac12\right)^{-j-1}\\[12pt] &=2j!\tag{5} \end{align} $$ Combining $(1)$ and $(4)$ yields $$ \sum_{m=0}^n\frac1{\binom{n}{m}}=\sum_{j=0}^{m-1}\frac{2}{\binom{n}{j}}+O\left(\frac1{n^m}\right)\tag{6} $$ Equation $(6)$ may seem like a big circle, but it actually tells us that we can ignore the sum of the middle terms as being of the order of the largest term omitted.

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

Your sum is $$\frac1n \sum_{k=0}^{n-1} \dfrac1{\binom{n-1}{k}}.$$

A web search for sum, reciprocal and binomial coefficients turns up some nice identities for this sum, but there does not seem to be a closed form.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for point this out. It enabled me to reach the first expression in the update, which removes the factorials from the sum. $\endgroup$ – jamesthenabignumber Jan 6 '14 at 22:42
1
$\begingroup$

I agree with Phira's answer that a closed form for this sum might not exist. That being said, based on numerical experiment, it seems that asymptotic behaviour of the sum is quite simple and can be approximated as:

$$\sum_{k=0}^{n-1} \frac{1}{\binom{n}{k}(n-k)} \sim \frac{2}{n-1} + \frac{4}{(n+1)(n-1)(n-6)}+O(n^{-6})$$

While this might be somewhat complicated to prove, there is an easier bound which can computed easily. Since all terms of the sequence are positive, if we throw away some terms, we'll obtain a lower bound. In particular, take first $T$ and last $T$ terms for a fixed value of $T$. The first not-taken (and also last non-taken) term is then equal to $$\frac{1}{n}\frac{1}{\binom{n-1}{T}}<\frac{1}{n}\frac{T!}{(n-T)^T}$$ and all the terms in between are even smaller. Since there are $(n-2T)$ of them in total, we can bound their sum by $$\frac{(n-2T)T!}{n(n-T)^T} < \frac{T!}{(n-T)^T}$$

The full sum can then be bounded by: $$\frac{2}{n}\sum_{k=0}^{T-1}\frac{1}{\binom{n-1}{k}} \leq \sum_{k=0}^{n-1} \frac{1}{\binom{n}{k}(n-k)} \leq \frac{2}{n}\sum_{k=0}^{T-1}\frac{1}{\binom{n-1}{k}} + \frac{T!}{(n-T)^T}$$

For example, for $T=2$, we get $$\frac{2}{n} + \frac{2}{n(n-1)}\leq \sum_{k=0}^{n-1} \frac{1}{\binom{n}{k}(n-k)} \leq \frac{2}{n} + \frac{2}{n(n-1)} + \frac{2}{(n-2)^2}$$ or, after simplification, $$\frac{2}{n-1} \leq \sum_{k=0}^{n-1} \frac{1}{\binom{n}{k}(n-k)} \leq \frac{2}{n-1} + \frac{2}{(n-2)^2}$$ which confirms the first coefficient in the conjectured asymptotic formula above.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you very much for this. It seems in agreement with section 3 of this paper, which I found from using your approximation as a search term. $\endgroup$ – jamesthenabignumber Jan 6 '14 at 22:41
  • $\begingroup$ It is interesting that your asymptotic expansion of two terms gives $O(n^{-6})$ error (and it does). My expansion, while simple to continue, requires five terms. $\endgroup$ – robjohn Jan 7 '14 at 22:54
1
$\begingroup$

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ \begin{align} &\sum_{k = 0}^{n - 1}{1 \over {n \choose k}\pars{n - k}} =\sum_{k = 0}^{n - 1}{k!\pars{n - k - 1}! \over n!} =\sum_{k = 0}^{n - 1}{\Gamma\pars{k + 1}\Gamma\pars{n - k}! \over \Gamma\pars{n + 1}} =\sum_{k = 0}^{n - 1}{\rm B}\pars{k + 1,n - k} \end{align} where $\ds{{\rm B}\pars{x,y} \equiv \int_{0}^{1}t^{x - 1}\pars{1 - t}^{y - 1}\,\dd t ={\Gamma\pars{x}\Gamma\pars{y} \over \Gamma\pars{x + y}}}$ is the Beta Function. $\ds{\Re\pars{x},\Re\pars{y} > 0}$. $\ds{\Gamma\pars{z}}$ is the Gamma Function.

\begin{align} &\sum_{k = 0}^{n - 1}{1 \over {n \choose k}\pars{n - k}} =\sum_{k = 0}^{n - 1}\int_{0}^{1}t^{k}\pars{1 - t}^{n - k - 1}\,\dd t =\int_{0}^{1}\pars{1 - t}^{n - 1}\sum_{k = 0}^{n - 1}\pars{t \over 1 - t}^{k}\,\dd t \\[3mm]&=\int_{0}^{1}\pars{1 - t}^{n - 1}\, {\bracks{t/\pars{1 - t}}^{n} - 1 \over t/\pars{1 - t} - 1}\,\dd t =\int_{0}^{1}{t^{n} - \pars{1 - t}^{n} \over 2t - 1}\,\dd t \\[3mm]&=\int_{-1}^{1} {\bracks{\pars{1 + t}/2}^{n} - \bracks{\pars{1 - t}/2}^{n} \over t}\,{\dd t \over 2} ={1 \over 2^{n}}\int_{0}^{1} {\pars{1 + t}^{n} - \pars{1 - t}^{n} \over t}\,\dd t \\[3mm]&=-\,{n \over 2^{n}}\bracks{% \color{#00f}{\int_{0}^{1}\ln\pars{t}\pars{1 + t}^{n - 1}\,\dd t} + \color{#c00000}{\int_{0}^{1}\ln\pars{t}\pars{1 - t}^{n -1}\,\dd t}} \end{align}

$$ \color{#00f}{\int_{0}^{1}\ln\pars{t}\pars{1 + t}^{n - 1}\,\dd t} =\ _{4}{\rm F}_{2}\pars{1,1,1,-n;2,2;-1} $$ $\ds{_{p}{\rm F}_{q}\pars{a_{1},\ldots,a_{p};b_{1},\ldots,b_{q},z}}$ is the Generalized Hypergeometric Function. $$ \color{#c00000}{\int_{0}^{1}\ln\pars{t}\pars{1 - t}^{n -1}\,\dd t} =-\,{H_{n} \over n} $$ $\ds{H_{n}}$ is the $n$-th Harmonic Number.

$$\color{#00f}{\large% \sum_{k = 0}^{n - 1}{1 \over {n \choose k}\pars{n - k}} ={1 \over 2^{n}}\bracks{H_{n} - n\ _{4}{\rm F}_{2}\pars{1,1,1,-n;2,2;-1}}} $$

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