# Show that $p \in \left[\frac{4^m}{2\sqrt{m}},\frac{4^m}{\sqrt{2m+1}}\right]$

If the number of ways in which $m$ identical apples can be put in $2m$ boxes, so that no box contains more than one apple, is $p$, prove that $$p \in \left[\frac{4^m}{2\sqrt{m}},\frac{4^m}{\sqrt{2m+1}}\right]$$

I did this as follows :

Let the number of apples in $i^{th}$ box be $x_{i}$, then,

$$\sum_{i=1}^{2m}x_{i}=m$$

where $x_{i} \in \{0,1\}$ and the number of ways would be the number of solutions to this equation, which is equal to the coefficient of $x^m$ in $(1+x)^{2m}$ i.e, $p=\dbinom{2m}{m}$

However, I can't prove that $p \in \left[\frac{4^m}{2\sqrt{m}},\frac{4^m}{\sqrt{2m+1}}\right]$. Can we prove this inequality without induction? Also, is my method correct ?

Any help will be appreciated.
Thanks

• @RoryDaulton The square braces denote an interval, and I think you can assume that the ball is the same as the apple. – wythagoras Jul 7 '15 at 15:06
• I would have thought that there may be some problems here: first $\frac{4^m}{\sqrt{2m}} \gt \frac{4^m}{\sqrt{2m+1}}$ and second ${2m \choose m}$ is outside the interval. Wikipedia gives $\frac{4^n}{\sqrt{4n}} \leq {2n \choose n} \leq \frac{4^n}{\sqrt{3n+1}}$ – Henry Jul 7 '15 at 15:53
• @Henry Sorry, there was a typo in the question which I'd written earlier. I've corrected it now. – Henry Jul 8 '15 at 7:53

Here's an approach without induction. In fact it's one of the standard ways to derive Wallis' formula and to get an asymptotic behaviour of this quantity (in a way better result than inequalities). First, it's easy to see that $$\binom{2m}{m}=\frac{(2m)!}{(m!)^2}=4^m\frac{(2m)!!(2m-1)!!}{(2m)!!(2m)!!}=4^m\frac{(2m-1)!!}{(2m)!!},$$ where $(2m)!!=2\cdot4\cdot 6\cdot\ldots\cdot2m$ and $(2m-1)!!=1\cdot3\cdot 5\cdot\ldots\cdot(2m-1)$, so it suffices to prove that $$\frac{1}{4m}<\left(\frac{(2m-1)!!}{(2m)!!}\right)^2<\frac{1}{2m+1}.$$ For this purpose we consider integral $$\int_{0}^{\pi/2}\sin^n x\,dx=\begin{cases}\frac{(n-1)!!}{n!!}\cdot\frac{\pi}{2},\mbox{ if }n=2m,\\ \frac{(n-1)!!}{n!!},\mbox{ if }n=2m-1.\end{cases}$$ Using obvious inequality $$\int_{0}^{\pi/2}\sin^{2m+1} x\,dx<\int_{0}^{\pi/2}\sin^{2m} x\,dx<\int_{0}^{\pi/2}\sin^{2m-1} x\,dx,$$ i.e. $$\frac{(2m)!!}{(2m+1)!!}<\frac{(2m-1)!!}{(2m)!!}\cdot\frac{\pi}{2}<\frac{(2m-2)!!}{(2m-1)!!},$$ we get $$\frac{1}{\pi(m+\frac12)}<\left(\frac{(2m-1)!!}{(2m)!!}\right)^2<\frac{1}{\pi m}.$$ Since $\pi(m+\frac12)<\frac{16}{5}(m+\frac12)\leq 4m$ when $4m+2\leq 5m$, $m\geq2$, and $\pi m>3m\geq2m+1$ when $m\geq 1$, the inequality in question follows. Moreover, we also have asymptotic relation $$\left(\frac{(2m-1)!!}{(2m)!!}\right)^2\sim \frac{1}{\pi m},\quad\mbox{ or }\quad\binom{2m}{m}\sim\frac{4^m}{\sqrt{\pi m}},\quad m\to\infty.$$

So you need to pick $m$ boxes out of $2m$ in which to put an apple each, which is clearly $\binom {2m}m$ as you note.

We can use induction to show $p$ lies in the required interval. This is trivial for $m=1$ and the inductive step requires us to show $$4\sqrt{\frac{m}{m+1}}\le \frac{(2m+1)(2m+2)}{(m+1)^2}\le 4\sqrt{\frac{2m+1}{2m+3}}$$

On simplification the left inequality reduces to the AM-GM $2\sqrt{m(m+1)}\le 2m+1$ and the right inequality is equivalent to $2\sqrt{(2m+1)(2m+3)}\le 4m+4$ which is also AM-GM.

• Induction feels bashful in this case... Isn't there any way to do without it? – Henry Jul 10 '15 at 15:07
• If you didn't want induction, you should have specified upfront, not 3 days later! – Macavity Jul 10 '15 at 15:14
• For better estimates of the central binomial coefficient, you can check math.stackexchange.com/questions/58560/… and pick your method. If thats what you really want, this question is really a duplicate. – Macavity Jul 10 '15 at 15:38
• Here is another reference, but this one requires induction amotlpaa.org/math/sinepower.pdf. – Batominovski Jul 12 '15 at 17:36

Here is another rather elementary answer.

Let $a_m=\frac{1}{4m}\binom{2m}{m}$. We show the following is valid

Now we consider $a_m^2$ and obtain \begin{align*} a_m^2&=\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdot\frac{5}{6}\cdots\frac{2n-1}{2n}\cdot\frac{2n-1}{2n}\\ &>\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{3}{4}\cdot\frac{4}{5}\cdot\frac{5}{6}\cdots\frac{2m-2}{2m-1}\cdot\frac{2m-1}{2m}\\ &=\frac{1}{4m} \end{align*} Thus \begin{align*} a_m>\frac{1}{2\sqrt{m}} \end{align*}