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

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.

• 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}$. – Batominovski Aug 12 '15 at 19:27
• 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? – 727 Aug 12 '15 at 19:29
• 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. – 727 Aug 12 '15 at 19:35
• @LJL - I realised there was no closed form. If I had to bound it using this method, I guess an integral might work. – Marconius Aug 12 '15 at 19:46
• @LJL I was not targeting your comment. I was simply saying that this problem is meant to be solved using traditional methods. – 1-___- Aug 12 '15 at 19:56

## 2 Answers

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

• $\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. – Marconius Aug 12 '15 at 19:55
• Sorry, typo. Fixed it! – 1-___- Aug 12 '15 at 19:56
• @Marconius it's a typo. I'm sure it was meant to be "$\frac{3}{4} > \frac{3}{5}$". – 727 Aug 12 '15 at 19:57
• @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! – Marconius Aug 12 '15 at 20:12
• @Marconius Are you a high school student in Canada studying for the CMO? – 1-___- Aug 12 '15 at 20:13

$${ 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 } }$$