Results 1 to 2 of 2

Math Help - Help with mathematical induction problem

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    Ohio
    Posts
    14

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    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

    \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 < \frac{1}{\sqrt{3(n+1)}}. However,

    \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

    \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 \frac{1}{\sqrt{3n+1}}<\frac{1}{\sqrt{3n}}, or consider n = 2 in the base step.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] mathematical induction problem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 7th 2011, 05:04 AM
  2. Mathematical Induction Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2011, 01:36 PM
  3. Mathematical Induction problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 6th 2011, 11:52 AM
  4. mathematical induction problem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: February 24th 2009, 06:06 PM
  5. mathematical induction problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: January 12th 2008, 07:22 PM

Search Tags


/mathhelpforum @mathhelpforum