0
$\begingroup$

The question as stated on a past exam:

Use mathematical induction to prove that $$ \frac{1}{2}\cdot \frac{3}{4}\cdot \frac{5}{6}\cdot ...\cdot \frac{2n-1}{2n} \leq \frac{1}{\sqrt{3n+1}} $$ for any positive integer n.

I have done plenty of induction proofs before and understand the how and why they work. However I can't seem the find the algebraic trick to this question. I start of by multiplying both sides by $$ \frac{2n+1}{2n+2} $$ with the final goal of proving that $$ \frac{1}{\sqrt{3n+1}} \cdot \frac{2n+1}{2n+2} \le \frac{1}{\sqrt{3n+4}}$$ to complete the proof but I quickly get lost, any help or tips would be very appreciated.

$\endgroup$

marked as duplicate by Martin R, Michael Burr, Jack D'Aurizio inequality May 31 '17 at 20:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ You may prove that the given product is indeed $\leq\frac{1}{\sqrt{\pi n}}$ without using induction. Anyway, this is a duplicate. $\endgroup$ – Jack D'Aurizio May 31 '17 at 20:39
  • 1
    $\begingroup$ $0<n=(2n+2)^2(3n+1)-(2n+1)^2(3n+4)$ ... $\endgroup$ – Donald Splutterwit May 31 '17 at 20:44
  • $\begingroup$ Also: math.stackexchange.com/questions/1507754/…. $\endgroup$ – Martin R May 31 '17 at 20:51
  • $\begingroup$ Yes actually that other question answers mine perfectly, should I delete this then or leave it? $\endgroup$ – Jackson Godfrey May 31 '17 at 20:53
2
$\begingroup$

To prove this using induction, we have the base case and the inductive case.

BASE STEP: Consider the case where $n=1$, then the product on the left is $\frac{1}{2}$ and the right is $\frac{1}{\sqrt{4}}=\frac{1}{2}$, so the inequality holds when $n=1$.

INDUCTIVE STEP: Assume that the inequality holds when $n=k$. In other words: $$ \prod_{i=1}^k\frac{2i-1}{2i}\leq\frac{1}{\sqrt{3k+1}}. $$ Our goal is to prove the corresponding inequality for the case $n=k+1$. So, we consider $$ \prod_{i=1}^{k+1}\frac{2i-1}{2i}=\left(\prod_{i=1}^{k}\frac{2i-1}{2i}\right)\frac{2k+1}{2k+2}. $$ Since the first factor is the inductive case when $n=k$, we can use the inductive hypothesis to show that $$ \prod_{i=1}^{k+1}\frac{2i-1}{2i}\leq\frac{1}{\sqrt{3k+1}}\cdot\frac{2k+1}{2k+2}. $$ As the OP mentions, if we could prove that $$ \frac{1}{\sqrt{3k+1}}\cdot\frac{2k+1}{2k+2}\leq\frac{1}{\sqrt{3k+4}}, $$ then we would be done. Unfortunately, unlike the equality inductions, the formula that you're looking for doesn't just pop out. Instead, you have to do some scratch work to figure it out.

SCRATCH WORK (Scratch work is not part of the proof, you do scratch work to figure out how the proof should go. In scratch work, you can do any operations you want, but you'll need to prove that they're OK later.)

Clearing the fractions, we get $$ (2k+1)\sqrt{3k+4}\leq(2k+2)\sqrt{3k+1} $$ Squaring both sides, $$ (2k+1)^2(3k+4)\leq(2k+2)^2(3k+1) $$ Multiplying this out, we get $$ 12k^3+28k^2+19k+4\leq12k^3+28k^2+20k+4. $$ Simplifying everything, we get $0\leq k$, which we know is true.

BACK TO PROOF In order to prove the desired inequality, we have to start with something we know is true and derive the inequality. We start with $0\leq k$, which we know is true. Then, we add $12k^3+28k^2+19k+4$ to both sides and the resulting inequality is $$ 12k^3+28k^2+19k+4\leq12k^3+28k^2+20k+4. $$ We can now factor both sides to get $$ (2k+1)^2(3k+4)\leq(2k+2)^2(3k+1). $$ Since all the terms are positive and the square root is an increasing function, we can take the square root and preserve the inequality to get $$ (2k+1)\sqrt{3k+4}\leq(2k+2)\sqrt{3k+1} $$ Finally, by dividing both sides by the positive quantities $(2k+2)$, $\sqrt{3k+4}$, and $\sqrt{3k+1}$, we get the desired inequality.

MORAL OF THE STORY When dealing with an inequality, do some scratch work to get to something you know is true, then do the work backwards in the proof itself, being careful to justify each step.

$\endgroup$
1
$\begingroup$

Multiply by the square root in the denominator on the left side and then square the whole thing:

$$\frac{2n+1}{2n+2}\le\frac{\sqrt{3n+1}}{\sqrt{3n+4}}\iff\frac{4n^2+4n+1}{4n^2+8n+4}\le\frac{3n+1}{3n+4}\iff$$

$$12n^3+28n^2+19n+4\le12n^3+28n^2+20n+4\iff19n\le20n$$

and since the last inequality is trivial you're done.

$\endgroup$

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