1
$\begingroup$

How can I get an approximation formula for the sum $J(n) = 2^{-n} \sum_{k=1}^n \frac{1}{k} {n \choose k}$?

I know it tends to $\frac{2}{n-1}$ but I need higher order terms. I have tried Stirling's approximation on the middle term giving: $\sqrt{\frac{2}{\pi n}}$ but I don't think it's the right way.

$\endgroup$
  • $\begingroup$ $J(n)$ can be shown to be equal to $2^{-n} \int\limits_{0}^{1} ((1+x)^n-1)/x dx$ using binomial expansion of $(1+x)^n$. However, the integral is not easy to compute and results in $\frac{x^{n}\,_2F_1(-n,-n;1-n;\frac{-1}{x})}{2^n n} - \frac{1}{2^n}\log(x)$. Expanding the hypergeometric function will give higher order terms. $\endgroup$ – Dhruv Kohli - expiTTp1z0 Nov 19 '16 at 13:30
0
$\begingroup$

$$\newcommand{\stirtwo}[2]{\left\{#1\atop#2\right\}} \begin{align} 2^{-n}\sum_{k=1}^n\frac1k\binom{n}{k} &=2^{-n}\sum_{k=1}^n\frac1k\sum_{j=k}^n\binom{j-1}{k-1}\tag{1}\\ &=2^{-n}\sum_{k=1}^n\sum_{j=k}^n\frac1j\binom{j}{k}\tag{2}\\ &=2^{-n}\sum_{j=1}^n\sum_{k=1}^j\frac1j\binom{j}{k}\tag{3}\\ &=2^{-n}\sum_{j=1}^n\frac{2^j-1}j\tag{4}\\ &\sim\sum_{j=0}^{n-1}\frac{2^{-j}}{n-j}\tag{5}\\ &=\frac1n\sum_{j=0}^{n-1}2^{-j}\sum_{k=0}^\infty\frac{j^k}{n^k}\tag{6}\\ &\sim\sum_{k=0}^\infty\frac1{n^{k+1}}\sum_{j=0}^\infty\frac{j^k}{2^j}\tag{7}\\ &=\sum_{k=0}^\infty\frac1{n^{k+1}}\sum_{j=0}^\infty\sum_{i=0}^k2^{-j}\binom{j}{i}\stirtwo{k}{i}i!\tag{8}\\ &=\sum_{k=0}^\infty\frac1{n^{k+1}}\sum_{i=0}^k\stirtwo{k}{i}i!\sum_{j=0}^\infty2^{-j}\binom{j}{i}\tag{9}\\ &=\sum_{k=0}^\infty\frac2{n^{k+1}}\sum_{i=0}^k\stirtwo{k}{i}i!\tag{10}\\[3pt] &=\sum_{k=0}^\infty\frac{2a_k}{n^{k+1}}\tag{11}\\[4pt] &=\frac2n+\frac2{n^2}+\frac6{n^3}+\frac{26}{n^4}+\frac{150}{n^5}+O\!\left(\frac1{n^6}\right)\tag{12}\\[9pt] &=\frac2{n-1}+\frac4{(n-1)^3}+\frac{12}{(n-1)^4}+\frac{76}{(n-1)^5}+O\!\left(\frac1{n^6}\right)\tag{13} \end{align} $$ Explanation
$\phantom{0}(1)$: $\binom{n}{k}=\sum\limits_{j=k}^n\binom{j-1}{k-1}$
$\phantom{0}(2)$: $\frac1k\binom{j-1}{k-1}=\frac1j\binom{j}{k}$
$\phantom{0}(3)$: change order of summation
$\phantom{0}(4)$: $\sum\limits_{k=1}^j\binom{j}{k}=2^j-1$
$\phantom{0}(5)$: substitute $j\mapsto n-j$ and ignore terms that decay exponentially
$\phantom{0}(6)$: $\frac1{n-j}=\frac1n\sum_{k=0}^\infty\frac{j^k}{n^k}$
$\phantom{0}(7)$: change order of summation and ignore terms that decay exponentially
$\phantom{0}(8)$: $j^k=\sum\limits_{i=0}^k\binom{j}{i}\stirtwo{k}{i}i!$ where $\stirtwo{k}{i}$ is a Stirling Number of the Second Kind
$\phantom{0}(9)$: change order of summation
$(10)$: $\sum\limits_{j=0}^\infty2^{-j}\binom{j}{i}=2$
$(11)$: $a_k=\sum\limits_{i=0}^k\stirtwo{k}{i}i!$ is an Ordered Bell Number or Fubini Number
$(12)$: compute the first few terms of the asymptotic expansion
$(13)$: base the expansion at $n-1$

$\endgroup$
  • $\begingroup$ A formal suggestion: You can use $\mathcal O$ (\mathcal O) instead of $O$. $\endgroup$ – callculus Nov 19 '16 at 13:34

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.