4

We want to prove by induction that $$\frac1{2}\cdot\frac3{4}\cdot\frac5{6}\cdots\frac{2n-1}{2n}\le \frac{1}{\sqrt{3n+1}}$$ for all $n,k \in \mathbb{Z^+}$

For k=1 : $\frac1{2}\le\frac{1}{2}$ which it is true.

Assume the induction hypothesis $\frac1{2}\cdot\frac3{4}\cdot\frac5{6}\cdots\frac{2k-1}{2k}\le \frac{1}{\sqrt{3k+1}}$

We need to prove $\frac1{2}\cdot\frac3{4}\cdot\frac5{6}\cdots\frac{2(k+1)-1}{2(k+1)}\le \frac{1}{\sqrt{3(k+1)+1}}$

We can take the induction hypothesis and multiply by $\frac{2(k+1)-1}{2(k+1)}$ on both sides.

Then, we need to prove that $\frac{1}{\sqrt{3k+1}}\cdot\frac{2(k+1)-1}{2(k+1)}\le \frac{1}{\sqrt{3(k+1)+1}}$

$\frac{(2k+1)^2}{4(3k+1)(k+1)^2}\le \frac{1}{(3k+4)} \Leftrightarrow$

$(3k+4)(2k+1)^2\le 4(3k+1)(k+1)^2 \Leftrightarrow$

$12k^3+28k^2+19k+4\le 12k^3+16k^2+20k+4 \Leftrightarrow$

$12k^2-k\le 0$ which is not true!

Where is the mistake??

Martin Sleziak
  • 53,687
Oualid
  • 319
  • https://www.wolframalpha.com/input/?i=expand+4(3x%2B1)(x%2B1)%5E2 – CY Aries May 01 '17 at 16:40
  • I will prove a stronger inequality with elementary tools. By integration by parts we have $$ \prod_{k=1}^{n}\frac{2k-1}{2k} = \frac{(2n-1)!!}{(2n)!!} = \frac{2}{\pi}\int_{0}^{\pi/2}\cos(x)^{2n},dx \tag{1} $$ and since over the interval $\left(0,\frac{\pi}{2}\right)$ we have $\tan(x)>x$, we also have $-\log\cos x\geq \frac{x^2}{2}$ (by integrating both sides), from which $\cos(x)\leq e^{-x^2/2}$ and $$ \prod_{k=1}^{n}\frac{2k-1}{2k} \leq \frac{2}{\pi}\int_{0}^{\pi/2}e^{-nx^2},dx\leq \frac{2}{\pi}\int_{0}^{+\infty}e^{-nx^2},dx = \frac{1}{\sqrt{\pi n}}\tag{2} $$ – Jack D'Aurizio May 01 '17 at 18:11
  • that is $<\frac{1}{\sqrt{3n+1}}$ for any $n\geq 8$. The remaining cases, $n\in{1,2,\ldots,7}$, are simple to check by hand. – Jack D'Aurizio May 01 '17 at 18:11

3 Answers3

2

for the right-hand side i have got $$12k^3+28k^2+20k+4$$ and the left-Hand side is given by $$12\,{k}^{3}+28\,{k}^{2}+19\,k+4$$

Dr. Sonnhard Graubner
  • 95,283
2

$$\begin{align}4(3n+1)(n+1)^2&= 4(3n+1)(n^2+2n+1) \\ &= 4 (3n^3+6n^2+3n+n^2 + 2n+1)\\ &= 12n^3 + \mathbf{28n^2} + 20n + 4\\ &\ne 12n^3 + 16n^2 + 20n + 4\end{align}$$ For the record, I just plugged the larger algebraic steps into a calculator with arbitrary numbers and saw there was arbitrary mismatch at that line.

I trust you can carry on from here.

Thomas Andrews
  • 177,126
infinitylord
  • 4,777
1

Just for fun, here's an alternate method $$2\cdot 4\cdot ...\cdot 2n=n!2^n$$

$$1\cdot 3\cdot ...\cdot (2n-1) =\frac{(2n)!}{2^nn!}$$

Then $$\frac1{2}\cdot\frac3{4}\cdot\frac5{6}\cdot...\cdot\frac{2n-1}{2n} = \frac{(2n)!}{2^nn!}\cdot\frac{1}{n!2^n}=\frac{(2n)!}{(2^nn!)^2}$$

Now the problem is equivalent to proving $$\frac{(2n)!}{(2^nn!)^2} \leq \frac{1}{\sqrt{3n+1}},\quad n\in\mathbb{Z^+}$$

$n=1: LHS = \frac{2}{2^2}=\frac{1}{2}$

$RHS = \frac{1}{2}=LHS\quad $ so it holds for $n=1$. Then assume true for $n$; now we must prove true for $n+1$.

$$\frac{(2n+2)!}{(2^{n+1}(n+1)!)^2} =\frac{(2n+2)(2n+1)(2n)!}{(2(n+1)\cdot 2^nn!)^2} =\frac{(2n+2)(2n+1)(2n)!}{4(n+1)^2(2^nn!)^2} =\frac{(2n+1)(2n)!}{2(n+1)(2^nn!)^2}$$

Then we have $$\frac{(2n)!}{(2^nn!)^2} \leq \frac{1}{\sqrt{3n+1}} \implies \frac{(2n+1)(2n)!}{2(n+1)(2^nn!)^2} \leq \frac{(2n+1)}{2(n+1)\sqrt{3n+1}}$$

Consider $$\frac{1}{\sqrt{3n+4}}-\frac{(2n+1)}{2(n+1)\sqrt{3n+1}} = \frac{2(n+1)\sqrt{3n+1}-(2n+1)\sqrt{3n+4}}{2(n+1)\sqrt{3n+1}\sqrt{3n+4}}$$

If we can show $2(n+1)\sqrt{3n+1}-(2n+1)\sqrt{3n+4}\geq 0$, then we are done.

$$2(n+1)\sqrt{3n+1}\geq (2n+1)\sqrt{3n+4} \iff 4(n+1)^2(3n+1)\geq (2n+1)^2(3n+4)$$ which expands into $n\geq 0$ (which we are given from the question since $n\in\mathbb{Z^+}$.

Therefore we have $$\frac{1}{\sqrt{3n+4}}-\frac{(2n+1)}{2(n+1)\sqrt{3n+1}}\geq 0\implies \frac{1}{\sqrt{3n+4}}\geq \frac{(2n+2)!}{(2^{n+1}(n+1)!)^2}$$ as required.

mrnovice
  • 5,773
  • Why turn all the double factorials into plain ol' factorials? I would keep them as double factorials, which should make it more elementary – Brevan Ellefsen May 01 '17 at 17:34
  • @BrevanEllefsen I'm not familiar with using double factorials, also I was using this a bit of an exercise for myself just to see if I was able to do it. – mrnovice May 01 '17 at 17:37