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

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


    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


    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