1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction Proof

  1. May 18, 2010 #1
    1. The problem statement, all variables and given/known data
    Suppose that v is of type Vector of Integers and we know the following:-

    1. v is sorted.
    2. No two items in v are the same.
    3. v.at(1) is 12.

    For an integer n, where 1 <= n <= v.size(), let p(n) be the following proposition: p(n): v.at(n) => 11 + n.

    A. Explain why p(1) is true?
    B. suppose that p(k - 1) is true (where 1 < k <= v.size()). Explain why p(k) must then be true.
    C. Complete a proof that p(n) is true for all integers n with 1 <= n < v.size().


    2. Relevant equations



    3. The attempt at a solution
    A.
    Let n = 1.
    p(1) = v.at(1) => 11 + 1 = 12
    As per part 3, v.at(1) is 12 and so p(1) is true. This is the base step.

    B.
    As per parts 2 & 3, v.at(k - 1) < v.at(k). Then,
    p(k) = v.at(k) => v.at(k - 1) + 1.
    Thus p(k) is true. This is the inductive step.

    C.
    From the base step, p(1) = v.at(1) => 11 + 1 = 12.

    Now, p(1) => 12 --> p(2) = v.at(2) => 11 + 2 = 13.
    Hence, p(2) => 13 --> p(3) = v.at(3) => 11 + 3 = 14.
    Hence, p(3) => 14 --> p(4) = v.at(4) => 11 + 4 = 15.
    Hence, p(4) => 15 --> p(5) = v.at(5) => 11 + 5 = 16.
    : :
    : :
    Now, p(k - 1) => 11 + k -1 --> p(k) = v.at(k) => 11 + k.

    Thus, for any k => 1, p(k - 1) --> p(k) = v.at(k) => 11 + k.

    Since the inductive step has been proven the proof is now complete.


    *****
    I'm not very confident with this and would really appreciate it if someone could double check it for me. I'm thinking most of C belongs in b because its basically proving the inductive step which is what b is asking.
     
  2. jcsd
  3. May 18, 2010 #2

    Mark44

    Staff: Mentor

    It is given that v.at(1) = 12, and 12 = 11 + 1, so p(1) is true.
    You are using the proposition to show that the proposition is true, which is not valid. This is your step that I am questioning: v.at(1) => 11 + 1.

    BTW, what's with the => symbol? Doesn't = work just a well?
    No, you can't do this.

    Start by assuming p(k - 1) is true. I.e., v.at(k - 1) = 11 + (k - 1) = 10 + k.
    Now use this, plus the other given information, to conclude that p(k) = 11 + k. (How to do this isn't obvious to me.)

    BTW, don't write p(k) = ... p(k) represents a particular statement. Its value is either true or false.
     
  4. May 19, 2010 #3

    Mark44

    Staff: Mentor

    I think that the key to this problem is that your vector has only a finite number of elements. IOW, there is a last element at index v.size(). This is different from most induction proofs, where the index is an element of the positive integers, a set without a largest element.
     
  5. May 19, 2010 #4
    Can anyone else help with this?
     
  6. May 21, 2010 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I'm guessing the problem is in the notation. You have written

    p(k)=>k + 11

    which looks like some kind of implication symbol. Are you actually trying to prove:

    p(k) ≥ 11 + k ?

    That is very easy to show. Is that really what your question is?
     
  7. May 21, 2010 #6

    Mark44

    Staff: Mentor

    From the OP,
    p(n) is proposition/statement n. The statement itself is v.at(n) >= 11 + n. Here, v is an instance of the vector class in C++, and at(n) is a function that returns a reference to the value at index n.
     
  8. May 21, 2010 #7

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Maybe I just don't see what the problem or what it has to do with C++ or its vector class. Isn't he just asking this question:

    Given sequence of {v(n)} of integers which is sorted with v(1) = 12, show that v(n) ≥ 11 + n for all positive integers n? That is a perfectly sensible and easily proven statement. If that isn't what the question is, I need more clarification.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Induction Proof
Loading...