1. Limited time only! Sign up for a free 30min personal 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!

Proving that n(n^2+5) is divisible by 6

  1. Nov 4, 2012 #1
    1. The problem statement, all variables and given/known data

    Prove by induction that [itex] n (n^2 +5) [/itex] is divisible by 6 for all positive integers [itex] n [/itex]

    3. The attempt at a solution

    Let [itex] f(n) = n (n^2 +5) [/itex]

    [itex] f(1) = 6 [/itex]

    So, true for [itex] n=1 [/itex]

    Assume true for [itex] f(k) [/itex]

    For [itex] n = k + 1 [/itex]:

    [itex] f(k+1) = (k+1)[(k+1)^2 +5] [/itex]
    [itex] f(k+1)-f(k) = (k+1)(k^2 +2k +6) - k^3 + 5k [/itex]
    [itex] f(k+1)-f(k) = k^3 + 2k^2 + 6k +k^2 + 2k + 6 - k^3 -5k [/itex]
    [itex] f(k+1)-f(k) = 3k^2 + 3k +6 [/itex]

    I'm totally stuck from here. I was expecting f(k+1) - f(k) to be divisible by six, so then f(k+1) would be equal to the sum of two numbers divisible by six, which would show that f(k+1) is divisible by six. How can I show that final term is divisible by six? Or have I made a dumb mistake somewhere? Thanks.
     
    Last edited: Nov 4, 2012
  2. jcsd
  3. Nov 4, 2012 #2

    Mentallic

    User Avatar
    Homework Helper

    No no no... You shouldn't instantly jump to f(k+1)-f(k) to try and prove this. To prove this divisibility problem, you need to do something more with your assumption:

    Since
    [tex]f(k)=k(k^2+5)[/tex]
    and is divisible by 6 by assumption, then we have that
    [tex]f(k)=6N[/tex] for some integer N. We will be using this substitution in our proof.

    Now, by working with f(k+1) we want to try and get it into a format such that we can directly substitute [itex]k(k^2+5)=6N[/itex] in.

    So we have that

    [tex]f(k+1)=(k+1)((k+1)^2+5)[/tex]

    Now you should expand completely, then you'll need to rearrange things to make it something like f(k+1)=f(k) + ...
     
  4. Nov 4, 2012 #3

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Why not? It works quite nicely.

    Take both sides modulo 6. Obviously the +6 term on the right hand side contributes nothing. Can you take it from there?
     
  5. Nov 4, 2012 #4

    Mentallic

    User Avatar
    Homework Helper

    What is the reasoning behind taking that approach?
     
  6. Nov 4, 2012 #5
    What does modulo mean?
     
  7. Nov 4, 2012 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    A constructive proof that finds some integer [itex]a_n[/itex] such that [itex]f(n) \equiv n(n^2+5) = 6a_n[/itex] certainly is one way to solve this problem. There are other ways. Another approach is to use the fact that a number [itex]n[/itex] divides some number [itex]a[/itex] iff [itex]a = 0 \mod n[/itex]. In other words, all one has to do solve this problem is to show that [itex]f(n) \equiv n(n^2+5) = 0 \mod 6[/itex].

    I don't want to post my solution here in this thread; this is a homework question after all. I sent my solution as a PM to you instead. Read your private messages.
     
  8. Nov 4, 2012 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Essentially it means remainder. For example [itex]20\bmod6=4[/itex] because dividing 20 by 6 leaves a remainder of 4.

    Another way of saying that some number n divides some other number a is that [itex]a\bmod n = 0[/itex] (dividing a by n has a remainder of 0).
     
  9. Nov 4, 2012 #8

    Mentallic

    User Avatar
    Homework Helper

    DH, the proof you sent me is essentially what I would've done as well, minus the use of modulo and instead using the technique I posted in post #2 which is more intuitive for the younger Mathematicians, especially considering:

    Anyway, the reason I don't like instantly finding f(k+1) - f(k) is because it doesn't seem to have any reasoning to back it up. Why have you chosen to evaluate this expression? Now even though you'll end up evaluating that expression eventually, it doesn't justify the leap of faith you have to take to evaluate it straight away.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proving that n(n^2+5) is divisible by 6
  1. Prove n^3 <= 2^n (Replies: 9)

Loading...