# Proving $\log\left(\frac{4^n}{\sqrt{2n+1}{2n\choose n+m}}\right)\geq \frac{m^2}{n}$

I have tried doing this exercise,

Let $$m,n\in\mathbb{N}, m\leq n$$, prove that $$\log\left(\frac{4^n}{\displaystyle\sqrt{2n+1}{2n\choose n+m}}\right)\geq \frac{m^2}{n}$$

I achieved some results like for example, $$\displaystyle\sum_{i=0}^n 2^i\binom{2n-i}{n} = 4^n$$ and $$\displaystyle {{2n}\choose{n}} > \frac{4^n}{2n}$$ trying to find a relationship but it doesn't work for me. Any idea?

• If $n=m=1$, this says $\log{\frac4{\sqrt3}}\geq1$, or that $\frac4{\sqrt3}\geq e$, assuming $\log$ mean the natural logarithm. This is false. $\frac4{\sqrt3}\approx2.3$ Commented Jul 22, 2020 at 18:12
• Just a note—this isn't true for $m=n=1$ or $m=n=2$ (though I think those are the only exceptions). (Oh @saulspatz, sorry! I didn't see your comment :D) Commented Jul 22, 2020 at 18:12
• @boink No problem. I didn't check $n=m=2$. Commented Jul 22, 2020 at 18:13
• The WA inequality plot looks something interesting. Did you try Stirling's formula for factorials? Thanks. @MiguelHuaylla Commented Jul 22, 2020 at 18:18
• Is it enough to show it for $n=m.$ Commented Jul 22, 2020 at 18:27

With @skbmoore's work, we know that this is true for $$m<\sqrt{\log(\pi/2)}n$$. I'll now show that it's also true for $$m>\frac12n$$, which will obviously prove the result.

Rearrange the desired inequality as thus: $$\log\left(\frac{4^n}{\sqrt{2n+1}}\right)\ge\frac{m^2}n+\log\binom{2n}{n+m}=f_n(m).$$ We're basically going to try to show that $$f_n(m)$$ is decreasing after $$m=n/2$$ (actually, it's a bit before that; I believe it is somehow related to OEIS A143978).

Observe that $$\frac d{dm}f_n(m)=\frac{2m}n+\psi(n-m+1)-\psi(n+m+1),$$ where $$\psi$$ is the digamma function. (This is from Wolfram Alpha; I've actually never worked with $$\psi$$ before today, so please let me know if I mess up anywhere here—I'm a bit out of my depth!) Do note that we're extending $$f_n(m)$$ to be over $$[1,n]$$, instead of only the integers.

Apparently, for $$z\ne-1,-2,\dots$$, there is an equation for the digamma function, namely $$\psi(z+1)=-\gamma+\sum_{k=1}^\infty\left(\frac1k-\frac1{k+z}\right),$$ where $$\gamma$$ is the Euler-Mascheroni constant. It is fortunate for us, then, that $$n-m$$ and $$n+m$$ are never nonnegative integers! This means, in particular, that $$-g_n(m)=\psi(n-m+1)-\psi(n+m+1)=\sum_{k=1}^\infty\left(\frac1{k+n+m}-\frac1{k+n-m}\right).$$

Our goal, then, is going to be to show that $$g_n(m)>\frac{2m}n$$ for all $$n>m>\frac n2$$. Then we can show that $$f_n(m)=\frac{2m}n-g_n(m)<0$$.

First, observe that $$\frac d{dm}g_n(m)=\sum_{k=1}^\infty\left(\frac1{(k+n+m)^2}-\frac1{(k+n-m)^2}\right)>0$$ for all $$m$$. This means, in particular, that if $$m$$ is not an integer, then $$g_n(m)$$ is sandwiched between $$g_n(\lfloor m\rfloor)$$ and $$g_n(\lceil m\rceil)$$. Obviously, the function $$\frac{2m}n$$ is increasing with respect to $$m$$. This all implies that it is sufficient to show that $$\tag{*}g_n(m)\ge\frac{2m-2}n$$ for integers $$m\ge\frac n2$$.

However, for integers $$m$$, we know that $$g_n(m)$$ telescopes as $$g_n(m)=\sum_{k=1}^{2m}\frac1{k+n-m}.$$ Now, if $$(*)$$ holds for $$m$$, then it holds for $$m+1$$. This can be seen by observing that the left hand side increases by $$\frac1{n-m}+\frac1{n+m+1}$$, while the right side increases by $$\frac2n$$.

Thus it suffices to prove the statement $$(*)$$ for $$m=\lceil\frac n2\rceil$$. But then \begin{align*}g_n(m)&\ge\sum_{k=1}^n\frac1{k+(n-1)/2}\\\frac{2(m-1)}n&\le1.\end{align*} So it suffices to prove that $$h(n)=\sum_{k=1}^n\frac1{k+(n-1)/2}\ge1$$.

But it is easy to see that if we define $$h(n)$$ to be the sum above, but removing the floors, then $$\frac d{dn}h(n)<0$$. Moreover, as $$n\to\infty$$, this approaches $$\log3>1$$, according to Wolfram. If someone wants to give me a tip as to how to actually show this limit, I'd love to hear it, but, honestly, I'm a bit pooped! (Check out @skbmoore's explanation for why $$h(n)\to\log3$$ in the comments!)

This does, however, prove the conjecture! I'm sure there's a much simpler way to do this, since there's no real intuition here; it's just bashing with the one tool I know how to use (Wolfram Alpha! :D)

• PS. Why I think the linked OEIS sequence is related: For a fixed $n$, it seems that $f_n(m)$ attains its maximum (where $m$ is an integer less than $n$; the actual maximum is at a non-integer, usually) at the integer $m$ so that $a(m)\le n<a(m+1)$, or something like that. (I might have the indices/strictness wrong, since I accidentally deleted the code already.) So if anyone has any ideas for why this is the case, that'd be pretty cool! Commented Jul 23, 2020 at 1:33
• I like the proof completion, and suggest to the proposer to assign you the correct answer. (It saved me a lot of time from my pursuing my idea, which would not have been elegant.) By the way, to show $h(n) \to \log(3)$ for $n \to \infty,$ turn it into a Riemann sum $1/N \sum_{k=1}^{2N} 1/(1+k/N)$ which as $N \to \infty$ is $\int_0^2 \ dx/(1+x) = \log{3}$. Commented Jul 23, 2020 at 2:03
• Ahh thanks! Your solution was pretty cool (there's no way I would've thought of it!). And the $h(n)\to\log3$ makes a lot of sense—thanks! Commented Jul 23, 2020 at 18:58

Here is a partial proof. I have some ideas, but it will be a while before I can return to it. I'll show that the conjecture is true for $$m<\sqrt{\log{(\pi/2)}} \ n \sim .672 \ n.$$ Maybe someone else can use these ideas for a full proof.

Use the fact that the central binomial $$\binom{2n}{n+m}$$ has its max at $$m=0.$$ Do an asymptotic expansion

$$\binom{2n}{n+m} \big/\binom{2n}{n}=1-\frac{m^2}{n}+\frac{m^2(1+m^2)}{2n^2}-\frac{m^2(1+4m^2+m^4)}{6n^3}...$$ It 'just so happens' that these are the first three terms in $$\exp{\big(-\frac{m^2}{n}(1-\frac{1}{2n}) \big)} =1-\frac{m^2}{n}+\frac{m^2(1+m^2)}{2n^2}-\frac{m^2(3m^2+m^4)}{6n^3}...$$ match. (The gaussian approximation is well known and I added the factor $$(1-1/(2n))$$ to match the third term.) The exponential makes a convenient bound to go in this problem (note the flip): $$\binom{2n}{n} \big/\binom{2n}{n+m} \ge \exp{\big(\frac{m^2}{n}(1-\frac{1}{2n}) \big)}$$

Then $$L:=\log\Big(\frac{4^n}{\sqrt{2n+1}\binom{2n}{n+m}}\Big)= \log\Big(\frac{4^n}{\sqrt{2n+1}\binom{2n}{n}} \binom{2n}{n} \big/\binom{2n}{n+m}\Big)$$ $$\ge\log\Big(\frac{4^n}{\sqrt{2n+1}\binom{2n}{n}} \exp{\big(\frac{m^2}{n}(1-\frac{1}{2n})}\big) \Big)$$ $$\geq \frac{1}{2} \log{\big( \pi \ n/(2n+1) \big)} + \frac{m^2}{n}(1-\frac{1}{2n})$$ where the Stirling approximation has been used for the central binomial. For large $$n$$ proposer's reduces to $$\frac{1}{2} \log{\big( \pi /2)} > \frac{m^2}{2n^2} .$$ This is indeed true for $$m<\sqrt{\log{(\pi/2)}} \ n.$$

The problem that I see with this method is that the Gaussian approximation, even with my correction to get the third order term matched, does not do a good job in the 'wings' (large $$m.$$) A better function is needed, and I believe there are 'entropy' function formulations that can do this. I don't know if an analytic solution will be available using it, but at least the one I've given gets part of the way there.