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