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!

Proof by contraposition

  1. Mar 12, 2014 #1
    1. The problem statement, all variables and given/known data

    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)


    3. 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.
     
  2. jcsd
  3. Mar 12, 2014 #2
    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 = ...
     
  4. Mar 12, 2014 #3
    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?
     
  5. Mar 12, 2014 #4
    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.
     
  6. Mar 12, 2014 #5
    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
     
    Last edited: Mar 12, 2014
  7. Mar 12, 2014 #6
    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.)
     
  8. Mar 12, 2014 #7
    if n is odd, then n = 2k + 1 right?
     
  9. Mar 12, 2014 #8
    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.
     
  10. Mar 12, 2014 #9
    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.
     
  11. Mar 12, 2014 #10
    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 = ?##.
     
  12. Mar 12, 2014 #11
    Ohhhh alright, so 2(16k^5 + 3) +1, l = 16k^5 + 3. Ok so this is how you would figure out a direct proof?
     
  13. Mar 12, 2014 #12
    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."
     
  14. Mar 12, 2014 #13
    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.
     
  15. Mar 12, 2014 #14
    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?
     
  16. Mar 12, 2014 #15
    Yes, you would begin by assuming x and y are odd and work with definitions. For example, x=2a+1 and y=2b+1.
     
  17. Mar 12, 2014 #16
    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".
     
  18. Mar 12, 2014 #17
    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.
     
  19. Mar 12, 2014 #18
    Ahh alright, now I need to incorporate quantifiers in to the proofs and I am good to go. Thanks!
     
  20. Mar 12, 2014 #19
    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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted