Asymptotic lower bound of this function

Question

Suppose that $n$ is an even number. Let $$f(n)=\frac{\sum_{j=1}^{n/2}\binom{n}{2j}\log(2j)}{2^{n-1}}.$$ Can we find some function $g(n)$ (e.g. $\log(n)$ or $n^\alpha$) such that $f(n)=\Omega(g(n))$?

Thank you!

Answer 1

Not full-fledged, but a detailed outline giving a $\Theta(\log n)$ bound.

Let us rewrite $n=2m$ to avoid annoying fractions. Since the $2^n$ is fixed, we can focus on the sum. Since we want $\Theta(\cdot)$ asymptotics, the basis of the logarithm is irrelevant, I will assume binary.

First, upper bound: $$ \sum_{j=1}^m \binom{2m}{2j} \log 2j \leq \log 2m\cdot \sum_{j=1}^m \binom{2m}{2j} \leq \log 2m\cdot \sum_{j=0}^{2m} \binom{2m}{j} = \log 2m\cdot 2^{2m} $$

Second, lower bound (I assume m is even, otherwise we can carry floor functions, thi'll be similar): $$\begin{align} \sum_{j=1}^m \binom{2m}{2j} \log 2j &\geq \sum_{j=m/2}^m \binom{2m}{2j} \log 2j\geq \log m \sum_{j=m/2}^m \binom{2m}{2j} \\ &= \log m \cdot \Omega(1)\sum_{\ell=m}^{2m} \binom{2m}{\ell} \tag{1}\\ &= \log m \cdot \Omega(1)\sum_{\ell=0}^{2m} \binom{2m}{\ell} \tag{2}\\ &= \log m \cdot \Omega(2^{2m}) \end{align}$$

so that the numerator is $\Theta(\log m 2^{2m})= \Theta(\log n 2^n)$, and your quantity overall is $\Theta(\log n)$.

---

For (1), we used that the hypercube is roughly balanced, i.e. $$ \sum_{\substack{m \leq \ell\leq 2m\\ \ell\text{ even}}}^{} \binom{2m}{\ell} = \Theta\Big( \sum_{\substack{m \leq \ell\leq 2m\\ \ell\text{ odd}}}^{} \binom{2m}{\ell} \Big) $$

For (2), we used that $$ \sum_{\ell=0}^{m-1} \binom{2m}{\ell} = \sum_{\ell=m+1}^{2m} \binom{2m}{\ell} $$

---

Conjecture. The correct, exact asymptotic bound is $$ \frac{1}{2^{n-1}}\sum_{j=1}^{\frac{n}{2}}\binom{n}{2j}\log 2j = (1+o(1)) \log n. $$ (Moreover, it should not be insanely hard to show.)

Empirical validation: (i.e., "not even remotely a proof, but look! pretty picture")