Results 1 to 5 of 5

Math Help - Proof By Induction

  1. #1
    Junior Member
    Joined
    Aug 2007
    Posts
    32

    Proof By Induction

    (1-1/2)(1-1/3)(1-1/4). . . (1-1/n)=1/n

    How do i start this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by Edbaseball17 View Post
    (1-1/2)(1-1/3)(1-1/4). . . (1-1/n)=1/n

    How do i start this?
    The k-1th term is
    1 - \frac{1}{k} = \frac{k -1}{k}

    So this may be represented in "Pi" notation as:
    \prod_{k = 2}^n \frac{k - 1}{k}
    (I shifted the variable a bit to make the form simpler to look at.)

    Can you finish from here?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2007
    Posts
    32
    so far i have this

    <br />
1 - \frac{1}{2} *1 - \frac{1}{3} *1 - \frac{1}{4}...1 - \frac{1}{k} = \frac{1}{k}<br />

    <br />
1 - \frac{1}{2}*1 - \frac{1}{3}*1 - \frac{1}{4}...1 - \frac{1}{k}*1 - \frac{1}{k+1}= \frac{1}{k}*\frac{1}{k+1}<br />
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by Edbaseball17 View Post
    so far i have this

    <br />
1 - \frac{1}{2} *1 - \frac{1}{3} *1 - \frac{1}{4}...1 - \frac{1}{k} = \frac{1}{k}<br />

    <br />
1 - \frac{1}{2}*1 - \frac{1}{3}*1 - \frac{1}{4}...1 - \frac{1}{k}*1 - \frac{1}{k+1}= \frac{1}{k}*\frac{1}{k+1}<br />
    Sorry, I didn't read the title.

    Okay, we have the "base" case:
    1 - \frac{1}{2} = \frac{1}{2}

    So this works for n = 2.

    Let's assume this works for some n = k, that is that
    \left ( 1 - \frac{1}{2} \right ) \left ( 1 - \frac{1}{3} \right ) ~ ... ~ \left ( 1 - \frac{1}{k} \right ) = \frac{1}{k}

    Let's see what the n = k + 1 case says:
    \left ( 1 - \frac{1}{2} \right ) \left ( 1 - \frac{1}{3} \right ) ~ ... ~ \left ( 1 - \frac{1}{k} \right ) \left ( 1 - \frac{1}{k + 1} \right )

    By hypothesis, the product of all but the last factor is simply 1/k, so:
    \left ( 1 - \frac{1}{2} \right ) \left ( 1 - \frac{1}{3} \right ) ~ ... ~ \left ( 1 - \frac{1}{k} \right ) \left ( 1 - \frac{1}{k + 1} \right ) = \frac{1}{k} \cdot \left ( 1 - \frac{1}{k + 1} \right )

    Simplifying a bit:
    = \frac{1}{k} \cdot \frac{(k + 1) - 1}{k + 1}

     = \frac{1}{k} \cdot \frac{k}{k + 1} = \frac{1}{k + 1}
    as required.

    So it is true for n = 2, thus it is true for n = 3, 4, ...

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Say n=5 it is easier to do the following trick.

    \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \left( 1 - \frac{1}{4} \right)\left( 1 - \frac{1}{5} \right)
    Combine,
    \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{3}{4} \cdot \frac{4}{5}
    Everything cancels to give,
    \frac{1}{5}.

    Now generalize!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum