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!

Induction, proving function divisible by 8

  1. Mar 19, 2014 #1
    1. The problem statement, all variables and given/known data
    Prove if n is an odd integer then n^2 - 1 is divisible by 8

    3. The attempt at a solution
    I already set up the whole inductive step and everything but I am trying to prove it works for n+1, here is what I have so far...
    n=2k+1
    ((2k+1)+1)^2 - 1 = 4k^2 + 8k + 3 = 8m
    Where k and m are arbitrary integers.
    What do I do from here to get it in the form 8m? I can't figure it out.
     
  2. jcsd
  3. Mar 19, 2014 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    2k+1 is an odd integer.

    The next odd integer is 2(k+1)+1 = 2k + 3 .
     
    Last edited: Mar 19, 2014
  4. Mar 19, 2014 #3
    Then it's 4k^2 + 12k + 8 ...that whole function can't be put in the form 8m as I see it there
     
  5. Mar 19, 2014 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Do you know how to do an inductive proof ?
     
  6. Mar 19, 2014 #5
    I know how to do an inductive proof in some settings, but ones like this, not really. In class my professor did something with a similar question, he added the most random term, then subtracted it, and everything worked out. But I can't figure out what to do for this one.
     
  7. Mar 19, 2014 #6

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    What do you assume for the inductive step?
     
  8. Mar 19, 2014 #7
    For all k in 0..(+infinity) ((2k+1)^2 -1) mod 8 = 0
     
  9. Mar 19, 2014 #8

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    If it's true for all k, then there's nothing to prove.


    Assume that for some positive integer k, ((2k+1)^2 -1) mod 8 = 0 .

    Of course that means that there is an integer, m, such that ((2k+1)2 -1) = 8m​

    Now with that assumption, you need to show that it follows that ((2k+3)^2 -1) mod 8 = 0 .

    Right ?
     
  10. Mar 19, 2014 #9
    Yea, I understand all of that. Am I supposed to use P(2k+1), in some way with P(2k+3), where P(2k+1) is the unary predicate, "((2k+1)^2-1)"
     
    Last edited: Mar 19, 2014
  11. Mar 19, 2014 #10
    I think I figured it out, so we assume that P(2k+1) is true, so to prove P(2(k+1)+1), P(2k+1) has to show up somewhere, since P(2k+1) is defined as 4k^2 + 4k = 8m that means P(2(k+1)+1) = 4k^2 + 12k + 8 = 4k^2 +4(3k+2), which is in the form, 4k^2 + 4k, so is that proof enough?
     
  12. Mar 19, 2014 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No, but you're getting warmer. You have 4k^2+4k is divisible by 8. Now you want to conclude 4k^2+12k+8 is also divisible by 8. What's the difference between the two?
     
  13. Mar 19, 2014 #12

    Curious3141

    User Avatar
    Homework Helper

    Do you need to use induction? This is actually very easy to prove without it.
     
  14. Mar 19, 2014 #13
    Oh my...it was staring at my the entire time, split up the 12k, so its 4k^2 + 4k + 8k + 8, by definition 4k^2 + 4k is divisible by 8, but 8k + 8, is also divisible by 8. I am 99% sure this is the right answer.
     
  15. Mar 19, 2014 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'm 100% sure.
     
  16. Mar 19, 2014 #15
    Thanks alot, now I know exactly what I am supposed to do in induction.
     
  17. Mar 19, 2014 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yeah, separate the part you know is true from the induction hypothesis from the part you don't know does and show the combination is true.
     
    Last edited: Mar 19, 2014
  18. Mar 20, 2014 #17

    Mark44

    Staff: Mentor

    "((2k+1)^2-1)" is not a predicate, unary or otherwise.
     
  19. Mar 20, 2014 #18
    Well then obviously my professor has been mistaken, because that was the exact line from a slide he had.
     
  20. Mar 20, 2014 #19

    Mark44

    Staff: Mentor

    From the wikipedia page on Predicates (http://en.wikipedia.org/wiki/Logical_predicate)
    Mathematically, (2k + 1)2 - 1 is an expression that has a value that depends on the value of k. It is not a statement that is either true or false. An example of a statement might be something like "(2k + 1)2 - 1 is divisible by 3".

    I should add that in your other thread about proofs by contradiction, you said "prove a statement like ##\sqrt{2}## by contradiction". You are not using the terms statement and predicate correctly. Whatever textbook you're using should have definitions of these terms.
     
    Last edited: Mar 20, 2014
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: Induction, proving function divisible by 8
  1. Proving divisibility (Replies: 1)

  2. Induction Division (Replies: 2)

Loading...