# Help with mathematical induction problem

#### Walshy

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.

#### emakarov

MHF Hall of Honor
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.