0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – stewbasic Jul 7 '16 at 4:40
  • $\begingroup$ @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. $\endgroup$ – Eduardo M. Jul 7 '16 at 4:44
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jul 7 '16 at 4:46
  • $\begingroup$ 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}}$. $\endgroup$ – stewbasic Jul 7 '16 at 4:51
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.