Results 1 to 5 of 5

Math Help - Proving correctness of a loop using Induction

  1. #1
    Junior Member
    Joined
    Feb 2008
    Posts
    51

    Proving correctness of a loop using Induction

    I was hoping someone could help me solve this question, or even just give me a good idea on how to start it.

    Thanks in advance.
    Attached Thumbnails Attached Thumbnails Proving correctness of a loop using Induction-1.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by shawn View Post
    I was hoping someone could help me solve this question, or even just give me a good idea on how to start it.

    Thanks in advance.
    For part (a) ask what value i has when the loop is exited, then compare this with the loop invariant.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Quote Originally Posted by CaptainBlack View Post
    For part (a) ask what value i has when the loop is exited, then compare this with the loop invariant.

    RonL
    I think I have to prove that the invariant is true for I(0) which is the basis which is easy, and then assume the ith works, and prove i+1 works, and then prove that it terminates correctly and then I'll have the full proof.

    It's easy to just figure out the values like you suggest and say yes, 1=1 so it is correct, but that's not a formal enough proof, it just tells us that it should be correct.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Anyone? pleease!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by shawn View Post
    I think I have to prove that the invariant is true for I(0) which is the basis which is easy, and then assume the ith works, and prove i+1 works, and then prove that it terminates correctly and then I'll have the full proof.

    It's easy to just figure out the values like you suggest and say yes, 1=1 so it is correct, but that's not a formal enough proof, it just tells us that it should be correct.
    Well the question as asked does not ask for a proof of the invariant, but

    You can show the base cae is true, now suppose the invariant holds for some k \in \mathbb{N}, if k is odd then on the k+1 -st trip around the loop at the top of the loop a=-2(k+1),\ b=k(-1)^{k+1}=k.

    Now at the end of the loop:

    b=-2(k+1)+k+1 = -k-1=-1(k+1)=(k+1)(-1)^{k+1}

    and:

    a=-2(k+1)+4(k+1)=2(k+1)

    (note in the last line the value of b used is that produced by the previous line not what it was at the top of the loop)

    So the invariant holds in this case.

    Now if k is even, at the top of the look after the k-th itteration: a=2k,\ b=k(-1)^{k+1}=-k

    and at the end of the loop:

    b=2k-k+1=k+1=(k+1)(-1)^{k+2}

    and:

    a= 2k-4(k+1)=-2k-4=-2[(k+1)+1]

    so the invariant holds in this case also, and so the given loop invariant is indeed a loop invariant for this loop.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Complete Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 10th 2011, 01:13 PM
  2. Proving NFA Correctness
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 3rd 2011, 01:12 PM
  3. Using my assumption when proving by induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 28th 2010, 03:05 AM
  4. proving (by induction)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 30th 2009, 04:50 PM
  5. Need help proving!! Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 06:38 PM

Search Tags


/mathhelpforum @mathhelpforum