Results 1 to 4 of 4

Math Help - proof by induction help

  1. #1
    Super Member
    Joined
    Sep 2008
    Posts
    607

    proof by induction help

    For each integer,   r \geq 0 , the Mersenne number  M_{r} is defined to be  2^{r} -1

    Prove by induction that  \sum_{ r = 0}^n M_{r} = M_{n+1} -n -1

    So I proved it works for 1 first,

    I got  2^{1} -1 = 2^{1+1} -1-1-1

    so it is true for n =1

    assume it s also true for n =k

    so  \sum_{r=0}^k 2^{r} -1 = 2^{k+1}-1-k-1

    and so with n=k+1

     \sum_{r=0}^{k+1} 2^{r}-1 = 1 + 3+ 5....2^{k}-1 + 2^{k+1 +1} -1

    =

    not sure what to do from here...

    [tex]
    Last edited by Tweety; October 17th 2012 at 04:30 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: proof by induction help

    You need to prove \sum_{r=0}^{k+1}(2^r-1)=2^{k+2}-1-(k+1)-1. Since you want to use the induction hypothesis, which contains \sum_{r=0}^k(2^r-1), it makes sense to represent \sum_{r=0}^{k+1}(2^r-1) as \sum_{r=0}^k(2^r-1)+(2^{k+1}-1). Then use the hypothesis.

    By the way,

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

    using the formula for the sum of geometric progression.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Sep 2008
    Posts
    607

    Re: proof by induction help

    Thank you for that, but I cant seem to follow from

    I have the kth term and the k+1 therm,

     2^{k+1} -k -1 + 2^{k+1}-1

    and from this I need to show that this expressin is eqvialent to  2^{n+1}-n -1

    But I am not sue how to 'manipulate the first expression, to get it like the second expression,
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: proof by induction help

    Quote Originally Posted by Tweety View Post
    I have the kth term and the k+1 therm,

     2^{k+1} -k -1 + 2^{k+1}-1

    and from this I need to show that this expressin is eqvialent to  2^{n+1}-n -1
    No, this is not what you need to show. To begin with, there is no n. You assume the induction hypothesis for k and prove it for k + 1.

    Before starting a proof by induction, you need to identify the induction statement, which is usually denoted by P(k). Usually to get the induction statement you just need to drop the universal quantifier from the statement you need to prove. In this case, you need to prove,

    for all n\ge 1, \sum_{r=0}^{n}(2^r-1)=2^{n+1}-1-n-1.

    Therefore, P(n) is \sum_{r=0}^{n}(2^r-1)=2^{n+1}-1-n-1. Just by renaming n with k (which is not required), P(k) is \sum_{r=0}^{k}(2^r-1)=2^{k+1}-1-k-1.

    Next you prove the base case, which is P(1). (By the way, P(0) also holds. You did not write whether you need to prove P(n) for all n ≥ 0 or for all n ≥ 1.) After that, you fix an arbitrary k, assume P(k) and prove P(k + 1). So, P(k + 1) is \sum_{r=0}^{k+1}(2^r-1)=2^{k+2}-1-(k+1)-1. Start with the left-hand side, divide the sum up to k + 1 into the sum up to k plus the (k + 1)st term and use the induction hypothesis P(k) to rewrite the sum up to k.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: February 24th 2011, 02:32 AM
  2. Proof By Induction
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: July 20th 2009, 09:33 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 25th 2008, 08:01 PM

Search Tags


/mathhelpforum @mathhelpforum