Results 1 to 4 of 4

Math Help - Mathematical induction

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    8

    Mathematical induction

    (a) Give a recursive definition of the set P of all non negative integers,
    (b) formulate the applicable induction principle and
    (c) then apply the induction principle to prove that 1/2^0+1/2^1+1/2^2....+1/2^i = 2-1/2^n for n>=0

    I have solved parts a and b and stuck on c

    (a) P is the smallest subset of R (Real numbers) such that 0 belongs to P and if k belongs to P then also k+1 belongs to P. Recursive definition

    (b) If a subset B of P is such that 0 belongs to B and if k belongs to B then also k+1 belongs to B, then subset B is equal to P. Induction principle

    (c) Proof:
    Step 1:
    Let B = {n│ n belongs to P, 1/2^0+1/2^1+1/2^2+1/2^n = 2-1/2^n}

    Step 2:
    0 belongs to B: 0 belongs to B because 1/2^0 =2- 1/2^0 Therefore 1 = 1

    Step 3:
    Let k belong to B, thus 1/2^0+1/2^1+1/2^2+1/2^k = 2-1/2^k
    Is k+1 belong to B? I am stuck Here

    Any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by annitaz View Post
    Step 3:
    Let k belong to B, thus 1/2^0+1/2^1+1/2^2…+1/2^k = 2-1/2^k
    Is k+1 belong to B? I am stuck Here

    Any ideas?
    Add (1/2)^{(k+1)} to both sides:

    (1/2)^0 + (1/2)^1 + ... + (1/2)^k + (1/2)^{(k+1)} = 2 - (1/2)^k + (1/2)^{(k+1)}

    Now simplify the right hand side and you are done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    8
    Is the following correct?

    ((2.2^k+1)-2+1)/(2^(k+1)=2^(k+2)-1)/2^k+1=2-1/2^(k+1)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by annitaz View Post
    Is the following correct?

    ((2.2^k+1)-2+1)/(2^(k+1)=2^(k+2)-1)/2^k+1=2-1/2^(k+1)
    Yes, if you add a few more pairs of parentheses:

    \frac{2 \cdot 2^{(k+1)} - 2 + 1}{2^{(k+1)}} = \frac{2^{(k+2)} - 1}{2^{(k+1)}} = 2 - (1/2)^{(k+1)}

    However, it's easier to do this:

    2 - (1/2)^k + (1/2)^{(k+1)} = 2 - 2 \cdot (1/2)^{(k+1)} + (1/2)^{(k+1)} = 2 - (1/2)^{(k+1)}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2010, 12:22 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 8th 2009, 12:27 AM
  4. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 17th 2009, 11:30 AM
  5. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 30th 2007, 03:21 PM

Search Tags


/mathhelpforum @mathhelpforum