5
$\begingroup$

This MO question prompted me to ask:

What is the second order asymptotic growth/decay rate for the sum $$\sum_{k=0}^n\frac1{\binom{n}k}$$ as $n\rightarrow\infty$?

$\endgroup$
3
6
$\begingroup$

This sum can be written in the form, see 2-adic Logarithm and Resistance of n-dimensional Cube $$S_{n+1}=\frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k}.$$ The last term in the sum gives the estimate $S_n>1.$ You can get sharper estimates taking more terms.

$\endgroup$
1
  • 3
    $\begingroup$ This converges slower than the original sum... $\endgroup$ – Will Sawin Mar 28 '19 at 6:57
5
$\begingroup$

The following asymptotic expansion is proved in https://arxiv.org/abs/0904.1757 (The Hypercube of Resistors, Asymptotic Expansions, and Preferential Arrangements, by Nicholas Pippenger. Published in Mathematics Magazine 83(N5) (2010), 331-346): $$\sum_{k=0}^n\frac{1}{\binom{n}{k}}=2\left(1+\frac{1}{n}+\frac{2}{n(n-1)}+\ldots \frac{k!}{n(n-1)\cdots(n-k+1)}+O(\frac{1}{n^{k+1}})\right).$$

P.S. This result confirms the answer given in the Gerhard Paseman's comment.

$\endgroup$
1
  • $\begingroup$ For k less than sqrt(n)-3, the terms look a little like a geometric sequence with common ratio more than order of sqrt(n), giving that the middle terms add up to less than (1 +2/sqrt(n)) times the kth term. Even for most k less than n/3, the middle terms add up to less than (1+ 2log_2(n)) times the kth term. So the O term above can be given an explicit constant for many k and n sufficiently large. Gerhard "Simple Estimates Are The Best" Paseman, 2018.06.05. $\endgroup$ – Gerhard Paseman Jun 5 '18 at 8:06

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.