1. Not finding help here? Sign up for a free 30min 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!

Prove that for all integers n, n^2-n+3 is odd. stuck on algebra part

  1. Sep 22, 2006 #1
    Prove that for all integers n, n^2-n+3 is odd. stuck on algebra part :(

    The question in the book is the following bolded statement.
    Prove that for all integers n, n^2-n+3 is odd.
    I rewrote it as this, is that right?
    For all integers n, there exists an integer such that n^2-n+3 is odd.

    I'm having problems proving this, the professor said the algebra isn't supose to be hard, but i can't get that. Doing the form of the proof isnt what i'm stuck on though.

    Heres my start:

    Proof:
    Let n be an integer.
    We must show n^2-n+3 is an odd integer.
    Since n is an integer, then n(n-1)+3.

    I don't think i'm doing this the right way, this chapter goes over the quotient remainder theorem. Which is Given any integer n and postie integer d, there exists unique integers q and r such that n = dp + r and 0 =< r < d.

    From this you can see, that integers can be written in the form,
    n = 4q or n = 4q + 1 or n = 4q + 2 or n = 4q + 3, for some integer q.

    Where n = 4q is even, and 4q + 2 is even, and 4q + 1 is odd as well as 4q + 3.
    This sounds like the right place, becuase the 4q+3 looks really similar to the n(n-1)+3. but i'm not sure what i'm doing becuase I think i can do the following:

    Since n is an integer, and they say: We must show n^2-n+3 is an odd integer. can i do somthing like this?

    n^2-n+3 = 4q+3?, where q is an integer.
    becuase 4q + 3 is an odd integer.
    Then i come out with:
    n^2-n = 4q. #but now it seems it lost the odd integer form, and now looks even!
    n(n-1)=4q;
    q = n(n-1)/4

    But now i'm lost again...any help or suggestions? Thanks!
     
    Last edited: Sep 22, 2006
  2. jcsd
  3. Sep 22, 2006 #2

    0rthodontist

    User Avatar
    Science Advisor

    This is all you need to know. n(n-1) is the product of two consecutive integers. What do you know about any two consecutive integers?
     
  4. Sep 22, 2006 #3
    hm..
    I know that Consecutive integers have opposite parity, meaning given any two consectuive integers, one is even and the other is odd.

    so if one integer is m, the next consectuvie integer is m+1.
    so can i say like:
    n is even, and n - 1 is odd?
    In the book I have a proof that Any two consectuive integers have opposite parity but i'm not seeing the connection.

    so if ur multiplying an even number, by an odd number u could get even or odd result can't u?
     
  5. Sep 22, 2006 #4
    I suggest trying some examples and seeing if you still think this is true.
     
  6. Sep 22, 2006 #5
    Think about this for a minute, try a few examples the answer should be fairly obvious.
     
  7. Sep 23, 2006 #6
    It seems if you multiply an even number by an odd you get an even, wee!
    Which works out nicely, since i have:
    n(n-1)+3. That even result will then end up always being odd after you add the 3.

    Okay so this is my new proof and it got pretty messy...

    Proof:
    Let n be an integer.
    We must show n^2-n+3 is an odd integer.
    Since n is an integer, then n(n-1)+3.
    So let p and q be two consectuive integers, such that p = n and q = n-1.
    Then p and q have opposite parity by theorem 3.4.2.
    Therefore pq is an even integer and pq+3 = n(n-1)+3 must be an odd integer.

    Okay my first problem is, the professor said, we know all properties of integers only. So if we know all properties of integers only, can i leave out that Then p and q have opposite parity by theorem 3.4.2. Could I just write:
    Then p and q have opposite parity. Theorum 3.4.2 is just a huge proof and i can't add that into my proof. But if i leave in Theorem 3.4.2 the reader won't know what proof i'm talking about and it will also be incorrect.
    Any suggestions and does the form look good or too much jibberish"? Thanks guys!
     
  8. Sep 23, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    erm, yes, surely that is blindingly obvious to everyone, since the defintion of even is that it is a multiple of 2.



    then it is a bad proof given it is a clean idea

    why would I want to do this? there is no need to introduce p and q at all

    oh, good, 'cos we all know what theorem 3.4.2 states (and, no it is never acceptable to write this. There is no reason to suppose that anyone, even someone marking the answer has ever seen any written notes written by your lecturer).


    n(n-1) is even since one of n and n-1 must be even is all you need to say (plus the bit about then n(n-1)+3 must be odd.)
     
  9. Sep 25, 2006 #8
    Matt,

    Today my professor said, if you have a theorem you read in your chapter you could just write, according to theorem blah blah blah and state the part of the theorem your using or else no one is going to know where u got that information. But i do see why that would be pointless, becuase if they don't have the book nor page number its useless.

    So should I not write According to Theorem blah, and just write what part of the theorem i'm using? This theromum woudlnt be so bad if we were allowed to assume the reader knew what an even number is.

    LIke this, where you say n(n-1) is even, in other poofs he made us define what even was, so now in future proofs do I not have to define what an even number is and assume the reader knows what even means?

    For example, anytime the book says, odd, they say, suppose n is any odd integer. By definition of odd, n = 2k +1 for some integer k.

    So for me to say
    n(n-1) is even, now do i have to say, suppose n(n-1) is any even integer. By definition of even, n = 2k for some integer k. And now never use the variable k? or now do i have to some how incorperate the k in the proof?


    He told us to only assume the reader knows about integer properties, like the sume of 2 ints is an int, and the product of 2 ints is an int. It seems like this is going to make the proof massive and introduce a ton of variables.


    Here is my new proof, comments suggestions?


    Proof:
    Let n be an integer.
    We must show that n^2-n+3 is odd.
    Since n is an integer, then n^2-n+3 = n(n-1)+3, where n and n-1 are two consecutive integers.
    Then by the parity property, either n is even or n is odd.
    Let n be even and n-1 be odd.
    Hence the product of any even and odd number, n(n-1) must be even.
    Therefore n(n-1) is even then n(n-1)+3 must be odd.
     
    Last edited: Sep 25, 2006
  10. Sep 25, 2006 #9

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Maybe you mean "n(n-1) is even, so we can write n(n-1)=2k..." You'd only need to do this if the 'k' was somehow important later in your proof and it needed a name. it would also be fine to toss around n(n-1)/2 and treat it as an integer after you had established n(n-1) was even. For this proof, there's no need at all to introduce this k. Just "n(n-1) is even, so n(n-1)+(Odd number)= odd number" would be sufficient assuming you've got an earlier result like even+odd=odd.

    Write to your audience. Your prof wants you to assume that minimal knowledge for the reader because he wants to see if you are capable of putting down the steps needed. He's assuming that you began the course with that level of knowledge, this is a way for him to know that you know what it is you are supposed to know. Part of writing assignments and tests is figuring out what the prof is testing you on, and what steps he wants to make sure you understand. figuring this out goes well beyond just getting the marks, if you can understand what parts of the question the prof considers are important then you should have a better understanding of the question and how it fits in the material.

    You'll be able to take more for granted as the course goes on and it becomes assumed you've all mastered the material from weeks ago.

    for quoting theorems, if it's from your text writing 'theroem 3.4.2 in (textbook author's name)' would be fair game for someone in your course. You should be able to assume your prof/TA/marker/whoever has access to this text. As mentioned before, if your marker isn't your prof, they probably don't have the class notes. In this case it would be better to say "by theorem in class which says blah blah' and state the relevant bits of the theorem and how they apply to the case at hand.
     
  11. Sep 25, 2006 #10

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    What if n is odd?


    I'm guessing your 'parity property' says something like 'one of n and n-1 is even'. That's enough to conclude n(n-1) is even since it's the product of an even and odd number. We don't care which of n or n-1 is even, just that one of them is so there's no need to split it into the two cases. you can if you really like though, it's not wrong just unecessary.
     
  12. Sep 25, 2006 #11
    Thanks shmoe that makes sense alot of sense!
    Here is the revised proof:

    Proof:
    Let n be an integer.
    We must show that n^2-n+3 is odd.
    Since n is an integer, then n^2-n+3 = n(n-1)+3, where n and n-1 are two consecutive integers.
    Then by the parity property, either n is even or n is odd.
    Hence the product of any even and odd number, n(n-1) must be even and n(n-1) + (Odd number) = odd number.
    Therefore n(n-1)+3 must be odd.


    And you are correct, the property partiy proof breaks it up into 2 cases and concludes, one of m and m+1 is even and the other is odd.
     
    Last edited: Sep 25, 2006
  13. Sep 26, 2006 #12

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    ??Apparently you heard your teacher say "and state the part of the theorem you're using" since you just wrote that. That is what matt grime was telling you to do when he said (slightly sarcastically)
     
  14. Sep 26, 2006 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    The reasons you should not say 'by theorem 3.4.2' alone are at least two fold.

    1. We don't know what it is.
    2. It might not even say what you think it says.

    For all we know, 3.4.2 is actually the prime number theorem, and you're mistakenly thinking it implies something it does not. If we don't know what 3.4.2 is we have no way of knowing if you have got the right idea or not. At one extreme, you could plausibly even just list all of the theorems, lemmas etc in your notes and say 'hence it follows that...' and you would technically be correct because it may well indeed 'follow that....'.


    Another thing to get across is that with very few exceptions theorems do not have names. Thus even just saying "by The Parity Theorem, 3.4.2 " is not acceptable since I for one would have to guess what the parity theorem stated. It could also be called the even-odd dichotomy theorem, or just the odd-even theorem, who knows. Perhaps someone else thinks the parity theorem is the fact that (-1)^n is 1 for even n and -1 for odd n?

    One other thing I'm seeing here is that your teacher is teaching you the right slogans, which makes me happy. But it does show me that you need to do more than teach the slogans. For instance, I often say to students: if something refers to an odd or even number, it is probably helpful to write n=2k+1 or n=2k for some integer k. Of course, it isn't always a help to do this, or necessary, as we saw above.
     
    Last edited: Sep 26, 2006
  15. Sep 26, 2006 #14
    Thanks for clearing that up guys and for the help!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prove that for all integers n, n^2-n+3 is odd. stuck on algebra part
  1. Prove n^3 <= 2^n (Replies: 9)

Loading...