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!

Mathematical Induction Proof

  1. May 9, 2010 #1
    I cannot get my head around this at all.

    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().

    For A. I have,

    In plain English the proposition means,
    The n at position n in v is greater than or equal to 11 + n.

    Let n = 1.

    P(1): v.at(1) ≥ 11 + 1 = 12. (B)

    From statement 3 which indicates v.at(1) is 12 and statement 2 which indicates no two items in v are the same, the above statement proves p(1) is true.

    I'm struggling with the Inductive hypothesis (question b).
  2. jcsd
  3. May 9, 2010 #2


    User Avatar
    Science Advisor

    Try using the facts that v is sorted and no two elements of v are the same. What does this tell you?
  4. May 9, 2010 #3
    This tells me that:-

    Let n = 2.

    P(2): v.at(1) ≥ 11 + 2 = 13. (B)
    P(3): v.at(1) ≥ 11 + 3 = 14. (B)
    P(4): v.at(1) ≥ 11 + 4 = 15. (B)
    P(5): v.at(1) ≥ 11 + 5 = 16. (B)
  5. May 9, 2010 #4


    User Avatar
    Science Advisor

    If they are sorted and no two are the same, doesn't this mean that v.at(n)>v.at(n-1)?
  6. May 9, 2010 #5
    Yes it does.

    Given that v is sorted and no item in the vector is identical then:-

    v.at(n) > v.at(n - 1).

    Where does p(k - 1) come into play?
  7. May 10, 2010 #6
    I'm still struggling to work this out, so any help appreciated.
  8. May 10, 2010 #7


    User Avatar
    Science Advisor

    Since they are integers and v.at(n)>v.at(n-1), then v.at(n)>=v.at(n-1)+1. Can't you then work by induction?
  9. May 10, 2010 #8
    What your saying makes sense to me, I understand it. I'm not sure how p(k - 1) comes into play. I fairly sure I'm learning from bad text because the book is based entirely on using mathematical induction as proof for recurrence systems. Yet this question doesn't involve a recurrence system. I've tried looking for induction learning material but nothing I've come across really helps.
  10. May 11, 2010 #9
    Still struggling with this, feel as though I'm banging my head against a brick wall. I'm not sure how to put it all together into a meaningful proof.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook