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

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

1,629
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:

0rthodontist

Science Advisor
1,230
0
n(n-1)+3.
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?
 
1,629
1
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?
 
998
0
mr_coffee said:
so if ur multiplying an even number, by an odd number u could get even or odd result can't u?
I suggest trying some examples and seeing if you still think this is true.
 
1,074
1
mr_coffee said:
so if ur multiplying an even number, by an odd number u could get even or odd result can't u?
Think about this for a minute, try a few examples the answer should be fairly obvious.
 
1,629
1
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!
 

matt grime

Science Advisor
Homework Helper
9,392
3
mr_coffee said:
It seems if you multiply an even number by an odd you get an even, wee!
erm, yes, surely that is blindingly obvious to everyone, since the defintion of even is that it is a multiple of 2.



Okay so this is my new proof and it got pretty messy...
then it is a bad proof given it is a clean idea

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,
why would I want to do this? there is no need to introduce p and q at all

such that p = n and q = n-1.
Then p and q have opposite parity by theorem 3.4.2.
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.)
 
1,629
1
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).
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.

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

shmoe

Science Advisor
Homework Helper
1,993
1
mr_coffee said:
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?
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.
 

shmoe

Science Advisor
Homework Helper
1,993
1
mr_coffee said:

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.
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.
 
1,629
1
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:

HallsofIvy

Science Advisor
41,626
821
mr coffee said:
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.
??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)
matt grime said:
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).
 

matt grime

Science Advisor
Homework Helper
9,392
3
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:
1,629
1
Thanks for clearing that up guys and for the help!
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top