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 contradiction

  1. Feb 27, 2015 #1
    1. The problem statement, all variables and given/known data
    lets say i have an int n that is greater than 2.
    I know n!-1 = xk where x and k are integers I must show that x <= n leads to a contradiction



    3. The attempt at a solution
    i assume x = n
    n!-1 =nk
    (n-1)! -1/n = k
    it seems to me that because of the 1/n k would not be an integer which would be a contradiction. But i am not even sure if that is true that it would not be an integer in any case. Am i going about this the right way?
     
  2. jcsd
  3. Feb 27, 2015 #2
    also x > 1
     
  4. Feb 27, 2015 #3
    and i also know x < n!
     
  5. Feb 27, 2015 #4
    wait so i have (n-1)! -k = 1/n
    then (n-1)! - k is an integer because it is the sum and products of integers.
    so int = 1/n
    but n>2 so 1/n is not an int therefore there is a contradiction. is this correct?
     
  6. Feb 28, 2015 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That's correct, but you've only proved it for x =n. You need to prove it for every 1 < x <= n.
     
  7. Feb 28, 2015 #6
    i was worried about that. I am not quite sure how to do this. I thought about doing it again for a n-1 but that also wont cover every case
     
  8. Feb 28, 2015 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That's right, you won't get there doing one at a time, but you can generalise your method so that it works for any x from 2 to n.
     
  9. Feb 28, 2015 #8
    I am not entirely sure how to do that. Can i say x is a particular but arbitrary integer from (2,n] and we have
    int = 1/x
    we know x is an int greater than 2 and there are no integers x greater than 2 such that 1/x is an integer therefore 1/x is not an int if 2 <x <= n
    I am not sure how convincing this is though
     
  10. Feb 28, 2015 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If x is an integer in [2,n] then n!/x is an integer and xk/x is an integer and 1/x isn't. If that's what you meant, then it's convincing.
     
    Last edited: Feb 28, 2015
  11. Mar 2, 2015 #10
    i get up to n!/x is an integer because if x is between 2 and n then it will divide into one of the ints in n!. The rest I am not as confident. let me start back a few steps
    n!-1 = xk
    (n!-1)/x = k
    n!/x-1/x = k
    n!/x must be an int because x is a int from 2 to n so it cancels one of the ints in n! and then the rest will be an int because it is the product of ints.
    n!/x - k = 1/x
    now we have n!/x-k is an int because it is a sum of ints. this is a contradiction because we know that 1/x is not an int because x>2
     
  12. Mar 2, 2015 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, 1/x is not an integer for x>=2. But as you've shown n!/x-k=1/x and the left side is an integer. That's a contradiction. So the assumption x<=n must be false.
     
  13. Mar 2, 2015 #12
    thank you
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof by contradiction
  1. Proof By Contradiction (Replies: 7)

  2. Proof by contradiction (Replies: 1)

  3. Proof by Contradiction (Replies: 1)

  4. Proof by contradiction (Replies: 13)

Loading...