Proving the Contrapositive: If n is even, then n^5 + 7 is odd

[Panphobia]

Homework Statement

Prove that for any integer n, if n^5 + 7 is even then n is odd.(I wasn't sure which section I was supposed to post this in)

The Attempt at a Solution

Ok so we just got into proofs in my math class and we are supposed to use proof by contraposition for this one. So I was thinking
p = n^5 + 7 is even
q = n is odd

so we have p → q, but we need to use ~q→~p, so prove that, "if n is even then n^5 + 7 is odd"? How would I even go about doing this? The professor didn't even show an example. I know how to do proof by contradiction/exhaustion/induction already, but this one has me kind of stumped.

 

[Tsunoyukami]

This is a very simple type of proof that is similar to a "direct" proof.

As you have stated, the question is of the form "If P, then Q." But the P part looks a bit tricky, so we want to prove the contrapositive, "If ~Q, then ~P." So, as you stated, we must prove the following statement:

"If n is even, then $n^{5}+7$ is odd."

In order to do this we begin by assuming $n$ is even and then manipulating $n$ to reach the conclusion. You might want to recall the definitions of even and odd.

Your proof will begin as follows:
Assume n is even. Then n = ...

 

[Panphobia]

If n is an even number, then n = 2k? Since it is even, it can be divided by two. So (2k)^5 + 7 = 32*k^5 + 7
So I know on my own, that an even number multiplied by any Integer will give an even number, and then if you add 7 which is odd, the whole expression evaluates to an odd number. But that doesn't seem to be proof worthy, so how would I state it in terms of a proof?

 

[Tsunoyukami]

Very good. You almost have the solution (ie. proof).

As you said, because $n$ is an even number we can write $n = 2k$ for some integer $k$. Then We do as you said - $n^{5}+7=(2k)^{5}+7=32k^{5}+7$. Now we need to find a way to show that this is odd.

What is the definition of an odd number? If an even number is $n=2k$, an odd number should be...?

Once you have a way to write an odd number you should be able to manipulate the expression $32k^{5}+7$ to the form of an odd number and can conclude it is odd.

 

[Panphobia]

I am pretty sure that the definition of an odd number is that, if p is odd, then p = 1 mod 2, or (p-1) mod 2 = 0

 

[Tsunoyukami]

That is correct. Can you translate that definition into something a bit easier to work with? For example, we wrote an even integer as $n=2k$ for some integer $k$. Can you write an odd integer in a form similar to this? (Hint: If you manipulate the definition you gave you should come to the correct result; it should be obvious when you see it.)

 

[Panphobia]

if n is odd, then n = 2k + 1 right?

 

[Tsunoyukami]

Yes, that is correct. One thing to be careful about is that the $k$ in your definition of even and odd need not be the same $k$. So in your proof you got to the expression $n^{5}+7=32k^{5}+7$. You need to manipulate the right side of this expression into the form $2l+1$, where $l$ is an integer. Then you will have shown that $n^{5}+7$ is odd.

 

[Panphobia]

well, I don't know how to do that...how are you supposed to get it in the for 2l + 1, if there is a 7, even if you break it up into, +1 and +6, there is still that extra + 6. The solution is probably much simpler than I imagine.

 

[Tsunoyukami]

You're very close. I chose to remind you that the $k$ in the definition of even and odd are not necessarily the same $k$. They could be different.

So, as you suggested, we can break of up 7 into 6+1. Then we have:

$n^{5}+7=32k^{5}+7=32k^{5}+6+1=(32k^{5}+6)+1$ Do you agree with this?

Now all we have left to do is rewrite $(32k^{5}+6)$ as the product of 2 and an integer (it shouldn't be called "$k$" since we've already used $k$ and this is a different integer). So we need to write $32k^{5}+6=2l$ where $l = ?$.

 

[Panphobia]

Ohhhh alright, so 2(16k^5 + 3) +1, l = 16k^5 + 3. Ok so this is how you would figure out a direct proof?

 

[Tsunoyukami]

Very good! This is a proof by contrapositive which is very similar to a direct proof. The 'only' difference is that for a direct proof we seek to prove "If P, then Q." and for a proof by contrapositive we seek to prove "If ~Q, then ~P." However the idea and techniques are the same.

In general, say we want to prove a statement "If A, then B." Your proof will (usually) begin with the statement "Assume A." Then you will use properties of A that you know are true by various definitions to try and manipulate your way to B.

I suggest you write up your full solution to this problem as a single post (or in your notebook) so that you can see how the idea and argument flows step-by-step in a nice and simple manner. If you can post it here that would be great too because I might be able to provide feedback about the precision of your final proof.

If you want some more practice here's another similar problem. "Let $x$ be an integer. Prove that if $7x + 5$ is odd, then $x$ is even."

 

[Panphobia]

I would rather not post it here, since it is an assignment question. But I think I know the general way to do it. Have a proposition, and then the proof.

 

[Panphobia]

Also, if I wanted to prove that the product of two odd integers is odd. Would this be a direct proof? So If x and y are odd, then xy is odd?

 

[Tsunoyukami]

Yes, you would begin by assuming x and y are odd and work with definitions. For example, x=2a+1 and y=2b+1.

 

[Panphobia]

Btw quick question, what are, "Rules of Inference". We have to prove some premises like, "I am either dreaming or hallucinating", "I am not dreaming", "If I am hallucinating, I see elephants running down the road" Prove that this implies the conclusion, "I see elephants running down the road".

 

[Tsunoyukami]

Btw quick question, what are, "Rules of Inference". We have to prove some premises like, "I am either dreaming or hallucinating", "I am not dreaming", "If I am hallucinating, I see elephants running down the road" Prove that this implies the conclusion, "I see elephants running down the road".

I am not familiar with the term "Rules of Inference". However, what you have here are a few statements that you can use logic to find the (correct) conclusion.

The statement "I am either dreaming or hallucinating." is a conjunction P v Q. Then "I am not dreaming." is a statement that tells us P is false. Since P v Q must be true and P is false, we conclude that Q is true (ie. the statement "I am hallucinating." is true). Then we have the statement "If I am hallucinating, [then] I see elephants running down the road." which is an example of the implication "If Q, then R." This statement is true if both Q and R are true or if Q is false (this follows from the truth table for the implication). Since we know Q is true, then R must also be true in order for the implication to be true. So the statement, "I see elephants running down the road." Must be true for the implication to be true.

 

[Panphobia]

Ahh alright, now I need to incorporate quantifiers into the proofs and I am good to go. Thanks!

 

[Tsunoyukami]

No problem! I'm glad to be of help.

If you have any other questions I recommend posting them as a separate thread so that others might be able to provide additional assistance if I can't respond right away. Good luck!