8
$\begingroup$

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?

$\endgroup$
14
  • 1
    $\begingroup$ 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$ $\endgroup$
    – saulspatz
    Jul 22, 2020 at 18:12
  • 1
    $\begingroup$ 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) $\endgroup$
    – boink
    Jul 22, 2020 at 18:12
  • 1
    $\begingroup$ @boink No problem. I didn't check $n=m=2$. $\endgroup$
    – saulspatz
    Jul 22, 2020 at 18:13
  • 1
    $\begingroup$ The WA inequality plot looks something interesting. Did you try Stirling's formula for factorials? Thanks. @MiguelHuaylla $\endgroup$ Jul 22, 2020 at 18:18
  • 3
    $\begingroup$ Is it enough to show it for $n=m.$ $\endgroup$
    – Phicar
    Jul 22, 2020 at 18:27

2 Answers 2

6
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – boink
    Jul 23, 2020 at 1:33
  • 1
    $\begingroup$ 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} $. $\endgroup$
    – skbmoore
    Jul 23, 2020 at 2:03
  • $\begingroup$ 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! $\endgroup$
    – boink
    Jul 23, 2020 at 18:58
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.