Closed form and/or approximation for $f_n=\sum\limits_{i=1}^{n-1}\binom{n}{i}\cdot i\cdot \log(i)$

Question

Is there any closed form for the expression : $$f_n=\sum_{i=1}^{n-1}\binom{n}{i}\cdot i\cdot \log(i)\ ?$$

If not, how to get an approximation?

Answer 1

As comments already said, I doubt that a closed form could exist.

However, in terms of approximation, considering the function $$f_n=\sum_{i=1}^{n-1}\binom{n}{i}\, i\,\log(i)$$ is is interesting to notice that its logarithm varies almost linearly with $n$ (at least for large values of $n$).

Generating values for $100 \leq n \leq 2000$ (step of $100$), a linear regression leads to $$\log(f_n)\approx 0.694652 \,n+6.23536$$ and a nonlinear regression leads to $$f_n\approx e^{0.693735\,n+7.66555}$$

Extrapolated to $n=3000$, for an "exact" value of $1.35\times 10^{907}$, the simple correlation leads to $1.53\times 10^{907}$. Far from perfection, for sure, but better than nothing to get at least the order of magnitude.

Answer 2

There is no hope to get exact formulas (since, for example, the logarithms of the prime numbers are linearly independent on the rational numbers). However, one can get rather precise asymptotics of

$$f_n=\sum_{k=1}^{n-1}{n\choose k}k\log k$$

To do so, first note that $$f_n=2^n\sum_{k=0}^n\frac1{2^n}{n\choose k}k\log k-n\log n=2^nE(B_n\log B_n)-n\log n$$ where $B_n$ is binomial $(n,\frac12)$ with expectation $E(B_n)=\frac{n}2$. The function $x\mapsto x\log x$ is convex hence $$f_n\geqslant2^nE(B_n)\log E(B_n)-n\log n=2^{n-1}n\log\left(\tfrac{n}2\right)-n\log n$$ Likewise, $k{n\choose k}=n{n-1\choose k-1}$ hence $$f_n=2^{n-1}n\sum_{k=0}^{n-1}\frac1{2^{n-1}}{n-1\choose k}\log(k+1)-n\log n=2^{n-1}nE(\log(1+B_{n-1}))-n\log n$$ where $B_{n-1}$ is binomial $(n-1,\frac12)$ with expectation $E(B_{n-1})=\frac{n-1}2$. The function $x\mapsto \log(1+x)$ is concave hence $$f_n\leqslant 2^{n-1}n\log(1+E(B_{n-1}))-n\log n=2^{n-1}n\log\left(\tfrac{n+1}2\right)-n\log n$$ To sum up, for every $n$, one has

$$2^{n-1}n\log(n)\leqslant f_n+2^{n-1}n\log(2)+n\log n\leqslant2^{n-1}n\log(n+1)<2^{n-1}n\log(n)+2^{n-1}$$

which can be simplified into

$$f_n=2^{n-1}n\log\left(\tfrac{n}2\right)+O(2^n)$$

for an explicit error term $O(2^n)$, which implies $$\log f_n=(n-1)\log2+\log n+\log\log\left(\tfrac{n}2\right)+O\left(\tfrac1{n\log n}\right)$$ for an explicit error term $O\left(\tfrac1{n\log n}\right)$.

Answer 3

By exploiting Frullani's theorem $$ \log(k) = \int_{0}^{+\infty}\frac{e^{-x}-e^{-kx}}{x}\,dx \tag{1}$$ we get that: $$ f_n = n\int_{0}^{+\infty}\left((2^{n-1}-1)e^{-x}-((e^x+1)^{n-1}-1)e^{-nx}\right)\frac{dx}{x}\tag{2}$$ from which: $$ f_n = n(2^{n-1}-1)\log n+\color{blue}{n\int_{0}^{+\infty}\left[(e^x+1)^{n-1}-2^{n-1}\right]\frac{dx}{x e^{nx}}}. \tag{3} $$ If $a>b>0$ we have $a^n-b^n \leq n(a-b)a^{n-1}$, hence the $\color{blue}{\text{remainder term}}$ in $(3)$ is bounded by: $$ n(n-1)\int_{0}^{+\infty}\frac{(e^x+1)^{n-2}(e^x-1)}{x e^{nx}}\,dx\leq n(n-1)\int_{0}^{+\infty}\frac{(e^x+1)^{n-2}}{e^{(n-1)x}}\,dx\leq n 2^{n-1} $$ hence: $$ f_n = n 2^{n-1}\left(\log n+O(1)\right) \tag{4}$$ without using any probabilistic argument.