Results 1 to 4 of 4

Math Help - Proof by Induction

  1. #1
    Super Member Quacky's Avatar
    Joined
    Nov 2009
    From
    Windsor, South-East England
    Posts
    901

    Proof by Induction

    Use the method of mathematical induction to prove that, for n \in Z

    \sum\limits_{r=1}^{n} r + \frac{1}{2}^{r-1} = \frac{1}{2}(n^2+n+4) - \frac{1}{2}^{n-1}

    I've done the first stage, which is to show that it's true for n=1 (both sides are equal to 2 in said situation). I can easily do the assumption stage, which is simply to substitute in n=k. I know that the next stage involves showing it's true for n=k+1 but I can't seem to do this correctly. I think my memory is slightly fuzzy and my notes are just confusing me. Any help would be appreciated.

    Edit: woops, posted this in pre-calc. >.< move this to pre-algebra and algebra if necessary, but please don't delete the thread - figuring out that latex took me hours.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie driegert's Avatar
    Joined
    Feb 2010
    From
    Kingston, Ontario
    Posts
    16
    So if I remember right the next step would be:

     \sum\limits_{r=1}^{n+1} r + (\frac{1}{2})^{r-1} = \frac{1}{2}(n^{2} + n + 4) - (\frac{1}{2})^{n-1} + (n+1) + (\frac{1}{2})^{n}

    I can't seem to get it to work out, it's been a while, but you want to re-arrange the right side to look like:

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

    Sorry I couldn't be more help .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    P(k)

    \displaystyle\sum_{r=1}^k\left(r+\frac{1}{2}^{r-1}\right)=\frac{1}{2}\left(k^2+k+4\right)-\frac{1}{2}^{k-1}

    P(k+1)

    \displaystyle\sum_{r=1}^{k+1}\left(r+\frac{1}{2}^{  r-1}\right)=\frac{1}{2}\left[(k+1)^2+(k+1)+4\right]-\frac{1}{2}^{k}

    Try to show that P(k) if true will cause P(k+1) to also be true.

    Proof

    \displaystyle\sum_{r=1}^{k+1}\left(r+\frac{1}{2}^{  r-1}\right)=\left[\frac{1}{2}\left(k^2+k+4\right)-\frac{1}{2}^{k-1}\right]+(k+1)+\frac{1}{2}^k

    Now try to write the RHS of P(k+1) in terms of this to complete the inductive step, by showing P(k+1) to be true
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Quacky's Avatar
    Joined
    Nov 2009
    From
    Windsor, South-East England
    Posts
    901
    Thanks for your time, I now have the solution.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction that 4| 5^n - 1
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 10:23 AM
  2. proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 17th 2010, 07:11 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. induction proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 1st 2008, 04:32 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

/mathhelpforum @mathhelpforum