Can You Prove This Fraction Sequence is Less Than 1/1000?

[anemone]

Show that $\dfrac{1}{2}\cdot\dfrac{3}{4}\cdot\dfrac{5}{6} \cdots\dfrac{999999}{1000000}<\dfrac{1}{1000}$

 

[Petek]

Spoiler

We claim that

$$\frac{1 \cdot 3 \cdot 5 \cdots (2n-1)}{2 \cdot 4 \cdot 6\cdots (2n)} \leq \frac{1}{\sqrt{3n+1}}$$

for all positive integers n. The result then follows by setting n = 500000 and observing that

$$\frac{1}{\sqrt{1500001}} < \frac{1}{1000}$$

The claim is proved by induction on n.
For n = 1, the claim is obvious.
Assume the claim is true for n. We have to show that

$$\frac{1 \cdot 3 \cdot 5 \cdots (2n-1)(2n+1)}{2 \cdot 4 \cdot 6\cdots (2n)(2n+2)} \leq \frac{1}{\sqrt{3n+4}}$$

But

$$\frac{1 \cdot 3 \cdot 5 \cdots (2n-1)(2n+1)}{2 \cdot 4 \cdot 6\cdots(2n)(2n+2)}=\frac{1 \cdot 3 \cdot 5 \cdots (2n-1)}{2 \cdot 4 \cdot 6\cdots (2n)} \frac{2n+1}{2n+2}\leq\frac{1}{\sqrt{3n+1}}\frac{2n+1}{2n+2}$$

So we have to show that

$$\frac{1}{\sqrt{3n+1}}\frac{2n+1}{2n+2}\leq \frac{1}{\sqrt{3n+4}}$$

This inequality follows by clearing fractions, squaring both sides and simplifying. The result is

$$19n \leq 20n$$

which holds for all positive n. This completes the proof of the claim.

 

[chisigma]

Spoiler

As reported in...

http://mathhelpboards.com/questions-other-sites-52/unsolved-analysis-number-theory-other-sites-7479-4.html#post40097

... the the explicit expression of the sequence is...

$\displaystyle a_{n} = \prod_{k=1}^{n} (1 - \frac{1}{2\ k})\ (1)$

... and it is the solution of the difference equation...$\displaystyle a_{n+1} = a_{n}\ (1 - \frac{1}{2\ n}),\ a_{1}=1\ (2)$

The (2) is related to the ODE...

$\displaystyle y^{\ '} = - \frac{y}{2\ x}\ (3)$

... the solution of which is $\displaystyle y = \frac{c}{\sqrt{x}}$, so that we can suppose $\displaystyle a_{n} \sim r_{n}= \frac{c}{\sqrt{n}}$. If we suppose that $r_{500000}= \frac{1}{1000}$ then is $\displaystyle c = \frac{1}{\sqrt{2}}$. In the following table the first values os $a_{n}$ and $r_{n}$ are reported... $a_{1}= 1,\ r_{1} = .70710678...$

$a_{2}= .5,\ r_{2} = .5$

$a_{3}= .375,\ r_{3} = .40824829...$

$a_{4}= .3125,\ r_{4} = .35355339...$

$a_{5}= .273438...,\ r_{5} = .31627766...$

$a_{6}= .246094...,\ r_{6} = .2886751...$

$a_{7}= .225586...,\ r_{7} = .2672612...$

$a_{8}= .209473...,\ r_{8} = .25$

$a_{9}= .196381...,\ r_{9} = .2357022...$

$a_{10}= .185471...,\ r_{10} = .2236067...$

It is clear from the table that for n 'large enough' the relative increments of the $a_{n}$ and $r_{n}$ are pratically the same and that is verified considering that is... $\displaystyle \frac{a_{n+1}}{a_{n}} = 1 - \frac{1}{2\ n}$ $\displaystyle \frac{r_{n+1}}{r_{n}} = \sqrt{1 - \frac{1}{n}} = 1 - \frac{1}{2\ n} - \frac{1}{8\ n^{2}} - ...\ (4)$... so that we can conclude that is $\displaystyle a_{500000} < r_{500000} = \frac{1}{1000}$...

Kind regards

$\chi$ $\sigma$

 

[anemone]

Thanks for participating to both of you, Petek and chisigma! Your induction method looks nice and great, Petek!

@chisigma, your solution post reminds me of this thread(http://mathhelpboards.com/discrete-mathematics-set-theory-logic-15/find-a_%7B100000%7D-8448.html)! Bravo, chisigma!:)

Solution provided by other:

Spoiler

Let $x=\dfrac{1}{2}\cdot\dfrac{3}{4}\cdot\dfrac{5}{6} \cdots\dfrac{999999}{1000000}$.

Thus, what we need to show is that $x<\dfrac{1}{1000}$.

Now, note that

$x^2=\dfrac{1^2}{2^2}\cdot\dfrac{3^2}{4^2}\cdot \dfrac{5^2}{6^2} \cdots\dfrac{999999^2}{1000000^2}$

Since decreasing the denominator of a fraction makes it bigger, we have that

$\dfrac{1^2}{2^2}\le \dfrac{1^2}{2^2-1}= \dfrac{1^2}{(2-1)(2+1)}=\dfrac{1^2}{1\cdot3}$

$\dfrac{3^2}{4^2}\le \dfrac{3^2}{4^2-1}= \dfrac{3^2}{(4-1)(4+1)}=\dfrac{3^2}{3\cdot5}$

$\dfrac{5^2}{6^2}\le \dfrac{5^2}{6^2-1}= \dfrac{5^2}{(6-1)(6+1)}=\dfrac{5^2}{5\cdot7}$

$\vdots\;\;\;\;\;\;\;\;\;\;\;\vdots$

$\dfrac{999999^2}{1000000^2}\le \dfrac{999999^2}{1000000^2-1}= \dfrac{999999^2}{(1000000-1)(1000000+1)}=\dfrac{999999^2}{999999\cdot1000001}$

Multiplying all these together we get

$x^2<\dfrac{1}{1000001}<\dfrac{1}{1000000}$

Now, taking square roof of both sides we obtain

$x<\dfrac{1}{1000}$ or

$\dfrac{1}{2}\cdot\dfrac{3}{4}\cdot\dfrac{5}{6} \cdots\dfrac{999999}{1000000}<\dfrac{1}{1000}$ (Q.E.D.)

 

[CellCoree]

There are a few ways to approach this problem. One way is to recognize that each fraction in the product is less than 1, and as the denominators increase, the fractions get closer and closer to 1. Therefore, the product must be less than 1.

Another approach is to use mathematical induction. Let's consider the first few terms of the product:
$\dfrac{1}{2}\cdot\dfrac{3}{4}\cdot\dfrac{5}{6}=\dfrac{5}{16}$
$\dfrac{1}{2}\cdot\dfrac{3}{4}\cdot\dfrac{5}{6}\cdot\dfrac{7}{8}=\dfrac{35}{128}$
$\dfrac{1}{2}\cdot\dfrac{3}{4}\cdot\dfrac{5}{6}\cdot\dfrac{7}{8}\cdot\dfrac{9}{10}=\dfrac{315}{1024}$

We can see that each subsequent term in the product is decreasing, and the numerator is increasing. We can then use mathematical induction to prove that this pattern continues for all terms up to $\dfrac{999999}{1000000}$.

Base case: For $n=1$, we have $\dfrac{1}{2}<\dfrac{1}{1000}$, which is true.

Inductive step: Assume that for some $n=k$, $\dfrac{1}{2}\cdot\dfrac{3}{4}\cdot\dfrac{5}{6} \cdots\dfrac{2k-1}{2k}<\dfrac{1}{1000}$

For $n=k+1$, we have $\dfrac{1}{2}\cdot\dfrac{3}{4}\cdot\dfrac{5}{6} \cdots\dfrac{2k-1}{2k}\cdot\dfrac{2k+1}{2k+2}<\dfrac{1}{1000}\cdot\dfrac{2k+1}{2k+2}$

Since $\dfrac{2k+1}{2k+2}<1$, we can multiply both sides by $\dfrac{1}{1000}$ without changing the direction of the inequality.

Therefore, $\dfrac{1}{2}\cdot\dfrac{3}{4}\cdot\dfrac{5}{6} \cdots\d