# Using induction on modified inequalities.

Here's the original problem:

Prove by induction that $\left(\frac{1}{2}\right) \left(\frac{3}{4}\right) \cdots \left(\frac{2n-1}{2n} \right) \leq \frac{1}{\sqrt{n+1}}$ for all $n \in \mathbb{N}$.

After some time trying and getting nowhere, I thought that maybe I could start with a simpler form and try to get somehow to the result I wanted. So I did this:

First, we can see that $\frac{1}{\sqrt{n+1}}<n$ for all $n \in \mathbb{N}$, so $$\left(\frac{1}{2}\right) \cdots \left(\frac{2n-1}{2n} \right) \leq \frac{1}{\sqrt{n+1}} < n \implies \left(\frac{1}{2}\right) \cdots \left(\frac{2n-1}{2n} \right) \leq n.$$ If we are able to prove the second inequality, then the original one must also be true. So, let $P(n): \left(\frac{1}{2}\right) \cdots \left(\frac{2n-1}{2n} \right) \leq n.$ We can check that $P(1)$ is true, since $\frac{1}{2} \leq 1$. So, suppose that $P(n)$ holds, such that $$P(n+1): \left(\frac{1}{2}\right) \cdots \left(\frac{2n-1}{2n} \right) \left(\frac{2n+1}{2n+2}\right) \leq n+1.$$

Now,

\begin{align} \left(\frac{1}{2}\right) \cdots \left(\frac{2n-1}{2n} \right) \left(\frac{2n+1}{2n+2}\right) &\leq n\left(\frac{2n+1}{2n+2}\right) && \text{(by induction hypotheses)}\\ &<n\left(\frac{2n+1}{2n+2}\right)\left(\frac{2n+2}{2n+1}\right) && (\text{because } (2n+1)/(2n+2) < (2n+2/2n+1))\\ &<n<n+1. \end{align}

It follows that $P(n+1)$ holds if $P(n)$ holds, so, by mathematical induction, $P(n)$ is true. So, as a consequence, $\left(\frac{1}{2}\right) \left(\frac{3}{4} \right) \cdots \left(\frac{2n-1}{2n} \right) \leq \frac{1}{\sqrt{n+1}}$ is also true.

My questions are:

Is my logic correct? Am I able to take a simpler case, as I did, to prove the expression that falls in between? I'm almost sure that what I did was correct, but I don't know how to justify it. Also, if this is correct, why is it so and is this also true in general for different situations?

• You've switched the direction of implication. (LHS $\leq$ RHS) implies (LHS $\leq n$), but (LHS $\leq n$) does not imply (LHS $\leq$ RHS). So proving (LHS $\leq n$) is not sufficient. – stewbasic Jul 7 '16 at 4:40
• @stewbasic I though that what I did was: if $a < b$ and we show that $b < c$, then $a < c$. Is this not what I did? I can't find the error. – Eduardo M. Jul 7 '16 at 4:44
• @stewbasic: It’s what you did; the problem is that it’s not what you needed to do in order to prove the desired result. – Brian M. Scott Jul 7 '16 at 4:46
• That reasoning is correct, but it doesn't quite match up with what you've done. What are you taking as $a,b,c$? You have $\frac1{\sqrt{n+1}}<n$ and you proved LHS $<n$, and you need $LHS<\frac1{\sqrt{n+1}}$. – stewbasic Jul 7 '16 at 4:51

HINT: The induction step can be done without any special tricks. You’re assuming that

$$\left(\frac{1}{2}\right) \left(\frac{3}{4}\right)\ldots \left(\frac{2n-1}{2n} \right) \leq \frac{1}{\sqrt{n+1}}\;,$$

and you want to show that

$$\left(\frac{1}{2}\right) \left(\frac{3}{4}\right)\ldots \left(\frac{2n-1}{2n} \right)\left(\frac{2n+1}{2n+2}\right) \leq \frac{1}{\sqrt{n+2}}\;.\tag{1}$$

This will follow immediately if you can show that

$$\frac1{\sqrt{n+1}}\cdot\frac{2n+1}{2n+2}\le\frac1{\sqrt{n+2}}\;.\tag{2}$$

(Why?) Since everything in sight is positive, the inequality $(2)$ is equivalent to

$$(2n+1)\sqrt{n+2}\le(2n+2)\sqrt{n+1}\;,$$

which holds if and only if

$$(2n+1)^2(n+2)\le(2n+2)^2(n+1)\;.$$

This is easily checked.

• Thank you, I took me a while, but I see how I was incorrect. – Eduardo M. Jul 7 '16 at 16:17
• @Eduardo: You're welcome. – Brian M. Scott Jul 7 '16 at 18:44