# binomial sum approximation

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.

• $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. – Dhruv Kohli - expiTTp1z0 Nov 19 '16 at 13:30

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

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