# Mathematical Induction

• June 24th 2006, 03:02 PM
Nichelle14
Mathematical Induction
I need a little help on this problem:

1/2 x 3/4 x ... x (2n-1)/2n <= 1/(sqrt(3n+1)

I know that I have to show that for n= 1 works first and it does. Then I know that I need to show for n+1.

This is what I did, I first added n+1 to both sides

this is what I got: 1/2 x 3/4 x ... x (2n-1)/2n x [2(n+1) - 1]/2(n+1)<=
1/(sqrt(3(n+1)+1))

now i know that the first part of what I did on the LHS is <= to the RHS, so I substituted: and got this:

1/(sqrt(3n+1) x (2n+1)/(2n+2) <= 1(sqrt(3n+4))

Am I on the right track here?
• June 24th 2006, 11:32 PM
CaptainBlack
Quote:

Originally Posted by Nichelle14
I need a little help on this problem:

1/2 x 3/4 x ... x (2n-1)/2n <= 1/(sqrt(3n+1)

I know that I have to show that for n= 1 works first and it does. Then I know that I need to show for n+1.

This is what I did, I first added n+1 to both sides

this is what I got: 1/2 x 3/4 x ... x (2n-1)/2n x [2(n+1) - 1]/2(n+1)<=
1/(sqrt(3(n+1)+1))

now i know that the first part of what I did on the LHS is <= to the RHS, so I substituted: and got this:

1/(sqrt(3n+1) x (2n+1)/(2n+2) <= 1(sqrt(3n+4))

Am I on the right track here?

You have done the base case so I won't worry about that, so let's assume
this is true for some $k \ge 1$, that is for this $k$:

$
\frac{1}{2}\times \frac{3}{4}\times \dots \times \frac{2k-1}{2k}$
$\le \frac{1}{\sqrt{3k+1}}\ \ \ \dots(1)
$
.

Now multiply both sides by $(2k+1)/(2k+2)$, which would be the next term
of the product on the Left Hand Side (LHS) to give:

$
\frac{1}{2}\times \frac{3}{4}\times \dots \times \frac{2k-1}{2k} \times \frac{2k+1}{2k+2}$
$\le \frac{1}{\sqrt{3k+1}}\times \frac{2k+1}{2k+2}\ \ \ \dots(2)
$
.

Now if we can prove that the RHS of $(2)$ is less than or equal $\frac{1}{\sqrt{3k+2}}$
this will be sufficient to prove:

$
\frac{1}{2}\times \frac{3}{4}\times \dots \times \frac{2k+1}{2k+2}$
$\le \frac{1}{\sqrt{3k+4}}\ \ \ \dots(3)
$
,

which is what we need for the induction step.

So we now seek to proove:

$
\frac{1}{\sqrt{3k+1}}\times \frac{2k+1}{2k+2} \le \frac{1}{\sqrt{3k+2}}\ \ \ \dots(4)
$

Now $(4)$ is true iff (if and only if):

$
\frac{2k+1}{2k+2} \le \left( \frac{3k+1}{3k+2} \right)^2
$
,

which itself is true iff:

$
\left( \frac{2k+1}{2k+2} \right)^2 \le \frac{3k+1}{3k+2}
$
.

Which is true iff:

$(2k+1)^2(3k+2) \le (2k+2)^2(3k+1)$

multiplying both sides of the above out give this is true iff:

$
12k^3+20k^2+11k+2 \le 12k^2+28k^2+20k+4
$

which is true as the coefficients of the powers of $k$ on the LHS
are all $\le$ the corresponding coefficients on the RHS, and so
the induction step is proven.

RonL