Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proving divisibility by induction

  1. Sep 6, 2006 #1
    Hello, I'm struggling with the question on induction.
    I was wondering if you could help me?

    Prove that n(n^2 +5) is divisible by 6 for n belonging to Z^+

    P_1 is (1(1^2 + 5))/6=1 hence P_1 is true

    If P_k is true then (k(K^2 +5))/6=r and if and only if (k(k^2 +5))=6r
    then P_(k+1) is

    (k+1)((K+1)^2 +5))=6r

    We're looking for something with 6 as a factor.
     
  2. jcsd
  3. Sep 6, 2006 #2
    What have you done so far?
     
  4. Sep 6, 2006 #3

    HallsofIvy

    User Avatar
    Science Advisor

    Yes, that's true.
    No, of course not. you just said 6r was equal to K(K^2+ 1). (K+1)^2= K^2+ 2k+ 1 so (K+1)((K+1)^2+ 5)= (K+1)(K^2+ 1+ 2k+ 5)= K(K^2+ 1)+ what?
     
  5. Sep 6, 2006 #4

    0rthodontist

    User Avatar
    Science Advisor

    No- you want (k+1)((k+1)^2 +5))=6s for some s. You've already used r in P_k, you can't use it again to mean something different in P_(k+1). Also be careful about capital letters--if you define k as lowercase it should be lowercase throughout.

    Also, "If P_k is true then (k(K^2 +5))/6=r and if and only if (k(k^2 +5))=6r" is true whether or not P_k is true--it's just algebra and doesn't help the induction. You want to start with P_k and then derive P_(k+1).
    Start with assuming
    (k(k^2 +5)) = 6r
    and then SHOW that
    (k+1)((k+1)^2 + 5) = 6s
    for some integer s. One way to try it is to add something to both sides of your assumption--what is (k+1)((k+1)^2 + 5) - (k(k^2 +5))?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook