Results 1 to 5 of 5

Thread: 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
    11,152
    Thanks
    731
    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
    $\displaystyle 1 - \frac{1}{k} = \frac{k -1}{k}$

    So this may be represented in "Pi" notation as:
    $\displaystyle \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

    $\displaystyle
    1 - \frac{1}{2} *1 - \frac{1}{3} *1 - \frac{1}{4}...1 - \frac{1}{k} = \frac{1}{k}
    $

    $\displaystyle
    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}
    $
    Follow Math Help Forum on Facebook and Google+

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

    $\displaystyle
    1 - \frac{1}{2} *1 - \frac{1}{3} *1 - \frac{1}{4}...1 - \frac{1}{k} = \frac{1}{k}
    $

    $\displaystyle
    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}
    $
    Sorry, I didn't read the title.

    Okay, we have the "base" case:
    $\displaystyle 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
    $\displaystyle \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:
    $\displaystyle \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:
    $\displaystyle \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:
    $\displaystyle = \frac{1}{k} \cdot \frac{(k + 1) - 1}{k + 1}$

    $\displaystyle = \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
    10
    Say $\displaystyle n=5$ it is easier to do the following trick.

    $\displaystyle \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,
    $\displaystyle \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{3}{4} \cdot \frac{4}{5} $
    Everything cancels to give,
    $\displaystyle \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: Oct 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: Mar 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum