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$?
$\begingroup$
$\endgroup$
3
asked Jun 5, 2018 at 0:18
-
4$\begingroup$ Elementary considerations give 2 + 2/n +4/(n(n-1)) + 12/(n(n-1)(n-2)) + (n-7) times terms of order at greatest n^{-4}. How much finer growth do you want? Gerhard "Thinks There's No Closed Form" Paseman, 2018.06.04. $\endgroup$– Gerhard PasemanCommented Jun 5, 2018 at 0:23
-
$\begingroup$ If you start combining terms, you can get 2 + 2/(n-2) + a cubic term plus a quartic error term, but I doubt you will get as far as 2+ 2/(n-3). That should be good enough. Gerhard "We're Not Splitting Atoms Here" Paseman, 2018.06.04. $\endgroup$– Gerhard PasemanCommented Jun 5, 2018 at 0:37
-
$\begingroup$ Using Approach0 you can find a few posts on Mathematics that seem related. For example, Compute $\sum_{k=0}^{n}\frac{1}{\binom{n}{k}}$ or Finding $\lim\limits_{n \to \infty} \sum\limits_{k=0}^n { n \choose k}^{-1}$ $\endgroup$– Martin SleziakCommented Jun 5, 2018 at 2:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Jun 5, 2018 at 1:37
-
3$\begingroup$ This converges slower than the original sum... $\endgroup$ Commented Mar 28, 2019 at 6:57
$\begingroup$
$\endgroup$
1
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.
answered Jun 5, 2018 at 5:01
-
$\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$ Commented Jun 5, 2018 at 8:06