4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @RoryDaulton The square braces denote an interval, and I think you can assume that the ball is the same as the apple. $\endgroup$ – wythagoras Jul 7 '15 at 15:06
  • 3
    $\begingroup$ 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}}$ $\endgroup$ – Henry Jul 7 '15 at 15:53
  • $\begingroup$ @Henry Sorry, there was a typo in the question which I'd written earlier. I've corrected it now. $\endgroup$ – Henry Jul 8 '15 at 7:53
4
+50
$\begingroup$

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.$$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Induction feels bashful in this case... Isn't there any way to do without it? $\endgroup$ – Henry Jul 10 '15 at 15:07
  • $\begingroup$ If you didn't want induction, you should have specified upfront, not 3 days later! $\endgroup$ – Macavity Jul 10 '15 at 15:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Macavity Jul 10 '15 at 15:38
  • $\begingroup$ Here is another reference, but this one requires induction amotlpaa.org/math/sinepower.pdf. $\endgroup$ – Batominovski Jul 12 '15 at 17:36
2
$\begingroup$

Here is another rather elementary answer.

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

\begin{align*} \frac{1}{2\sqrt{m}}\leq a_m \leq \frac{1}{\sqrt{2m+1}}\qquad\qquad m\geq 1\tag{1} \end{align*}

We start similarly to @CuriousGuest

\begin{align*} a_m&=\frac{1}{4^m}\binom{2m}{m}=\frac{(2m)!}{4^mm!m!}=\frac{(2m)!!(2m-1)!!}{4^mm!m!}\\ &=\frac{(2m-1)!!}{2^mm!}=\frac{(2m-1)!!}{(2m)!!}\\ &=\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdots\frac{2m-1}{2m} \end{align*}

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*}

which proves the left inequality of (1)

$$$$

In order to show the right inequality we observe \begin{align*} a_m&=\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdots \frac{2m-1}{2m}\\ &<\frac{2}{3}\cdot\frac{4}{5}\cdot\frac{6}{7}\cdots \frac{2m}{2m+1}\\ &=\frac{2}{1}\cdot\frac{4}{3}\cdot\frac{6}{5}\cdots \frac{2m}{2m-1}\,\cdot\,\frac{1}{2m+1}\\ &=\frac{1}{a_m}\cdot\frac{1}{2m+1} \end{align*} We conclude \begin{align*} a_m^2&<\frac{1}{2m+1}\\ a_m&<\frac{1}{\sqrt{2m+1}} \end{align*} which proves the right inequality of (1).

$\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.