3
$\begingroup$

Prove that $$\dfrac{1}{1999} < \prod_{i=1}^{999}{\dfrac{2i−1}{2i}} < \dfrac{1}{44}$$

from the 1997 Canada National Olympiad.

I have been able to prove the left half of the inequality using induction. Need help with the second part.


Prove $\prod_{i=1}^{n}{(1-\frac{1}{2i})} \ge \frac{1}{2n}$

Define $$p(n)=\prod_{i=1}^{n}{\left(1-\frac{1}{2i}\right)} \tag{1}$$

We wish to show $$p(n)\ge\frac{1}{2n},\quad\forall{n}\in\mathbb{Z^+} \tag{2}$$

For the base case, $n=1$, we have $p(1)=1-\frac{1}{2}=\frac{1}{2}\ge\frac{1}{2}$ which holds.

Assume the induction hypothesis (2) for $n$. Then for $n+1$, we can write:

$$\begin{align} p(n+1) = \prod_{i=1}^{n+1}{\left(1-\frac{1}{2i}\right)} &= \left(1-\frac{1}{2(n+1)}\right) \cdot \prod_{i=1}^{n}{\left(1-\frac{1}{2i}\right)} \\ &\ge \left(1-\frac{1}{2(n+1)}\right) \cdot \frac{1}{2n} &(\text{by IH}) \\ &\ge \left(\frac{2n+1}{2(n+1)}\right) \cdot \frac{1}{2n} \\ &\ge \left(\frac{1}{2(n+1)}\right) \cdot \frac{2n+1}{2n} \\ &> \left(\frac{1}{2(n+1)}\right) &(\text{for }n\ge1) \end{align}$$

This proves the induction step, establishing (2) for all positive $n$. Hence, we conclude

$$\boxed{\prod_{i=1}^{999}{\dfrac{2i−1}{2i}} = p(999) \ge \frac{1}{2\times999} = \frac{1}{1998} > \frac{1}{1999}}$$

Prove $\prod_{i=1}^{999}{\left(1-\frac{1}{2i}\right)} < \frac{1}{44}$

For this part, I have applied AM-GM to get an upper bound with a harmonic sum.

$$\left(\prod_{i=1}^{999}{\left(1-\frac{1}{2i}\right)}\right)^{1/999} \le \frac{1}{999} \cdot \sum_{i=1}^{999}{\left(1-\frac{1}{2i}\right)} \tag{3}$$

I can't see a way of evaluating the summation on the RHS.

$\endgroup$
  • 1
    $\begingroup$ Perhaps, this will give you some idea: math.stackexchange.com/questions/1373124/…. You can indeed show that $\frac{1}{64}<\prod_{i=1}^{999}\,\frac{2i-1}{2i}<\frac{1}{44}$, or something even stronger: $\frac{1}{56.5}<\prod_{i=1}^{999}\,\frac{2i-1}{2i}<\frac{1}{56}$. $\endgroup$ – Batominovski Aug 12 '15 at 19:27
  • $\begingroup$ The sum $\sum_{i=1}^{999}(1 - \frac{1}{2i})$ can be expressed as $999 - \frac{1}{2}H_{999}$, where $H_{999}$ is the $999$-th harmonic number. There are good estimates for the $n$-th harmonic number, maybe that can help? $\endgroup$ – 727 Aug 12 '15 at 19:29
  • $\begingroup$ Also, since $\sum_{i=1}^n (1-\frac{1}{2i}) = n - \frac{1}{2}H_n$, it probably wouldn't be a good use of your time to try to find a closed-form evaluation for it (since none exists for $H_n = \sum_{i=1}^n \frac{1}{i}$). You're better off trying to bound it. $\endgroup$ – 727 Aug 12 '15 at 19:35
  • 1
    $\begingroup$ @LJL - I realised there was no closed form. If I had to bound it using this method, I guess an integral might work. $\endgroup$ – Marconius Aug 12 '15 at 19:46
  • 1
    $\begingroup$ @LJL I was not targeting your comment. I was simply saying that this problem is meant to be solved using traditional methods. $\endgroup$ – 1-___- Aug 12 '15 at 19:56
4
$\begingroup$

You have made the problem much hard than it is suppose to be.

For the left hand side, simply observe that $\frac{1}{2}>\frac{1}{3}$ and $\frac{3}{4}>\frac{3}{5}$ and so on... to $\frac{1997}{1998}>\frac{1997}{1999}$. Now, take the product of these inequalities to get the desired result.

For the other inequality, it is a similar trick except you need to observe that $P^2<\frac{1}{1999}<\frac{1}{1936}=\frac{1}{44^2}$.

$\endgroup$
  • $\begingroup$ $\frac{3}{4} \ngtr \frac{4}{5}$. I am not sure how the terms would cancel in the first product in any case. For the second, I can see now that $(\frac{1}{2})^2<\frac{1}{3}, (\frac{3}{4})^2<\frac{3}{5},\ldots$ and this product is telescoping. $\endgroup$ – Marconius Aug 12 '15 at 19:55
  • $\begingroup$ Sorry, typo. Fixed it! $\endgroup$ – 1-___- Aug 12 '15 at 19:56
  • $\begingroup$ @Marconius it's a typo. I'm sure it was meant to be "$\frac{3}{4} > \frac{3}{5}$". $\endgroup$ – 727 Aug 12 '15 at 19:57
  • $\begingroup$ @user2770287 - thanks, your answer is good. The fact that $\frac{1}{2n}<\frac{1}{2n+1}$ is buried in the induction step, which is not good. The $(\frac{1}{2})^2<\frac{1}{3}, (\frac{3}{4})^2<\frac{3}{5},\ldots$ is AM-GM in a thin disguise. I won't be so hasty to move from products to summations in future! $\endgroup$ – Marconius Aug 12 '15 at 20:12
  • $\begingroup$ @Marconius Are you a high school student in Canada studying for the CMO? $\endgroup$ – 1-___- Aug 12 '15 at 20:13
2
$\begingroup$

$${ P }_{ n }^{ 2 }\left( 999 \right) =\frac { { 1 }^{ 2 }\cdot { 3 }^{ 2 }...\cdot { \left( 2\cdot 999-1 \right) }^{ 2 } }{ { 2 }^{ 2 }\cdot { 4 }^{ 2 }...\cdot { \left( 2\cdot 999 \right) }^{ 2 } } =\frac { 1\cdot 3 }{ { 2 }^{ 2 } } \cdot \frac { 3\cdot 5 }{ { 4 }^{ 2 } } \cdot ...\cdot \frac { \left( 2\cdot 999-1 \right) \left( 2\cdot 999+1 \right) }{ { \left( 2\cdot 999 \right) }^{ 2 } } \cdot \frac { 1 }{ 2\cdot 999+1 } <\frac { 1 }{ 2\cdot 999+1 } =\frac { 1 }{ 1999 } <\frac { 1 }{ 1936 } =\frac { 1 }{ { 44 }^{ 2 } } $$

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