# Help with mathematical induction problem

• Oct 29th 2012, 06:18 PM
Walshy
Help with mathematical induction problem
Suppose we want to prove that: 1/2 * 3/4 ... 2n-1/2n < 1/sqrt(3n)

for all positive integers.
(a) Show that if we try to prove this inequality using mathematical induction, the basis step works, but
the inductive step fails.

(b) Show that mathematical induction can be used to prove the stronger inequality: 1/2 * 3/4 ... 2n-1/2n < 1/sqrt(3n+1)

So far I have proven the basis step works in part a by plugging in 1, however, I do not know how to say the inductive step fails. I have no clue on part b. Thanks.
• Oct 30th 2012, 01:12 PM
emakarov
Re: Help with mathematical induction problem
Let P(n) be 1/2 * 3/4 ... (2n-1)/2n < 1/sqrt(3n) (note that parentheses around 2n-1 are mandatory). You verified that P(1) is true. The induction step consists of proving that P(k) implies P(k + 1) for all k >= 1. Strictly speaking, this is a true statement just because the conclusion P(k + 1) is true. After all, the overall problem is to prove P(n) for all n. What fails is a particular, most natural way of proving the step. Indeed, the natural way is to say

$\displaystyle \frac{1}{2} \cdot \frac{3}{4} \cdot \dots\cdot\frac{2n-1}{2n}\cdot \frac{2n+1}{2n+2} < \frac{1}{\sqrt{3n}}\cdot \frac{2n+1}{2n+2}$

by the induction hypothesis and then to try proving that the right-hand side is < $\displaystyle \frac{1}{\sqrt{3(n+1)}}$. However,

$\displaystyle \frac{1}{\sqrt{3n}}\cdot\frac{2n+1}{2n+2} < \frac{1}{\sqrt{3(n+1)}}$

has no solutions.

When we strengthen the induction hypothesis, the method above works. Note that the new strict inequality fails for n = 1, so you should either prove a non-strict inequality

$\displaystyle \frac{1}{2}\cdot\frac{3}{4}\cdot\dots\cdot\frac{2n-1}{2n}\le\frac{1}{\sqrt{3n+1}}$

for all positive integers n and then say that $\displaystyle \frac{1}{\sqrt{3n+1}}<\frac{1}{\sqrt{3n}}$, or consider n = 2 in the base step.