Asymptotic Value of $\sum_{n=1}^{N} \log(1+1/n) \log (\sum_{m=0}^{n} \binom{N}{m})$? I want to compute the asymptotic value of $f(N) =  \sum_{n=1}^{N} [ \log(1+1/n) \cdot \log (\sum_{m=0}^{n} \binom{N}{m})]$. There's an upper bound
$$f(N) \leq \sum_{n=1}^{N} \log(1+1/n) \log 2^N = N \log 2 \cdot \sum_{n=1}^{N} \log((1+1/n)) \leq N \log 2 \sum_{n=1}^{N} \frac{1}{n} = N \log N \cdot \log 2.$$
There's also a lower bound
$$f(N) \geq  \sum_{n=\frac{N}{2}}^{N} \log(1+1/n)  \log 2^{N-1} \approx (N-1) (\log(N)-\log(N/2)) \log 2 \approx (N-1) (\log 2)^2.$$
My questions are

*

*Does $f(N)$ increase at a rate $N \log N$ or $N$?

*Is there a function $g(N)$ such that $\lim_{N \to \infty} f(N)/g(N) = c$ for some constant $c$?

 A: Not a complete answer, but maybe in the right direction.
One way to solve this is to look at $h(N+1) = f(N+1)-f(N)$, and then compute $\lim_{n \to \infty} f(N) =\sum_{N=1}^{\infty} h(N+1)$.
Here $h(N+1) = \log(1+1/(N+1)) \log \sum_{m=0}^{N+1} \binom{N+1}{n} + \sum_{n=1}^{N} \log(1+1/n)[ \log \sum_{m=0}^{n} \binom{N+1}{n} - \log \sum_{m=0}^{n} \binom{N}{n}]$.
The first term is $\log(1+\frac{1}{N+1}) \log 2^{N+1} = \log 2  \log((1+\frac{1}{N+1})^{N+1}) \to log 2  \cdot \log e = \log 2$ when $N$ is large.
I'm not so sure about the second term. When I compute it in Matlab it seems to be slightly above 1.
When I compute the original expression $f(N)/N$ into Matlab, I get a value around $\log 2 + 1$ which seems to support the conjecture that $\lim_{N \to \infty} h(N) = \log 2 + 1$ and $\lim_{N \to \infty} \frac{f(N)}{N}= \log 2 + 1$.
A: From https://en.wikipedia.org/wiki/Binomial_distribution#Tail_bounds we have
$$2^N \frac{1}{\sqrt{2N}} e^{-N g(n/N)} \leq \sum_{m=0}^n {N \choose m} \leq 2^N e^{-N g(n/N)}$$
where
$$g(p)=\log(2) + p \log(p) + (1-p) \log(1-p).$$
This holds for $n \leq N/2$. For larger $n$, the method used in your lower bound introduces at most a constant factor of error.
Thus
$$N \log(2) - \frac{1}{2} \log(2N) - N f(n/N) \leq \log \left ( \sum_{m=0}^n {N \choose m} \right ) \leq N \log(2) - N f(n/N).$$
Or more explicitly
$$n \log \left ( \frac{N}{n} \right ) + (N-n) \log \left ( \frac{N}{N-n} \right ) - \frac{1}{2} \log(2N) \leq \log \left ( \sum_{m=0}^n {N \choose m} \right ) \leq n \log \left ( \frac{N}{n} \right ) + (N-n) \log \left ( \frac{N}{N-n} \right ).$$
So you can then obtain the bounds on the first half of the sum, call it $\tilde{f}(N)$, by using the simple estimate $x/2 \leq \log(1+x) \leq x$ for $0 \leq x \leq 1$):
$$\tilde{f}(N) \geq \sum_{n=1}^{\lfloor N/2 \rfloor} \frac{1}{2n} \left ( n \log \left ( \frac{N}{n} \right ) + (N-n) \log \left ( \frac{N}{N-n} \right ) - \frac{1}{2} \log(2N) \right ) \\
\tilde{f}(N) \leq \sum_{n=1}^{\lfloor N/2 \rfloor} \frac{1}{n} \left ( n \log \left ( \frac{N}{n} \right ) + (N-n) \log \left ( \frac{N}{N-n} \right ) \right ).$$
As I said before, the second half of the sum is $\Theta(N)$ by your method, so I think this is sufficient to finish the problem. It is really just a matter of getting the asymptotics for $\sum_{n=1}^{N/2} \log(N/n)$ and $\sum_{n=1}^{N/2} \frac{N-n}{n} \log \left ( \frac{N}{N-n} \right )$, which appear to both be $\Theta(N)$ though I am not totally confident on how to prove that for the latter case.
A: From Ian's answer, we have
$$
\log \left( {\sum\limits_{m = 0}^n {\binom{N}{m}} } \right) = n\log \left( {\frac{N}{n}} \right) - (N - n)\log \left( {1-\frac{n}{{N}}} \right) + \mathcal{O}(\log N).
$$
for $1 \leq n \leq N-1$. Now
$$
\sum\limits_{n = 1}^{N-1} {\log \left( {1 + \frac{1}{n}} \right)\mathcal{O}(\log N)}  = \mathcal{O}(\log N)\sum\limits_{n = 1}^{N-1} {\frac{1}{n}}  = \mathcal{O}(\log ^2 N).
$$
I showed in my answer to your other question (https://math.stackexchange.com/q/4099634) that
$$
\sum\limits_{n = 1}^{N-1} {\log \left( {1 + \frac{1}{n}} \right)\left( {n\log \left( {\frac{N}{n}} \right) - (N - n)\log \left( {1 - \frac{n}{N}} \right)} \right)}  = \frac{{\pi ^2 }}{6}N + \mathcal{O}(\log ^2 N).
$$
Putting these together, shows that
$$
\sum\limits_{n = 1}^N {\log \left( {1 + \frac{1}{n}} \right)\log \left( {\sum\limits_{m = 0}^n {\binom{N}{m}} } \right)}  = \frac{{\pi ^2 }}{6}N + \mathcal{O}(\log ^2 N)
$$
as $N\to +\infty$ (the term corresponding to $n=N$ on the left-hand side is $\mathcal{O}(1)$).
