Results 1 to 3 of 3

Math Help - Hi any Ideas where I went wrong (induction)?

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    180

    Hi any Ideas where I went wrong (induction)?

    What is wrong with this solution?
    Problem:
    Prove that \frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+...+\frac{  n}{2^n} = 2-\frac{n+2}{2^n} for n=1,2,3,...

    Solution:
    Proof by induction
    Let the LHS =
     <br />
\sum_{k=1}^{n+1}(\frac{n}{2^n})= \sum_{k=1}^{n}(\frac{n}{2^n})+\sum_{n}^{n+1}(\frac  {n}{2^n})<br />

    RHS is 2-\frac{n+2}{2^n}

    Is it valid for n=1?
    LHS = \frac{1}{2}
    RHS= 2-\frac{1+2}{2^1} = \frac{1}{2} True!
    Now let LHS =
     <br />
\sum_{k=n}^{n+1}(\frac{n}{2^n}) = \frac{n+1}{2^{n+1}}<br />
    Thats what we want our RHS to look like:
    Now
    Lets look att RHS.
    Lets set (n+1) into the formula and subract n that should then equal the LHS hopefully:
     <br />
2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{n+2}{2^{n}} \right)<br />
    .
     <br />
2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{2(n+2)}{2\times 2^{n}} \right)<br />
    .
     <br />
2-\frac{(n+1)+2}{2^{n+1}}- 2+\frac{2(n+2)}{2\times 2^{n}}<br />
    .
     <br />
\frac{2n+4}{2\times 2^{n}}-\frac{n+3}{2\times 2^{n}}<br />
    .
     <br />
\frac{n+1}{2\times 2^{n}}<br />
    RHS = LHS and by induction this is true for all n  \in \textbf{R}
    Why is this not right?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Henryt999 View Post
    What is wrong with this solution?
    Problem:
    Prove that \frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+...+\frac{  n}{2^n} = 2-\frac{n+2}{2^n} for n=1,2,3,...

    Solution:
    Proof by induction
    Let the LHS =
     <br />
\sum_{k=1}^{n+1}(\frac{n}{2^n})= \sum_{k=1}^{n}(\frac{n}{2^n})+\sum_{n}^{n+1}(\frac  {n}{2^n})<br />

    RHS is 2-\frac{n+2}{2^n}


    Here really begins your proof. The above stuff is only algebraic manipulations.


    Is it valid for n=1?
    LHS = \frac{1}{2}
    RHS= 2-\frac{1+2}{2^1} = \frac{1}{2} True!
    Now let LHS =
     <br />
\sum_{k=n}^{n+1}(\frac{n}{2^n}) = \frac{n+1}{2^{n+1}}<br />
    Thats what we want our RHS to look like:
    Now
    Lets look att RHS.
    Lets set (n+1) into the formula and subract n that should then equal the LHS hopefully:
     <br />
2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{n+2}{2^{n}} \right)<br />
    .
     <br />
2-\frac{(n+1)+2}{2^{n+1}}-\left( 2-\frac{2(n+2)}{2\times 2^{n}} \right)<br />
    .
     <br />
2-\frac{(n+1)+2}{2^{n+1}}- 2+\frac{2(n+2)}{2\times 2^{n}}<br />
    .
     <br />
\frac{2n+4}{2\times 2^{n}}-\frac{n+3}{2\times 2^{n}}<br />
    .
     <br />
\frac{n+1}{2\times 2^{n}}<br />
    RHS = LHS and by induction this is true for all n  \in \textbf{R}
    Why is this not right?

    I think it is right but you did it so messed up and unclear that, apparently, you succeeded to confuse, and perhaps even annoy, your instructor.

    After proving the claim for n=1, you must say/write: let us assume the claim's true for n (this is also called "inductive hypothesis") and we shall prove for n+1, i.e. we must prove that

    \sum\limits_{k=1}^{n+1}\frac{k}{2^k}=2-\frac{n+3}{2^{n+1}} . We now take the LHS and develop it:

    \sum\limits_{k=1}^{n+1}\frac{k}{2^k}=\sum\limits_{  k=1}^n\frac{k}{2^k}+\frac{n+1}{2^{n+1}} =_{\substack{Ind. Hyp.}}2-\frac{n+2}{2^n}+\frac{n+1}{2^{n+1}}=2-\frac{1}{2^{n+1}}\left[2(n+2)-n-1\right] =2-\frac{n+3}{2^{n+1}} and we're done since now we got the RHS...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2009
    Posts
    180
    I think it is right but you did it so messed up and unclear that, apparently, you succeeded to confuse, and perhaps even annoy, your instructor.

    IŽll give you a big thanks for making me laugh for 2 minutes =)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Any ideas here please? :-)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 5th 2010, 07:56 AM
  2. Replies: 3
    Last Post: October 12th 2010, 08:11 PM
  3. Any ideas...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 28th 2010, 09:19 PM
  4. What's wrong with this proof (complete induction)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 4th 2009, 10:32 PM
  5. i need some ideas
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 6th 2008, 07:22 AM

Search Tags


/mathhelpforum @mathhelpforum