Results 1 to 4 of 4

Math Help - Quantifiers and the general solution of the recurrence relation

  1. #1
    Newbie
    Joined
    May 2012
    From
    LA
    Posts
    7

    Quantifiers and the general solution of the recurrence relation

    Please help me with these 2 problems

    1)
    a) Express the statement "Every negative number has another negative number greater than it" using quantifiers.
    b) Express the negation with no negation symbols in front of quantifiers, and then state the negation in words.
    c) Is the statement true for the integers? For the rationals?

    so I for part a) i did ∀x∃y[( x< 0 Y <0) --> x < y ) , the statement is false because if x = -1 , there is no negative number greater than -1

    i'm not sure how to do the negation , but i'm sure that the negation statement is true for the integers, not sure for the rationals.

    2) Find the general solution of the recurrence relation a1 = 1 , a2 = 2, an = 7an-1 - 10 an-2 + 3n + 8
    I got an = (-2) (2)n + (17/10) (5)n -(9/2) 3n +2, but i think i got the coefficient (-2) and (17/10) are wrong.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Quantifiers and the general solution of the recurrence relation

    Quote Originally Posted by Tiome View Post
    so I for part a) i did ∀x∃y[( x< 0 ∧ Y <0) --> x < y ), the statement is false because if x = -1 , there is no negative number greater than -1
    I agree that the original statement is false for the integers. However, the formula you wrote is true for the integers! Indeed, given any x, take y = 1. Then the premise of (x < 0 ∧ y < 0) -> x < y is false, so the whole statement is true.

    It helps to think in terms of proof of formulas. What should a proof of the statement "Every negative number has another negative number greater than it" do? Given any x together with an evidence that x is negative, it must produce some y and two pieces of evidence: that y is negative and that x < y. Note that producing the evidence that y < 0 is the proof's responsibility; it is not given to it for free in the same way as the evidence that x < 0 is given. In general, a proof of ∀x P(x) is given x while a proof of ∃x P(x) has to produce x. Similarly, a proof of P -> Q is given an evidence for P and it has to produce an evidence for Q. For this problem, this means that y < 0 should be on the right-hand side of the implication: ∀x∃y[x < 0 -> (y < 0 ∧ x < y)]. In fact, I prefer ∀x[x < 0 -> ∃y(y < 0 ∧ x < y)] because here the proof can use the evidence that x < 0 to help it come up with y.

    Constructing negation is very simple. First, you put in front of the whole formula. The problem says to move inside the quantifiers, which you can do using the following equivalences:

    ∀x P(x) <=> ∃x P(x)
    ∃x P(x) <=> ∀x P(x)

    If you'd like, you can move further inside using

    (P -> Q) <=> P ∧ Q
    (P ∧ Q) <=> P ∨ Q
    (P ∨ Q) <=> P ∧ Q
    P <=> P

    Quote Originally Posted by Tiome View Post
    c) Is the statement true for the integers? For the rationals?
    The original statement is true on rationals because for each positive rational x there exists a smaller positive rational, e.g., x/2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2012
    From
    LA
    Posts
    7

    Re: Quantifiers and the general solution of the recurrence relation

    Thank you , it helped a lot
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,400
    Thanks
    1849

    Re: Quantifiers and the general solution of the recurrence relation

    Quote Originally Posted by Tiome View Post
    Please help me with these 2 problems

    1)
    a) Express the statement "Every negative number has another negative number greater than it" using quantifiers.
    b) Express the negation with no negation symbols in front of quantifiers, and then state the negation in words.
    c) Is the statement true for the integers? For the rationals?

    so I for part a) i did ∀x∃y[( x< 0 Y <0) --> x < y ) , the statement is false because if x = -1 , there is no negative number greater than -1

    Your original statement was "Every negative number has another negative number greater than it". There is nothing in that about integers. If x=-1 then y= -1/2 is a negative number larger than x. For any negative number x, x/2 is a negative number larger than x.

    [quote i'm not sure how to do the negation , but i'm sure that the negation statement is true for the integers, not sure for the rationals.[/quote]
    The negation of the statement is "There exist a negative number having no negative number larger than it". Yes, the negation is true for integers because the original statement was false for integers. Because the original statement was true for rational numbers, the negation is false for rational numbers.

    2) Find the general solution of the recurrence relation a1 = 1 , a2 = 2, an = 7an-1 - 10 an-2 + 3n + 8
    I got an = (-2) (2)n + (17/10) (5)n -(9/2) 3n +2, but i think i got the coefficient (-2) and (17/10) are wrong.
    [/QUOTE]
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. General solution to 3rd order recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 11th 2011, 05:41 AM
  2. f(n) general term of recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 20th 2010, 02:35 AM
  3. general solution of a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2010, 10:55 PM
  4. Replies: 4
    Last Post: May 3rd 2009, 10:31 PM
  5. Find solution to a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 20th 2009, 12:17 PM

Search Tags


/mathhelpforum @mathhelpforum