# Prove $\frac{1}{2}\cdot\frac{3}{4}\cdot...\cdot\frac{2n-1}{2n}<\frac{1}{\sqrt{3n}}$ for all $n$.

Prove for all $$n$$: $$\frac{1}{2}\cdot\frac{3}{4}\cdot...\cdot\frac{2n-1}{2n}<\frac{1}{\sqrt{3n}}$$.

Using induction, I tried the brain-dead method and went straight for $$\frac{2n+1}{2n+2}\cdot\frac{1}{\sqrt{3n}}<\frac{1}{\sqrt{3n+3}}$$ $$...$$ $$1<0.$$ After embarrassing myself, I looked around and I found this thread. Using induction, we can then easily prove $$\frac{1}{2}\cdot\frac{3}{4}\cdot...\cdot\frac{2n-1}{2n}\leq\frac{1}{\sqrt{3n+1}}$$ $$\frac{1}{2}\cdot\frac{3}{4}\cdot...\cdot\frac{2n-1}{2n}\leq\frac{1}{\sqrt{3n+1}}<\frac{1}{\sqrt{3n}}.$$ This gets me to the original problem. But in a problem solving standpoint, how do you think to use $$\frac{1}{\sqrt{3n+1}}$$? Is there some point in the first induction that leads to this idea? Or is there a better method than the above?

• You might find this thread interesting. In fact, this exact question shows up as an answer, but no explanation is given. Commented Dec 18, 2020 at 6:53

Write $$a_n$$ for the $$n$$th term in your sequence. Look at the square of $$a_n$$, and rotate the numerators left by one position. Starting at $$n=2$$ you observe $$a_2^2=\frac12\frac12\frac34\frac34=\frac12\left(\frac32\frac34\right)\frac14\\ a_3^2=\frac12\frac12\frac34\frac34\frac56\frac56=\frac12\left(\frac32\frac34\right)\left(\frac54\frac56\right)\frac16\\ a_4^2=\frac12\frac12\frac34\frac34\frac56\frac56\frac78\frac78=\frac12\left(\frac32\frac34\right)\left(\frac54\frac56\right)\left(\frac76\frac78\right)\frac18$$ and so on. The inequality $$1+x\le e^x$$ then gives $$a_2^2\le \frac18 \exp\left(\frac18\right)\\ a_3^2\le\frac1{12}\exp\left(\frac18+\frac1{24}\right)\\ a_4^2\le\frac1{16}\exp\left(\frac18+\frac1{24}+\frac1{48}\right)$$ and in general for $$n\ge 2$$ $$a_n^2\le \frac1{4n}\exp\left[\frac14\left(\frac12+\frac16+\frac1{12}+\cdots+\frac1{n(n-1)}\right)\right].$$ The series $$\frac12+\frac16+\frac1{12}+\cdots+\frac1{n(n-1)}$$ telescopes to $$1$$, yielding $$a_n^2\le \frac{e^{1/4}}{4n}$$ which also holds for $$n=1$$. Since $$e^{1/4}\approx 1.284 < 4/3$$, this proves $$a_n^2< \frac1{3n}$$.

Notice that $$\frac{1}{\sqrt{an+b}} \cdot \frac{2n+1}{2n+2} \le \frac{1}{\sqrt{a(n+1)+b}} \\ \iff (a(n+1)+b)(2n+1)^2 \le (2n+2)^2 (an+b) \\ \iff an+a-4bn-3b \le 0$$

Hence if $$a=3$$, then $$b=1$$ would work. Of course, you need to prove the initial case ($$n$$=1).

BTW: how amazing it is that the first two answers got $$e$$ and $$\pi$$, respectively.

• (+1) So as long as $\min(4b-a,3b-a)\ge0$, the induction proceeds. I like this approach (I have used a similar technique a few times). I have added a more elementary approach, based on bounds for $\frac1{4^n}\binom{2n}{n}$ from an earlier answer.
– robjohn
Commented Dec 20, 2020 at 2:49

A First Approach \begin{align} n\prod_{k=1}^n\left(\frac{2k-1}{2k}\right)^2 &=\frac14\prod_{k=2}^n\left(\frac{2k-1}{2k}\right)^2\frac{k}{k-1}\tag{1a}\\ &=\frac14\prod_{k=2}^n\frac{2k-1}{2k}\frac{2k-1}{2k-2}\tag{1b}\\ &=\frac14\prod_{k=2}^n\frac{\color{#C00}{k-1/2}}{\color{#090}{k}}\frac{\color{#75F}{k-1/2}}{\color{#C90}{k-1}}\tag{1c}\\ &=\frac14\color{#C00}{\frac{\Gamma(n+1/2)}{\Gamma(3/2)}}\color{#090}{\frac{\Gamma(2)}{\Gamma(n+1)}}\color{#75F}{\frac{\Gamma(n+1/2)}{\Gamma(3/2)}}\color{#C90}{\frac{\Gamma(1)}{\Gamma(n)}}\tag{1d}\\[3pt] &=\frac1\pi\frac{\Gamma(n+1/2)^2}{\Gamma(n+1)\,\Gamma(n)}\tag{1e}\\[3pt] &\le\frac1\pi\tag{1f} \end{align} Explanation:
$$\text{(1a)}$$: pull the $$k=1$$ term out front and bring $$n$$ inside as a telescoping product
$$\text{(1b)}$$: rearrange terms
$$\text{(1c)}$$: divide numerator and denominator by $$2$$
$$\text{(1d)}$$: write the products as ratios of the Gamma function, using $$\Gamma(x+1)=x\,\Gamma(x)$$
$$\text{(1e)}$$: collect terms using $$\Gamma(1)=\Gamma(2)=1$$ and $$\Gamma(3/2)=\sqrt\pi/2$$
$$\text{(1f)}$$: $$\Gamma(x)$$ is log-convex

Thus, we get the stronger $$\prod_{k=1}^n\frac{2k-1}{2k}\le\frac1{\sqrt{\pi n}}\tag2$$

A Slightly Simpler Approach with a Better Bound \begin{align} \prod_{k=1}^n\frac{2k-1}{2k} &=\prod_{k=1}^n\frac{(2k-1)2k}{4k^2}\tag{3a}\\ &=\frac1{4^n}\binom{2n}{n}\tag{3b}\\ &\le\frac1{\sqrt{\pi\!\left(n+\frac14\right)}}\tag{3c} \end{align} Explanation:
$$\text{(3a)}$$: multiply numerator and denominator by $$2k$$
$$\text{(3b)}$$: $$\prod\limits_{k=1}^n(2k-1)2k=(2n)!$$ and $$\prod\limits_{k=1}^n2k=2^nn!$$
$$\text{(3c)}$$: inequality $$(9)$$ from this answer

In fact, using inequality $$(10)$$ from this answer, we get $$\frac1{\sqrt{\pi\!\left(n+\frac13\right)}}\le\prod_{k=1}^n\frac{2k-1}{2k}\le\frac1{\sqrt{\pi\!\left(n+\frac14\right)}}\tag4$$

• (+1) Cool! Like both approaches. Commented Dec 20, 2020 at 2:56