3

Find this sum closed form $$f(n)=\sum_{i=1}^{n}\dfrac{\binom{n}{i}}{i}$$

My idea: since $$\dfrac{1}{i}=\int_{0}^{1}x^{i-1}dx$$ so $$f(n)=\sum_{i=1}^{n}\left(\int_{0}^{1}x^{i-1}dx\binom{n}{i}\right)=\int_{0}^{1}\sum_{i=1}^{n}\binom{n}{i}x^{i-1}dx$$

then I can't,Thank you

math110
  • 93,304
  • $\int_{0}^{1}\sum_{i=1}^{n}\binom{n}{i}x^{i-1}dx$=$\int_{0}^{1}\frac{1}{x}\sum_{i=1}^{n}\binom{n}{i}x^{i}1^{n-i}dx$ –  Mar 13 '14 at 10:03
  • @china math where do you find such problems ? – OBDA Mar 13 '14 at 10:58

5 Answers5

7

I cannot find a closed form, but I can get a different sum which has an easier asymptotic expansion: $$ \begin{align} a_n &=\sum_{i=1}^n\frac1i\binom{n}{i}\\ &=\sum_{i=1}^n\frac1i\left[\binom{n-1}{i}+\binom{n-1}{i-1}\right]\\ &=a_{n-1}+\sum_{i=1}^n\frac1n\binom{n}{i}\\ &=a_{n-1}+\frac{2^n-1}{n} \end{align} $$ Thus, $$ \begin{align} a_n &=\sum_{i=1}^n\frac{2^i-1}{i}\\ &\sim\frac{2^{n+1}}{n}\left(1+\frac1n+\frac3{n^2}+\frac{13}{n^3}+\frac{75}{n^4}+\dots\right) \end{align} $$

Asymptotic Expansion $$ \begin{align} \frac{n}{2^{n+1}}\sum_{i=1}^n\frac{2^i-1}{i} &=1+\frac{n}{2^{n+1}}\left[\sum_{i=1}^n\frac{2^i-1}{i}-\sum_{i=1}^n\frac{2^i}{n}-\frac2n\right]\\ &=1+\frac{n}{2^{n+1}}\left[\sum_{i=1}^n2^i\left(\frac1i-\frac1n\right)-\left(H_n+\frac2n\right)\right]\\ &=1+\sum_{i=1}^n2^{i-n}\frac{n-i}{2i}-\frac{n}{2^{n+1}}\left(H_n+\frac2n\right)\\ &=1+\sum_{i=0}^{n-1}2^{-i}\frac{i}{2(n-i)}\color{#C00000}{-\frac{n}{2^{n+1}}\left(H_n+\frac2n\right)}\\ &\sim1+\sum_{i=0}^\infty2^{-i}\frac12\left(\frac{i}{n}+\frac{i^2}{n^2}+\frac{i^3}{n^3}+\dots\right)\\ &\sim1+\frac1n+\frac3{n^2}+\frac{13}{n^3}+\frac{75}{n^4}+\dots \end{align} $$ The red term decays exponentially, so it can essentially be ignored.

robjohn
  • 345,667
1

Using your idea, sooner or later one reaches the formula $$ f(n)=n\int_0^1\!\!\int_0^1(1+xy)^{n-1}\mathrm dx\mathrm dy. $$ Whether this is a "closed form" or not is at best debatable...

Did
  • 279,727
1

There is a closed form which is probably not the most pleasant one since it involves an hypergeometric function $$f(n)=\sum_{i=1}^{n}\dfrac{\binom{n}{i}}{i}=n \text { } \, _3F_2(1,1,1-n;2,2;-1)$$ If $\log (f(n))$ is plotted as a function of $n$, it looks quite linear (may be this could give an idea to other participants).

Claude Leibovici
  • 260,315
  • n! * f(n) is http://oeis.org/A103213 and there you find a E.G.F. $log((1-2*x)/(1-x))/(x-1)$ and so this is the OGF for f(n). The Hypergeometric closed form is also mentioned. – Wouter M. Mar 13 '14 at 11:09
  • @WouterM. Thanks for the information. Cheers. – Claude Leibovici Mar 13 '14 at 13:31
  • 1
    According to the asymptotic approximation I give, $\log(f(n))\sim(n+1)\log(2)-\log(n)$ which is pretty linear looking. – robjohn Mar 13 '14 at 15:29
  • +1 At first sight, I thought it was some kind of Beta function. Later on, I saw it was something like Hypergeometric job. Fine answer. – Felix Marin Mar 14 '14 at 00:41
0

$$\sum_{i=1}^n {n\choose i} x^{i-1} = \frac1x \left(\sum_{i=1}^n{n\choose i} 1^{n-i}x^{i}\right)=\frac1x\left(\sum_{i=0}^n{n\choose i} 1^{n-i}x^{i} -1\right)= \frac1x\left((1+x)^n - 1\right)$$

5xum
  • 123,496
  • 6
  • 128
  • 204
0

Just another way at ending at an integral form for the answer: $$(1+x)^n = \sum_{i=0}^n \binom{n}{i}x^i \implies \sum_{i=1}^n \binom{n}{i}x^{i-1} = \frac{(1+x)^n-1}x$$

Now integrate both sides and set $x=1$. Mathematica gives a hypergeometric function as the answer, so I guess for now the best is: $$ \left. \int_0^x \frac{(1+t)^n- 1}{t}dx \right |_{x=1}$$

Macavity
  • 46,381