Results 1 to 2 of 2

Math Help - Mathematical Induction Proof

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    37

    Unhappy Mathematical Induction Proof

    I cannot get my head around this at all.

    Suppose that v is of type Set 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().
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by RedKMan View Post
    I cannot get my head around this at all.

    Suppose that v is of type Set 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().
    Your notation/terminology is a bit odd to me. Normally I'd call v a vector or a tuple instead of a set of integers. There seems to be a mixture of mathematics and computer science terms.

    It seems clear from context that we are dealing with a k-tuple with indices going from 1 to k, as opposed to 0 to k-1.

    But if I'm understanding the main question properly, the answer is intuitively very easy to understand. For any index i, the least possible value for v.at(i) is 11+i. This is because the tuple with minimal values is simply (12,13,14,15,...,11+k).

    It can be seen that for the above tuple, it is not possible to replace v.at(i) with any value less than v.at(i), because then it would no longer be sorted and free from duplicate elements.

    The rest is formalising with mathematical induction.

    A. p(1) is true because p(1) = 12 >= 11+1 = 12. This is trivial.

    B. So we assume that p(n-1) is true. Then the least possible value for p(n) is p(n-1)+1. So p(n) >= p(n-1)+1 >= 11+(n-1)+1 >= 11+n.

    C. We have our induction step and base case. The proof is already complete.

    Edit: By the way, "v is sorted" translates to v.at(1) <= v.at(2) <= v.at(3) <= ... <= v.at(k). Disallowing duplicates, this becomes v.at(1) < v.at(2) < v.at(3) < ... < v.at(k).

    An equivalent way to state this is that given any two indices i and j, i < j, "v is sorted" implies that v.at(i) <= v.at(j). Disallowing duplicates, this becomes v.at(i) < v.at(j).
    Last edited by undefined; May 5th 2010 at 12:00 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical induction proof, help?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 23rd 2010, 07:39 PM
  2. Proof by Mathematical induction!
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 30th 2008, 09:45 AM
  3. Proof By Mathematical Induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 6th 2008, 05:32 AM
  4. Proof Of Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 19th 2007, 08:24 PM
  5. Mathematical induction proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 13th 2007, 01:10 PM

Search Tags


/mathhelpforum @mathhelpforum