Results 1 to 4 of 4

Math Help - Where did I go wrong on this proof? (Mathematical Induction)

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    48

    Where did I go wrong on this proof? (Mathematical Induction)

    I apologize in advance for not knowing how to type mathematical notation, I'll do the best I can to make the question as clear as possible.

    The problem is:

    Show that (sigma)(i=1 to n) i/(2^i) = 2 - (n+2) / (2^n) for all natural numbers n.

    Here is what I did:

    Proof. We proceed by weak mathematical induction.

    Base Case. Put n = 1. Then (sigma)(i=1 to n) i/(2^i) = (sigma)(i=1 to 1) i/(2^i) = 1/(2^1) = 1/2 = 2 - (1+2)/(2^1) = 2 - (n+2)/(2^n) , so the base case is established.

    Induction Step. Fix a natural number n and suppose (sigma)(i=1 to n) i/(2^i) = 2 - (n+2)/(2^n).
    Observe that (sigma)(i=1 to (n+1)) i/(2^i)
    = 1/(2^1) + 2/(2^2) + 3/(2^3) +...+ (n+1)/(2^(n+1))
    = [1/(2^1) + 2/(2^2) + ... + n/(2^n)] + (n+1)/(2^(n+1))
    = [(sigma)(i=1 to n) i/(2^i)] + (n+1)/(2^(n+1))
    = [2 - (n+2)/(2^n)] + (n+1)/(2^(n+1))
    = [2 - (2)(n+2) / (2)(2^n)] + (n+1)/(2^(n+1))
    = [2 - (2n+4) / (2^(n+1))] + (n+1)/(2^(n+1))
    = 2 - (3n+5) / (2^(n+1))
    = 2 - (3n + 3 + 2) / (2^(n+1))
    = 2 - [3(n+1) + 2] / (2^(n+1))

    My goal was to show 2 - [(n+1)+2] / (2^(n+1)) ... I got really close except for the extra 3. Did I do something wrong, or is the proof finished?

    Again, I apologize if this is difficult to read...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Lprdgecko View Post
    I apologize in advance for not knowing how to type mathematical notation, I'll do the best I can to make the question as clear as possible.

    The problem is:

    Show that (sigma)(i=1 to n) i/(2^i) = 2 - (n+2) / (2^n) for all natural numbers n.

    Here is what I did:

    Proof. We proceed by weak mathematical induction.

    Base Case. Put n = 1. Then (sigma)(i=1 to n) i/(2^i) = (sigma)(i=1 to 1) i/(2^i) = 1/(2^1) = 1/2 = 2 - (1+2)/(2^1) = 2 - (n+2)/(2^n) , so the base case is established.

    Induction Step. Fix a natural number n and suppose (sigma)(i=1 to n) i/(2^i) = 2 - (n+2)/(2^n).
    Observe that (sigma)(i=1 to (n+1)) i/(2^i)
    = 1/(2^1) + 2/(2^2) + 3/(2^3) +...+ (n+1)/(2^(n+1))
    = [1/(2^1) + 2/(2^2) + ... + n/(2^n)] + (n+1)/(2^(n+1))
    = [(sigma)(i=1 to n) i/(2^i)] + (n+1)/(2^(n+1))
    = [2 - (n+2)/(2^n)] + (n+1)/(2^(n+1))
    = [2 - (2)(n+2) / (2)(2^n)] + (n+1)/(2^(n+1))
    = [2 - (2n+4) / (2^(n+1))] + (n+1)/(2^(n+1))
    = 2 - (3n+5) / (2^(n+1))
    = 2 - (3n + 3 + 2) / (2^(n+1))
    = 2 - [3(n+1) + 2] / (2^(n+1))

    My goal was to show 2 - [(n+1)+2] / (2^(n+1)) ... I got really close except for the extra 3. Did I do something wrong, or is the proof finished?

    Again, I apologize if this is difficult to read...

    Yes...it is VERY difficult to read. Perhaps somebody else can understand it better, but in the meantime why won't you learn

    how to type LaTeXin the site? Go to the help section.

    You could also type it nicely on a JPG or PDF (not .DOC !) file and attach it to your question.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2010
    Posts
    86
    Its correct until four before the bottom line:

    = [2 - (2n+4) / (2^(n+1))] + (n+1)/(2^(n+1))

    2 - \frac{(2n+4)}{2^{n+1}} + \frac{n+1}{2^{n+1}}

    You just added the two terms in the numerator as they were both negative. Take the different signs into consideration and the next step will yield your solution. PS: Don't forget to show that it is true for some specific value of n to complete your induction proof.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2010
    Posts
    48


    Here it is written out, though I just saw raphw's reply. Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 24th 2011, 03:33 PM
  2. Proof by mathematical induction.
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: June 23rd 2011, 10:12 PM
  3. Proof by Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 28th 2010, 09:07 AM
  4. proof and mathematical induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 11th 2007, 12:16 PM
  5. Proof Of Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 19th 2007, 09:24 PM

Search Tags


/mathhelpforum @mathhelpforum